操作系统进程调度实验报告(共19页)

1、 计算机 学院 计算机科学与技术 专业 班姓名 学号 教师评定_实验题目 进程调度 一、 实验目的用高级语言编写和调试一个进程调度程序，以加深对进程的概念及进程调度算法的理解。二、实验内容和要求设计一个有N个进程并发的进程调度程序，要采用FIFO（先进先出）、简单时间片轮转法、多级反馈队列调度算法这三种算法。每个进程有一个进程控制块（ PCB）表示。进程控制块可以包含如下信息：进程名、到达时间、需要运行时间、已运行时间、进程状态等等。 进程的到达时间及需要的运行时间可以事先人为地指定（也可以由随机数产生）。进程的运行时间以时间片为单位进行计算。 每个进程的状态可以是就绪 W（Wait）、运行R

2、（Run）、或完成F(Finish)三种状态之一。就绪进程获得 CPU后都只能运行一个时间片。用已占用CPU时间加1来表示。 如果运行一个时间片后，进程的已占用 CPU时间已达到所需要的运行时间，则撤消该进程，如果运行一个时间片后进程的已占用CPU时间还未达所需要的运行时间，也就是进程还需要继续运行，此时应分配时间片给就绪队列中排在该进程之后的进程，并将它插入就绪队列队尾。 每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的 PCB，以便进行检查。重复以上过程，直到所要进程都完成为止。三、实验原理及设计方案1、FIFO算法：其基本思想是所有进程按先进来就排在前头，一个一个往后接下去

3、的顺序排成一个队列，总是把全部的处理机分配给先进来的进程，然后等待它运行完，释放CPU资源，把处理机重新分配给下一个先进来的进程。直至所有的进程运行完毕。2、轮转法：所有就绪进程按FCFS排成一个队列，总是把处理机分配给队首的进程，各进程占用CPU的时间片相同。如果运行进程用完它的时间片后还未完成，就把它送回到就绪队列的队尾，把处理机重新分配给队首的进程。直至所有的进程运行完毕。3、多级反馈队列调度算法。其基本思想是：当一个新进程进入内在后，首先将它放入第一个队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚为完成，调

4、度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行，以此类推。四、流程图1.FIFO和轮转法：开始初始化PCB，输入进程信息各进程按到达到时间先后顺序排成一个队列就绪队列为空？就绪队列首进程投入运行时间片到，运行进程运行时间+1i=1 or i=2选择算法i=1或i=2i=1FIFOs算法时间轮转法i=2Ni=1i=2运行时间是否小于所需要时间Y执行进程进程执行完毕，调度下一进程运行时间是否等于所需时间YN将该进程放到就绪队列的队尾，再等待激发执行下一个进程结束2、多级反馈队列算法：开始运行时间是否到达所需时间Y进程完成，撤销该进程Y将该进程插入到下一个就绪队列的队尾初始化

5、PCB,输入进程信息各进程按到达时间先后顺序排列就绪队列i空N就绪队列首进程投入运行当前就绪队列时间片到，运行时间+时间片N指向下一个就绪队列就绪队列i空?结束Y五、给出程序中源程序名和执行程序名1、FIFO和时间轮转法源程序名：FIFO lunzhuan，执行程序名：FIFO AND LUNZHUAN.CPP2、多级反馈队列源程序名：duoji，执行程序名：d.cpp六、程序清单1.FIFO 和时间轮转#include <stdio.h>#include <stdlib.h>#include <conio.h> #define getpch(type) (

