操作系统进程调度实验报告

学院

姓名 学号 教师评定_________________

实验题目 进程调度

一、实验目的

用高级语言编写和调试一个进程调度程序，以加深对进程的概念及进程调度算法的理解。

二、实验内容和要求

设计一个有N个进程并发的进程调度程序，要采用FIFO（先进先出）、简单时间片轮转法、多级反馈队列调度算法这三种算法。

每个进程有一个进程控制块（ PCB）表示。进程控制块可以包含如下信息：进程名、到达时间、需要运行时间、已运行时间、进程状态等等。

进程的到达时间及需要的运行时间可以事先人为地指定（也可以由随机数产生）。进程的运行时间以时间片为单位进行计算。 每个进程的状态可以是就绪 W（Wait）、运行R（Run）、或完成F(Finish)三种状态之一。 就绪进程获得 CPU后都只能运行一个时间片。用已占用CPU时间加1来表示。

如果运行一个时间片后，进程的已占用 CPU时间已达到所需要的运行时间，则撤消该进程，如果运行一个时间片后进程的已占用CPU时间还未达所需要的运行时间，也就是进程还需要继续运行，此时应分配时间片给就绪队列中排在该进程之后的进程，并将它插入就绪队列队尾。 每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的 PCB，以便进行检查。

重复以上过程，直到所要进程都完成为止。 三、实验原理及设计方案

1、FIFO算法：其基本思想是所有进程按先进来就排在前头，一个一个往后接下去的顺序排成一个队列，总是把全部的处理机分配给先进来的进程，然后等待它运行完，释放CPU资源，把处理机重新分配给下一个先进来的进程。直至所有的进程运行完毕。

2、轮转法：所有就绪进程按FCFS排成一个队列，总是把处理机分配给队首的进程，各进程占用CPU的时间片相同。如果运行进程用完它的时间片后还未完成，就把它送回到就绪队列的队尾，把处理机重新分配给队首的进程。直至所有的进程运行完毕。

3、多级反馈队列调度算法。其基本思想是：当一个新进程进入内在后，首先将它放入第一个队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚为完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行，以此类推。

四、流程图

1.FIFO和轮转法：

2、多级反馈队列算法：

五、给出程序中源程序名和执行程序名

1、FIFO和时间轮转法

源程序名：FIFO lunzhuan，执行程序名：FIFO AND LUNZHUAN.CPP 2、多级反馈队列

源程序名：duoji，执行程序名：d.cpp

六、程序清单 1.FIFO 和时间轮转 #include

#include #include

#define getpch(type) (type*)malloc(sizeof(type))/*用getpcb(type)给type类型的变量申请一个空间*/

struct pcb { /*定义进程控制块PCB */

char name[10]; /*进程名*/

char state; /*进程状态*/

int ntime; /*进程需要运行时间*/ int rtime; /*进程已经运行的时间*/

struct pcb *link; /*定义了一个指向pcb结构类型的指针link作为自己的成员函数*/ }*ready=NULL,*p; /*定义了两个指向pcb结构类型的指针ready和p ,ready的初值为空*/

typedef struct pcb PCB; /*定义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指向的进程插入队尾*/ } }

void input() /*建立进程控制块函数*/ {

int i,num;

printf("\n输入进程个数："); scanf("%d",&num);

for(i=0;i

printf("\n进程号No.%d:\n",i);

p=getpch(PCB); /*给进程申请一个空间,并用指针p指向这个空间*/ printf("\n进程名字:");

scanf("%s",p->name); /*输入进程的名字 */ printf("\n 进程运行时间:");

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->link; /* pr向下以一个进程*/ } return(l); }

void disp(PCB * pr)/*建立进程显示函数,用于显示使用FCFS算法的当前进程*/ {

printf("\n name \t state \t ntime rtime \n");

printf(" |%s\t",pr->name); /* 显示当前进程的进程名*/ printf(" |%c\t",pr->state); /*显示当前进程的状态 */

printf(" |%d\t",pr->ntime); /*显示当前进程的运行时间 */ printf(" |%d\t",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) /*就绪队列不为空时*/

{ /*根据标识符值显示不同算法下的就绪队列状态*/ 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->rtime=p->ntime;

printf("\n\n ****该进程执行完成的状态：\n"); p->state='F'; disp(p);

destroy();/*调用destroy函数 */ } else

{

p->state='w'; /* 将状态置为等待 */ sort(); /*调用sort1函数 */ } }

void running2() {

while(p->rtime

ntime)//运行时间还没达到所需时间时继续运行

{

p->state = 'R'; (p->rtime)++; }

printf("\n\n ****该进程执行完成的状态：\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(); /*进程个数赋给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:%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("\n\n 进程已完成.\n"); ch=getchar(); }

}

2、多级反馈队列算法 #include "stdio.h" #include

#include

#define getpch(type) (type*)malloc(sizeof(type))

struct pcb{

char name[10]; char state; int atime; int ntime; int rtime; int queue;

struct pcb* link;

}*ready=NULL, *ready1=NULL, *p;

typedef struct pcb PCB;

void sort() /* 建立对进程进行提交时间排列函数*/ {

PCB *first, *second;

int insert=0;

if((ready==NULL)||((p->atime)atime))) /*进程提交时间最短的,插入队首*/ {

p->link=ready; ready=p;

}

else /* 进程比较提交时间,插入适当的位置中*/ {

first=ready;

second=first->link; while(second!=NULL)

{

if((p->atime)atime)) /*若插入进程比当前进程提交时间短,*/ { /*插入到当前进程前面*/ 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=0; 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"); 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(" %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->queue); 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; } } }

