操作系统_进程调度算法

1、计算机程序设计实践报告课程设计报告书2012 / 2013 学年 第 1 学期课程名称： 操作系统课程设计 专业班级：_计算机科学与技术1401班学 号：_130405220_姓 名：_柴艳_指导教师：_李威_课程设计指导教师评语 成 绩：_ 指导教师签字：_15进程调度算法模拟11 题目的主要研究内容及预期达到的目标1.1.1目的通过优先权法和轮转算法的模拟加深对进程概念和进程调度过程的理解，掌握进程状态之间的切换，同时掌握进程调度算法的实现方法和技巧。1.1.2目标1用C+语言来实现对n个进程采用优先权优先算法以及轮转算法的进程调度。2每个用来标识进程的进程控制块PCB用结构来描述，包括以

2、下字段：（1）进程标识ID，其中0为闲逛进程，用户进程的标识数为1，2，3。（2）进程优先级Priority，闲逛进程（idle）的优先级为0，用户进程的优先级大于0，且随机产生，标识数越大，优先级越高。（3）进程占用的CPU时间CPUtime，进程每运行一次，累计值等于4。（4）进程总共需要运行时间Alltime，利用随机函数产生。（5）进程状态，0就绪态；1运行态；2阻塞态。（6）队列指针next，用来将多个进程控制块PCB链接为队列。1.1.3优先数改变的原则（1）进程在就绪队列中每呆一个时间片，优先数增加1。（2）进程每运行一个时间片，优先数减3。1.1.4在调度前，系统中拥有的进程数

3、PCB_number由键盘输入，经初始化后，所有的进程控制块PCB链接成就绪队列。1.1.5为了清楚地观察诸进程的调度过程，程序应将每个时间片内的进程的情况显示出来。12 题目研究的工作基础或实验条件windowsXP系统、VC+6.0 13 设计思想n 进程调度的思想（1）当系统空闲（就绪队列为空）时，系统运行闲逛进程，否则运行其他进程，发生变迁1（就绪运行）。（2）在运行进程（包括闲逛进程）的过程中，可能发生变迁2（运行阻塞），即将运行进程插入到阻塞队列（闲逛进程不能被阻塞），可能有其他新的进程创建PCB，还可能唤醒阻塞队列中的某些进程PCB，发生变迁3（阻塞就绪），即从阻塞队列中移出并插

4、入就绪队列中。n （3）时间片运行结束后，若进程累计占用CPU时间大于等于进程需要运行的时间，则进程执行结束，释放其PCB。若进程累计占用CPU时间小于进程需要运行时间，发生变动态优先权的迁4（运行就绪），即将当前运行的进程插入就绪队列中。14 流程图1 进程调度算法模拟流程创建n个PCB并加入ready_queue中输入开始进程个数n各进程按优先级从高到低排列Yready_queue为空?NRunning<=逐个将ready_pc中PCBRunning<=idle阻塞running?NYYrunning=idle?N将running从 ready_queue中删除,再将runni

5、ng 加入block_queuebN是否创建新PCB?Y创建新进程并加入到ready_queue中对ready_queue中的进程PCB进行优先级排序随机对block_queue中的进程PCB询问是否要唤醒？Y处理完了吗？NN是否要唤醒？YNY将其从 block_queue队列中删除,再将其加入ready_queue队列中并进行优先级排序（图1.4.1）2轮转法进程调度算法模拟流程输入开始进程个数n创建n个PCB并加入ready_queue中Yready_queue为空?NRunning<=逐个将ready_pc中PCBRunning<=idle阻塞running?NYYrunni

6、ng=idle?N将running从 ready_queue中删除,再将running 加入block_queuebN是否创建新PCB?Y创建新进程并加入到ready_queue中随机对block_queue中的进程PCB询问是否要唤醒？Y处理完了吗？NN是否要唤醒？Y将其从 block_queue队列中删除,再将其加入ready_queue队列中 （图1.4.2）15 主要程序代码#define NULL 0#include <stdio.h>#include <stdlib.h>#include<iostream>using namespace std;

