多級反饋隊(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)擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
