多級å饋隊(duì)列調(dià o)度算法沒有實(shÃ)ç¾(xià n)，其他å‡å·²å¯¦(shÃ)ç¾(xià n)，由于自己注釋寫的較少，所以ä¸æ˜¯å¾ˆå¥½çš„把代碼表ç¾(xià n)出來ï¼
下é¢é™„上實(shÃ)ç¾(xià n)的進(jìn)程調(dià o)度的代碼：
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include < string .h> 4 #include <time.h> 5 6 #define maxnum 10 7 #define getpch(type) (type* malloc(sizeof(type))) 8 typedef struct pcb PCB; 9 struct pcb{ 10 int id; 11 char name[ 10 ]; 12 int time_start; // 到é”(dá)時間 13 int time_need; // æœå‹™(wù)時間 14 int time_left; // 剩余é‹(yùn)行時間 15 int time_used; // 已經(jÄ«ng)使用CPU時間 16 char state; 17 }; 18 19 void _sleep( int n){ 20 clock_t goal; 21 goal = (clock_t)n * CLOCKS_PER_SEC + clock(); 22 while (goal > clock()); 23 } 24 25 26 char _keygo(){ 27 char c; 28 printf( " ....\n " ); 29 c = getchar(); 30 return c; 31 } 32 33 int time_unit = 2 ; 34 // const int maxnum = 10; 35 int num = 5 ; 36 PCB pcbdata[maxnum] = { 37 { 1000 , " A " , 0 , 4 , 4 , 0 , ' R ' }, 38 { 1001 , " B " , 1 , 3 , 3 , 0 , ' R ' }, 39 { 1002 , " C " , 2 , 5 , 5 , 0 , ' R ' }, 40 { 1003 , " D " , 3 , 2 , 2 , 0 , ' R ' }, 41 { 1004 , " E " , 4 , 4 , 4 , 0 , ' R ' }, 42 }; 43 // PCB pcbdata[maxnum] = { 44 // {1000, "A", 1, 3, 3, 0, 'R'}, 45 // {1001, "B", 1, 2, 2, 0, 'R'}, 46 // {1002, "C", 5, 1, 1, 0, 'R'}, 47 // {1003, "D", 6, 5, 5, 0, 'R'}, 48 // {1004, "E", 6, 4, 4, 0, 'R'}, 49 // }; 50 // PCB pcbdata[maxnum] = { 51 // {1000, "A", 10, 8, 8, 0, 'R'}, 52 // {1001, "B", 12, 14, 14, 0, 'R'}, 53 // {1002, "C", 14, 4, 4, 0, 'R'}, 54 // {1003, "D", 16, 6, 6, 0, 'R'}, 55 // }; 56 // PCB pcbdata[maxnum] = { 57 // {1000, "A", 8, 2, 4, 0, 'R'}, 58 // {1001, "B", 8.5, 0.5, 3, 0, 'R'}, 59 // {1002, "C", 9, 5, 0.1, 0, 'R'}, 60 // {1003, "D", 9.5, 0.2, 2, 0, 'R'}, 61 // }; 62 int ready[maxnum]; 63 int order[maxnum]; 64 void input(){ 65 int i; 66 printf( " pid number is : " ); 67 scanf( " %d " , & num); 68 for (i= 0 ;i<num;++ i){ 69 pcbdata[i].id = 1000 + i; 70 printf( " input %d pid's name : " , i+ 1 ); 71 scanf( " %s " , pcbdata[i].name); 72 printf( " input %d pid's start time: " , i+ 1 ); 73 scanf( " %d " , & pcbdata[i].time_start); 74 printf( " input %d pid's need time: " , i+ 1 ); 75 scanf( " %d " , & pcbdata[i].time_need); 76 pcbdata[i].time_left = pcbdata[i].time_need; 77 printf( " \n " ); 78 pcbdata[i].time_used = 0 ; 79 pcbdata[i].state = ' R ' ; 80 } 81 } 82 83 void _swap( int A[], int a, int b){ 84 int tmp; 85 tmp = A[a]; 86 A[a] = A[b]; 87 A[b] = tmp; 88 } 89 90 void _swap1(PCB A[], int a, int b){ 91 PCB 92 tmp; 93 tmp = A[a]; 94 A[a] = A[b]; 95 A[b] = tmp; 96 } 97 98 int comp ( const void *a, const void * b ) 99 { 100 return (* ( PCB * ) a).time_start - (* ( PCB * ) b).time_start; 101 } 102 103 int compID ( const void *a, const void * b ) 104 { 105 return (* ( PCB * ) a).id - (* ( PCB * ) b).id; 106 } 107 108 int compneed ( const void *a, const void * b ) 109 { 110 return (* ( PCB * ) a).time_need - (* ( PCB * ) b).time_need; 111 } 112 113 114 // è€å¸«ç‰ˆæœ¬ 115 void FCFS(){ 116 int i, j, temp; 117 double k; 118 for (i= 0 ;i<num;++ i){ 119 order[i] = pcbdata[i].time_start; 120 ready[i] = i; 121 } 122 for (i= 0 ;i<num;++ i) 123 for (j=i+ 1 ;j<num;++ j){ 124 if (order[i] > order[j]){ 125 _swap(order, i, j); 126 _swap(ready, i, j); 127 } 128 } 129 printf( " FCFS :\n " ); 130 temp = pcbdata[ready[ 0 ]].time_start; 131 for (i= 0 ;i<num;++ i){ 132 printf( " %d --> %s, " , i+ 1 , pcbdata[ready[i]].name); 133 printf( " start time -> %d, need time -> %d\n " , pcbdata[ready[i]].time_start, pcbdata[ready[i]].time_need); 134 printf( " The pid running ....\n " ); 135 _sleep( 1 ); 136 137 printf( " Finish \n " ); 138 temp += pcbdata[ready[i]].time_need; 139 j = temp - pcbdata[ready[i]].time_start; 140 k = ( float )j / pcbdata[ready[i]].time_need; 141 printf( " The finish time ->%d, the zhouzhuan time ->%d, daiquan -> %.1f\n " , temp, j, k); 142 } 143 printf( " pid diaodu over!!\n " ); 144 } 145 146 // 自己手寫一個FCFS å¿«æŽ’ç‰ˆæœ¬ï¼ 147 void FCFS1(){ 148 int i, j, temp= 0 ; 149 double k; 150 qsort(pcbdata, num, sizeof (PCB), comp); // å°é€²(jìn)程進(jìn)行的到é”(dá)æ™‚é–“æŽ’åº 151 printf( " FCFS :\n " ); 152 temp = pcbdata[ 0 ].time_start; // æ¤åˆ»æ™‚é–“ 153 for (i= 0 ;i<num;++ i){ 154 printf( " %d -> %s\n " , i+ 1 , pcbdata[i].name); // 輸出進(jìn)程的åå— 155 printf( " start_time = %d, need time = %d\n " , pcbdata[i].time_start, pcbdata[i].time_need); 156 // 輸出進(jìn)程開始時間，æœå‹™(wù)時間 157 _sleep( 1 ); 158 temp+=pcbdata[i].time_need; // çµ(jié)æŸæ™‚é–“ 159 j = temp - pcbdata[i].time_start; // ä¸è½‰(zhuÇŽn)時間 160 k = ( float )j / pcbdata[i].time_need; // 帶權(quán)ä¸è½‰(zhuÇŽn)時間 161 printf( " The finist_time = %d, The zhongzhuan_time = %d, The daiquanzhongzhuan time = %g\n " , temp, j, k); 162 // 打å°é€²(jìn)程çµ(jié)æŸæ™‚間，ä¸è½‰(zhuÇŽn)時間，帶權(quán)ä¸è½‰(zhuÇŽn)時間 163 } 164 printf( " pid diaodu over !!\n " ); // 調(dià o)度çµ(jié)æŸ 165 } 166 167 168 void SJF(){ 169 int i, j, temp; 170 int mark = 0 ; 171 double k; 172 qsort(pcbdata, num, sizeof (PCB), comp); // å°é€²(jìn)程進(jìn)行到é”(dá)æ™‚é–“æŽ’åº 173 printf( " SJF : \n " ); 174 temp = pcbdata[ 0 ].time_start; // æ¤åˆ»æ™‚é–“ 175 for (i= 0 ;i<num;++ i){ 176 if (temp < pcbdata[num- 1 ].time_start && !mark){ // æ¤åˆ»æ™‚é–“å°äºŽæœ€é•·åˆ°é”(dá)時間的進(jìn)程的到é”(dá)時間 177 for (j=i+ 1 ;j<num;++ j) 178 if (temp<pcbdata[j].time_start){ // 如果æ¤åˆ»æ™‚é–“å°äºŽç¬¬j個進(jìn)程的到é”(dá)時間 179 qsort(pcbdata+i, j-i, sizeof (PCB), compneed); // å°ç¬¬i+1到第j個進(jìn)程進(jìn)行到é”(dá)æœå‹™(wù)æ™‚é–“æŽ’åº 180 break ; 181 } 182 } 183 else { 184 qsort(pcbdata+i, num-i, sizeof (PCB), compneed); // å°ç¬¬i+1進(jìn)程到åŽé¢æ‰€æœ‰é€²(jìn)程進(jìn)è¡Œæœå‹™(wù)æ™‚é–“æŽ’åº 185 mark = 1 ; // 標(biÄo)記 代表所有進(jìn)程已經(jÄ«ng)全部到é”(dá) 186 } 187 printf( " %d -> %s\n " , i+ 1 , pcbdata[i].name); // 輸出進(jìn)程åå— 188 printf( " start_time = %d, need time = %d\n " , pcbdata[i].time_start, pcbdata[i].time_need); 189 // 輸出進(jìn)程開始時間，æœå‹™(wù)時間 190 _sleep( 1 ); 191 temp+= pcbdata[i].time_need; 192 j = temp - pcbdata[i].time_start; 193 k = ( float )j / pcbdata[i].time_need; 194 printf( " The finist_time = %d, The zhongzhuan_time = %d, The daiquanzhongzhuan time = %g\n " , temp, j, k); 195 } 196 printf( " pid diaodu over !!\n " ); 197 198 } 199 200 void HRF(){ 201 int i, j, jj, temp, pos, mark; 202 double k; 203 mark = 0 ; 204 float w[ 10 ], max; 205 qsort(pcbdata, num, sizeof (PCB), comp); // å°é€²(jìn)程進(jìn)行到é”(dá)æ™‚é–“æŽ’åº 206 printf( " HRF: \n " ); 207 temp = pcbdata[ 0 ].time_start; // æ¤åˆ»æ™‚é–“ 208 for (i= 0 ;i<num;++ i){ 209 if (i!= 0 && i!= pos){ 210 mark = 0 ; 211 _swap1(pcbdata, i, pos); // 交æ›ç¬¬i個進(jìn)程和高響應(yÄ«ng)比進(jìn)程的ä½ç½® 212 qsort(pcbdata+i, pos-i, sizeof (PCB), comp); // å°é™¤äº†é¸ä¸çš„高響應(yÄ«ng)比進(jìn)程外其他進(jìn)程進(jìn)行到é”(dá)æ™‚é–“æŽ’åº 213 } 214 printf( " %d -> %s\n " , i+ 1 , pcbdata[i].name); 215 printf( " start_time = %d, need time = %d\n " , pcbdata[i].time_start, pcbdata[i].time_need); 216 _sleep( 1 ); 217 temp+= pcbdata[i].time_need; 218 jj = temp - pcbdata[i].time_start; 219 k = ( float )jj / pcbdata[i].time_need; 220 max = 0 ; 221 for (j=i+ 1 ;j<num;++ j){ 222 if (temp > pcbdata[j].time_start){ // 如果ç¾(xià n)在時間大于到é”(dá)時間 223 w[j] = temp - pcbdata[j].time_start + pcbdata[j].time_need; // 算出第j個進(jìn)程的優(yÅu)先權(quán) 224 w[j] /= pcbdata[j].time_need; // 算優(yÅu)先權(quán) 225 printf( " w[%d] = %g " ,j, w[j]); // 輸出到é”(dá)進(jìn)程的所有進(jìn)程的優(yÅu)先權(quán)值 226 if (w[j] > max) { // 計(jì)算最大優(yÅu)先權(quán)值的進(jìn)程 227 max = w[j]; 228 pos = j; // pos 為最大優(yÅu)先權(quán)值進(jìn)程的數(shù)組標(biÄo)記 229 } 230 mark = 1 ; 231 } 232 } 233 printf( " The finist_time = %d, The zhongzhuan_time = %d, The daiquanzhongzhuan time = %g, next weight = %g\n " ,temp, jj, k, max); 234 // 輸出進(jìn)程çµ(jié)æŸæ™‚間，ä¸è½‰(zhuÇŽn)時間，帶權(quán)ä¸è½‰(zhuÇŽn)時間，下一個優(yÅu)先權(quán)。 235 } 236 } 237 238 // 這是之å‰æŒ‰ç…§ç¬¬ä¸€æ¬¡è€å¸«è¬›è§£çš„方法所編寫，由于第一次ç†è«–ä¸æ˜¯æŒ‰é€²(jìn)程執(zhÃ)è¡ŒåŽæ’到就緒隊(duì)列末尾的方法，所以çµ(jié)æžœåªæ˜¯å’Œè€å¸«ä¹‹å‰æœ‰éŒ¯çš„PPT çµ(jié)果相åŒã€‚ 239 void _Timeslice(){ 240 int i, j, temp, mark, gap, n, k; 241 float kk; 242 qsort(pcbdata, num, sizeof (PCB), comp); 243 mark = k = 0 ; 244 temp = pcbdata[ 0 ].time_start; 245 printf( " Timeslice:\nThe gap is : " ); 246 scanf( " %d " , & n); 247 int vis[maxnum]; 248 memset(vis, 0 , sizeof (vis)); 249 while ( 1 ){ 250 for (i= 0 ;i<num;++ i){ 251 if (pcbdata[i].state == ' E ' ) continue ; 252 if (temp <= pcbdata[i].time_start && i!= 0 ) i = 0 ; 253 printf( " temp : %d\n " , temp); 254 ++ k; 255 gap = n; 256 if (pcbdata[i].time_left >= gap) 257 pcbdata[i].time_left -= gap; 258 else if (pcbdata[i].time_left > 0 && pcbdata[i].time_left < gap){ 259 gap = pcbdata[i].time_left; 260 pcbdata[i].time_left = 0 ; 261 } 262 temp += gap; 263 pcbdata[i].time_used = pcbdata[i].time_need - pcbdata[i].time_left; 264 printf( " %d -> %s, the gap : %d, the time_left: %d, the time_used : %d\n " , k, pcbdata[i].name, gap, pcbdata[i].time_left, pcbdata[i].time_used); 265 if (pcbdata[i].time_left == 0 ){ 266 pcbdata[i].state = ' E ' ; 267 vis[i] = 1 ; 268 j = temp - pcbdata[i].time_start; 269 kk = ( float )j / pcbdata[i].time_need; 270 printf( " The %s's state: %c ,The finist_time = %d, The zhongzhuan_time = %d, The daiquanzhongzhuan time = %g\n " , pcbdata[i].name, pcbdata[i].state, temp, j, kk); 271 } 272 _sleep( 1 ); 273 } 274 for (i= 0 ;i<num;++ i){ 275 if (vis[i] == 1 ) mark = 1 ; 276 else { mark = 0 ; break ;} 277 } 278 if (mark == 1 ) break ; 279 } 280 } 281 282 // 改進(jìn)éŽçš„時間片輪轉(zhuÇŽn)，按照第二次è€å¸«ä¸Šèª²è¬›è§£çš„åšæ³•æ‰€ç·¨å¯«ï¼Œç”±äºŽè¦ç¶è·(hù)å‹•æ…‹(tà i)就緒隊(duì)列，所以用éˆè¡¨ä¾†æ¨¡æ“¬å°±ç·’隊(duì)列。 283 typedef struct node * link; 284 typedef struct node { int data; link next;} Node; 285 // 創(chuà ng)建éˆè¡¨ä¾†æ¨¡æ“¬å°±ç·’隊(duì)列 286 void insert( int data, link L){ // å°¾æ’法æ’å…¥å…ƒç´ 287 link y = malloc( sizeof (Node)); 288 link p = L; 289 while (p->next) p = p-> next; 290 y->data = data; 291 y->next = p-> next; 292 p->next = y; 293 } 294 295 void delete(link L){ // 從éˆè¡¨é éƒ¨åˆªé™¤å…ƒç´ 296 L->next = L->next-> next; 297 } 298 void Timeslice(){ 299 int i, j, temp, mark, gap, n, k, pos; 300 float kk; 301 int vis[maxnum]; 302 memset(vis, 0 , sizeof (vis)); 303 link L = malloc( sizeof * L); 304 L->next = 0 ; 305 k = 0 ; 306 qsort(pcbdata, num, sizeof (PCB), comp); // å°é€²(jìn)程進(jìn)行到é”(dá)æ™‚é–“æŽ’åº 307 temp = pcbdata[ 0 ].time_start; 308 printf( " Timeslice:\nThe gap is : " ); 309 scanf( " %d " , &n); // è¼¸å…¥æ™‚é–“ç‰‡çš„é•·çŸ 310 insert( 0 , L); 311 vis[ 0 ] = 1 ; 312 while ( 1 ){ 313 ++ k; 314 gap = n; 315 if (L->next){ // 如果éˆè¡¨æœ‰å…ƒç´ 316 pos = L->next->data; // pos 為éˆè¡¨çš„é¦–å…ƒç´ 317 if (pcbdata[pos].time_left >= gap) // 如果剩余時間大于時間片長度，就用剩余時間減去時間片長度 318 pcbdata[pos].time_left -= gap; 319 else if (pcbdata[pos].time_left > 0 && pcbdata[pos].time_left < gap){ 320 // 如果剩余時間ä¸å¤§äºŽæ™‚間片長度，則剩余時間為0,æ¤åˆ»çš„時間片長度ç‰äºŽå‰©ä½™æ™‚é–“ 321 gap = pcbdata[pos].time_left; 322 pcbdata[pos].time_left = 0 ; 323 } 324 temp += gap; 325 pcbdata[pos].time_used = pcbdata[pos].time_need - pcbdata[pos].time_left; // 求CPU進(jìn)程是用時間 326 printf( " %d -> %s, the gap : %d, the time_left: %d, the time_used : %d\n " , k, pcbdata[pos].name, gap, pcbdata[pos].time_left, pcbdata[pos].time_used); 327 // 打å°é€²(jìn)程的剩余時間，使用時間 328 printf( " The now time : %d\n " , temp); 329 // 打å°æ¤åˆ»æ™‚é–“ 330 if (pcbdata[pos].time_left == 0 ){ // 如果剩余時間為0，把進(jìn)程狀態(tà i)從'R'改æˆâ€˜E’ 331 pcbdata[pos].state = ' E ' ; 332 j = temp - pcbdata[pos].time_start; 333 kk = ( float )j / pcbdata[pos].time_need; 334 printf( " The %s's state: %c ,The finist_time = %d, The zhongzhuan_time = %d, The daiquanzhongzhuan time = %g\n " , pcbdata[pos].name, pcbdata[pos].state, temp, j, kk); 335 } 336 _sleep( 1 ); 337 } 338 else break ; 339 340 delete(L); // 刪除éˆè¡¨ç¬¬ä¸€å€‹å…ƒç´ ，相當(dÄng)于ç¶è·(hù)就緒隊(duì)列 341 for (i= 0 ;i<num;++ i){ 342 if (vis[i]) continue ; 343 if (!vis[i] && pcbdata[i].time_start<= temp){ 344 insert(i, L); 345 vis[i] = 1 ; 346 } 347 } 348 if (pcbdata[pos].time_left > 0 ) // 剛æ‰åŸ·(zhÃ)è¡ŒéŽçš„進(jìn)程æ’到就緒隊(duì)列末尾 349 insert(pos, L); 350 } 351 } 352 353 354 355 void MRLA(){} 356 357 int main( int argc, char const * argv[]) 358 { 359 int i = 0 ; 360 int sch = 99 ; 361 // input(); 362 while (sch != 0 ){ 363 qsort(pcbdata, num, sizeof (PCB), compID); // 剛開始按進(jìn)程IDé †åºæŽ’åº 364 printf( " Please choose one diaodu : \n " ); 365 printf( " 1: FCFS\n " ); 366 printf( " 2: SJF\n " ); 367 printf( " 3: HRF\n " ); 368 printf( " 4: Timeslice\n " ); 369 printf( " 5: MRLA\n " ); 370 printf( " 0: exit\n " ); 371 printf( " Please input a number : " ); 372 scanf( " %d " , & sch); 373 switch (sch){ 374 case 1 : FCFS(); break ; 375 case 2 : SJF(); break ; 376 case 3 : HRF(); break ; 377 case 4 : Timeslice(); break ; 378 case 5 : MRLA(); break ; 379 case 0 : printf( " exit the programe\n " ); break ; 380 } 381 } 382 _keygo(); 383 return 0 ; 384 }
?
?
?
?
æ›´å¤šæ–‡ç« ã€æŠ€è¡“(shù)交æµã€å•†å‹™(wù)åˆä½œã€è¯(lián)ç³»åšä¸»
微信掃碼或æœç´¢ï¼šz360901061
å¾®ä¿¡æŽƒä¸€æŽƒåŠ æˆ‘ç‚ºå¥½å‹
QQ號è¯(lián)系： 360901061
您的支æŒæ˜¯åšä¸»å¯«ä½œæœ€å¤§çš„動力，如果您喜æ¡æˆ‘çš„æ–‡ç« ï¼Œæ„Ÿè¦ºæˆ‘çš„æ–‡ç« å°æ‚¨æœ‰å¹«åŠ©ï¼Œè«‹ç”¨å¾®ä¿¡æŽƒæ下é¢äºŒç¶ç¢¼æ”¯æŒåšä¸»2å…ƒã€5å…ƒã€10å…ƒã€20å…ƒç‰æ‚¨æƒ³æ的金é¡å§ï¼Œç‹ ç‹ é»ž(diÇŽn)擊下é¢çµ¦é»ž(diÇŽn)支æŒå§ï¼Œç«™é•·éžå¸¸æ„Ÿæ¿€æ‚¨ï¼æ‰‹æ©Ÿ(jÄ«)微信長按ä¸èƒ½æ”¯ä»˜è§£æ±ºè¾¦æ³•ï¼šè«‹å°‡å¾®ä¿¡æ”¯ä»˜äºŒç¶ç¢¼ä¿å˜åˆ°ç›¸å†Šï¼Œåˆ‡æ›åˆ°å¾®ä¿¡ï¼Œç„¶åŽé»ž(diÇŽn)擊微信å³ä¸Šè§’掃一掃功能，é¸æ“‡æ”¯ä»˜äºŒç¶ç¢¼å®Œæˆæ”¯ä»˜ã€‚
ã€æœ¬æ–‡å°æ‚¨æœ‰å¹«åŠ©å°±å¥½ã€‘å…ƒ
