作业调度算法(先来先服务算法,短作业算法)

《振作系统》卖脸报告

题目:作业调度算法

班级:网络工程

姓名:朱锦涛

学号:E31314037

一、实验目的

用代码实现页面调度算法,即先来先服务（FCFS调度算法

、短作业优先算法、高响应比优先调度算法。通过代码的具体实现,

加深对算法的核心的理解。

二、实验原理

1.先来先服务（FCFS调度算法

FCFS是最简单的调度算法，该算法既可用于作业调度，也可用于进

程调度。当在作业调度中采用该算法时,系统将按照作业到达的先后

次序来进行调度，或者说它是优先考虑在系统中等待时间最长的作业,

而不管该作业所需执行的时间的长短，从后备作业队列中选择几个最

先进入该队列的作业，将它们调入内存，为它们分配资源和创建进程。

然后把它放入就绪队列。

2.短作业优先算法

SJF算法是以作业的长短来计算优先级，作业越短，其优先级越高。

作业的长短是以作业所要求的运行时间来衡量的。SJF算法可以分别

用于作业和进程调度。在把短作业优先调度算法用于作业调度时，它

将从外存的作业后备队列中选择若干个估计运行时间最短的作业，优

先将它们调入内存。

3、高响应比优先调度算法

高响应比优先调度算法则是既考虑了作业的等待时间，又考虑了作业

的运行时间的算法，因此既照顾了短作业，又不致使长作业等待的时

间过长，从而改善了处理机调度的性能。

如果我们引入一个动态优先级，即优先级是可以改变的令它随等待的

时间的延长而增加,这将使长作业的优先级在等待期间不断地增加，

等到足够的时间后，必然有机会获得处理机。该优先级的变化规律可

以描述为：

优先权=（等待时间+要求服务时间/要求服务时间

三、实验内容

源程序:

#include<stdio.h>

#include<stdlib.h>

#include<time.h>

structwork

(

intid；

intarrive_time；

intwork_time；

intwait；

floatpriority；

);

typedefstructsjf_work

(

structworks_work；〃数据域

structsjf_work*pNext；〃指针域

}NODE,*PNODE；

voidFCFSO；

voidSJFO；

voidshowmenuO；

boolIs_empty<PN0DEpHead>；

intcnt_work<PNODEpHead>；

PNODEdo_work<PNODEpHead,int*w_finish_time,inti>；

voidshow<int*w_finish_time,inti,PNODEq,int

*w_rel_time>；

voidHRRNO；

PNODEpriorit<PNODEpHead>；

voiddo_work_l<PN0DEpHead,int*w_finish_time,inti>；

intmainO

(

intchoice；〃设置选择数

showmenuO；〃显示菜单

scanf<n%d",&choice>；

while<choice!=0>〃选择算法

switch<choice>

case1：

printf＜"您选择的是先来先服务算法:\n"＞；

FCFSO；

break；

case2：

printf＜"您选择的是短作业优先算法:\n"＞；

SJFO；

break；

case3：

printf＜"您选择的是高响应比优先调度算法\n"＞；

HRRNO；

break；

default：

printf〈"请重新选择！"＞；

break；

)

printf＜M\n"＞；

printf＜"下面是菜单，请继续,或者按‘0'退出"＞；

showmenuO；

scanf＜"%d”,&choice＞；

}

printf〈"感谢您使用本系统,再见！"＞；

return0；

)

voidFCFSO

(

intj,k；

intw_rel_time[5]；

intw_finish_time[5]；

floatrel_time=0；

structworktemp；

inti；

structworkw[5]；

srand<time<0»；

for<i=0；i<5；i++>

(

w[i].id=rand<>%10；

w[i].arrive_time=rand<>%10；

w[i].work_time=rand<>%10+l；

)

for<j=0；j<5；j++>

(

printf<"第%d个作业的编号是：%d\t",j+l,w[j].id>；

printf<"第%d个作业到达时

问:%d\t",j+l,w[j].arrive_time>；

printf〈”第％d个作业服务时

间：%d\t",j+l,w[j].work_time>；

printf<',\nn>；

)

for<j=l；j<5；j++>

for<k=0；k<5-j；k++>

(

if<w[k].arrive_time>wEk+1].arrive_time>

{

temp=wEk]；

w[k]=w[k+l]；

w[k+l]=temp；

)

)

