进程动态优先级调度

简单的进程优先级动态调度

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	",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("
pid");
 35     for(i=0; i<P; i++) {
 36         printf("%d	",pro[i].pid);
 37     }
 38     PrintF("
next");
 39     for(i=0; i<P; i++) {
 40         printf("%d	",pro[i].next);
 41     }
 42     PrintF("
time");
 43     for(i=0; i<P; i++) {
 44         printf("%d	",pro[i].time);
 45     }
 46     PrintF("
pri");
 47     for(i=0; i<P; i++) {
 48         printf("%d	",pro[i].priority);
 49     }
 50     PrintF("
state");
 51     for(i=0; i<P; i++) {
 52         printf("%d	",pro[i].state);
 53     }
 54     printf("
");
 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("进程以全部运行完毕
");
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("(无进程)
");
 79         return;
 80     }
 81     while(pro != NULL) {
 82         printf("id:%d,  pri:%d,  alltime:%d
", 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("就绪队列里的进程信息为：
");
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("阻塞队列里的进程信息为：
");
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正执行的进程信息为：
");
240     printf("id:%d,  pri:%d,  alltime:%d
", 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("
第%d个时间片后：
", timeSlice);
273         // 模拟cpu执行1个时间片的操作
274         cpuWord(cpuProcess);
275         if(cpuProcess->allTime == 0) {
276             cpuProcess->state = Finish;
277             printf("	--	--	--进程 %d 完成任务
",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("
模拟进程调度算法结束
");
296     return 0;
297 }