簡(jiǎn)單的進(jìn)程優(yōu)先級(jí)動(dòng)態(tài)調(diào)度

cup運(yùn)行： 每執(zhí)行一次，優(yōu)先級(jí)減一，運(yùn)行時(shí)間減一。

就緒隊(duì)列中的進(jìn)程：每次按優(yōu)先級(jí)降序排序（優(yōu)先級(jí)越大越優(yōu)先執(zhí)行），若優(yōu)先級(jí)相等再按時(shí)間升序排序（時(shí)間越小越優(yōu)先執(zhí)行）。

所用知識(shí)點(diǎn)：結(jié)構(gòu)體數(shù)組、結(jié)構(gòu)體排序。

1 /******************************************* 2 * 3 * File : pro.c 4 * describe: 操作系統(tǒng)進(jìn)程調(diào)度，動(dòng)態(tài)優(yōu)先級(jí)算法 5 * Author : 阿Q 6 * Iime : 2016.11.19 7 * 8 *******************************************/ 9 #include<stdio.h> 10 #define P 5 11 #define PrintF(proprety) printf("%s\t",proprety) 12 struct pcb { //定義進(jìn)程結(jié)構(gòu) 13 int pid; //進(jìn)程Id 14 struct pcb *next; //指向下一個(gè)進(jìn)程 15 int time; //進(jìn)程所需執(zhí)行的時(shí)間 16 int priority; //進(jìn)程優(yōu)先級(jí) 17 int state; //進(jìn)程執(zhí)行的狀態(tài)，只有0、1狀態(tài).0未執(zhí)行，1已執(zhí)行 18 }; 19 struct pcb pro[P]= {//初始化5個(gè)進(jìn)程 20 {0,1,6,3,0}, 21 {1,2,4,4,0}, 22 {2,3,4,3,0}, 23 {3,4,4,2,0}, 24 {4,0,1,0,0}, 25 }; 26 27 /******************************************* 28 * 29 * Function : 顯示所有進(jìn)程的狀態(tài) 30 * 31 *******************************************/ 32 void display() { 33 int i=0,property=5; 34 PrintF("\npid"); 35 for(i=0; i<P; i++) { 36 printf("%d\t",pro[i].pid); 37 } 38 PrintF("\nnext"); 39 for(i=0; i<P; i++) { 40 printf("%d\t",pro[i].next); 41 } 42 PrintF("\ntime"); 43 for(i=0; i<P; i++) { 44 printf("%d\t",pro[i].time); 45 } 46 PrintF("\npri"); 47 for(i=0; i<P; i++) { 48 printf("%d\t",pro[i].priority); 49 } 50 PrintF("\nstate"); 51 for(i=0; i<P; i++) { 52 printf("%d\t",pro[i].state); 53 } 54 printf("\n"); 55 } 56 57 /******************************************* 58 * 59 * Function : 對(duì)結(jié)構(gòu)體進(jìn)行排序，按優(yōu)先級(jí)降序*時(shí)間升序 60 * 61 *******************************************/ 62 int cmp(const void *a,const void *b) { 63 struct pcb *aa=(struct pcb *)a; 64 struct pcb *bb=(struct pcb *)b; 65 66 //如果進(jìn)程執(zhí)行結(jié)束，則直接返回狀態(tài) 67 if(aa->time==0||aa->state==1)return 1; 68 else if(bb->time==0||bb->state==1)return -1; 69 70 if(bb->priority!=aa->priority) 71 return (bb->priority - aa->priority); 72 else 73 return (aa->time - bb->time); 74 } 75 76 /******************************************* 77 * 78 * Function : 進(jìn)程排序 需要子函數(shù) cmp() 79 * 80 *******************************************/ 81 void reSort() { 82 qsort(pro,P,sizeof(pro[0]),cmp); 83 } 84 85 /******************************************* 86 * 87 * Function : 檢查是否存在未執(zhí)行完的程序 88 * 89 *******************************************/ 90 int check() { 91 int i=0; 92 for(i=0; i<P; i++) { 93 if(!pro[i].state)return 1; 94 } 95 return 0; 96 } 97 98 /******************************************* 99 * 100 * Function : 修改指針指向 101 * 102 *******************************************/ 103 void rePoint() { 104 int i=0; 105 for(; i<P; i++) { 106 if(pro[i].state&&i>0) { 107 pro[i-1].next=0; 108 } 109 if(i<(P-1)) 110 pro[i].next=pro[i+1].pid; 111 } 112 } 113 114 int main() { 115 int f=0,i=1; 116 printf("初始狀態(tài)為："); 117 display(); 118 while(check()) {//每執(zhí)行完一次，測(cè)試是否還有進(jìn)程未執(zhí)行完 119 printf("第%d次運(yùn)行后:",i++); 120 //pro[0]為第一個(gè)進(jìn)程，這里當(dāng)作是在CUP中執(zhí)行的進(jìn)程.每次執(zhí)行執(zhí)行時(shí)間減一，優(yōu)先級(jí)減一。 121 pro[0].time-=1;//執(zhí)行一次進(jìn)程執(zhí)行時(shí)間減一 122 pro[0].priority-=1;//動(dòng)態(tài)優(yōu)先級(jí)，每執(zhí)行一次優(yōu)先級(jí)減一 123 124 if(pro[0].time==0)pro[0].state=1,pro[0].priority=-1,pro[0].next=0;//如果該進(jìn)程執(zhí)行完畢，及執(zhí)行時(shí)間為0,則狀態(tài)該為1，同時(shí)調(diào)整優(yōu)先級(jí)，指針調(diào)制為0 125 reSort();//重排進(jìn)程 126 rePoint();//重排指針 127 display();//輸出 128 } 129 printf("進(jìn)程以全部運(yùn)行完畢\n"); 130 return 0; 131 }

