进程模拟调度算法课程设计报告

一．课程概述

1.1.设计构想

程序能够完成以下操作：创建进程：先输入进程的数目，再一次输入每个进程的进程名、运行总时间和优先级，先到达的先输入；进程调度：进程创建完成后就选择进程调度算法，并单步执行，每次执行的结果都从屏幕上输出来。

1.2.需求分析

在多道程序环境下，主存中有着多个进程，其数目往往多于处理机数目，要使这多个进程能够并发地执行，这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。分配处理机的任务是由处理机调度程序完成的。由于处理机是最重要的计算机资源，提高处理机的利用率及改善系统必（吞吐量、响应时间），在很大程度上取决于处理机调度性能的好坏，因而，处理机调度便成为操作系统设计的中心问题之一。本次实验在VC++6.0环境下实现先来先服务调度算法，短作业优先调度算法，高优先权调度算法，时间片轮转调度算法和多级反馈队列调度算法。

1.3.理论依据

为了描述和管制进程的运行，系统为每个进程定义了一个数据结构——进程控制块PCB(Process Control Block),PCB中记录了操作系统所需的、用于描述进程的当前情况以及控制进程运行的全部信息，系统总是通过PCB对进程进行控制，亦即，系统是根据进程的PCB而不是任何别的什么而感知进程的存在的，PCB是进程存在的惟一标志。本次课程设计用结构体Process代替PCB的功能。

1.4.课程任务

一、用C语言（或C++）编程实现操作模拟操作系统进程调度子系统的基本功能；运用多种

算法实现对进程的模拟调度。

二、通过编写程序实现进程或作业先来先服务、高优先权、按时间片轮转、短作业优先、多

级反馈队列调度算法，使学生进一步掌握进程调度的概念和算法，加深对处理机分配的理解。

三、实现用户界面的开发

专业知识分享

WORD格式可编辑

1.5.功能模块分析：

1、进程概念：进程是被分配资源的最小单位。进程是动态概念，必须程序运行才有 进程的产生。

2、进程的状态模型：

（1）运行：进程已获得处理机，当前处于运行状态。 （2）就绪：进程已经准备好，一旦有处理器就可运行。

3、处理机调度：在多道程序设计系统中，内存中有多道程序运行，他们相互争夺处理机 这一重要的资源。处理机调度就是从就绪队列中，按照一定的算法选择一个进程并将 处理机分配给它运行，以实现进程并发地执行。 4、进程调度算法的功能：

记录系统中所有进程的执行情况 选择占有处理机的进程 进行进程的上下文切换

5、进程调度的算法：

（1）先来先服务算法：如果早就绪的进程排在就绪队列的前面，迟就绪的进程排在 就绪队列的后面，那么先来先服务总是把当前处于就绪队列之首的那个进程调 度到运行状态。

（2）优先数算法：即进程的执行顺序由高优先级到低优先级。系统或用户按某种原

则为进程指定一个优先级来表示该进程所享有的确调度优先权。该算法核心是确定进程的优先级。

（3）时间片轮转算法：固定时间片，每个进程在执行一个时间片后，轮到下一进程

执行，知道所有的进程执行完毕。处理器同一个时间只能处理一个任务。处理器在处理多任务的时候，就要看请求的时间顺序，如果时间一致，就要进行预测。挑到一个任务后，需要若干步骤才能做完，这些步骤中有些需要处理器参与，有些不需要（如磁盘控制器的存储过程）。不需要处理器处理的时候，这部分时间就要分配给其他的进程。原来的进程就要处于等待的时间段上。经过周密分配时间，宏观上就象是多个任务一起运行一样，但微观上是有先后的，就是时间片轮换。 (4) 多级反馈队列法：又称反馈循环队列或多队列策略， 主要思想是将就绪进程分

为两级或多级，系统相应建立两个或多个就绪进程队列， 较高优先级的队列一般分配给较短的时间片。 处理器调度先从高级就绪进程队列中选取可占有处理器的进程， 只有在选不到时， 才从较低 级的就绪进程队列中选取。

（5）短作业优先法：对短进程优先调度的算法，它是从后备队列中选择一个或者若

干个进程，将处理机分配给它，使它立即执行并一直执行到完成， 或发生某事件而被阻塞放弃处理机时再重新调度。

专业知识分享

WORD格式可编辑

