进程调度算法课程设计

1、信息与计算科学操作系统原理课程设计报告题目： 进程调度算法 班级： 姓名： 专业： 进程调度算法一、实验目的 通过优先权法与轮转调度算法的模拟加深对进程概念和进程调度过程的理解，掌握进程状态之间的切换，同时掌握进程调度算法的实现方法和技巧。二、实验内容 1、用C语言或C+语言来实现对N个进程采用优先算法以及轮转算法的进程调度。 2、每个用来标示进程的进程控制块PCB用结果来描述，包括以下字段 （1）进程标识ID，其中0为闲逛进程，用户进程的标识数为1、2、3、。 （2）进程优先级Priority，闲逛进程（idle）的优先级为0，用户有进程的优先级大于0，且随机产生，标识数越大，优先级越高。

2、（3）进程占用的CPU时间CPUtime，进程每运一次，累积等于4. （4）进程总共需要运行时间Alltime，利用随机函数产生。 （5）进程状态，0就绪态，1运行态，2阻塞态。 （6）队列指针next，用来将多个进程控制块PCB链接为队列。 3、优先数改变的原则 （1）进程在就绪队列中每呆一个时间片，优先数增加1. （2）进程每运行一个时间片，优先数增加1.4、在调度前，系统中拥有的进程数PCB_number有键盘输入，进初始化后，所有的进程控制块PCB连接成就绪队列。5、为了清楚的观察诸进程的调度过程，程序应将每个时间片内的进程的情况显示出来。三、实验步骤1、进程管理程序调式好后，运行进程

3、管理程序输入开始进程数n创建n个PCB并加入readyqueue中ready-queue是否为空Y NRunning<=idRunning<逐个将redy_pc中的PCB阻塞RunningN YRunning=idleYN将Running从ready_queue中删除，再将running加入block_queueb 更新新进程就绪队列进程优先数，优先数加1是否创建新PCB N Y创建新进程并加入到ready_queue中随机 对block_queue中的进程PCB询问是否要唤醒？处理完了吗 Y N是否要唤醒 N Y将其从blick_queuek队列是中删除，再将其加入ready_q

4、ueuek 2、优先权调度（1）输入1选择优先权调度算法模拟。（2）输入开始进程个数n，创建n个PCB并加入就绪队列ready_queue中。（3）就绪队列ready_queue不为空，调度就绪队列中第一个进程运行，否则，从闲逛队列idleprocess中调度闲逛进程运行。（4）在运行过程中，当遇到阻塞，则该进程插入到阻塞队列block_queue中，且将该进程从ready_queue中删除。（5）如果运行时间CPUtime大于等于Alltime，该进程运行完毕，释放该进程；否则插入到就绪队列中。（6）更新就绪队列中的优先级数。（7）随机对阻塞队列block_queue中的进程PCB询问是否要

5、唤醒，唤醒，即从唤醒队列中选择第一个进程，且插入就绪队列中；阻塞队列中没有阻塞进程返回。（8）重复上述步骤，直到本次调度结束。3、轮转调度（1）输入2选择优先权调度算法模拟。（2）输入开始进程个数n，创建n个PCB并加入就绪队列ready_queue中。（3）就绪队列ready_queue不为空，调度就绪队列中第一个进程运行，否则，从闲逛队列idleprocess中调度闲逛进程运行。（4）在运行过程中，当遇到阻塞，则该进程插入到阻塞队列block_queue中，且将该进程从ready_queue中删除。（5）如果运行时间CPUtime大于等于Alltime，该进程运行完毕，释放该进程；否则插入

6、到就绪队列中。（6）随机对阻塞队列block_queue中的进程PCB询问是否要唤醒，唤醒，即从唤醒队列中选择第一个进程，且插入就绪队列中；阻塞队列中没有阻塞进程返回。（7）如果时间到，本次调度结束，否则重复上述步骤，直到本次调度结束。输入开始进程数n创建n个PCB并加入readyqueue中ready-queue是否为空Y NRunning<=idRunning<逐个将redy_pc中的PCB阻塞RunningN YRunning=idleYN将Running从ready_queue中删除，再将running加入block_queueb 是否创建新PCB N Y创建新进程并加入到