?

具有就緒隊(duì)列、阻塞隊(duì)列的動(dòng)態(tài)優(yōu)先級(jí)調(diào)度。

1 /********************************************************************************************************************** 2 * 3 * File : pro.cpp 4 * Time : 2016.12.04 5 * Introduce : CPU每執(zhí)行一次,就緒隊(duì)列中進(jìn)程優(yōu)先級(jí)+1，CPU執(zhí)行中的進(jìn)程優(yōu)先級(jí)-3，阻塞中的優(yōu)先級(jí)不增加，增加阻塞時(shí)間。 6 * 如果就緒隊(duì)列中進(jìn)程的優(yōu)先級(jí)比CPU中的進(jìn)程優(yōu)先級(jí)高，則CPU中的進(jìn)程進(jìn)入阻塞隊(duì)列，進(jìn)程最長(zhǎng)阻塞時(shí)間默認(rèn)為3(每次+1，>=3,進(jìn)入就緒隊(duì)列）。 7 * 8 **********************************************************************************************************************/ 9 #include<stdio.h> 10 #include<stdlib.h> 11 #define N 6 12 13 // 待插入就緒隊(duì)列的進(jìn)程數(shù)據(jù) 14 int id[N] = { 0, 1, 2, 3, 4, 5 }; 15 int priority[N] = { 14, 38, 27, 9, 7, 18 }; 16 int cpuTime[N] = { 0, 0, 0, 0, 0, 0 }; 17 int allTime[N] = { 5, 2, 3, 4, 2, 1 }; 18 19 20 /********************************* 21 * 22 * 模擬進(jìn)程/PCB數(shù)據(jù)結(jié)構(gòu) 23 * 24 *********************************/ 25 26 // 枚舉進(jìn)程的狀態(tài)：就緒、執(zhí)行、阻塞、完成 27 enum STATE { Ready, Run, Block, Finish }; 28 29 30 // 建立PCB結(jié)構(gòu)體 31 struct PCB { 32 int id; // 標(biāo)志數(shù) 33 int priority; // 優(yōu)先數(shù) 34 int cpuTime; // 已占CPU時(shí)間 35 int allTime; // 還需占CPU時(shí)間 36 int blockTime; // 已被阻塞的時(shí)間 37 STATE state; // 進(jìn)程狀態(tài) 38 PCB *pre; // PCB的前指針 39 PCB *nxt; // PCB的后指針 40 }; 41 42 43 /********************************* 44 * 45 * 模擬進(jìn)程隊(duì)列 46 * 47 *********************************/ 48 49 // 進(jìn)程入列 50 void queQush(PCB *process, PCB *queHead) { 51 process->pre = NULL; 52 process->nxt = queHead->nxt; 53 if(queHead->nxt != NULL) { 54 // 非第一個(gè)入列 55 queHead->nxt->pre = process; 56 } 57 queHead->nxt = process; 58 } 59 // 進(jìn)程出列 60 void quePop(PCB *process, PCB *queHead) { 61 if(process->pre != NULL) { 62 // 不是頭節(jié)點(diǎn) 63 process->pre->nxt = process->nxt; 64 } else { 65 queHead->nxt = process->nxt; 66 } 67 if(process->nxt != NULL) { 68 // 不是尾節(jié)點(diǎn) 69 process->nxt->pre = process->pre; 70 } 71 // 清空進(jìn)程指針 72 process->pre = process->nxt = NULL; 73 } 74 // 查看隊(duì)列里進(jìn)程的信息 75 void queWalk(PCB *queHead) { 76 PCB *pro = queHead->nxt; 77 if(pro == NULL) { 78 printf("(無進(jìn)程)\n"); 79 return; 80 } 81 while(pro != NULL) { 82 printf("id:%d, pri:%d, alltime:%d\n", pro->id, 83 pro->priority, pro->allTime); 84 pro = pro->nxt; 85 } 86 } 87 88 /********************************* 89 * 90 * 模擬就緒隊(duì)列 91 * 92 **********************************/ 93 94 int readyQueNum; // 就緒隊(duì)列的進(jìn)程數(shù)量 95 PCB readyQueHead; // 就緒隊(duì)列的頭部 96 PCB *readyMaxProcess; // 就緒隊(duì)列中優(yōu)先級(jí)最高的進(jìn)程 97 98 99 // 進(jìn)程插入到就緒隊(duì)列 100 void readyQueQush(PCB *process) { 101 readyQueNum ++; 102 process->state = Ready; 103 queQush(process, &readyQueHead); 104 } 105 // 優(yōu)先級(jí)最高的進(jìn)程出列 106 PCB* readyQuePop() { 107 readyQueNum --; 108 quePop(readyMaxProcess, &readyQueHead); 109 return readyMaxProcess; 110 } 111 //更新就緒隊(duì)列 112 void readyQueUpdate() { 113 int maxPriority = -1; 114 PCB *pro = readyQueHead.nxt; 115 if(pro == NULL) { 116 // 就緒隊(duì)列沒有進(jìn)程 117 readyMaxProcess = NULL; 118 return; 119 } 120 while(pro != NULL) { 121 pro->priority ++; 122 if(pro->priority > maxPriority) { 123 maxPriority = pro->priority; 124 readyMaxProcess = pro; 125 } 126 pro = pro->nxt; 127 } 128 } 129 // 返回就緒隊(duì)列最高優(yōu)先級(jí)的值 130 int readyMaxPriority() { 131 return readyMaxProcess->priority; 132 } 133 // 查看就緒隊(duì)列里進(jìn)程的信息 134 void readyQueWalk() { 135 printf("就緒隊(duì)列里的進(jìn)程信息為：\n"); 136 queWalk(&readyQueHead); 137 } 138 139 140 /********************************* 141 * 142 * 模擬阻塞隊(duì)列 143 * 144 *********************************/ 145 146 #define EndBlockTime 3 // 進(jìn)程最長(zhǎng)被阻塞時(shí)間 147 148 149 int blockQueNum; // 阻塞隊(duì)列的進(jìn)程數(shù)量 150 PCB blockQueHead; // 阻塞隊(duì)列的頭部 151 PCB *blockMaxProcess; // 阻塞隊(duì)列中優(yōu)先級(jí)最高的進(jìn)程 152 153 154 // 進(jìn)程插入到阻塞隊(duì)列 155 void blockQueQush(PCB *process) { 156 blockQueNum ++; 157 process->blockTime = 0; 158 process->state = Block; 159 queQush(process, &blockQueHead); 160 } 161 // 優(yōu)先級(jí)最高的進(jìn)程出列 162 PCB* blockQuePop() { 163 blockQueNum --; 164 quePop(blockMaxProcess, &blockQueHead); 165 return blockMaxProcess; 166 } 167 // 每個(gè)時(shí)間片，更新阻塞隊(duì)列里進(jìn)程的信息 168 void blockQueUpdate() { 169 int maxPriority = -1; 170 PCB *pro = blockQueHead.nxt; 171 while(pro != NULL) { 172 pro->blockTime ++; 173 if(pro->blockTime >= EndBlockTime) { 174 PCB *process = pro; 175 pro = pro->nxt; 176 // 阻塞時(shí)間到，調(diào)入就緒隊(duì)列 177 blockQueNum --; 178 quePop(process, &blockQueHead); 179 readyQueQush(process); 180 } else if(pro->priority > maxPriority) { 181 // 更新阻塞隊(duì)列里優(yōu)先級(jí)最高的進(jìn)程指針 182 maxPriority = pro->priority; 183 blockMaxProcess = pro; 184 pro = pro->nxt; 185 } 186 } 187 } 188 // 查看阻塞隊(duì)列里進(jìn)程的信息 189 void blockQueWalk() { 190 printf("阻塞隊(duì)列里的進(jìn)程信息為：\n"); 191 queWalk(&blockQueHead); 192 } 193 194 195 /******************************** 196 * 197 * 模擬動(dòng)態(tài)優(yōu)先權(quán)的進(jìn)程調(diào)度 198 * 199 *********************************/ 200 201 // 初始化數(shù)據(jù) 202 void initData() { 203 // 初始化就緒隊(duì)列和阻塞隊(duì)列 204 readyQueNum = blockQueNum = 0; 205 readyMaxProcess = blockMaxProcess = NULL; 206 readyQueHead.pre = readyQueHead.nxt = NULL; 207 blockQueHead.pre = blockQueHead.nxt = NULL; 208 // 初始化進(jìn)程進(jìn)入就緒隊(duì)列 209 int i, maxPriority = -1; 210 for(i = 0; i < N; i ++) { 211 // 分配一個(gè)PCB的內(nèi)存空間 212 PCB *pro = (PCB *)malloc(sizeof(PCB)); 213 // 給當(dāng)前的PCB賦值 214 pro->id = id[i]; 215 pro->priority = priority[i]; 216 pro->cpuTime = cpuTime[i]; 217 pro->allTime = allTime[i]; 218 pro->blockTime = 0; 219 if(pro->allTime > 0) { 220 // 插入到就緒隊(duì)列中 221 readyQueQush(pro); 222 // 更新就緒隊(duì)列優(yōu)先級(jí)最高的進(jìn)程指針 223 if(pro->priority > maxPriority) { 224 maxPriority = pro->priority; 225 readyMaxProcess = pro; 226 } 227 } 228 } 229 } 230 // 模擬cpu執(zhí)行1個(gè)時(shí)間片的操作 231 void cpuWord(PCB *cpuProcess) { 232 cpuProcess->priority -= 3;//優(yōu)先級(jí)-3 233 if(cpuProcess->priority < 0) { 234 cpuProcess->priority = 0; 235 } 236 cpuProcess->cpuTime ++; 237 cpuProcess->allTime --; 238 // 顯示正執(zhí)行進(jìn)程的信息： 239 printf("CPU正執(zhí)行的進(jìn)程信息為：\n"); 240 printf("id:%d, pri:%d, alltime:%d\n", cpuProcess->id, 241 cpuProcess->priority, cpuProcess->allTime); 242 } 243 244 245 int main() { 246 int timeSlice = 0; // 模擬時(shí)間片 247 int cpuBusy = 0; // 模擬cpu狀態(tài) 248 PCB *cpuProcess = NULL; // 當(dāng)前在cpu執(zhí)行的進(jìn)程 249 250 // 初始化數(shù)據(jù) 251 initData(); 252 // 模擬進(jìn)程調(diào)度 253 while(1) { 254 if(readyQueNum == 0 && blockQueNum == 0 && cpuBusy == 0) { 255 // 就緒隊(duì)列、阻塞隊(duì)列和cpu無進(jìn)程，退出 256 break; 257 } 258 if(cpuBusy == 0) { 259 // cpu空閑，選擇一個(gè)進(jìn)程進(jìn)入cpu 260 if(readyQueNum > 0) { 261 // 選擇緒隊(duì)列優(yōu)先級(jí)最高的進(jìn)程 262 cpuProcess = readyQuePop(); 263 } else { 264 // 就緒隊(duì)列沒有進(jìn)程，改為選擇阻塞隊(duì)列優(yōu)先級(jí)最高的進(jìn)程 265 cpuProcess = blockQuePop(); 266 } 267 cpuProcess->cpuTime = 0; 268 cpuProcess->state = Run; 269 cpuBusy = 1; 270 } 271 timeSlice ++; 272 printf("\n第%d個(gè)時(shí)間片后：\n", timeSlice); 273 // 模擬cpu執(zhí)行1個(gè)時(shí)間片的操作 274 cpuWord(cpuProcess); 275 if(cpuProcess->allTime == 0) { 276 cpuProcess->state = Finish; 277 printf("\t--\t--\t--進(jìn)程 %d 完成任務(wù)\n",cpuProcess->id); 278 // 釋放已完成進(jìn)程的PCB 279 free(cpuProcess); 280 cpuBusy = 0; 281 } 282 // 更新就緒隊(duì)列和阻塞隊(duì)列里的進(jìn)程信息 283 blockQueUpdate(); 284 readyQueUpdate(); 285 // 查看就緒隊(duì)列和阻塞隊(duì)列的進(jìn)程信息 286 readyQueWalk(); 287 blockQueWalk(); 288 if(cpuBusy == 1 && readyQueNum >0 && 289 cpuProcess->priority < readyMaxPriority()) { 290 // 需搶占cpu，當(dāng)前執(zhí)行的進(jìn)程調(diào)入阻塞隊(duì)列 291 blockQueQush(cpuProcess); 292 cpuProcess = readyQuePop(); 293 } 294 } 295 printf("\n模擬進(jìn)程調(diào)度算法結(jié)束\n"); 296 return 0; 297 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/A--Q/p/6104885.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的进程动态优先级调度的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。