二．设计方案

2.1．先来先服务调度

2.1.1．算法思想

先来先服务调度算法的思想是按照进程进入就绪队列的先后顺序调度并分配处理机执行。先来先服务调度算法是一种不可抢占的算法，先进入就绪队列的进程，先被处理机运行。一旦一个进程占有了处理机，它就一直运行下去，直到该进程完成工作或者因为等待某事件而不能继续运行时才释放处理机。

2.1.2．算法流程图

开始初始化所有JCB使JCB按作业提交时刻的先后顺序排队时间量 T: =0调度队首的作业投入运行：（更改队首指针，使作业的状态为R，记住作业开始运行的时刻Tb等等）计算并打印运行作业i的完成时刻Tc,周转时间Ti，带权周转时间Wi(完成时刻Tc=开始运行时刻+运行时间周转时间Ti=完成时间-提交时间带权周转时间Wi=周转时间÷运行时间)更改时间量T的值（T: =T+作业1的运行时间）不空等待队列空？空计算并打印这组作业的平均周转时间及带权平均周转时间结束 图1.先来先服务算法流程图

专业知识分享

WORD格式可编辑

2.1.3．程序代码

#include #include #include typedef struct node {

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

int cputime; /*占用cpu时间*/ char starttime[5]; //进程开始时间 int needtime; /*要求运行时间*/ char state; /*状态*/ struct node *next; /*指针*/ }PCB;

PCB *ready, *run, *finish; //就绪、执行、结束指针 int N; //进程数量

void print() //输出函数 {

PCB *p;

printf(\" NAME CPUTIME STARTTIME NEEDTIME STATUS\\n\"); if(run != NULL)

printf(\" %-10s%-10d%-10s%-10d %c\\n\ run->name, run->cputime, run->starttime, run->needtime,

run->state); /*输出执行的进程的信息*/ p=ready;

while(p != NULL) {

printf(\" %-10s%-10d%-10s%-10d %c\\n\ p->name, p->cputime, p->starttime, p->needtime,

p->state); /*输出就绪进程的信息*/ p=p->next; }

p=finish;

while(p != NULL) {

printf(\" %-10s%-10d%-10s%-10d %c\\n\ p->name, p->cputime,

专业知识分享

WORD格式可编辑

p->starttime, p->needtime,

p->state); /*输出结束队列的信息*/ p=p->next; }

getchar(); /*使用getchar()函数可以让输出时停留画面， 等待人按回车继续*/ }

void insert(PCB *q) /*插入新进程，把进程按进程到来时间大小排序*/ {

PCB *p1,*s,*r; int b;

s=q; /*指针s指向新要插入的进程*/

p1=ready; /*指针p1指向原来的进程队列的队首*/ r=p1; /*使用指针r是指向p1前面的进程*/ b=1;

while((p1!=NULL)&&b)

if(strcmp(p1->starttime,s->starttime)<0) {

r=p1; p1=p1->next;

} /*新进程的开始时间大，则p1 指向下一个进程继续比*/ else

b=0; if(r!=p1) {

r->next=s; s->next=p1;

} /*新进程找到位置，插在r和p1之间*/ else {

s->next=p1; ready=s;

} /*新进程的开始时间按最小，插在队首，并修改就绪队首ready指针*/ }