printf<"\n">；

w_finish_time[O]=wEO].arrive_time+

w[0Lwork_time；

for<j=0；j<5；j++>

if<w_finish_time[j]<w[j+l].arrive_time>

w_finish_time[j+l]=w[j+l].arrive_time+

w[j+l].work_time；

)

else

w_finish_time[j+l]=w_finish_time[j]+

w[j+l].work_time；

}

for<j=0；j<5；j++>

w_rel_time[j]=w_finish_time[j]-

w[j].arrive_time；

for<j=0；j<5；j++>

(

rel_time+=w_rel_time[j]；

)

for<j=0；j<5；j++>

(

printf<"第%d个系统执行的作业到达时间：%d

j+l,w[j].arrive_time>；

printf〈"编号是：%dn,w[j].id>；

printf〈"服务时间是：%dn,w[jLwork_time>；

printf<"完成时间是:%d",w_finish_time[j]>；

printf〈"周转时间是：%dn,w_rel_time[j]>；

printf<n\n">；

}

printf<"平均周转时间：%f\n",rel_time/5>；

)

voidSJFO

(

intw_rel_time[10]；

intw_finish_time[10]；

floatrel_time=0；

srand<time<0»；

inti；

intj=0；

PNODEpHead=<PN0DE>malloc<sizeof<N0DE»；

if<NULL==pHead>

printf<"分配失败，程序终止!\n">；

exit<-l>；

)

PNODEpTail=pHead；

pTail->pNext=NULL；〃定义该链表有头结点，且第一个节点

初始化为空

for<i=0；i<10；i++>

(

PNODEpNew=<PNODE>malloc<sizeof<NODE»；

if<NULL==pNew>

(

printf〈"分配失败，程序终止!\n">；

exit<-l>；

)

pNew->s_work.id=rand<>%100；

pNew->s_work.arrive_time=rand<>%10；

pNew->s_work.work_time=rand<>%10+l；

pTail->pNext=pNew；

pNew->pNext=NULL；

pTail=pNew；

}

PNODEp=pHead->pNext；〃p指向第一个节点

while<NULL!=p>

(

printf<"第％d个作业的编号是：%d\t",j+1,p->s_work.id>；

printf<"第％d个作业到达时

间：%d\tn,j+1,p->s_work.arrive_time>；

printf<"第%d个作业服务时

间：％d\t",j+1,p->s_work.work_time>；

printf<l,\nn>；

p=p->pNext；

printf<',\nff>；

j++;

p=pHead->pNext；

PNODEq=p；〃p,q都指向第一个节点

p=p->pNext；

while<p!=NULL>

(

if<p->s_work.arrive_time<q->s_work.arrive_time>

q=P；

p=p->pNext；

)

PNODEr=pHead->pNext；〃r也指向第一个节点

intent=0；〃记录所有节点数据域中到达时间最短且相等的

个数

while<r!=NULL>

if<r->s_work.arrive_time==q->s_work.arrive_time>

cnt++；

r=r->pNext；

)

p=pHead->pNext；

while<p!=NULL>〃在相等到达时间的作业中找服务时间最

短的作业

(

if<cnt>1>

{

if<p->s_work.arrive_time==

q->s_work.arrive_time>

if<p->s_work.work_time<q->s_work.work_time>

q=p；

p=p->pNext；

}

else

p=NULL；

}〃确定q所指作业最先到达且服务时间最短

w_finish_timeEO]=q->s_work.arrive_time+

q->s_work.work_time；

w_rel_time[O]=w_finish_time[01-

q->s_work.arrive_time；

printf<"第1个系统执行的作业到达时间：%d

n,q->s_work.arrive_time>；

printf<"编号是：%dn,q->s_work.id>；

printf<"服务时间是：%d\nn,q->s_work.work_time>；

printf<"完成时间是：%d",w_finish_time[0]>；

printf〈"周转时间是：%d\n",w_rel_time[0]>；

p=pHead;〃寻找q的前一个节点，方便删掉q节点

while<p->pNext!=q>

(

p=p->pNext；

)

p->pNext=q->pNext；

free<q>；

q=NULL；

for<i=0；i<9&&!Is_empty<pHead>；i++>

(

printf<"现在系统还剩％(1个作业！\n",cnt_work<pHead>>；

q=do_work<pHead,w_finish_time,i>；

show<w_finish_time,i,q,w_rel_time>；

p=pHead;〃寻找q的前一个节点，方便删掉q节点

while<p->pNext!=q>

(

p=p->pNext；

}

p->pNext=q->pNext；

free<q>；

q=NULL；

)

for<j=0；j<10；j++>

rel_time+=w_rel_time[j]；

)

