优先调度时间片轮转剖析

1、计算机操作系统课程实验报告 姓名: 学号: 班级: 完成日期: 实验题目 进程调度模拟程序 实验形式 小组合作独立完成 设计目的 1 .加深对进程、进程控制块及进程队列等概念的理解。 2 .了解优先数调度算法、时间片轮转算法、先来先服务调度算法、短作业优先调度算法的具体实施办法，加深对进程管理各部分内容的理解。 设计预备知识 1 .进程管理。 2 .优先数调度算法、时间片轮转算法、先来先服务调度算法、短作业优先调度算法。 设计内容 设一个至少包含两种调度算法的模拟进程调度程序(已给出优 先数算法模拟进程调度程序， 要求再加进至少一种调度算法， 模拟程序的设计可以在给出的优先数算法的基础上添加，

2、也可以自行设计，开发语后可自选)。 设计的模拟程序要求如下： (1) 设计适合所选算法的进程控制块PCB表结构。 (2) 对/、同的算法建立进程就绪队列。 (3) 设计的程序中能显示或打印进程控制块的动态变化过程。 一、设计理论描述 a)a)优先数调度算法 为了照顾紧迫型作业，使之在进入系统后便获取优先处理，引入了最高优先权优先调度算法，此算法常被用于批处理系统中，作为作业调度算法木，也作为多钟操作系统中的进程调度算法，还可以用于实时操作系统中。当把该算法用于作业调度时，系统将从后备队列中选择若干优先权最高的作业装入内存。 b)b)时间片轮转调度算法 在早期的时间片轮转法中，系统将所有的就绪进

3、程按照先来先服务的原则排成一个队列，每次调度时，把 CPUCPU 分配桂队首进程，并执行一个时间片。当执行时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号停止该进程的执行，并将它送往就绪队列的队尾。 二、设计思想、设计分析及数据结构模型 1 1、优先数调度算法 (1)(1)设计思想 按某种原则对就绪队列中的每个进程赋予一个优先级，进程调度时则根据进程的优先级确定选择顺序，即把处理机分配给就绪队列中优先级高的进程。由于进程的优先级别通常用数字表示，所以又称为进程的优先数。有些操作系统中规定优先数愈小，其优先级愈高，本设计研究的是优先数愈高，优先级愈高的情况。 优先数调度算法一般可以

4、采用抢占式优先调度算法或非抢占优先调度算法。 在采用抢占式优先调度算法时，系统同样是把处理机分配给优先数最高的进程，使之执行。但在其执行期间，只要又出现了另一个具优先数更高的进程，进程调度程序就立即停止当前进程(原优先数最高的进程)的执行，重新将处理机分配给新到的优先数最高的进程。 在采用非抢占式优先调度算法时，系统一旦把处理机分配给就绪队列中优先数最高的进程后，该进程便一直执行下去，直至结束；或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先数最高的进程。这种调 度算法主要用于批处理系统中；也可用于某些对实时性要求不严的实时系统中。 (2)(2)设计分析 进程调度所依赖

