操作系统实验-进程调度程序设计

本科实验报告课程名称： 操作系统B 实验项目： 进程调度程序设计 实验地点： 专业班级： 学号： 学生姓名： 指导教师： 2011年 11月 目录进程调度程序设计一、实验目的和要求1二、实验内容及原理1三、实验仪器设备3四、操作方法与实验步骤3五、实验数据记录和处理3六、实验结果与分析10七、实验感想1111实验二 进程调度程序设计一、实验目的和要求（一） 目的进程是操作系统最重要的概念之一，进程调度是操作系统的主要内容，本实验要求学生独立地用高级语言编写一个进程调度程序，调度算法可任意选择或自行设计，本实验可使学生加深对进程调度和各种调度算法的理解。（二） 要求1 设计一个有几个进程并发执行的进程调度程序，每个进程由一个进程控制块(PCB)表示，进程控制块通常应包括下述信息：进程名，进程优先数，进程需要运行的时间，占用CPU的时间以及进程的状态等，且可按照调度算法的不同而增删。2 调度程序应包含23种不同的调度算法，运行时可以任选一种，以利于各种方法的分析和比较。3 系统应能显示或打印各进程状态和参数的变化情况，便于观察。二、实验内容及原理1 本程序可选用优先数法或简单轮转法对五个进程进行调度。每个进程处于运行R(run)、就绪W(wait)和完成F(finish)三种状态之一，并假定起始状态都是就绪状态W。为了便于处理，程序中进程的运行时间以时间片为单位计算。各进程的优先数或轮转时间片数、以及进程需要运行的时间片数，均由伪随机数发生器产生。进程控制块结构如表2-1所示： 表2-1 PCB 进程标识符 链指针 优先数/轮转时间片数 占用CPU时间片数 进程所需时间片数 进程状态进程控制块链结构如图2-1所示： RUN HEAD TAIL 1 R 3 W 5 W W 0 2 图2-1 进程控制块链结构其中：RUN当前运行进程指针；HEAD进程就绪链链首指针；TAIL进程就绪链链尾指针。2. 算法与框图 程序框图如图2-2所示。priority是 输入调度算法alog 开始 alog=priority/round robin?生成并按优先数大小排列进程控制块链进程时间片数为0？从链首取一个进程投入运行生成并按进入次序排列进程控制块链链首进程投入运行时间片到，进程时间片数减1，优先数减3运行进程退出，排到进程链尾部 撤消该进程链首进程投入运行时间片到，进程时间片数减1，占用CPU时间加1优先数大于链首进程?进程时间片数为0？ 撤消该进程运行进程退出，按优先数插入进程链从链首取一个进程投入运行 结束 结束 进程队列空?进程队列空?是是是否否否否否是round robin占用处理机时间片到?否是图2-2 进程调度框图 (1)优先数法。 进程就绪链按优先数大小从大到小排列，链首进程首先投入运行。每过一个时间片，运行进程所需运行的时间片数减1，说明它已运行了一个时间片，优先数也减3。理由是该进程如果在一个时间片中完成不了，优先级应降低一级。接着比较现行进程和就绪链链首进程的优先数，如果仍是现行进程高或者相同，就让现行进程继续运行，否则，调度就绪链链首进程投入运行。原运行进程再按其优先数大小插入就绪链，且改变它们对应的进程状态，直至所有进程都运行完各自的时间片数。(2)简单轮转法。 进程就绪链按各进程进入的先后次序排列，链首进程首先投入运行。进程每次占用处理机的轮转时间按其重要程度登入进程控制块中的轮转时间片数记录项（相应于优先数法的优先数记录项位置）。每过一个时间片，运行进程占用处理机的时间片数加1，然后比较占用处理机的时间片数是否与该进程的轮转时间片数相等，若相等说明已到达轮转时间，应将现运行进程排到就绪链末尾，调度链首进程占用处理机，且改变它们的进程状态，直至所有进程完成各自的时间片。 三、实验仪器设备微型计算机。C+6.0 编程软件四、操作方法与实验步骤1.编写源程序2.编译运行，查看结果五、实验数据记录和处理 优先权调度算法：1设定系统中有五个进程，每一个进程用一个进程控制块（PCB）表示，进程队列采用链表数据结构。2.进程控制块包含如下信息：进程名、优先数、需要运行时间、已用CPU时间、进程状态等等。3.在每次运行设计的处理调度程序之前，由终端输入五个进程的“优先数”和“要求运行时间”。4.进程的优先数及需要的运行时间人为地指定.进程的运行时间以时间片为单位进行计算。5.采用优先权调度算法，将五个进程按给定的优先数从大到小连成就绪队列。用头指针指出队列首进程，队列采用链表结构。6.处理机调度总是选队列首进程运行。采用动态优先数办法，进程每运行一次优先数减“1”，同时将已运行时间加“1”。7.进程运行一次后，若要求运行时间不等于已运行时间，则再将它加入就绪队列；否则将其状态置为“结束”,且退出就绪队列。8.“就绪”状态的进程队列不为空，则重复上面6，7步骤，直到所有进程都成为“结束”状态。9.在设计的程序中有输入语句，输入5个进程的“优先数”和“要求运行时间”，也有显示或打印语句，能显示或打印每次被选中进程的进程名、运行一次后队列的变化，以及结束进程的进程名。10、最后，为五个进程任意确定一组“优先数”和“要求运行时间”，运行并调试所设计的程序，显示或打印出逐次被选中进程的进程名及其进程控制块的动态变化过程。简单时间片轮转法：1.设系统有5个进程，每个进程用一个进程控制块PCB来代表。2.为每个进程任意确定一个要求运行时间。3.按照进程输入的先后顺序排成一个队列。再设一个队首指针指向第一个到达进程的首址。4.执行处理机调度时，开始选择队首的第一个进程运行。另外，再设一个当前运行进程的指针，指向当前正在运行的进程。5.考虑到代码的可重用性, 轮转法调度程序和最高优先级优先调度是调用同一个模快进行输出注:由于轮转法调度程序和最高优先级优先调度是调用同一个模快进行输出,所以在时间轮转法调度算法的进程中,依然显示了随即产生的优先级数.6.进程运行一次后，以后的调度则将当前指针依此下移一个位置，指向下一个进程，即调整当前运行指针指向该进程的链接指针所指进程，以指示应运行进程。同时还应判断该进程的要求运行时间是否等于已运行时间。若不等，则等待下一轮的运行，否则将该进程的状态置为完成态C，并退出循环队列。7.若就绪队列不空，则重复上述的（5）和（6）步骤直到所有的进程都运行完为止。8.在所设计的调度程序中,包含显示或打印语句。显示或打印每次选中的进程的名称及运行一次后队列的变化情况。源程序：#include#include#include#define furthest 5 struct process int id; int priority; int cputime; int alltime; char state; int next; prochainfurthest-1; int procnum; int rand(); int algo; int run,head,tail,j;void main()agan:printf(type the algorithm is (1:RR,2:PRIO):); scanf(%d,&algo); if(algo=2) printf(output of priority.n); extern void init(); extern void prisch(); else if(algo=1) printf(output of round robin.n); extern void init(); extern void timesch(); else printf(try again,pleasen); goto agan; for (j=1;j=40;j+)printf(=); printf(nn); for(j=1;j=40;j+) printf(=); printf(nn); printf(system finishedn);void print()int k,p;for(k=1;k=40;k+)printf(=);printf(nrunning proc. );printf(waiting queue.);printf(n %d ,prochainrun.id);p=head;while(p!=0)printf(%5d,p);p=prochainp.next;printf(n);for(k=1;k=40;k+)printf(=);printf(n);printf(id );for(k=1;kfurthest+1;k+)printf(%5d,prochaink.id);printf(n);printf(priority );for(k=1;kfurthest+1;k+)printf(%5d,prochaink.priority);printf(n);printf(cputime );for(k=1;kfurthest+1;k+)printf(%5d,prochaink.cputime);printf(n);printf(alltime );for(k=1;kfurthest+1;k+)printf(%5d,prochaink.alltime);printf(n);printf(state );for(k=1;kfurthest+1;k+)printf(%5d,prochaink.state);printf(n);printf(next );for(k=1;kfurthest+1;k+)printf(%5d,prochaink.next);printf(n);void insert(int q)int p,s; p=head;s=prochainhead.next;while(prochainq.priorityprochains.priority)&(s!=0)p=s;s=prochains.next;prochainp.next=q;prochainq.next=s;void insert2()prochaintail.next=run;tail=run;prochainrun.next=0;void init()int i;head=0;if(algo=2)for(i=1;ifurthest+1;i+)prochaini.id=i;prochaini.priority=(rand()+11)%41;prochaini.cputime=0;prochaini.alltime=(rand()+1)%7;prochaini.state=W;prochaini.next=0;if(prochaini.priorityprochainhead.priority)&(head!=0)insert(prochaini.id);elseprochaini.next=head;head=prochaini.id;else for(i=1;ifurthest+1;i+)prochaini.id=i;prochaini.priority=(rand()+1)%3+1;prochaini.cputime=0;prochaini.alltime=(rand()+1)%7;prochaini.state=W;prochaini.next=(i+1)%(furthest+1);head=1;tail=furthest;prochainfurthest.next =0;run=head;prochainrun.state=R;head=prochainhead.next;prochainrun.next=0;print();void prisch()while(run!=0)prochainrun.cputime+=1;prochainrun.priority-=3;prochainrun.alltime-=1;if(prochainrun.alltime=0)prochainrun.state=F;prochainrun.next=0;if(head!=0)run=head;prochainrun.state=R;head=prochainhead.next;elseprochain0.id=prochainrun.id;run=0;elseif(prochainrun.priorityprochainhead.priority)&(head!=0)prochainrun.state=W;insert(run);run=head;prochainrun.state=R;head=prochainhead.next;print();void timesch()while(run!=0) prochainrun.alltime-=1;prochainrun.cputime+=1;if(prochainrun.alltime=0)prochainrun.state=F;prochainrun.next=0;if(head!=0)run=head;prochainrun.state=R;head=prochainhead.next;elseprochain0.id=procha