void create() {

PCB *p; int i;

ready=NULL; run=NULL; finish=NULL;

printf(\"Please enter the name and time and starttime of PCB:\\n\"); /*输入进程名、运行时间和开始时间*/

for(i=0;ip=(PCB *)malloc(sizeof(PCB)); /*为新进程开辟空间*/

专业知识分享

WORD格式可编辑

scanf(\"%s\输入进程名*/

scanf(\"%d\输入进程要求运行时间*/ scanf(\"%s\输入进程开始时间 p->cputime=0;

p->state='W'; /*表示就绪队列中未在队首先执行，但也是就绪状态*/ if (ready!=NULL)

insert(p); /*就绪队首不为NULL，插入新进程*/ else

{ /*否则先插在NULL前*/ p->next=ready; ready=p; } }

printf(\" Display is going to start: \\n\"); printf(\"***********************************************\\n\"); print(); getchar();

run=ready; /*队列排好，run指向就绪队列队首*/ ready=ready->next; /*ready指向下一个进程*/ run->state='R'; /*队首进程的状态为就绪*/ }

void FCFS() {

while(run != NULL) {

run->cputime=run->cputime+run->needtime; run->needtime=0; run->next=finish; finish = run; run->state='E'; run = NULL;

if(ready != NULL) {

run = ready; run->state='R'; ready=ready->next; }

print(); } }

void main() {

printf(\"Please enter the total number of PCB:\\n\"); scanf(\"%d\

专业知识分享

WORD格式可编辑

create(); /*模拟创建进程，并输入相关信息*/ FCFS(); /*先来先服务调度算法*/ }

2.1.4．测试结果及说明

首先输入进程个数（为5个），这里命名为A,B,C,D,E，然后分别输入运行时间和开始时间

所有进程都在队列中，并都处于等待状态

其中一个进程执行完毕

所有进程都执行完毕

2.2．优先级调度

2.2.1．算法思想

进程的执行顺序由高优先级到低优先级，系统或用户按某种原则为进程指定

专业知识分享

WORD格式可编辑

一个优先级来表示该进程所享有的确调度优先权。该算法核心是确定进程的优先级。

2.2.2．算法流程图

图2.优先级调度流程图

2.2.3．程序代码

#include #include #include typedef struct node

{ char name[10]; /*进程名*/ int prio; /*优先数*/

int cputime; /*占用cpu时间*/ int needtime; /*要求运行时间*/ char state; /*状态*/ struct node *next; /*指针*/ }PCB;

PCB *ready,*run,*finish; /*就绪 执行 结束指针*/ int N;

void prt() /*输出函数，可以方便看到进程执行的演示*/ {

PCB *p;

printf(\" NAME CPUTIME NEEDTIME PRIORITY STATUS\\n\");

专业知识分享

WORD格式可编辑

if(run!=NULL)

printf(\" %-10s%-10d%-10d%-10d %c\\nime,run->prio,run->state); /*输出执行的进程的信息*/ p=ready;

while(p!=NULL)

{printf(\" %-10s%-10d%-10d%-10d %c\\n\p->prio,p->state); /*输出就绪进程的信息*/ p=p->next; } p=finish; while(p!=NULL)

{ printf(\" %-10s%-10d%-10d%-10d %c\\n\e,p->prio,p->state); /*输出结束队列的信息*/ p=p->next; }

getchar(); } /*使用getchar()函数可以让输出时停留画面，等待人按回车继续*/

void insert(PCB *q) /*插入新进程，把进程按优先数大小排序*/ { PCB *p1,*s,*r; int b;

s=q; /*指针s指向新要插入的进程*/

p1=ready; /*指针p1指向原来的进程队列的队首*/ r=p1; /*使用指针r是指向p1前面的进程*/ b=1;

while((p1!=NULL)&&b)

if(p1->prio>=s->prio) { r=p1; p1=p1->next; } /*新进程的优先数小，则p1 指向下一个进程继续比*/

else b=0;

if(r!=p1) { r->next=s; s->next=p1; } /*新进程找到位置，插在r和p1之间*/

else { s->next=p1; ready=s; } } /*新进程的优先数最大，插在队首，并

修改就绪队首ready指针*/

void create() { PCB *p; int i;

ready=NULL; run=NULL; finish=NULL;

printf(\"Please enter the name and time and priority of PCB:\\n\"); /*输入进程名、运行时间和优先级*/

for(i=0;i{ p=(PCB *)malloc(sizeof(PCB)); /*为新进程开辟空间*/ scanf(\"%s\输入进程名*/

专业知识分享

WORD格式可编辑

scanf(\"%d\输入进程要求运行时间*/ scanf(\"%d\输入进程优先数*/ p->cputime=0;

p->state='W'; /*表示就绪队列中未在队首先执行，但也是就绪状态*/

if (ready!=NULL) insert(p); /*就绪队首不为NULL，插入新进程*/

else { p->next=ready; ready=p; } } /*否则先插在NULL前*/ printf(\" Display is going to start: \\n\"); printf(\"***********************************************\\n\"); prt();

run=ready; /*队列排好，run指向就绪队列队首*/

ready=ready->next; /*ready指向下一个进程，这样当进程执行时如果优先数小于其他的进程，应该先进行优先数最大的进程*/ run->state='R'; } /*队首进程的状态为就绪*/ void prio()

{ while(run!=NULL)

{ run->cputime=run->cputime+1; /*运行一次cpu占用时间加一*/ run->needtime=run->needtime-1; /*运行一次要求运行时间减一*/ run->prio=run->prio-1; /*运行一次优先数减一*/ if(run->needtime==0) /*若要求运行时间为0时*/ { run->next=finish; /*退出队列*/

finish=run; /*finish为结束进程的队列 */ run->state='E'; /*修改状态为结束*/ run=NULL; /*释放run指针*/

if (ready!=NULL) /*创建新就绪队列的头指针*/ { run=ready; run->state='R'; ready=ready->next; } } else

if((ready!=NULL)&&(run->prioprio))

/*队首进程的优先数比它下一个小，且下一个进程不为NULL时执行*/ { run->state='W';

run->next=NULL; /*队首进程退出进程队列*/

insert(run); /*在进程队列中重新插入原来的队首进程*/ run=ready; /*重新置就绪队列的头指针*/ run->state='R';

ready=ready->next; } prt(); } } void main()

{ printf(\"Please enter the total number of PCB:\\n\"); scanf(\"%d\

create(); /*模拟创建进程，并输入相关信息*/ prio(); } /*优先数调度算法*/

专业知识分享

WORD格式可编辑

2.2.4．测试结果及说明

优先级调度算法运行情况如图1，图2，图3，图4所示

图1.输入进程块的数量

图2.输入每个进程的名称、时间、优先级

图3.输入所有的进程的相关信息

专业知识分享

WORD格式可编辑

图4.所有进程调度算法完成

2.3．时间片轮转调度 2.3.1．算法思想

所有就绪进程按先来先服务的原则排成一个队列，将新来的进程加到就绪对列的末尾，每当执行进程调度时，总是把处理机分配给队首的进程，各进程占用CPU的时间片相同。也就是说CPU的处理时间划分成一个个相同的时间片，就绪队列的所有进程轮流运行一个时间片。当一个时间片结束时，如果运行进程用完它的时间片后还未完成，就强迫运行进程让出CPU，就把它送回到就绪队列的末尾，等待下一次调度。同时，进程调度又去选择就绪队列中的队首进程，分配给它一时间片，以投入运行。直至所有的进程运行完毕。

2.3.2．算法流程图

专业知识分享

WORD格式可编辑

2.3.3．程序代码

#include #include #include typedef struct node { char name[10]; /*进程名*/

int count; /*计数器，判断是否=时间片的大小*/ int cputime; /*占用cpu时间*/ int needtime; /*要求运行时间*/ char state; /*状态*/ struct node *next; /*指针*/ }PCB;

PCB *ready,*run,*finish,*tail; /*就绪 执行 结束 尾指针*/ int N,round;

void prt() /*输出函数，可以方便看到进程执行的演示*/ { PCB *p;

printf(\" NAME CPUTIME NEEDTIME STATUS\\n\"); if(run!=NULL)

专业知识分享

WORD格式可编辑

printf(\" %-10s%-10d%-10d %c\\n\needtime,run->state); /*输出执行的进程的信息*/ p=ready;

while(p!=NULL) { printf(\" %-10s%-10d%-10d %c\\n\me,p->state); /*输出就绪进程的信息*/ p=p->next; } p=finish; while(p!=NULL) { printf(\" %-10s%-10d%-10d %c\\n\me,p->state); /*输出结束队列的信息*/ p=p->next; } getchar(); }

void insert(PCB *q) /*在队尾插入新的进程*/ { PCB *p; p=ready; while(p->next!=NULL) { p=ready->next; } tail=p; tail->next=q; q->next=NULL; }

void create() { PCB *p; int i; ready=NULL; run=NULL; finish=NULL; printf(\"Please enter the name and time of PCB:\\n\"); /*输入进程名、和*/ for(i=0;i专业知识分享

WORD格式可编辑

scanf(\"%d\输入进程要求运行时间*/ p->cputime=0;

p->state='W'; /*表示就绪队列中未在队首先执行，但也是就绪状态*/ if (ready!=NULL) insert(p); /*就绪队首不为NULL，插入新进程*/ else { p->next=ready; ready=p; tail=p; } }

printf(\" Display is going to start: \\n\"); printf(\"***********************************************\\n\"); prt(); getchar();

run=ready; /*队列排好，run指向就绪队列队首*/ ready=ready->next; /*ready指向下一个进程*/ run->state='R';

} /*队首进程的状态为就绪*/ void count() { while(run!=NULL) { run->cputime=run->cputime+1; /*运行一次cpu占用时间加一*/ run->needtime=run->needtime-1; /*运行一次要求运行时间减一*/ run->count=run->count+1; /*运行一次计数器加一*/ if(run->needtime==0) /*若要求运行时间为0时*/ { run->next=finish; /*退出队列*/ finish=run; /*finish为结束进程的队列 */ run->state='E'; /*修改状态为结束*/ run=NULL; /*释放run指针*/ if (ready!=NULL) /*创建新就绪队列的头指针*/ { run=ready; run->state='R'; ready=ready->next; } } else if(run->count==round) /*如果时间片到*/ { run->count=0; /*计数器置0*/ if(ready!=NULL) /*如就绪队列不空*/ { run->state='W'; insert(run); /*在进程队列中重新插入原来进程,

专业知识分享

WORD格式可编辑

插入队尾*/ }

void main() { }

}

run=ready; /*重新置就绪队列的头指针*/ run->state='R';

ready=ready->next; } }

prt();

printf(\"Please enter the total number of PCB:\\n\"); scanf(\"%d\

create(); /*模拟创建进程，并输入相关信息*/ count(); /*优先数调度算法*/

2.3.4．测试结果及说明

时间片轮转调度算法运行情况如图1，图2，图3所示

图1 所有的进程都在队列中

图2 其中一个进程执行完毕

专业知识分享

WORD格式可编辑

图4 所有的进程都执行完毕

2.4．多级反馈队列调度 2.4.1算法思想

允许进程在队列之间移动。在系统中设置多个就绪队列，每个队列对应一个优先级，第一个队列的优先级最高，第二队列次之。以下各队列的优先级逐步低。各就绪队列中的进程的运行时间片不同，高优先级队列的时间片小，低优先级队列的时间片大。进程并非总是固定在某一队列中，新进程进入系统后，被存放在第一个队列的末尾。如果某个进程在规定的时间片内没有完成工作，则把它转入到下一个队列的末尾，直至进入最后一个队列。系统先运行第一个队列中的进程。当第一队列为空时，才运行第二个队列中的进程。依此类推，仅当前面所有的队列都为空时，才运行最后一个队列中的进程。当处理器正在第i个队列中为某个进程服务时，又有新进程进入优先级最高的队列（第1—（i-1）中的任何一个对列），则此新进程要抢占正在运行进程的处理器，即由调度程序把正在运行的进程放回第i队列的末尾，把处理器分配给新到的高优先级进程。除最低优先权队列外的所有其他队列，均采用相同的进程调度算法，即按时间片轮转的FIFO（先进先出）算法。最后一个队列中的进程按按时间片轮转或FCFS策略进行调度。它是综合了FIFO、RR和剥夺式HPF的一种进程调度算法。

专业知识分享

WORD格式可编辑

2.4.2算法流程图

2.4.3程序代码

#include #include #include #define NULL 0

typedef struct node {

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

int num; /*进程所在队列数,也是该队列的时间片*/ int cputime; /*占用cpu时间*/ int needtime; /*要求运行时间*/ struct node *next; /*指针*/ }PCB;

PCB *qf1,*ql1; PCB *qf2,*ql2;

PCB *qf3,*ql3;//定义三个队列的头指针和尾指针

专业知识分享

WORD格式可编辑

int blog1,blog2,blog3; /*分别记录队列1,、队列2、队列3中进程数*/

void insert(PCB *q,PCB *qf,PCB *ql) {

q->num++;

if(qf==NULL&&ql==NULL) { //队列为空 qf=ql=q; } else

{//队列不为空 ql->next=q; ql=q; }

ql->next=NULL; }

void create(int n)

{//创建进程，刚来的进程都进入队列1 PCB *p;

p=(PCB *)malloc(sizeof(PCB)); int i;

blog1=blog2=blog3=0; //各队列中进程数均为0

printf(\"Please enter the name and needtime of PCB:\\n\"); /*输入进程名和所需时间*/

for(i=0;i//p=(PCB *)malloc(sizeof(PCB)); /*为新进程开辟空间*/ scanf(\"%s\输入进程名*/

scanf(\"%d\输入进程要求运行时间*/ p->cputime=0; p->num=0;

insert(p,qf1,ql1);

blog1++; //队列中进程数加1 } }

int run(PCB *q,PCB *qf,PCB *ql) {

PCB *p,*f,*l;

/*p=(PCB *)malloc(sizeof(PCB)); f=(PCB *)malloc(sizeof(PCB)); l=(PCB *)malloc(sizeof(PCB));*/

专业知识分享

WORD格式可编辑

p=q; f=qf; l=ql;

if(q->needtime<=q->num) /*在时间片内完成*/ {

//q->cputime+=q->needtime; q->needtime=0; free(q); return 0; }

else /*不能在时间片内完成*/ {

//q->cputime+=q->num; q->needtime-=q->num; if(q->num<3) q->num++;

insert(p,f,l); //进入下一个队列 return 1; } }

void prt() /*输出函数，可以方便看到进程执行的演示*/ {

PCB *p;

//p=(PCB *)malloc(sizeof(PCB)); int a;

printf(\" NAME CPUTIME NEEDTIME STATUS\\n\"); while(blog1>0||blog2>0||blog3>0) {

if(blog1>0) /*第一个队列不为空*/ {

p=qf1;

qf1=qf1->next; p->next=NULL; blog1--;

printf(\" %-10s%-10d%\\n\ a=run(p,qf2,ql2); if(a==1) blog2++;

}

else if(blog2>0) /*第二个队列不为空*/ {

专业知识分享

WORD格式可编辑

p=qf2;

qf2=qf2->next;p->next=NULL; blog2--;

printf(\" %-10s%-10d%\\n\ a=run(p,qf3,ql3); if(a==1) blog3++; }

else if(blog3>0) /*第三个队列不为空*/ {

p=qf3;

qf3=qf3->next;p->next=NULL; blog3--;

printf(\" %-10s%-10d%\\n\ a=run(p,qf3,ql3); if(a==1) blog3++; } }

} /*使用getchar()函数可以让输出时停留画面，等待人按回车继续*/ void main() {

qf1=ql1=(PCB *)malloc(sizeof(PCB)); qf2=ql2=(PCB *)malloc(sizeof(PCB)); qf2=ql2=(PCB *)malloc(sizeof(PCB)); int n;

blog1=blog2=blog3=0;

printf(\"请输入进程的个数: \"); scanf(\"%d\ create(n); prt(); }

2.4.4测试结果及说明

专业知识分享

WORD格式可编辑

2.5．短作业调度

2.5.1．算法思想

短作业优先调度算法是指对短作业进行调度的算法。它从后备队列总选择一个或若干

个运行时间最短的作业，将他们调入内存运行。

2.5.2．算法流程图：

开始 输入进程名 就绪队列空? Y 结束 N 按时间服务进行排序 执行程序 短作业优先算法流程图

2.5.3．程序代码

#include #include #include

专业知识分享

WORD格式可编辑

typedef struct node {

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

int cputime; /*占用cpu时间*/ int needtime; /*要求运行时间*/ char state; /*状态*/ struct node *next; /*指针*/ }PCB;

PCB *ready, *run, *finish; //就绪、执行、结束指针 int N; //进程数量

void print() //输出函数 {

PCB *p;

printf(\" NAME CPUTIME NEEDTIME STATUS\\n\"); if(run != NULL)

printf(\" %-10s%-10d%-10d %c\\n\ run->name, run->cputime, run->needtime,

run->state); /*输出执行的进程的信息*/ p=ready;

while(p != NULL) {

printf(\" %-10s%-10d%-10d %c\\n\ p->name, p->cputime, p->needtime,

p->state); /*输出就绪进程的信息*/ p=p->next; }

p=finish;

while(p != NULL) {

printf(\" %-10s%-10d%-10d %c\\n\ p->name, p->cputime, p->needtime,

p->state); /*输出结束队列的信息*/ p=p->next; }

getchar(); /*使用getchar()函数可以让输出时停留画面， 等待人按回车继续*/ }

void insert(PCB *q) /*插入新进程，把进程按进程到来时间大小排序*/

专业知识分享

WORD格式可编辑

{

PCB *p1,*s,*r; int b;

s=q; /*指针s指向新要插入的进程*/

p1=ready; /*指针p1指向原来的进程队列的队首*/ r=p1; /*使用指针r是指向p1前面的进程*/ b=1;

while((p1!=NULL)&&b)

if(p1->needtimeneedtime) {

r=p1; p1=p1->next;

} /*新进程的开始时间大，则p1 指向下一个进程继续比*/ else

b=0; if(r!=p1) {

r->next=s; s->next=p1;

} /*新进程找到位置，插在r和p1之间*/ else {

s->next=p1; ready=s;

} /*新进程的开始时间按最小，插在队首，并修改就绪队首ready指针*/ }

void create() {

PCB *p; int i;

ready=NULL; run=NULL; finish=NULL;

printf(\"Please enter the name and time of PCB:\\n\"); /*输入进程名、运行时间和开始时间*/

for(i=0;ip=(PCB *)malloc(sizeof(PCB)); /*为新进程开辟空间*/ scanf(\"%s\输入进程名*/

scanf(\"%d\输入进程要求运行时间*/ p->cputime=0;

p->state='W'; /*表示就绪队列中未在队首先执行，但也是就绪状态*/ if (ready!=NULL)

insert(p); /*就绪队首不为NULL，插入新进程*/ else

{ /*否则先插在NULL前*/ p->next=ready;

专业知识分享

WORD格式可编辑

ready=p; } }

printf(\" Display is going to start: \\n\"); printf(\"***********************************************\\n\"); print(); getchar();

run=ready; /*队列排好，run指向就绪队列队首*/ ready=ready->next; /*ready指向下一个进程*/ run->state='R'; /*队首进程的状态为就绪*/ }

void SJF() {

while(run != NULL) {

run->cputime=run->cputime+run->needtime; run->needtime=0; run->next=finish; finish = run; run->state='E'; run = NULL;

if(ready != NULL) {

run = ready; run->state='R'; ready=ready->next; }

print(); } }

void main() {

printf(\"Please enter the total number of PCB:\\n\"); scanf(\"%d\

create(); /*模拟创建进程，并输入相关信息*/ SJF(); /*短作业优先调度算法*/ }

2.5.4．测试结果截图及操作说明

首先输入2个控制进程快，分别命名s1和s2 ，并且时间分别是2和5.短作业优先调度算法运行情况如4-7到4-9所示

专业知识分享

WORD格式可编辑

。

图4-7所有作业都在队列中，并都处于等待状态

图4-8其中一个作业执行完毕

图4-9所有进程执行完毕

三．测试分析

1.先来先服务算法比较有利于长作业（进程），而不利于短作业（进程）。因为短作业运

专业知识分享

WORD格式可编辑

行时间很短，如果让它等待较长时间才得到服务，那么，它的带权周转时间就会很高；先来先服务调度算法有利于CPU繁忙型的作业，不利于I/O繁忙型的作业，而目前大多数事务处理都属于I/O繁忙型作业。

2.短作业优先调度算法能有效地降低作业的平均等待时间，提高系统吞吐量。然而该算法对长作业不利，因为调度程序总是优先调度那些短作业，将导致长作业长期不被调度，该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业会被及时处理，由于作业的长短只是根据用户提供的估计执行时间而定的，而用户又可能有意无意地缩短其作业的估计运行时间，致使该算法不能真正做到短作业优先调度；

3.优先级调度算法则保证了紧迫进程，而那些优先级较低的则可能长时间得不到调度；静态优先级调度算法简单易行，系统开销小，但是不太灵活，很可能出现低优先级的作业，长期得不到调度而等待的情况；静态优先级法仅适合于实现要求不太高的系统。动态优先级调度算法比较灵活科学，可防止有一些进程一直得不到调度，也可防止有些进程长期垄断处理机，但是需要花费相当多的执行程序时间，因而花费的系统开销比较大。

4.时间片轮转算法则算是对每个进程都是公平的，减少了进程的等待时间，但是时间片设得太短会导致过多的进程切换，降低了CPU效率；而设得太长又可能引起对短的交互请求的响应变差。将时间片设为100毫秒通常是一个比较合理的折衷 ；

5.多级反馈队列调度算法则是综合先来先服务，短作业优先，时间片轮转和优先级调度算法的优点，故多级反馈队列调度对大多数进程调度来说是一种最佳的调度算法，但具体算法则应根据实际需求选择。

专业知识分享