7、/*进程PCB结构*/struct Pcbint ID;/进程标识ID，其中0为闲逛进程，用户进程的标识数为1，2，3int priority;/进程优先级Priority，闲逛进程（idle）的优先级为0，用户进程的优先级大于0，且随机产生，标识数越大，优先级越高。int CPUtime;/进程占用的CPU时间CPUtime，进程每运行一次，累计值等于4int ALLtime;/进程总共需要运行时间Alltimeint State;/进程状态，0就绪态；1运行态；2阻塞态。struct Pcb *next;/队列指针next，用来将多个进程控制块PCB链接为队列;typedef struct

8、 Pcb PCB;void init(); /*产生idle进程，输入用户进程数目，调用insert()*/void print(PCB *pcb); /*输出进程属性信息*/void print_init(PCB *pcb); /*输出所有PCB的初始值*/void insert_queue(PCB *queue,PCB *item); /*动态优先权调试算法将item插入到队列中,使得插入后，队列中按照优先级从高到低有序*/void insert_queue1(PCB *queue,PCB *item); /*轮转法将item插入到队列末尾*/void pushback_queue(PCB

9、 *queue,PCB *item); /*将item插入到队列的尾部*/void insert(); /*动态优先权的进程调度算法生成进程属性信息，插入进程就绪队列*/void insert1(); /*轮转法的进程调度算法生成进程属性信息，插入进程就绪队列*/void run(PCB *pcb); /*运行进程，随机阻塞进程、产生新进程，插入就绪队列，唤醒阻塞进程*/void run1(PCB *pcb); /*轮转法试运行参数PCB所指的进程*/void block(PCB *pcb); /*调用destroy()，将进程插入阻塞队列*/void wakeup(); /*动态优先权的进程

10、调度算法唤醒进程，插入就绪队列*/void wakeup1(); /*轮转法的进程调度算法唤醒进程，插入就绪队列*/void proc_priority(); /*优先权调度算法模拟*/void proc_loop(); /*轮转法调度算法模拟*/void update(PCB *pcb); /*更新进程信息*/PCB *ready_queue,*block_queue,*idleprocess; /*就绪队列，阻塞队列及闲逛进程指针变量*/void main()int i=0;while(1)cout<<("n Please select a number (1,2,0

11、) ");cout<<("n 1- priority ");cout<<("n 2- loop");cout<<("n 0- exitn");cin>>i;if(i=1)cout<<("nThis is an example for priority processing:n");init();:proc_priority();else if (i=2)cout<<("nThis is an example for roun

12、d robin processing:n");init();proc_loop();else if(i=0)exit(1);/*输出所有PCB的初始值，此函数用于测试程序*/void print_init(PCB *pcb)PCB *temp=pcb->next;cout<<("n ID priority CPUtime ALLtime Staten");while(temp!=NULL)cout<<"n"<<" "<<temp->ID<<"

13、"<<temp->priority<<" "<<temp->CPUtime<<" "<<temp->ALLtime;if (temp->State=0)cout<<(" ready");else if (temp->State=1)cout<<(" running");elsecout<<(" blocked");temp=temp->next;/*输出进

14、程属性信息*/void print(PCB *pcb)PCB *temp;temp=pcb;if (pcb->ID=0) cout<<("ntThe idle process is running!");elsecout<<"n"<<" "<<temp->ID<<" "<<temp->priority<<" "<<temp->CPUtime<<" &quo

