优先调度、时间片轮转剖析

计算机操作系统课程实验报告姓名学号班级完成日期立 独 口 作 合 组 小设计目的法的 第容度内调分 o务部 m服各 形先理 貓来管 毗先程1 2 一 O 作解 mrm短理设计预备知识短 先 来 先设计内容H約开flo i T如 咂為側 瞬求蛇 附 进 示 M要斡F:法立显 M 拿 聿 聿 匕匕 中亠予口 厶冃 :加抚0 1 少程出 程也T丹 巨井)口 。以 、彳 、 任！|轻迩W设对设以自 的 十去 JJ 十 ) ) ) 、！、冷一 口 口 、123 设算计、一一口 设 数设语 先的发一、设计理论描述a) 优先数调度算法为了照顾紧迫型作业，使之在进入系统后便获取优先处理，引入了最高优先 权优先调度算法，此算法常被用于批处理系统中，作为作业调度算法木，也作为 多钟操作系统中的进程调度算法，还可以用于实时操作系统中。当把该算法用于 作业调度时，系统将从后备队列中选择若干优先权最高的作业装入内存。b) 时间片轮转调度算法在早期的时间片轮转法中，系统将所有的就绪进程按照先来先服务的原则排 成一个队列，每次调度时，把 CPU 分配桂队首进程，并执行一个时间片。当执 行时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号停止该 进程的执行，并将它送往就绪队列的队尾。二、设计思想、设计分析及数据结构模型1、 优先数调度算法（1）设计思想按某种原则对就绪队列中的每个进程赋予一个优先级 ,进程调度时则根据进 程的优先级确定选择顺序，即把处理机分配给就绪队列中优先级高的进程。由于 进程的优先级别通常用数字表示，所以又称为进程的优先数。有些操作系统中规 定优先数愈小，其优先级愈高，本设计研究的是优先数愈高，优先级愈高的情况。优先数调度算法一般可以采用抢占式优先调度算法或非抢占优先调度算法。在采用抢占式优先调度算法时，系统同样是把处理机分配给优先数最高的进 程，使之执行。但在其执行期间，只要又出现了另一个其优先数更高的进程，进 程调度程序就立即停止当前进程（原优先数最高的进程）的执行，重新将处理机 分配给新到的优先数最高的进程。在采用非抢占式优先调度算法时，系统一旦把处理机分配给就绪队列中优先 数最高的进程后，该进程便一直执行下去，直至结束；或因发生某事件使该进程 放弃处理机时，系统方可再将处理机重新分配给另一优先数最高的进程。这种调 度算法主要用于批处理系统中；也可用于某些对实时性要求不严的实时系统中。（2）设计分析进程调度所依赖的数据结构通常是调度队列，由于调度的原因不同，在单处 理器系统中设置了多种等待队列；只有就绪队列中的进程能够获得处理器而最终 运行，其他队列中的进程从队列中调度出来后，必须进入就绪队列才能分配处理 器。（3）数据结构模型用结构体变量定义进程控制块的优先级，进程需要占用 CPU 的时间 （cputime），运行后还需要CPU的时间，进程的状态，及指向pcb结构体变量的 指针。具体代码如下：typedef struct nodechar name10; /*进程标识符*/int prio; /*进程优先数*/int cputime; /*进程占用 CPU 时间*/int needtime; /*进程到完成还要的时间*/char state; /*进程的状态*/struct node *next; /*链指针*/PCB;进程名next优先数占用CPU时间到完成还要的时间状态2、 时间片轮转调度算法（1）设计思想时间片轮转的主要思想就是按顺序为每一个进程一次只分配一个时间片的 时间。算法要完成的功能就是将各个进程按照时间片轮转运行的动态过程显示出 来。时间片轮转算法中，系统将所有的就绪进程按先来先服务的原则排成一个队 列，每次调度时，把 CPU 分配给队首进程，并令其执行一个时间片。时间片的 大小从几ms到几百ms。当执行的时间片用完时，由一个计时器发出时钟中断请 求，调度程序便据此信号来停止该进程的执行，并将其送往就绪队列的末尾；然 后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。 这样就可以保证就绪队列中的所有进程在一定给定的时间内均能获得一时间片 的处理机执行时间。换言之，系统能在给定时间内响应所有用户的请求。（2）设计分析每个进程用一个PCB表示。PCB包括进程名，到达时间，运行时间，剩余 时间，进程状态，链接指针。其中，进程名，到达时间和运行时间由用户输入， 剩余时间的初值等于运行时间。为简单起见，进程状态设为三种：就绪，运行和 完成。链接指针指向下一个进程的PCB；按照进程到达的先后顺序排成一个队 列。设置一个队头指针指向队列中第一个进程，并设置一个队尾指针指向队列中 的最后一个进程； 执行调度时，先选择队首的第一个进程运行。另外设置一个 指向当前运行进程的指针。（3）数据结构模型用结构体变量定义进程控制块的优先级，进程需要占用 CPU 的时间 （cputime），运行后还需要CPU的时间，进程的状态，分配cpu时间，执行次数 及指向 pcb 结构体变量的指针。具体代码如下：typedef struct nodechar name10;/*进程标识符*/进程名next优先数占用CPU时间到完成还要的时间状态分配CPU的时间片执行次数int prio;/*进程优先数*/int cputime;/*进程占用CPU时间*/int needtime;/*进程到完成还要的时间*/char state;/*进程的状态*/int round;/*分配 cpu 的时间片*/int count;/*执行次数*/struct node *next;/*链指针*/PCB;三、变量说明及程序流程图优先数调度算法创建进程 就绪队列 先数最高 执行进程时间片轮转调度算法：否运忏E是列为叮g余时间锻创建进程执行进程进程结束循环队列四、源代码#include#include #include #include typedef struct node char name10;/*进程标识符*/int prio;/*进程优先数*/int cputime;/*进程占用CPU时间*/int needtime;/*进程到完成还要的时间*/char state;/*进程的状态*/struct node *next;/*链指针*/int round;/*分配 cpu 的时间片*/int count;/*执行次数*/PCB;PCB *finish,*ready,*run; /*队列指针*/int N; /*选择数*/*将就绪队列中的第一个进程投入运行*/void firstin()run=ready;/*就绪队列头指针赋值给运行头指针*/run-state=R;/*进程状态变为运行态*/ready=ready-next; /*就绪对列头指针后移到下一进程*/void prt1()/*标题输出函数*/if(N=1)printf( namecputime needtime priority staten);elseprintf( namecputime needtime state countn);void prt2(PCB *q) /*进程 PCB 输出 */if(N=1)printf( %-10s%-10d%-10d%-10d %cn,q-name, q-cputime,q-needtime,q-prio,q-state);elseq-count=q-cputime/q-round;printf( %-10s%-10d%-10d %ct%-10dn,q-name, q-cputime,q-needtime,q-state,q-count);void prt()/*输出函数*/PCB *p;prt1();/*输出标题*/if(run!=NULL) /*如果运行指针不空*/prt2(run); /*输出当前正在运行的 PCB*/p=ready;/*输出就绪队列 PCB*/while(p!=NULL)prt2(p);p=p-next;p=finish;/*输出完成队列的 PCB*/while(p!=NULL)prt2(p);p=p-next;getch();/*按任意键继续*/void insert(PCB *q)/*优先数的插入算法*/PCB *p1,*s,*r;int b;s=q; /*待插入的PCB指针*/p1=ready; /*就绪队列头指针*/r=p1; /*r做pl的前驱指针*/b=1;while(pl!=NULL)&b) /*根据优先数确定插入位置*/ if(pl-prio=s-prio)r=pl; pl=pl-next;elseb=0;if(r!=p1) /*如果条件成立说明插入在r与pl之间*/r-next=s;s-next=p1;elses-next=p1; /*否则插入在就绪队列的头*/ready=s;void create。/*优先数创建初始PCB信息*/PCB *p;int i,time;char na10;ready=NULL; /*就绪队列头指针*/finish=NULL; /*完成队列头指针*/run=NULL;/*运行队列指针*/printf(nn输入5个进程标识和所需时间山)；/*输入进程标识和所需时间创建PCB*/for(i=1;iname,na);p-cputime=0;p-needtime=time;p-state=w;if(N=1)p-prio=35-time;/*进程的优先数以35-time构成*/*进程的优先数都为 50*/*就绪队列不空调用插入函数插入*/elsep-prio=50; if(ready!=NULL) insert(p);elsep-next=ready; /*创建就绪队列的第一个 PCB*/ ready=p;system(cls);printf(output of process:n); /uS uS uS uSuS uS uS uS uSuS uS uS uS uSuS uS uS uS uS *w 、vwwa *M * f 5|* 5|*平平平平平平平平平平平平平平平平平平平平平平平平平平平平平平平平平平平平平平平平平平平平5|*5|* 1prt()； /*输出进程PCB信息*/run=ready; /*将就绪队列的第一个进程投入运行*/ready=ready-next；run-state=R；void priority()/*优先数调度算法*/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 个单位*/elserun-needtime=run-needtime-run-round;/*进程还需要的时间片数减时间 片*/run-prio=run-prio-5; /*每运行一次优先数降低 5 个单位,即该进程到队列最 后*/if(run-needtime=0) /*如所需时间为0 将其插入完成队列*/run-next=finish;finish=run;run-state=F; /*置状态为完成态*/run=NULL;/*运行队列头指针为空*/if(ready!=NULL) /*如就绪队列不空*/firstin();/*将就绪对列的第一个进程投入运行*/*没有运行完同时优先数不是最大，则将其变为就绪态插入到就绪队列*/ else if(ready!=NULL)&(run-prioprio)run-state=W;insert(run);firstin(); /*将就绪队列的第一个进程投入运行*/prt()； /*输出进程PCB信息*/*主函数*/ void main()system(cls);/ tfW/ uS uS uS uS uS uS uS uS uS uS uS uS uS uS uS uS uS uS uS uS uS uS uS *w 、WX VM V* f 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 I w* 1 printf(请选择算法:1优先数调度算法；2时间片轮转算法:);scanf(%d,&N);create();priority();五、程序运行结果及分析优先数调度算法：输入 5 个进程的名称和时间请选择算法：1.优先数调度算法;2.时间片轮转算法半 *E:作业实验Debum时间片驼转实验-畐悻心才输出结果：”E:作业阴实验Debug时间片驼转实验_副本总疾”= 回outputof process:namecput imeneedtimeprioritystatep20827wPl01025wp301817wP502114wp40269wnamecput imeneedtimeprioritystatep21725RPl01025wp301817wpS02114wp40269wnamecputimeneedtimeprioritystatePlQIQ25Rp22623WP3Q1817wp502114wp40269wnamecputimeneedtimeprioritystatePl1923Rp22623Up3Q1817wp502114wp40269wnamecput imeneedtimeprioritystatep22623RPl2821Wp301817wP502114wp4Q半：269w时间片轮转算法： : E:4k0SDebug时间片驼转实验-副本.exe = I 回请选择算法:1.优先数调度算法；2 .时间片轮转算法:20 8 6 118 12 212 3 4 5 p p p p PFTT FTT FTT FTT FTT FTT n n n n n 吿吿吿厶了 和名名名名名 fin 程进进进进进 .r 12 3 4 5 *第第第第第 人)A)A)A)A)A .-.- !-|-.#|-|-.#|-|-.#|-|-.#|-|-.#|-|-.#输出结果：六、课程设计心得与体会 操作系统这门课具有很强的理论性、实践性、和综合性，仅仅靠课堂上短短的几 十分钟想要学好操作系统这门课是远远不够的，这就需要我们能在课余时间深入 理解操作系统中的一些比较抽象的概念。而这一次关于进程调度算法仿真设计的 实验恰恰就给了我们一次绝好的锻炼自己能力，深入理解现实中操作系统进程调 度机制的机会。在学习进程的理论课上，我知道了在多道程序系统出现之后，为了刻画系统内部 动态状况，描述运行程序的活动规律而引进的新概念。在操作系统中引入进程的 目的一是刻画系统的动态性，二是解决共享性。它具有结构性，共享性，动态性， 独立性，制约性，并发性六个属性。还了解到了它的三态模型，即运行态，就绪 态，以及等待态。进程当前占用处理器为运行态；进程具备运行条件，等待系统 分配处理器让其运行是就绪态；进程不具备运行条件，还处于等待某个时间完成 是阻塞态，也就是等待态。在这个基础上，又增加了挂起等待态和挂起就绪态。 通过学习和理解，挂起进程其实就是在被对换进主存之前不会参与低级调度，因 为操作系统或者父进程自身阻碍了它的运行。通过这次实验，我对操作系统有了一个全新的认识，编程能力也有了很大的提高。