6、type*)malloc(sizeof(type)/*用getpcb(type)给type类型的变量申请一个空间*/struct pcb /*定义进程控制块PCB */char name10; /*进程名*/char state; /*进程状态*/int ntime; /*进程需要运行时间*/int rtime; /*进程已经运行的时间*/struct pcb *link; /*定义了一个指向pcb结构类型的指针link作为自己的成员函数*/*ready=NULL,*p; /*定义了两个指向pcb结构类型的指针ready和p ,ready的初值为空*/typedef struct pcb PC

7、B; /*定义PCB为struct pcb的别名*/void sort() /*对进程进行轮转调度排列函数 */ PCB *first; if(ready=NULL) /*如果就绪队列为空*/ ready=p; /*将新建进程放入就绪队列中，将ready指向队首进程 */ else /*就绪队列中有进程在等待，将新建进程插入到队尾 */ first=ready; /*first指针指向队首进程 */while(first->link!=NULL) first=first->link; /*当first指针没有指向队尾时，指针后移 */first->link=p;/*将P指向的

8、进程插入队尾*/ void input() /*建立进程控制块函数*/ int i,num;printf("n输入进程个数：");scanf("%d",&num);for(i=0;i<num;i+)printf("n进程号No.%d:n",i);p=getpch(PCB); /*给进程申请一个空间,并用指针p指向这个空间*/printf("n进程名字:");scanf("%s",p->name); /*输入进程的名字 */printf("n 进程运行时间:"

9、;);scanf("%d",&p->ntime); /* 输入进程的运行时间*/printf("n");p->rtime=0; /*进程已运行的时间的初值为0*/p->state='w'p->link=NULL; /*新建进程的指针域为空*/sort(); /*调用sort1函数*/int space() /*计算进程控制块个数的函数 */ int l=0; PCB* pr=ready; /* pr指向队首进程*/while(pr!=NULL) /*pr为空,则说明计数完成*/ l+; pr=pr->

10、link; /* pr向下以一个进程*/ return(l); void disp(PCB * pr)/*建立进程显示函数,用于显示使用FCFS算法的当前进程*/ printf("n name t state t ntime rtime n"); printf(" |%st",pr->name); /* 显示当前进程的进程名*/printf(" |%ct",pr->state); /*显示当前进程的状态 */ printf(" |%dt",pr->ntime); /*显示当前进程的运行时间 */p

11、rintf(" |%dt",pr->rtime); /* 显示当前进程的已运行时间 */printf("n"); void check() /*进程查看函数*/ PCB* pr; printf("n *当前正在运行的进程是:%s",p->name);/*显示当前运行进程 */disp(p); /*标志变量不为1，调用disp1()函数*/pr=ready; /*pr指向等待队列的队首进程*/printf("n *当前就绪队列状态为:n"); /*显示就绪队列状态*/while(pr!=NULL) /*就

12、绪队列不为空时*/ /*根据标识符值显示不同算法下的就绪队列状态*/disp(pr); pr=pr->link; void destroy() /*建立进程撤消函数(进程运行结束,撤消进程)*/ printf("n 进程 %s 已完成.n",p->name); free(p); void running1() /*建立进程就绪函数(进程运行时间到,置就绪状态)*/ (p->rtime)+=2; /* 进程的运行时间加2*/if(p->rtime>=p->ntime) /* 如果已运行时间等于进程运行所需的时间,则将进程释放 */p->

13、;rtime=p->ntime; printf("nn *该进程执行完成的状态：n"); p->state='F' disp(p); destroy();/*调用destroy函数 */ else p->state='w' /* 将状态置为等待 */sort(); /*调用sort1函数 */ void running2()while(p->rtime < p->ntime)/运行时间还没达到所需时间时继续运行 p->state = 'R'(p->rtime)+;printf(&

14、quot;nn *该进程执行完成的状态：n");p->state='F'disp(p);destroy();void main() /*轮转法，FCFS算法的程序入口*/int i,len, h=0; /* len用来存放进程的个数*/char ch;printf("*n"); printf(" 计科班 n"); printf(" FIFO算法或时间轮转法 n"); printf("*n");input(); /*调用input1函数，输入进程信息*/len=space(); /*进

15、程个数赋给len*/printf("n选择算法: ");scanf("%d",&i);switch(i) case 1: printf("FIFO算法：n");break; case 2: printf("时间片轮转算法：n");break; default:printf("FAULSE");if(i=1|i=2)while(len!=0)&&(ready!=NULL) ch=getchar(); h+; printf("n The execute number

16、:%d n",h); p=ready; /*将队首指针赋给p*/ ready=p->link; /*ready指向原p的下一个进程*/ p->link=NULL; /*p的link赋空*/ p->state='R' /*p的运行状态置为运行*/ check(); /*调用check函数，运用值传递*/ if(i=1) running2(); if(i=2) running1(); /*调用running1函数*/ printf("n 按任意键继续."); ch=getchar(); printf("nn 进程已完成.n&

17、quot;); ch=getchar();2、多级反馈队列算法#include "stdio.h"#include <stdlib.h>#include <conio.h>#define getpch(type) (type*)malloc(sizeof(type)struct pcb char name10; char state; int atime; int ntime; int rtime; int queue; struct pcb* link;*ready=NULL, *ready1=NULL, *p;typedef struct pcb

18、 PCB;void sort() /* 建立对进程进行提交时间排列函数*/ PCB *first, *second; int insert=0; if(ready=NULL)|(p->atime)<(ready->atime) /*进程提交时间最短的,插入队首*/ p->link=ready; ready=p; else /* 进程比较提交时间,插入适当的位置中*/ first=ready; second=first->link; while(second!=NULL) if(p->atime)<(second->atime) /*若插入进程比当

19、前进程提交时间短,*/ /*插入到当前进程前面*/ p->link=second; first->link=p; second=NULL; insert=1; else /* 插入进程到达时间最长,则插入到队尾*/ first=first->link; second=second->link; if (insert=0) first->link=p; void input() /*建立进程控制块函数*/ int i,num; printf("n 请输入进程个数："); scanf("%d",&num); for(i=

20、0; i<num; i+) printf("n 请输入进程号NO.%d：n",i); p = getpch(PCB); printf(" 输入进程名："); scanf("%s",p->name);printf("n 输入进程到达时间："); scanf("%d",&p->atime); printf("n 输入进程运行时间："); scanf("%d",&p->ntime); printf("n"

21、;); p->rtime=0; p->state='w' p->queue=1; p->link=NULL; sort(); int space() /*查看进程个数*/ int l=0; PCB *pr=ready; while(pr!=NULL) l+; pr=pr->link; return(l);void disp(PCB *pr) /*建立进程显示函数，用于显示当前进程*/ printf("n name t state t atime t ntime t rtime t queue n"); printf("

22、 %s t",pr->name); printf(" %c t",pr->state); printf(" %d t",pr->atime); printf(" %d t",pr->ntime); printf(" %d t",pr->rtime); printf(" %d t",pr->queue); printf("n");void check() /*建立进程查看器*/ PCB *pr;int i,j; i=(p->q

23、ueue); j=(p->queue)+1; printf("n*当前正在运行的进程是：%s",p->name); disp(p); pr = ready1; printf("n*当前就绪队列%d状态为：n",i); /*显示就绪队列状态*/ while(pr!=NULL) disp(pr); pr=pr->link; pr=ready; printf("n*当前就绪队列%d状态为：n",j); /*显示就等待队列状态*/ while(pr != NULL) disp(pr); pr = pr->link; v

24、oid destroy() printf("n 进程%s 已完成。n",p->name); free(p);void running() (p->rtime)+=(2*(p->queue); /每一就绪队列对应的时间片 if(p->rtime>=p->ntime) p->rtime=p->ntime; printf("nn *该进程执行完成的状态：n"); p->state='F' disp(p); destroy(); else (p->state)='W' p

25、->queue+; /队列+1，说明该进程进入下一队列 sort(); void main() int len, h=0;/h表示执行的次数 char ch; printf("*n"); printf(" 计科7班 3210006174 n "); printf(" 多级反馈队列算法 n"); printf("*n"); input(); len = space(); while(ready!=NULL) ready1=ready; /ready1和ready同时指向队列头 ready=NULL; /read

26、y为空，让它成为下一队列的对头 while(len!=0)&&(ready1!=NULL) ch=getchar(); h+; printf("n The execute numbers：%dn",h); p=ready1; p->state='R' ready1=p->link; p->link=NULL; check(); running(); printf("n 按任一键继续."); ch=getchar(); printf("nn进程已完成。n"); ch=getchar();

27、七、运行结果：1.FIFO 和时间轮转 2、多级反馈队列算法八、结果分析与调试过程小结：在FIFO和时间轮转算法中，参照着实验书的例子稍微修改了，一开始按着FCFS的原则给进程排列，导致在调试时间轮转法中出现了一个问题，就是总是执行队首进程，在运行时间没有到达所需时间的要求时，它没有中止运行和进入到就绪队列的队尾等待下一次的执行，而是一直到它执行完才肯撤销，后来检查才知道，在running()里，没有给出约束条件，才导致浪费了时间。在这个多级反馈的实验中，我采取了用两条实际上的链表队列来模拟多个逻辑上的队列，这两条链表实际是循环工作着。当第一就绪队列有进程没有按时完成时就会转到第二就绪队列的队

28、尾等待着下一次的重新激发，等第一就绪队列没有进程了，就把第二就绪队列设为当前就绪队列，其本身就成了下一队列，让没有完成的进程放在此队列中继续等待，一直重复着，直到所有进程完成。虽然实验原理很简单，但是在编写代码的过程中遇到了不少的问题，可能是因为在心中构想的流程图不够完善，从而导致编写代码时出现了混乱，还有的就是，当前就绪队列与下一个就绪队列之间的链接，如果连接不对，就无法执行下一个就绪队列了。九、要求设计命令行操作界面或图形界面十、思考题1、 分析不同调度算法的调度策略，比较不同调度算法的优缺点，总结它们的适用范围。答：FIFO算法：自认为这个好，因为它的执行次数最少，占用CPU 时间不长。时间片的轮转法：系统将所有进程排成一个队列，按照先来先服务的原则，对队列首的进程进行处理，每个进程在用完自己的时间片后，从新回到队尾进行排队。每运行一次，进程的需要时间减1，直到就绪队列为空！这样很公平，每个进程有相同的执行时间，不用彼此争夺资源。但是这样也导致了每个进程都要等待和其它问题，如打印机