操作系统课程设计-莫黎(共29页)

1、PAGE 课 程 设 计 报 告课程名称 操作系统(co zu x tn) 课题(kt)名称 进程(jnchng)调度算法的设计 专 业 通信工程 班 级 1101 学 号 201103020135 姓 名 莫 黎 指导教师 颜国风 2014年 6 月 29 日湖南工程学院课 程 设 计 任 务 书课程名称 操作系统(co zu x tn) 课 题 进程调度(diod)算法的设计 专业(zhuny)班级 通信1101 学生姓名 莫 黎 学 号 201103020135 指导老师 颜国风 审 批 任务书下达日期 2014 年 6 月 23 日任务完成日期 2014 年 6 月 29 日1设计内容

2、(nirng)与设计要求1.1设计(shj)内容1.1.1 进程调度(diod)算法的设计 设计要求：设计进程控制块PCB表结构，分别适用于优先数调度算法和循环轮转调度算法。建立进程就绪队列。对两种不同算法编制入链子程序。编制两种进程调度算法：1）优先数调度；2）循环轮转调度 设计技术参数:本程序用两种算法对五个进程进行调度，每个进程可有三个状态，并假设初始状态为就绪状态。为了便于处理，程序中的某进程运行时间以时间片为单位计算。各进程的优先数或轮转时间数以及进程需运行的时间片数的初始值均由用户给定。在优先数算法中，优先数的值为50与运行时间的差值，即P_TIME-process-needtim

3、e。进程每执行一次，优先数减3，CPU时间片数加1，进程还需要的时间片数减1。在轮转算法中，采用固定时间片（即：每执行一次进程，该进程的执行时间片数为已执行了2个单位），这时，CPU时间片数加2，进程还需要的时间片数减2，并排列到就绪队列的尾上。对于遇到优先数一致的情况，采用FIFO策略解决。 1.1.2 银行家算法设计 设计要求：编制银行家算法通用程序，并检测所给状态的系统安全性。设进程I提出请求RequestN，则银行家算法按如下规则进行判断。 (1)如果RequestN=NEEDI，N，则转(2)；否则，出错。 (2)如果RequestNneedtime。进程每执行一次，优先数减3，CP

4、U时间片数加1，进程还需要的时间片数减1。在轮转算法中，采用固定时间片（即：每执行一次进程，该进程的执行时间片数为已执行了2个单位），这时，CPU时间片数加2，进程还需要的时间片数减2，并排列到就绪队列的尾上。对于遇到优先数一致的情况，采用FIFO策略解决。 三.设计原理3.1 循环轮转调度算法时间片轮转调度是一种最古老，最简单，最公平且使用最广的算法。每个进程被分配一个时间段，称作它的时间片，即该进程允许运行的时间。如果在时间片结束时进程还在运行，则CPU将被剥夺并分配给另一个进程。如果进程在时间片结束前阻塞或结束，则CPU当即进行切换。调度程序所要做的就是维护一张就绪进程列表，当进程用完它

5、的时间片后，它被移到队列的末尾。时间片轮转调度中唯一有趣的一点是时间片的长度。从一个进程切换到另一个进程是需要一定时间的-保存和装入寄存器值及内存映像，更新各种表格和队列等。在早期的时间片轮转法中,系统将所有的就绪进程按先来先服务的原则,排成一个队列,每次调度时,把CPU分配给队首进程,并令其执行一个时间片.时间片的大小从几ms到几百ms.当执行的时间片用完时,由一个计时器发出时钟中断请求,调度程序便据此信号来停止该进程的执行,并将它送往就绪队列的末尾;然后,再把处理机分配给就绪队列中新的队首进程,同时也让它执行一个时间片.这样就可以保证就绪队列中的所有进程,在一给定的时间内,均能获得一时间片