5、的数据结构通常是调度队列，由于调度的原因不同，在单处 理器系统中设置了多种等待队列；只有就绪队列中的进程能够获得处理器而最终运行，其他队列中的进程从队列中调度出来后，必须进入就绪队列才能分配处理 (3)(3)数据结构模型 用结构体变量定义进程控制块的优先级，进程需要占用 CPUCPU 的时间 (cputime),(cputime),运行后还需要 CPUCPU 的时间，进程的状态，及指向 pcbpcb 结构体变量的指针。具体代码如下： typedefstructnode ( charname10;/*进程标识符*/ intprio;/*进程优先数*/ intcputime;/*进程占用CPU时间

6、*/ intneedtime;/*进程到完成还要的时间*/ charstate;/*进程的状态*/ structnode*next;/*链指针*/ PCB; 进程名 next 优先数 占用CPU时间 到完成还要的时间 状态 2 2、时间片轮转调度算法 (1)(1)设计思想 时间片轮转的主要思想就是按顺序为每一个进程一次只分配一个时间片的时间。算法要完成的功能就是将各个进程按照时间片轮转运行的动态过程显示出来。 时间片轮转算法中，系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把 CPUCPU 分配给队首进程，并令其执行一个时间片。时间片的大小从几 msms 到几百 msms。当

7、执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将其送往就绪队列的末尾；然 后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程在一定给定的时间内均能获得一时间片的处理机执行时间。换言之，系统能在给定时间内响应所有用户的请求。 (2)(2)设计分析 每个进程用一个 PCBPCB 表示。PCBPCB 包括进程名，到达时间，运行时间，剩余时间，进程状态，链接指针。其中，进程名，到达时间和运行时间由用户输入，剩余时间的初值等于运行时间。 为简单起见， 进程状态设为三种： 就绪， 运行和完成。 链接指针指向下

8、一个进程的 PCB;PCB;按照进程到达的先后顺序排成一个队 列。设置一个队头指针指向队列中第一个进程，并设置一个队尾指针指向队列中 的最后一个进程；执行调度时，先选择队首的第一个进程运行。另外设置一个指向当前运行进程的指针。 (3)(3)数据结构模型 用结构体变量定义进程控制块的优先级，进程需要占用 CPUCPU 的时间 (cputime),(cputime),运行后还需要 CPUCPU 的时间，进程的状态，分配 cpucpu 时间，执行次数及指向 pcbpcb 结构体变量的指针。具体代码如下： typedefstructnode charname10; /*进程标识符*/ PCB; 进程名

9、 优先数 占用CPU时间 到完成还要的时间 next 状态 分配CPU的时间片 执行次数 三、变量说明及程序流程图 intcputime; /*进程占用CPU时间*/ intneedtime; /*进程到完成还要的时间 charstate; /*进程的状态*/ intround; /*分配cpu的时间片*/ intcount; /*执行次数*/ structnode*next; /*链指针*/ intprio; /*进程优先数*/ */ 优先数调度算法: 四、源代码 #include #include #include #include typedefstructnode( charname1

10、0; intprio; intcputime; intneedtime; charstate; structnode*next; intround; intcount;时间片轮转调度算法: /*进程标识符*/ /*进程优先数*/ /*进程占用CPU时间*/ /*进程到完成还要的时间*/ /*进程的状态*/ /*链指针*/ 分配cpu的时间片*/ /*执行次数*/ PCB; PCB*finish,*ready,*run;/*队列指针*/ intN;/*选择数*/ /*将就绪队列中的第一个进程投入运行*/ voidfirstin() if(N=1) else if(N=1) %-10s%-10d%

11、-10d%-10d%cn”,q-name, q-cputime,q-needtime,q-prio,q-state); else q-count=q-cputime/q-round; printf(%-10s%-10d%-10d%ct%-10dn,q-name, q-cputime,q-needtime,q-state,q-count); voidprt()/*输出函数*/ ( PCB*p; prt1();/*输出标题*/ if(run!=NULL)/*如果运行指针不空*/ prt2(run);/*输出当前正在运行的PCB*/ run=ready; /*就绪队列头指针赋值给运行头指针*/ ru

12、n-state=R; /*进程状态变为运行态*/ ready=ready-next; /*就绪对列头指针后移到下一进程*/ voidprt1()/*标题输出函数 */ printf( name cputimeneedtimeprioritystaten); printf( name cputimeneedtimestatecountn); voidprt2(PCB*q) /*进程 PCB输出*/ printf( p=ready;/*输出就绪队列PCB*/ while(p!=NULL)( prt2(p); p=p-next; p=finish;/*输出完成队列的PCB*/ while(p!=NU

13、LL)( prt2(p); p=p-next; getch();/*按任意键继续*/ voidinsert(PCB*q)/*优先数的插入算法*/ ( PCB*p1,*s,*r; intb; s=q;/*待插入的PCB指针*/ p1=ready;/*就绪队列头指针*/ r=p1;/*r做p1的前驱指针*/ b=1; while(p1!=NULL)&b)/*根据优先数确定插入位置*/ if(p1-prio=s-prio)( r=p1; p1=p1-next; else b=0; if(r!=p1)/*如果条件成立说明插入在r与p1之间*/ ( r-next=s; s-next=p1; el

14、se s-next=p1;/*否则插入在就绪队列的头*/ready=s; voidcreate()/*优先数创建初始PCB信息*/ PCB*p; charna10; for(i=1;iname,na); p-cputime=0; p-needtime=time; p-state=w; if(N=1) p-prio=35-time;/*进程的优先数以 else insert(p); elsep-prio=50; /*进程的优先数都为50*/ if(ready!=NULL) /*就绪队列不空调用插入函数插入*/ ready=NULL; /*就绪队列头指针*/ finish=NULL; /*完成队列

15、头指针*/ run=NULL; /*运行队列指针*/ printf(nn输入5个进程标识和所需时间 n);/*输入进程标识和所需时间创建 PCB*/ printf(输入第%d个进程的名字和时间 :,i); 35-time构成*/ p-next=ready;/*创建就绪队列的第一个PCB*/ ready=p; ) ) system(cls); printf(outputofprocess:n); printf(*n); prt();/*输出进程PCB信息*/ run=ready;/*将就绪队列的第一个进程投入运行*/ ready=ready-next; run-state=R; ) voidpr

16、iority()/*优先数调度算法*/ ( while(run!=NULL)/*当运行队列不空时，有进程正在运行*/ (run-round=1;/*时间片*/run-cputime=run-cputime+1;/*CPU时间片数加1*/if(N=1)(run-needtime=run-needtime-1;/*进程还需要的日间片数减1*/ run-prio=run-prio-2;/*每运行一次优先数降低2个单位*/ )else(run-needtime=run-needtime-run-round;/*进程还需要的时间片数减时间片*/run-prio=run-prio-5;/*每运行一次优先数

17、降低5个单位，即该进程到队列最 后*/ )if(run-needtime=0)/*如所需时间为0将其插入完成队列*/( run-next=finish; /*没有运行完同时优先数不是最大，则将其变为就绪态插入到就绪队列elseif(ready!=NULL)&(run-prioprio) run-state=W; insert(run); firstin();/*将就绪队列的第一个进程投入运行*/ prt();/*输出进程PCB信息*/ /*主函数*/voidmain() system(cls); printf(*n); printf(请选择算法：1.优先数调度算法；2.时间片轮转算法：

18、”); scanf(%d,&N); create(); priority(); 五、程序运行结果及分析 优先数调度算法:输入5个进程的名称和时间finish=run; run-state=F; /*置状态为完成态*/ run=NULL; /*运行队列头指针为空*/ if(ready!=NULL) /*如就绪队列不空*/ firstin(); /*将就绪对列的第一个进程投入运行*/ */ 方作业。读验Debug第T向片轮转实验-砺 输出结果: 广 “E:fPlkCl婚口后勺啊间片轮转犍-Bt.exe D 回 loutputofprocessloutputofprocessi i中HHMM

19、W=W*MMW IIII nanenanecputcputimeneedtimeneedtIneIneprioritystateprioritystate p2p208082727w w plW1025wplW1025w p301817up301817u pS0pS02121HuHu p40p40269269u u nnecputimcnedtimeprioritystatennecputimcnedtimeprioritystate p2p21 1725725R R pl010pl0102S2Sw w p3p3廿1817w1817w p502114up502114u p40p40269269

20、u u nanenanecputcputimeneedtimeneedtininppioritj/stateppioritj/state plplH H1025R1025R p22623p22623U U p3p30 018171817w w p5M2114wp5M2114w p40269up40269u namecputimenamecputimeneeneedtdtin)ppriain)ppriaritritJJstatestate plpl1 1923923H H p2p22 22323U U p3p30 0IB17IB17u u pSpS0 021142114w w p40269wp40269w namecputin)eneedtimeppioyitystatenamecputin)eneedtimeppioyitystate |p22623R|p22623R plpl2 2821821U U p3p30 0IBIB17w17w * *0 0212114w14w p40p40269269u u 半: 1 b1 J 2.2.时间片轮转算法：1 1 请选择算法:1:1.优先数调度算法; 08610861 1812218122 和名名名名名沪一 nt1234512345 1jlir吊Hg-F五FmF 入人入人入入 产- 时间片轮转算法: E:fplkQSDebugDeb