7、ready_queue中随机 对block_queue中的进程PCB询问是否要唤醒 ？处理完了吗 Y N是否要唤醒 N Y将其从blick_queuek队列是中删除，再将其加入ready_queuek Y四、实验过程中遇到的问题及解决方案1、请仔细阅读动态优先权的进程调度算法的模拟实现代码,说明该算法与教材中介绍的算法做了哪些简单化处理.优先权模拟时优先权是随机产生，在实际的系统中，系统进程的优先权高于一般用户进程的优先权。2、为什么对进程的优先数可按上述原则进行修改?最高优先权调度算法仅照顾了优先权高的进程，当不断有优先权高的进程需调度时，而优先权低的进程将很难得到处理机的调度，所以进程在就

8、绪队列中每呆一个时间片，优先数增加1，使优先权低的进程不总是忙等。3、请给出设计实现的轮转发进程调度算法的设计思想.时间轮转调度算法：系统将所有的就像进程按先来先服务的原则，排成一个队列，每次调度时，把CPU分配给首进程，并令其执行一个时间片。当执行的时间片用完时，发出中断请求，调度程序便据此信号来停止该进程的执行，并将其送到就绪队列的末尾，如此反复，就可以保证就绪队列中的所有进程在一个给定的时间内，均能获得一时间片处理机执行时间。4、在实际的进程调度中，除了按调度算法选择下一个执行的进程外,还应处理哪些工作?最高优先权调度算法，常用于批处理系统中，作为作业调度算法，也作为多种操作系统中的进程

9、调度算法，还可以用于实时系统中：时间轮转调度算法，一般用于分时系统中。五、课程设计总结1、当把该算法用于作业调度时，系统将从后备队列中选择若干个优先权最高的作业，装入内存，当用于进程调度算法时，该算法是把处理及分配给就绪队列中优先权最高的进程。2、当系统空闲（就绪队列为空）时，系统运行闲逛进程，否则运行其他进程，发生变迁（就绪à运行）3、在运行进程（包括闲逛进程）的过程中，可能发生变迁2(运行à阻塞)，即将运行进程插入到阻塞队列（闲逛进程不能不被阻塞），可能有其他的进程创建PCB，还可能唤醒阻塞队列中的某些进程PCB，发生变迁3（阻塞à就绪），即从阻塞队列中插入就

10、绪队列中。4、时间片运行结束后，若进程累积占用CPU时间大于等于进程需要运行时间，则进程执行结束，释放其PCB。若进程累积占用CPU时间小于进程需要运行时间，发生变迁4（运行à就绪），即将当前运行的进程插入就绪队列中。编译器：visual stidio 2008 professional附：进程调度算法代码/ process.cpp : Defines the entry point for the console application./#include "stdafx.h"#include "stdio.h"#include "

11、stdlib.h"#include "iostream"#define NULL 0#define false 0#define true 1bool _state=0;struct PCBint ID;int priority;int CPUtime;int ALLtime;int State;PCB* next;void init();/*产生idle进程，输入用户进程数目，调用insert()*/void print(PCB *pcb);/*输出进程属性信息*/void print_init(PCB *pcb);/*输出所有PCB的初始值*/void ins

12、ert();/*生成进程属性信息，插入进程就绪队列*/void Run_priority(PCB *pcb);/*运行进程，随机阻塞进程、产生新进程，插入就绪队列，唤醒阻塞进程*/void block(PCB *pcb);/*调用destroy()将进程插入阻塞队列*/void wakeup();/*唤醒进程，插入就绪队列*/void proc_priority();/*优先权调度算法模拟*/void Run_loop(PCB *pcb);void proc_loop();/*轮转法调度算法模拟*/void update(PCB *pcb);/*更新进程信息*/void pushback_qu

