优先调度、时间片轮转.doc

计算机操作系统课程实验报告姓名： 学号：班级：完成日期： 实验题目进程调度模拟程序实验形式小组合作 独立完成 R设计目的1加深对进程、进程控制块及进程队列等概念的理解。2了解优先数调度算法、时间片轮转算法、先来先服务调度算法、短作业优先调度算法的具体实施办法，加深对进程管理各部分内容的理解。设计预备知识1.进程管理。2.优先数调度算法、时间片轮转算法、先来先服务调度算法、短作业优先调度算法。设计内容设计一个至少包含两种调度算法的模拟进程调度程序(已给出优先数算法模拟进程调度程序,要求再加进至少一种调度算法，模拟程序的设计可以在给出的优先数算法的基础上添加，也可以自行设计，开发语言可自选)。设计的模拟程序要求如下：（1） 设计适合所选算法的进程控制块PCB表结构。（2） 对不同的算法建立进程就绪队列。（3） 设计的程序中能显示或打印进程控制块的动态变化过程。一、设计理论描述a) 优先数调度算法为了照顾紧迫型作业，使之在进入系统后便获取优先处理，引入了最高优先权优先调度算法，此算法常被用于批处理系统中，作为作业调度算法木，也作为多钟操作系统中的进程调度算法，还可以用于实时操作系统中。当把该算法用于作业调度时，系统将从后备队列中选择若干优先权最高的作业装入内存。b) 时间片轮转调度算法在早期的时间片轮转法中，系统将所有的就绪进程按照先来先服务的原则排成一个队列，每次调度时，把CPU分配桂队首进程，并执行一个时间片。当执行时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号停止该进程的执行，并将它送往就绪队列的队尾。二、 设计思想、设计分析及数据结构模型1、 优先数调度算法（1）设计思想按某种原则对就绪队列中的每个进程赋予一个优先级,进程调度时则根据进程的优先级确定选择顺序，即把处理机分配给就绪队列中优先级高的进程。由于进程的优先级别通常用数字表示，所以又称为进程的优先数。有些操作系统中规定优先数愈小，其优先级愈高，本设计研究的是优先数愈高，优先级愈高的情况。优先数调度算法一般可以采用抢占式优先调度算法或非抢占优先调度算法。在采用抢占式优先调度算法时，系统同样是把处理机分配给优先数最高的进程，使之执行。但在其执行期间，只要又出现了另一个其优先数更高的进程，进程调度程序就立即停止当前进程（原优先数最高的进程）的执行，重新将处理机分配给新到的优先数最高的进程。在采用非抢占式优先调度算法时，系统一旦把处理机分配给就绪队列中优先数最高的进程后，该进程便一直执行下去，直至结束；或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先数最高的进程。这种调度算法主要用于批处理系统中；也可用于某些对实时性要求不严的实时系统中。（2）设计分析进程调度所依赖的数据结构通常是调度队列，由于调度的原因不同，在单处理器系统中设置了多种等待队列；只有就绪队列中的进程能够获得处理器而最终运行，其他队列中的进程从队列中调度出来后，必须进入就绪队列才能分配处理器。（3）数据结构模型用结构体变量定义进程控制块的优先级，进程需要占用CPU的时间(cputime)，运行后还需要CPU的时间，进程的状态，及指向pcb结构体变量的指针。具体代码如下：typedef struct node char 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 node char name10; /*进程标识符*/ int prio; /*进程优先数*/ int cputime; /*进程占用CPU时间*/ int needtime; /*进程到完成还要的时间*/ char state; /*进程的状态*/ int round; /*分配cpu的时间片*/ int count; /*执行次数*/struct node *next; /*链指针*/PCB;进程名next优先数占用CPU时间到完成还要的时间状态分配CPU的时间片执行次数三、变量说明及程序流程图优先数调度算法：时间片轮转调度算法：四、源代码#include#include#include#includetypedef 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( name cputime needtime priority staten);elseprintf( name cputime 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做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; else s-next=p1; /*否则插入在就绪队列的头*/ ready=s; void create() /*优先数创建初始PCB信息*/ PCB *p; int i,time; char na10; ready=NULL; /*就绪队列头指针*/ finish=NULL; /*完成队列头指针*/ run=NULL; /*运行队列指针*/ printf(nn输入5个进程标识和所需时间n); /*输入进程标识和所需时间创建PCB*/ for(i=1;iname,na); p-cputime=0; p-needtime=time; p-state=w; if(N=1) p-prio=35-time;/*进程的优先数以35-time构成*/ else p-prio=50; /*进程的优先数都为50*/ if(ready!=NULL) /*就绪队列不空调用插入函数插入*/ insert(p); else p-next=ready; /*创建就绪队列的第一个PCB*/ ready=p; system(cls); printf(output of process:n); printf(*n); prt(); /*输出进程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); printf(*n); printf(请选择算法:1.优先数调度算法；2.时间片轮转算法:); scanf(%d,&N); create(); priority();五、程序运行结果及分析优先数调度算法：输入5个进程的名称和时间 输出结果： 时间片轮转算法：输出结果：六、课程设计心得与体会操作系统这门课具有很强的理论性、实践性、和综合性，仅仅靠课堂上短短的几十分钟想要学好操作系统这门课是远远不够的，这就需要我们能在课余时间深入理解操作系统中的一些比较抽象的概念。而这一次关于进程调度算法仿真设计的实验恰恰就给了我们一次绝好的锻炼自己能力，深入理解现实中操作系统进程调度机制的机会。在学习进程的理论课上，我知道了在多道程序系统出现之后，为了刻画系统内部动态状况，描述运行程序的活动规律而引进的新概念