printf<"平均周转时间:%f\n'*,rel_time/10>；

)

boolIs_empty<PN0DEpHead>〃判断作业是否做完

(

PNODEp；

p=pHead->pNext；

intlen=0；

while<p!=NULL>

(

len++；

p=p->pNext；

)

if<len==0>

returntrue；〃当没有作业时，返回为真

else

returnfalse；

)

intcnt_work<PNODEpHead>〃计算当前还剩多少作业

(

PNODEp；

p=pHead->pNext；

intlen=0；

while<p!=NULL>

(

len++；

p=p->pNext；

)

returnlen；

)

PNODEdo_work<PNODEpHead,int*w_finish_time,inti>

PNODEp,q；

intent=0；〃计数器清0,计算当前作业完成时，系统中有

多少个作业已经到达

p=pHead->pNext；

Q=P；

while<p!=NULL>

(

if<p->s_work.arrive_time<=w_finish_time[i]>

,{

ent++；

q=P；

p=p->pNext；

)

else

p=p->pNext；

}

}//q指向当前到达时间小于刚刚完成的作业，但不一定是

服务时间最短的<如果有的话》

printf<"系统中有%d个作业在当前作业完成时已经到达！

\n",cnt>；

p=pHead->pNext；

while<p!=NULL>

(

if<cnt>l>〃执行此次判断后,q现在指向所有条件都满足

的作业(如果有的话

(

if<p->s_work.arrive_time<=w_finish_time[i]>

(

if<p->s_work.work_time<q->s_work.work_time>

(

q=p；

p=p->pNext；

)

else

p=p->pNext；

)

else

p=p->pNext；

}

else〃当前作业完成时,没有作业到达的情况

p=p->pNext;〃用q来接收最先到达的，用p来遍历

while<p!=NULL>

(

if<p->s_work.arrive_time<

q->s_work.arrive_time>

q=P；

p=p->pNext；

)

w_finish_time[i+l]=q->s_work.arrive_time+

q->s_work.work_time；

)

w_finish_time[i+l]=w_finish_time[i]+

q->s_work.work_time；

returnq；

)

voidshow<int*w_finish_time,inti,PNODEq,int

*w_rel_time>

(

w_finish_timeEi+l]=w_finish_time[i]+

q->s_work.work_time；

w_rel_time[i+l]=w_finish_time[i+l]-

q->s_work.arrive_time；

printf〈"第%(1个系统执行的作业到达时间：%d

”,i+2,q->s_work.arrive_time>；

printf〈"编号是：%d°,q->s_work.id>；

printf〈”服务时间是：%d\nn,q->s_work.work_time>；

printf〈”完成时间是：%dn,w_finish_time[i+l]>；

printf〈"周转时间是：%d\n",w_rel_time[i+l]＞；

)

voidshowmenuO

(

printf＜***********************************\n*＞；

printf＜"请选择你要执行的命令1\n"＞；

printf＜"l：先来先服务算法\n"＞；

printf＜n2：短作业优先算法\n"＞；

printf＜"3：高响应比优先算法\n"＞；

printf＜"0：退出菜单\n"＞；

printf＜***********************************\n”＞；

)

voidHRRNO

(

intw_rel_time[10]；

intw_finish_time[10]；

floatreltime=0：

floatpriority；〃计算优先权

srand<time<0»；

inti；

intj=0；

PNODEpHead=<PNODE>malloc<sizeof<NODE»；

if<NULL==pHead>

（

printf<"分配失败，程序终止!\n">；

exit<-l>；

）

PNODEpTail=pHead；

pTail->pNext=NULL；〃定义该链表有头结点，且第一个节点

初始化为空

for<i=0；i<10；i++>〃定义了十个进程

{

PNODEpNew=<PNODE>malloc<sizeof<NODE»；

if<NULL==pNew>

printf<"分配失败，程序终止!\n">；

exit<-l>；

)

pNew->s_work.id=rand<>%100；

pNew->s_work.arrive_time=rand<>%10；

pNew->s_work.work_time=rand<>%10+l；

pTail->pNext=pNew；

pNew->pNext=NULL；

pTail=pNew；

)