13、eue(PCB *queue,PCB *item);/*将item插入到队列的尾部*/void insert_queue(PCB *queue,PCB *item);/*将item插入到队列中，使得插入后，队列中按照优先级从高到低有序*/void sort_queue(PCB *&queue);/*对queue中的结点进行排序，按照优先级从大到小*/PCB *ready_queue,*block_queue,*idleprocess;/*就绪队列，阻塞队列及闲逛进程指针变量*/int main(int argc, char* argv)int i=0;while(1)cout<&

14、lt;"*PROCESS*/"cout<<("n Please select a num in(1,2,0) ");cout<<("n 1-priority ");cout<<("n 2-loop ");cout<<("n 0- exitn"); cout<<"Please select a num:"cin>>i;while(i)if(i=1)cout<<("n This is a

15、 example for priority processing: n ");init();proc_priority();else if (i=2)cout<<("n This is a example for round robin processing: n ");init();proc_loop();elsecout<<"Please select a num in(1,2,0)n"cout<<"Please select a num:"cin>>i;return 0;

16、/输出所有PCB的初始值void print_init(PCB *pcb)PCB* temp=pcb->next ;cout<<("nID priority CPUtime ALLtime State");while(temp!=NULL)cout<<"n"<<temp->ID<<" "<<temp->priority<<" "<<temp->CPUtime<<" "<&

17、lt;temp->ALLtime;if(temp->State=0)cout<<(" ready");else if(temp->State =1)cout<<(" running");elsecout<<(" blocked");temp=temp->next;/输出进程属性信息void print(PCB *pcb)PCB *temp;temp=pcb;if(pcb->ID=0)cout<<("nThe idle peocess id runn

18、ing!");elsecout<<"n"<<temp->ID<<" "<<temp->priority<<" "<<temp->CPUtime<<" "<<temp->ALLtime;if(temp->State=0)cout<<(" ready");else if(temp->State =1)cout<<(" runn

19、ing");elsecout<<(" blocked");/将item插入到队列中，使得插入后，队列中按照优先级从高到低有序void insert_queue(PCB *queue,PCB *item)PCB *p,*q;q=queue;p=q->next;while(p!=0&&p->priority>=item->priority)q=p;p=p->next;if(p=0)item->next =0;q->next=item;elseitem->next =p;q->next =

20、item;/将item插入到阻塞队列的尾部void pushback_queue(PCB *queue,PCB *item)PCB *p,*q;q=queue,p=q->next;while(p!=0)q=p;p=p->next;item->next =q->next ;q->next =item;/对queue中的结点进行排序，按照优先级从大到小void sort_queue(PCB *&queue)PCB *temp=new PCB;temp->next =0;while(queue->next )PCB *p;p=queue->ne

21、xt;queue->next =p->next ;insert_queue(temp,p);queue->next =temp->next ;delete temp;/生成进程属性信息，插入进程就绪队列,显示进程信息void insert()PCB *newp=0;static long id =0;newp=new PCB;id+;newp->ID =id;newp->State=0;newp->CPUtime=0;newp->priority=rand()%3+1;newp->ALLtime=rand()%3+1;newp->ne

22、xt =NULL;pushback_queue(ready_queue,newp);/print(newp);/cout<<("建立: Creating -> readyn");/生成n个进程属性信息，插入进程就绪队列，显示进程信息void insert(int n)for(int i=0;i<n;i+)insert();/产生idle进程，输入用户进程数目，调用insert()void init()block_queue=new PCB;block_queue->next=0;ready_queue=new PCB;ready_queue-&

23、gt;next=0;int i=0,pcb_number=-1;/闲逛进程放入就绪队列idleprocess=NULL;idleprocess=(PCB *)malloc(sizeof(PCB);idleprocess->ID=0;idleprocess->State=0;idleprocess->CPUtime=0;idleprocess->priority=0;idleprocess->ALLtime=0;idleprocess->next=NULL;idleprocess->next=ready_queue->next;/闲逛进程放入就绪队

24、列ready_queue->next=idleprocess;/也可以假定初始时系统中只有一个idle进程/输入初始进程的个数 while(pcb_number<0)cout<<("Input the number of PCB to be start:");cin>>pcb_number;cout<<("nID priority CPUtime ALLtime Staten");for(;i<pcb_number;i+)insert();cout<<"*就绪队列初始化成功&qu

25、ot;<<endl;:print_init(ready_queue);cout<<endl;/调用destroy()将进程插入阻塞队列void block(PCB *pcb)pcb->State=2;pcb->CPUtime-=2;if(pcb->CPUtime<=0)pcb->CPUtime+=2;cout<<"nThe process no"<<pcb->ID<<" is blocked!"print(pcb);cout<<(" 变迁

26、2：running -> blockedn");pcb->next=block_queue->next;block_queue->next =pcb;/更新进程信息,就绪队列中进程的优先级均增加1void update(PCB *pcb)PCB *temp=pcb->next;while(temp&&temp->next )temp->priority+;temp=temp->next;/唤醒进程，插入就绪队列void wakeup()if(block_queue->next=0)/*此时没有阻塞的进程，无所谓的唤

27、醒*/return ;PCB *q,*p;while(true)q=block_queue;p=q->next;while(p&&rand()%20!=1)q=p;p=p->next;if(p!=0)q->next =p->next ;break;p->State=0;cout<<endl;print(p);cout<<" 变迁3: blocked -> ready"<<endl;insert_queue(ready_queue,p);/运行进程，随机阻塞进程、产生新进程，插入就绪队列，

28、唤醒阻塞进程void Run_priority(PCB *pcb)if(pcb->ID=0)insert_queue(ready_queue,pcb);print(pcb);cout<<"变迁1: ready -> runningn"elsepcb->State=1;pcb->CPUtime+=4;pcb->priority=pcb->priority -3;/*每运行一个时间片，其优先数减3*/if(pcb->priority <1)pcb->priority=1;print(pcb);printf(&qu

29、ot;变迁1: ready -> runningn");if(rand()%3=1)/*PCB不是闲逛进程，满足条件侧阻塞此进程*/if(pcb->CPUtime-2<pcb->ALLtime)block(pcb);else/*已执行完毕，应该销毁进程*/cout<<'n'cout<<"The process no"<<pcb->ID<<" is completed! 销毁：running->Destroy"<<endl;delete

30、 pcb;else/*否则看该进程是否执行完毕，如果执行完，则释放，否则再次放入就绪队列*/if(pcb->CPUtime>=pcb->ALLtime)/*释放*/cout<<'n'cout<<"The process no "<<pcb->ID<<" if completed! 销毁：running -> Destrory"<<endl;delete pcb;else:insert_queue(:ready_queue,pcb);update(re

31、ady_queue);/*更新就绪队列的优先级数*/if(rand()%5=1)insert(3);:sort_queue(ready_queue);if(rand()%7=1)wakeup();/运行进程，随机阻塞进程、产生新进程，插入就绪队列，唤醒阻塞进程void Run_loop(PCB *pcb) if(pcb->ID=0)insert_queue(ready_queue,pcb);print(pcb);cout<<"变迁1: ready -> runningn"elsepcb->State=1;pcb->CPUtime=pcb->ALLtime;print(pcb);printf("变迁1: ready -> runningn");if(rand()%3=1)/*PCB不是闲逛进程，满足条件侧阻塞此进程*/_state=1;block(pcb);elsecout<<'n'cout<<"The process no "<<pcb->ID<<" if completed! 销毁：running -> Destrory&quo