6、的处理机执行时间.3.2优先(yuxin)数调度算法优先数调度算法常用于批处理系统中。在进程调度中，每次调度时，系统把处理机分配(fnpi)给就绪队列中优先数最高的进程。它又分为两种：非抢占式优先数算法和抢占式优先数算法。在非抢占式优先数算法下，系统一旦把处理机分配给就绪队列中优先数最高的进程后，这个(zh ge)进程就会一直运行，直到完成或发生某事件使它放弃处理机，这时系统才能重新将处理机分配给就绪队列中的另一个优先数最高的进程。在抢占式优先数算法下，系统先将处理机分配给就绪队列中优先数最高的进程度让它运行，但在运行的过程中，如果出现另一个优先数比它高的进程，它就要立即停止，并将处理机分配给

7、新的高优先数进程。四设计步骤4.1 任务分析(1)PCB结构通常包括以下信息：进程名，进程优先数，轮转时间片，进程已占用的CPU时间，进程还需要的CPU时间，进程的状态，当前队列指针等。可根据实验的不同，PCB结构的内容可以作适当的增删(2)本程序用两种算法对五个进程进行调度，每个进程可有三个状态：就绪、执行、完成。并假设初始状态为就绪状态。 (3)为了便于处理，程序中的某进程运行时间以时间片为单位计算。各进程的优先数或轮转时间数以及进程需运行的时间片数的初始值均由用户给定。 (4)在优先数算法中，优先数可以先取值为一个常数减去进程所需要的时间片数目，进程每执行一次，优先数减3，CPU时间片数

8、加1，进程还需要的时间片数减1。在轮转算法中，采用固定时间片（即：每执行一次进程，该进程的执行时间片数为已执行了2个单位），这时，CPU时间片数加2，进程还需要的时间片数减2，并排列到就绪队列的尾上。(5)对于遇到优先数一致(yzh)的情况，采用FIFO策略(cl)解决。4.2 概要(giyo)设计1.本程序用两种算法对五个进程进行调度，每个进程可有三个状态，并假设初始状态为就绪状态。2.为了便于处理，程序中的某进程运行时间以时间片为单位计算。各进程的优先数或轮转时间数以及进程需运行的时间片数的初始值均由用户给定。3.在优先数算法中，优先数的值为50与运行时间的差值，即P_TIME-proce

9、ss-needtime。进程每执行一次，优先数减3，CPU时间片数加1，进程还需要的时间片数减1。在轮转算法中，采用固定时间片（即：每执行一次进程，该进程的执行时间片数为已执行了2个单位），这时，CPU时间片数加2，进程还需要的时间片数减2，并排列到就绪队列的尾上。4.对于遇到优先数一致的情况，采用FIFO策略解决。4.3 详细设计1.struct pcb（） / 定义pcb块2.Void display（） /显示结果信息函数3.int process_finished(pcb *q) /进程完成标示4.void display_round（） /显示循环轮转调度算法运行结果5.priori

10、ty_call() /优先数调度算法6.void cpu_round（）/处理器的工作状态4.4 流程图开始生成并按生成次序排列进程控制块链链首进程运行时间片到，进程时间片-1，优先级-3撤销该进程运行进程退出，取链首进程运行时间片=0？优先级队列中优先级最高的进程？进程队列=null？结束4.5 源程序源程序过程(guchng)如下(rxi)：#include#include #define P_TIME 50enum state ready, execute, block, finish;struct pcb/ 定义(dngy)pcb块 char name4; pcb * next;pcb

11、 * get_process();pcb * get_process() pcb *q; pcb *t; pcb *p; i+; /while return p;void display(pcb *p) /显示(xinsh)结果信息函数 coutname cputime needtime coutneedtime=0; q=q-next; return bl;void cpuexe(pcb *q) pcb *t=q; int tp=0; t-cputime+; void priority_call()/优先数调度(diod)算法 pcb * p; p=get_process(); int cp

12、u=0; ); getch();void display_menu()/显示(xinsh)菜单 coutCHOOSE THE ALGORITHM:endl; cout1 PRIORITYendl; cout2 ROUNDROBINendl; cout3 EXITendl;pcb * get_process_round()/显示循环轮转调度(diod)算法运行结果 pcb *q; pcb *t; pcb *p; int i=0; coutinput name and timecputime+=2; q-needtime-=2; q-process=execute;pcb * get_next(p

13、cb * k,pcb * head) pcb * t; t=k; return t;void set_state(pcb *p) while(p) if (p-needtime=0) p-process=finish; if (p-process=execute) p-process=ready; p=p-next; void display_round(pcb *p) coutNAME CPUTIME NEEDTIME COUNT ROUND STATEnext; void round_cal() pcb * p; set_state(p); void main() display_menu