15、t;<<temp->ALLtime;if (temp->State=0)cout<<(" ready");else if (temp->State=1)cout<<(" running");elsecout<<(" blocked");void insert_queue(PCB *queue,PCB *item)/动态优先权调试算法将item插入到队列中,使得插入后，队列中按照优先级从高到低有序PCB *p,*q;q=queue;p=q->next;while(p

16、!=0 &&p->priority>=item->priority )q=p;p=p->next;if(p=0)/在队尾插入item->next=0;q->next=item;else/在q之后、p之前插入item->next=p;q->next=item;void insert_queue1(PCB *queue,PCB *item)/轮转法将item插入到队列末尾PCB *p,*q;q=queue;p=q->next;item->next=0;q->next=item;void pushback_queue(

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

18、nsert_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->next=NULL;:pushback_queue

19、(ready_queue,newp);/将新生成进程插入到就绪队列尾部print(newp);cout<<("t建立： Creating -> readyn");/*轮转法的进程调度生成进程属性信息，插入进程就绪队列,显示进程信息*/void insert1()PCB *newp=0;static long id=0;newp=new PCB;id+;newp->ID=id;newp->State=0;newp->CPUtime=0;newp->ALLtime=rand()%3+1;newp->next=NULL;:pushb

20、ack_queue(ready_queue,newp);/将新生成进程插入到就绪队列尾部print(newp);cout<<("t建立： Creating -> readyn");/*生成n个进程属性信息，插入进程就绪队列,显示进程信息*/void insert(int n)for(int i=1;i<=n;i+)insert(); /*动态优先权调度产生idle进程，输入用户进程数目，调用insert()*/void init()/为每个队列设立头结点，便于插入删除操作block_queue=new PCB;block_queue->next

21、=0;ready_queue=new PCB;ready_queue->next=0;int i,pcb_number=-1;idleprocess=NULL; /*设置闲逛进程PCB各字段值*/idleprocess=(PCB *)malloc(sizeof(PCB);idleprocess->ID=0;idleprocess->State=0;idleprocess->CPUtime=0;idleprocess->priority=0;idleprocess->ALLtime=1;idleprocess->next=NULL;/闲逛进程放入就绪队列

22、idleprocess->next=ready_queue->next;ready_queue->next=idleprocess; /也可假定初始时系统中只有一个idle进程/输入初始时进程的个数/while (pcb_number<0)/cout<<("Input the number of the PCB to be started:");/cin>>pcb_number;/cout<<("n ID priority CPUtime ALLtime State");/for (i=0;i&

23、lt;pcb_number;i+)/insert();cout<<"就绪队列初始化成功"<<endl;:print_init(ready_queue);cout<<endl;/*调用destroy()，将进程插入阻塞队列*/void block(PCB *pcb)/将pcb插入到阻塞队列pcb->State=2; /*将PCB所指进程的状态设置为阻塞*/pcb->CPUtime-=2; /*设进程执行半个时间片单位后被阻塞*/*pcb->next=NULL;*/print(pcb);cout<<("

24、 变迁2：running -> blockedn");/将pcb插入到阻塞队列/按照什么方式插入呢，需要参考唤醒条件/因为是随机唤醒一个进程，所以我们就简单地把它放置在阻塞队列的头部pcb->next=block_queue->next;block_queue->next=pcb;void update(PCB *pcb)/就绪队列中进程的优先级均增加1PCB *temp=ready_queue->next;while(temp && temp->next )/就绪队列的最后一个是闲逛进程temp->priority+;tem

25、p=temp->next;/*动态优先权调度试运行参数PCB所指的进程*/void run(PCB *pcb) /如果pcb是闲逛进程，则不做处理，再次放入就绪队列ready_queueif(pcb->ID=0):insert_queue(ready_queue,pcb);print(pcb);cout<<" 变迁1：ready -> runningn"else/如果不是闲逛进程，则进行如下处理pcb->State=1;/*设置该进程的状态为"运行"*/pcb->CPUtime+=4;/*累计该进程占用CPU的时

26、间*/pcb->priority=pcb->priority-3; /*每运行一个时间片，其优先数减3*/if(pcb->priority<1)pcb->priority=1;print(pcb);printf(" 变迁1：ready -> runningn");if (rand()%3=1 ) /*PCB不是闲逛进程，满足条件则阻塞此进程*/if(pcb->CPUtime-2<pcb->ALLtime) block(pcb);else/已经执行完毕，应该销毁进程cout<<endl;cout<<

27、"t the process no "<<pcb->ID<<" is completed! 销毁：running->Destroy"<<endl;delete pcb;else/否则看改进程是否执行完毕，如果执行完，则释放，否则再次放入就绪队列if(pcb->CPUtime>=pcb->ALLtime)/释放cout<<endl;cout<<"t the process no "<<pcb->ID<<" i

28、s completed! 销毁：running->Destroy"<<endl;delete pcb;else/再次放入就绪队列,按照优先级有序:insert_queue(ready_queue,pcb);update(ready_queue);/*更新就绪队列进程优先数*/if (rand()%5=1)insert(3); /*创建3个新进程*/:sort_queue(ready_queue);if (rand()%7=1)wakeup(); /*唤醒一个进程*/ /*返回当前进程是否被阻塞，1（已阻塞），0（未阻塞）*/*轮转法试运行参数PCB所指的进程*/vo

29、id run1(PCB *pcb) /如果pcb是闲逛进程，则不做处理，再次放入就绪队列ready_queueif(pcb->ID=0):insert_queue1(ready_queue,pcb);print(pcb);cout<<" 变迁1：ready -> runningn"else/如果不是闲逛进程，则进行如下处理pcb->State=1;/*设置该进程的状态为"运行"*/pcb->CPUtime+=4;/*累计该进程占用CPU的时间*/if(pcb->priority<1)pcb->prio

30、rity=1;/print(pcb);/ printf(" 变迁1：ready -> runningn");if (rand()%3=1 ) /*PCB不是闲逛进程，满足条件则阻塞此进程*/if(pcb->CPUtime-2<pcb->ALLtime) block(pcb);else/已经执行完毕，应该销毁进程cout<<endl;cout<<"t the process no "<<pcb->ID<<" is completed! 销毁：running->De

31、stroy"<<endl;delete pcb;else/否则看改进程是否执行完毕，如果执行完，则释放，否则再次放入就绪队列if(pcb->CPUtime>=pcb->ALLtime)/释放cout<<endl;cout<<"t the process no "<<pcb->ID<<" is completed! 销毁：running->Destroy"<<endl;delete pcb;else/再次放入就绪队列:insert_queue1(

32、ready_queue,pcb);if (rand()%5=1)insert(3); /*创建3个新进程*/:sort_queue(ready_queue);if (rand()%7=1)wakeup1(); /*唤醒一个进程*/ /*返回当前进程是否被阻塞，1（已阻塞），0（未阻塞）*/*唤醒，即从阻塞队列中选择一个PCB，且插入就绪队列中*/void wakeup()/随机唤醒一个阻塞进程/这里采取的方法是遍历阻塞队列，每访问一个，就产生一个随机数/如果该随机数对20求余恰好是1，则当前结点被唤醒，就要纳入就绪队列if(block_queue->next=0)/此时没有被阻塞的进程，

33、无所谓唤醒return;PCB *q,*p;/下面遍历阻塞队列，q永远指向p的前驱while(true)q=block_queue;p=q->next;while(p && rand()%20!=1)q=p;p=p->next;if(p!=0)/p就是要唤醒的进程q->next=p->next;break;p->State=0;cout<<endl;:print(p);cout<<" 变迁3：blocked->ready"<<endl;:insert_queue(ready_queue,

34、p);void wakeup1()/随机唤醒一个阻塞进程/这里采取的方法是遍历阻塞队列，每访问一个，就产生一个随机数/如果该随机数对20求余恰好是1，则当前结点被唤醒，就要纳入就绪队列if(block_queue->next=0)/此时没有被阻塞的进程，无所谓唤醒return;PCB *q,*p;/下面遍历阻塞队列，q永远指向p的前驱while(true)q=block_queue;p=q->next;while(p && rand()%20!=1)q=p;p=p->next;if(p!=0)/p就是要唤醒的进程q->next=p->next;br

35、eak;p->State=0;cout<<endl;:print(p);cout<<" 变迁3：blocked->ready"<<endl;:insert_queue1(ready_queue,p);/*优先权优先调度算法*/void proc_priority():sort_queue(ready_queue);/对queue中的结点进行排序，按照优先级从大到小PCB *temp=0,*running=0; /*running的PCB指针*/int times;for(times=0;times<10;times+)/找到优先级最高的进程，并且从队列中删除cout<<"本次调度前："<<endl;:print_init(ready_queue);running=ready_queue->next; /*running指向就绪队列队首PCB*/ready_queue->next=r