《操作系统课程设计报告_进程调度算法.doc》由会员分享，可在线阅读，更多相关《操作系统课程设计报告_进程调度算法.doc（28页珍藏版）》请在三一文库上搜索。
1、操作系统课程设计报告_进程调度算法 1实验目的通过优先权法和轮转算法的模拟加深对进程概念和进程调度过程的理解，掌握进程状态之间的切换，同时掌握进程调度算法的实现方法和技巧。2实验内容1用C+语言来实现对n个进程采用优先权优先算法以及轮转算法的进程调度。2每个用来标识进程的进程控制块PCB用结构来描述，包括以下字段：（1）进程标识ID，其中0为闲逛进程，用户进程的标识数为1，2，3。（2）进程优先级Priority，闲逛进程（idle）的优先级为0，用户进程的优先级大于0，且随机产生，标识数越大，优先级越高。（3）进程占用的CPU时间CPUtime，进程每运行一次，累计值等于4。（4）进程总共需
2、要运行时间Alltime，利用随机函数产生。（5）进程状态，0就绪态；1运行态；2阻塞态。（6）队列指针next，用来将多个进程控制块PCB链接为队列。3优先数改变的原则（1）进程在就绪队列中每呆一个时间片，优先数增加1。（2）进程每运行一个时间片，优先数减3。4在调度前，系统中拥有的进程数PCB_number由键盘输入，经初始化后，所有的进程控制块PCB链接成就绪队列。5为了清楚地观察诸进程的调度过程，程序应将每个时间片内的进程的情况显示出来， 3实验步骤进程调度的思想（1）当系统空闲（就绪队列为空）时，系统运行闲逛进程，否则运行其他进程，发生变迁1（就绪运行）。（2）在运行进程（包括闲逛进
3、程）的过程中，可能发生变迁2（运行阻塞），即将运行进程插入到阻塞队列（闲逛进程不能被阻塞），可能有其他新的进程创建PCB，还可能唤醒阻塞队列中的某些进程PCB，发生变迁3（阻塞就绪），即从阻塞队列中移出并插入就绪队列中。（3）时间片运行结束后，若进程累计占用CPU时间大于等于进程需要运行的时间，则进程执行结束，释放其PCB。若进程累计占用CPU时间小于进程需要运行时间，发生变迁4（运行就绪），即将当前运行的进程插入就绪队列中。程序流程图动态优先权的进程调度算法模拟流程2轮转法进程调度算法模拟流程程序代码/*以下程序在C+环境调试通过*/#define NULL 0#include #inclu
4、de #include using namespace std;/*以下仅列出动态优先权的进程调度算法模拟*/*进程PCB结构*/struct Pcb int ID;/进程标识ID，其中0为闲逛进程，用户进程的标识数为1，2，3int priority;/进程优先级Priority，闲逛进程（idle）的优先级为0，用户进程的优先级大于0，且随机产生，标识数越大，优先级越高。int CPUtime;/进程占用的CPU时间CPUtime，进程每运行一次，累计值等于4int ALLtime;/进程总共需要运行时间Alltimeint State;/进程状态，0就绪态；1运行态；2阻塞态。struc
5、t Pcb *next;/队列指针next，用来将多个进程控制块PCB链接为队列 ;typedef struct 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,
6、PCB *item ; /*轮转法将item插入到队列末尾*/void pushback_queue PCB *queue,PCB *item ; /*将item插入到队列的尾部*/void insert ; /*动态优先权的进程调度算法生成进程属性信息，插入进程就绪队列*/void insert1 ; /*轮转法的进程调度算法生成进程属性信息，插入进程就绪队列*/void run PCB *pcb ; /*运行进程，随机阻塞进程、产生新进程，插入就绪队列，唤醒阻塞进程*/void run1 PCB *pcb ; /*轮转法试运行参数PCB所指的进程*/void block PCB *pcb
7、; /*调用destroy ，将进程插入阻塞队列*/void wakeup ; /*动态优先权的进程调度算法唤醒进程，插入就绪队列*/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
8、 n Please select a number 1,2,0 ;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 round robin processing:n ;init ;proc_loop ; else if i 0 exit 1 ; /*输出所有PCB的初始值，此函数用于测
9、试程序*/void print_init PCB *pcb PCB *temp pcb- next;cout n ID priority CPUtime ALLtime Staten ;while temp! NULL cout n temp- ID temp- priority temp- CPUtime temp- ALLtime;if temp- State 0 cout ready ;else if temp- State 1 cout running ;elsecout blocked ;temp temp- next; /*输出进程属性信息*/void print PCB *pcb
10、 PCB *temp;temp pcb;if pcb- ID 0 cout ntThe idle process is running! ;else cout n temp- ID temp- priority temp- CPUtime 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插入到队列中,使得插入后，队列中按照优先级从高到低有序P
11、CB *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; 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 PCB *
12、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;:insert_queue temp,p ; queue- next temp-
13、 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 ready_queue,newp ;/将新生成进程插入到就绪队列尾部print newp ;cout t建立： Creati
14、ng - 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;:pushback_queue ready_queue,newp ;/将新生成进程插入到就绪队列尾部print newp ;cout t建立： Creating - readyn ; /*生成n个进程属性信息，插入进程
15、就绪队列,显示进程信息*/void insert int n for int i 1;i n;i+ insert ; /*动态优先权调度产生idle进程，输入用户进程数目，调用insert */void init /为每个队列设立头结点，便于插入删除操作block_queue new PCB;block_queue- next 0;ready_queue new PCB;ready_queue- next 0;int i,pcb_number -1;idleprocess NULL; /*设置闲逛进程PCB各字段值*/idleprocess PCB * malloc sizeof PCB ;i
16、dleprocess- ID 0;idleprocess- State 0;idleprocess- CPUtime 0;idleprocess- priority 0;idleprocess- ALLtime 1;idleprocess- next NULL;/闲逛进程放入就绪队列idleprocess- next ready_queue- next;ready_queue- next idleprocess; /也可假定初始时系统中只有一个idle进程/输入初始时进程的个数/while pcb_number 0 / /cout Input the number of the PCB to
17、be started: ;/cin pcb_number;/ /cout n ID priority CPUtime ALLtime State ;/for i 0;i 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- nex
18、t NULL;*/print pcb ;cout 变迁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+;temp temp- next;
19、 /*动态优先权调度试运行参数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的时间*/pcb- priority pcb- priority-3; /*每运行一个时间片，其优先数减3*/if pc
20、b- 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 t the process no pcb- ID is completed! 销毁：running- Destroy endl;delete pcb; else /否则看改进程是否执行完毕，如果执行完，则释放，否则再次放入就绪队列i
21、f pcb- CPUtime pcb- ALLtime /释放cout endl;cout t the process no pcb- ID is 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 ; /*唤醒一个
22、进程*/ /*返回当前进程是否被阻塞，1（已阻塞），0（未阻塞）*/ /*轮转法试运行参数PCB所指的进程*/void 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-
23、 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 t the process no pcb- ID is completed! 销毁：running- Destroy endl;delete pcb; else /否则看改进程是否执行完毕，如果执行完，则释放，否则再次放入就绪队列if pcb- CPUtime
24、pcb- ALLtime /释放cout endl;cout t the process no pcb- ID is completed! 销毁：running- Destroy endl;delete pcb; else /再次放入就绪队列:insert_queue1 ready_queue,pcb ; if rand %5 1 insert 3 ; /*创建3个新进程*/:sort_queue ready_queue ; if rand %7 1 wakeup1 ; /*唤醒一个进程*/ /*返回当前进程是否被阻塞，1（已阻塞），0（未阻塞）*/ /*唤醒，即从阻塞队列中选择一个PCB，且
25、插入就绪队列中*/void wakeup /随机唤醒一个阻塞进程/这里采取的方法是遍历阻塞队列，每访问一个，就产生一个随机数/如果该随机数对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;break; p- State 0;cout
26、 endl;:print p ;cout 变迁3：blocked- ready endl;:insert_queue ready_queue,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;
27、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_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;tim
28、es+ /找到优先级最高的进程，并且从队列中删除cout 本次调度前： endl;:print_init ready_queue ;running ready_queue- next; /*running指向就绪队列队首PCB*/ready_queue- next running- next;cout endl;cout 本次调度开始 endl;:run running ;cout n本次调度结束。 endl; /*轮转法进程调用算法*/void proc_loop PCB *temp 0,*running 0; /*running的PCB指针*/int times;for times 0;t
29、imes 10;times+ cout 本次调度前： endl;:print_init ready_queue ;running ready_queue- next; /*running指向就绪队列队首PCB*/ready_queue- next running- next;cout endl;cout 本次调度开始 endl; :run1 running ; cout n本次调度结束。 endl; 图0 输入实现调度的方法图1 输入1 在动态优先级调度算法下执行图2图3 输入2 在轮转法调度算法下执行图44实验过程中遇到的问题及解决方案对进程调度的思想理解不够深刻，不知道如何实现对进程优先级
30、的排序，以及进程控制块如何配置信息。在翻阅在大量书箱和同学的帮助下，解决了用动态优先级在方法实现进程调度模拟算法。在对C+语言的使用尤其是在编写代码方面很欠缺，在组织语言时出错不断。经过自己的多次修改之后，程序才得以运行。在做轮转法实现的过程中，参考动态优先级在方法，便很容易实现。5课程设计总结通过本次的课程设计，使我能够正确运用操作系统课程中所学的基本理论和知识，加深了对进程调度基本概念的理解，还有让我感受很深的是对C+语言的应用，由于对C+语言在平时运用的不够，在对C+语言的使用尤其是在编写代码方面很欠缺，在组织语言时出错不断。在设计过程中，需要大量的相关资料，为了本次课程设计我在网上和图
31、书馆查阅了大量资料，不断的发现问题、提出问题、解决问题。在编程和调试的过程中，经常会出现意想不到的问题，并非每个问题都可以从相关资料中找到解决方法，有些问题是无法预料到的，这就需要通过自己理性的分析得出问题的解决方案。我还希望我们可以有更多这样的学习机会，使我们的知识体系变的更加牢固。1.创建n个PCB并加入ready_queue中输入开始进程个数n各进程按优先级从高到低排列Yready_queue为空?NRunning 逐个将ready_pc中PCBRunning idle阻塞running?NYYrunning idle?N将running从 ready_queue中删除,再将runnin
32、g 加入block_queuebN是否创建新PCB?Y创建新进程并加入到ready_queue中对ready_queue中的进程PCB进行优先级排序随机对block_queue中的进程PCB询问是否要唤醒？Y处理完了吗？NN是否要唤醒？YNY将其从 block_queue队列中删除,再将其加入ready_queue队列中并进行优先级排序输入开始进程个数n创建n个PCB并加入ready_queue中Yready_queue为空?NRunning 逐个将ready_pc中PCBRunning idle阻塞running?NYYrunning idle?N将running从 ready_queue中删除,再将running 加入block_queuebN是否创建新PCB?Y创建新进程并加入到ready_queue中随机对block_queue中的进程PCB询问是否要唤醒？Y处理完了吗？NN是否要唤醒？Y将其从 block_queue队列中删除,再将其加入ready_queue队列中