void 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("\n\n ****该进程执行完成的状态：\n"); p->state='F'; disp(p); destroy(); } else {

(p->state)='W';

p->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; //ready为空，让它成为下一队列的对头

while((len!=0)&&(ready1!=NULL))

{

ch=getchar();

h++;

printf("\n The execute numbers：%d\n",h);

p=ready1;

p->state='R';

ready1=p->link;

p->link=NULL;

check();

running();

printf("\n 按任一键继续...");

ch=getchar();

}

}

printf("\n\n进程已完成。\n");

ch=getchar();

}

七、运行结果：

1.FIFO 和时间轮转

2、多级反馈队列算法

八、结果分析与调试过程小结：

在FIFO和时间轮转算法中，参照着实验书的例子稍微修改了，一开始按着FCFS的原则给进程排列，导致在调试时间轮转法中出现了一个问题，就是总是执行队首进程，在运行时间没有到达所需时间的要求时，它没有中止运行和进入到就绪队列的队尾等待下一次的执行，而是一直到它执行完才肯撤销，后来检查才知道，在running()里，没有给出约束条件，才导致浪费了时间。

在这个多级反馈的实验中，我采取了用两条实际上的链表队列来模拟多个逻辑上的队列，这两条链表实际是循环工作着。当第一就绪队列有进程没有按时完成时就会转到第二就绪队列的队尾等待着下一次的重新激发，等第一就绪队列没有进程了，就把第二就绪队列设为当前就绪队列，其本身就成了下一队列，让没有完成的进程放在此队列中继续等待，一直重复着，直到所有进程完成。虽然实验原理很简单，但是在编写代码的过程中遇到了不少的问题，可能是因为在心中构想的流程图不够完善，从而导致编写代码时出现了混乱，还有的就是，当前就绪队列与下一个就绪队列之间的链接，如果连接不对，就无法执行下一个就绪队列了。

九、要求设计命令行操作界面或图形界面

十、思考题

1、 分析不同调度算法的调度策略，比较不同调度算法的优缺点，总结它们的适用范围。 答：FIFO算法：自认为这个好，因为它的执行次数最少，占用CPU 时间不长。

时间片的轮转法：系统将所有进程排成一个队列，按照先来先服务的原则，对队列首的进程进行处理，每个进程在用完自己的时间片后，从新回到队尾进行排队。每运行一次，进程的需要时间减1，直到就绪队列为空！这样很公平，每个进程有相同的执行时间，不用彼此争夺资源。但是这样也导致了每个进程都要等待和其它问题，如打印机，这个进程执行一次那个执行一次，导致打印出来的结果不是完成的某一个进程的结果，而过有着其它结果参杂在里面的结果。

多级反馈队列算法：在执行次数上比时间轮转法有明确改善，但是时间轮转法有的缺点，多级反馈队列也有。

2、 哪种进程最适合于多级反馈队列调度，是偏重于处理机型还是偏重于I/O型？

答：我觉得先进先出最适合于多级反馈队列调度，因为既可以解决执行次数长问题，又可以解决打印结果完成性的问题。是偏重于I/O型的。

附加：

关键函数：

对于FIFO算法来说，其关键函数是running()//当执行时间还没有达到其所需运行时间时，继续执行该进程，直到它运行完毕，总之一定遵守先进先出的原则来执行进程。对于时间片轮转法来说，其关键函数也是其本身对应的running()函数，这一部分包括规定时间片的大小和判断进程轮转执行后其执行时间是否大于等于所需运行时间，如果满足，则在打印结果时要实现p->rtime=p->ntime。对于多级反馈队列来说，其关键函数是sort()//按到达时间大小排列，check()//建立进程查看函数，并实现ready和ready1之间的链接执行，running()//判断执行时间与所需运行时间的关系和计算每一个队列的时间片，该时间片按

队列queue的大小而变化，还有mian()函数，在这里一定要进行ready!=NULL的判断，否则程序在执行完就绪队列1的进程后就不再执行下一队列的进程了。

数据结构：

对于FIFO和时间轮转法来说，它们都用了一个链表队列来实现进程的调度，其中ready指向对列头，按照先进先出的原则总是执行该队列的对头进程。但是在时间轮转法中，因为要考虑到每次进程执行只能执行给定的时间片，在未满足其所需运行时间时，该进程又会回到队列的队尾进行排队等待，所以若是它先进入内存执行，也不一定是它先到达完成状态的，还需要考虑到它的需要运行时间。对于多级反馈队列来说，它则运用了两个队列，一个指向当前就绪队列i，一个指向当前就绪队列i+1，首先ready=ready1均指向第一个就绪队列的对头，然后将ready==NULL，将在ready1中未执行完的进程插入到ready中，然后再ready!=NULL的条件下，将ready1=ready即实现了两队列的链接。