進程動態優先級調度

簡單的進程優先級動態調度

cup運行：每執行一次，優先級減一，運行時間減一。

就緒隊列中的進程：每次按優先級降序排序（優先級越大越優先執行），若優先級相等再按時間升序排序（時間越小越優先執行）。

所用知識點：結構體數組、結構體排序。

  1 /*******************************************
  2 *
  3 *  File    : pro.c
  4 *  describe: 操作系統進程調度，動態優先級算法
  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 {         //定義進程結構
 13     int pid;             //進程Id
 14     struct pcb *next;  //指向下一個進程
 15     int time;    //進程所需執行的時間
 16     int priority;  //進程優先級
 17     int state;  //進程執行的狀態，只有0、1狀態.0未執行，1已執行
 18 };
 19 struct pcb pro[P]= {//初始化5個進程
 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 : 顯示所有進程的狀態
 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 : 對結構體進行排序，按優先級降序*時間升序
 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     //如果進程執行結束，則直接返回狀態
 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 : 進程排序 需要子函數 cmp()
 79 *
 80 *******************************************/
 81 void reSort() {
 82     qsort(pro,P,sizeof(pro[0]),cmp);
 83 }
 84 
 85 /*******************************************
 86 *
 87 *  Function : 檢查是否存在未執行完的程序
 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("初始狀態為：");
117     display();
118     while(check()) {//每執行完一次，測試是否還有進程未執行完
119         printf("第%d次運行后:",i++);
120         //pro[0]為第一個進程，這里當作是在CUP中執行的進程.每次執行執行時間減一，優先級減一。
121         pro[0].time-=1;//執行一次進程執行時間減一
122         pro[0].priority-=1;//動態優先級，每執行一次優先級減一
123 
124         if(pro[0].time==0)pro[0].state=1,pro[0].priority=-1,pro[0].next=0;//如果該進程執行完畢，及執行時間為0,則狀態該為1，同時調整優先級，指針調制為0
125         reSort();//重排進程
126         rePoint();//重排指針
127         display();//輸出
128     }
129     printf("進程以全部運行完畢\n");
130     return 0;
131 }

具有就緒隊列、阻塞隊列的動態優先級調度。

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