14、(); int k; scanf(%d,&k); switch(k) case 1:priority_cal();break; case 2:round_cal();break; case 3:break; display_menu(); scanf(%d,&k); 4.6 程序(chngx)测试数据及结果图 SEQ 图 * ARABIC 1程序(chngx)测试数据图 1运用循环轮转调度(diod)算法的执行结果1图 2运用循环轮转调度算法的执行结果2图 3运用(ynyng)循环轮转调度算法的执行结果3图 4运用优先数调度算法(sun f)的执行结果1图5运用优先数调度算法(sun f)的执

15、行结果2图 6运用优先(yuxin)数调度算法的执行结果3五.设计(shj)总结通过本次试验，我了解到优先数算法是一种以进程(jnchng)优先级作为参考来调度进程的一种算法。这个算法的好处是能够让优先级高的进程得到更多的CPU占用时间，缺点是那些优先级低的进程可以永远得不到执行。对于轮转法是一种比较公平的算法，所有的进程都有机会得到执行。六.附录.#include#include #include#include#include#define P_NUM 5#define P_TIME 50enum state ready, execute, block, finish;struct pcb

16、 char name4; int priority; int cputime; int needtime; int count; int round; state process; pcb * next;pcb * get_process();pcb * get_process() pcb *q; pcb *t; pcb *p; int i=0; coutinput name and timeendl; while (iq-name; cinq-needtime; q-cputime=0; q-priority=P_TIME-q-needtime; q-process=ready; q-nex

17、t=NULL; if (i=0) p=q; t=q; else t-next=q; t=q; i+; /while return p;void display(pcb *p) coutname cputime needtime priority stateendl; while(p) coutname; cout ; coutcputime; cout ; coutneedtime; cout ; coutpriority; coutprocess) case ready:coutreadyendl;break; case execute:coutexecuteendl;break; case

18、 block:coutblockendl;break; case finish:coutfinishnext; int process_finish(pcb *q) int bl=1; while(bl&q) bl=bl&q-needtime=0; q=q-next; return bl;void cpuexe(pcb *q) pcb *t=q; int tp=0; while(q) if (q-process!=finish) q-process=ready; if(q-needtime=0) q-process=finish; if(tppriority&q-process!=finish

19、) tp=q-priority; t=q; q=q-next; if(t-needtime!=0) t-priority-=3; t-needtime-; t-process=execute; t-cputime+; void priority_cal() pcb * p; p=get_process(); int cpu=0; while(!process_finish(p) cpu+; coutcputime:cpuendl; cpuexe(p); display(p); printf(All processes have finished,press any key to exit);

20、getch();void display_menu() coutCHOOSE THE ALGORITHM:endl; cout1 PRIORITYendl; cout2 ROUNDROBINendl; cout3 EXITendl;pcb * get_process_round() pcb *q; pcb *t; pcb *p; int i=0; coutinput name and timeendl; while (iq-name; cinq-needtime; q-cputime=0; q-round=0; q-count=0; q-process=ready; q-next=NULL;

21、if (i=0) p=q; t=q; else t-next=q; t=q; i+; /while return p;void cpu_round(pcb *q) q-cputime+=2; q-needtime-=2; if(q-needtimeneedtime=0; q-count+; q-round+; q-process=execute;pcb * get_next(pcb * k,pcb * head) pcb * t; t=k; do t=t-next; while (t & t-process=finish); if(t=NULL) t=head; while (t-next!=k & t-process=finish) t=t-next; return t;void set_state(pcb *p) while(p) if (p-needtime=0) p-process=finish; if (p-process=execute) p-process=ready; p=p-next; void display_round(pcb *p) cout