PNODEp=pHead->pNext；〃p指向第一个节点

while<NULL!=p>

(

printf〈"第％d个作业的编号是：%d\tn,j+1,p->s_work.id>；

printf<"第％d个作业到达时

间：%d\t",j+1,p->s_work.arrive_time>；

printf〈"第刎个作业服务时

间：%d\t",j+l,p->s_work.work_time>；

printf<',\nn>；

p=p->pNext；

printf<w\n">；

j++；

)

p=pHead->pNext；

PNODEq=p；〃p,q都指向第一个节点

p=p->pNext；

while<p!=NULL>

(

if<p->s_work.arrive_time<q->s_work.arrive_time>

q=P；

p=p->pNext；

)

PNODEr=pHead->pNext；〃r也指向第一个节点

intent=0；〃记录所有节点数据域中到达时间最短且相等的

个数

while<r!=NULL>

(

if<r->s_work.arrive_time==q->s_work.arrive_time>

cnt++；

r=r->pNext；

)

p=pHead->pNext；

while<p!=NULL>〃在相等到达时间的作业中找服务时间最

短的作业

(

if<cnt>1>

(

if<p->s_work.arrive_time=-

q->s_work.arrive_time>

if<p->s_work.work_time<q->s_work.work_time>

q=P；

p=p->pNext；

)

else

p=NULL；

}〃确定q所指作业最先到达且服务时间最短

w_finish_time[0]=q->s_work.arrive_time+

q->s_work.work_time；

w_rel_time[O]=w_finish_time[01-

q->s_work.arrive_time；

printf〈"第1个系统执行的作业到达时间：%d

",q->s_work.arrive_time>；

printf<"编号是：%dn,q->s_work.id>；

printf<"服务时间是：%d\n",q->s_work.work_time>；

printf〈”完成时间是：%dn,w_finish_time[0]>；

printf<"周转时间是：%d\n",w_rel_time[0]>；

p=pHead;〃寻找q的前一个节点，方便删掉q节点

while<p->pNext!=q>

p=p->pNext；

p->pNext=q->pNext；

free<q>；

q=NULL;〃已经找到并执行第一个进程，执行完之后又将其

删除了

for<i=0；i<9&&!Is_empty<pHead>；i++>

(

printf<"现在系统还剩％(1个作业！\n",cnt_work<pHead>>；

do_work_l<pHead,w_finish_time,i>；

q=priorit<pHead>；

show<w_finish_time,i,q,w_rel_time>；

p=pHead；〃寻找q的前一个节点，方便删掉q节点

while<p->pNext!=q>

p=p->pNext;

p->pNext=q->pNext；

free<q>；

q=NULL；

)

for<j=0；j<10；j++>

(

rel_time+=w_rel_time[j]；

)

printf<"平均周转时间:%f\n",rel_time/10>；

)

voiddo_work_l<PN0DEpHead,int*w_finish_time,inti>

(

PNODEp,q；

intent=0；〃计数器清0,计算当前作业完成时，系统中有

多少个作业已经到达

p=pHead->pNext;

q=P；

while<p!=NULL>

if<p->s_work.arrive_time<=w_finish_time[i]>

(

ent++；

q=P；

p=p->pNext；

)

else

(

p=p->pNext；

)

}〃q指向当前到达时间小于刚刚完成的作业，但有可能有

另外几个进程也已经到达了，所以要进行下面的判断

printf<"系统中有%d个作业在当前作业完成时已经到达！

\nB,cnt>；

p=pHead->pNext；

while<p!=NULL>

if<cnt>l>〃说明此时有好几个都已经到达了

(

if<p->s_work.arrive_time<=w_finish_time[i]>

{

p->s_work.wait=w_finish_time[i]-

p->s_work.arrive_time；

p=p->pNext；

)

else

(

p->s_work.wait=0；

p=p->pNext；

)

)

else〃当前作业完成时,没有作业到达的情况

p=p->pNext；〃此时p指向第一个节点,q