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

《操作曲疣》卖险想告

题目：作业调度算法

班级：网络工程

姓名：朱锦涛

学号：E31314037

一、实验目得

用代码实现页面调度算法，即先来先服务(FCFS)调度算

法

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

加深对算法得核心得理解.

二、实验原理

1、先来先服务(FCFS)调度算法

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

用于进程调度。当在作业调度中采用该算法时，系统将按照作业到达

得先后次序来进行调度，或者说它就是优先考虑在系统中等待时间最

长得作业，而不管该作业所需执行得时间得长短，从后备作业队列中

选择几个最先进入该队列得作业，将它们调入内存，为它们分配资源

与创建进程.然后把它放入就绪队列。

2、短作业优先算法

SJF算法就是以作业得长短来计算优先级，作业越短，其优先级

越高。作业得长短就是以作业所要求得运行时间来衡量得。SJF算

法可以分别用于作业与进程调度。在把短作业优先调度算法用于作业

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

得作业，优先将它们调入内存。

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

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

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

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

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

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

增加，等到足够得时间后，必然有机会获得处理机.该优先级得变化规

律可以描述为：

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

三、实验内容

源程序:

#inc1ude<stdio,h>

#include<stdlib、h>

#include<time>h>

structwork

{

»intid；

intarrive_time；

intwork_time；

intwait；

f1oatpriority；

);

typedefstructsjf_work

{

structworks_work；//数据域

ostructsjf_work*pNext；〃指针域

}NODE,*PNODE；

voidFCFS()；

voidSJF()；

voidshowmenu()；

boolIs_empty(PNODEpHead)；

intcnt_work(PNODEpHead)；

PNODEdo_work(PNODEpHead,int*w_finish_time,

inti)；

voidshow(int*w_finish_time,inti,PNODEq,

int*w_re；

voidHRRN()；

PNODEpriorit(PNODEpHead)；

voiddo_work_l(PNODEpHead,int*w_finish_ti

me,inti)；

intmain()

{

intchoice；//设置选择数

showmenu()；//显示菜单

oscanf("%d",&choice)；

owhile(choice!=0)〃选择算法

switch(choice)

1ocase1：

，printf("您选择得就是先来先服务算法：\n")；

1®&®FCFS()；

…break；

「case2：

printf("您选择得就是短作业优先算法：\n”)；

，SJF()；

1>break；

(ocase3：

，>>>printf("您选择得就是高响应比优先调度算法'

n”)；

…HRRN()；

1>break；

default：

ooprintf(”请重新选择!n)；

o»>break；

b}

»oprintf("\n")；

sprintf("下面就是菜单，请继续,或者按‘0'退出")；

oshowmenu()；

oscanf("%d”,&choice)；

。}

Bprintf("感谢您使用本系统，再见！”)；

return0；

)

voidFCFS()

{

&intj,k；

intw_re1_time⑸；

ointw_finish_time[5]；

floatrel_time=0；

structworktemp；

inti；

struetworkw[5]；

srand（time（0））；

for（i=0；i<5；i++）

3{

ow[i]、id=rand（）%10；

»w[i]、arrive_time=rand（）%10；

»w[iKwork_time=rand（）%10+l；

9}

for（j=0；j<5；j++）

{

…printf（"第%d个作业得编号就是：％d\t”,j+1,w[j]、

id）；

o»printf（"第%d个作业到达时间:%d\t”,j+l,w[j]、arrive

_time）；

66printf（“第％（1个作业服务时间：％d\t",j+1,w[j]、

work_time）；

printf("\n")；

}

3for(j=1；j<5；j++)

ofor(k=0；k<5-j；k++)

66{

oooif(w[k]、arrive_time>w[k+1]、arriv

e_time)

3{

。otemp=w[k]；

sw[k]=wLk+11；

»w[k+l]=temp；

od}

o}

oprintf(w\n")；

w_finish_time[0]=w[0]、arrive_time

+w[0]、work_time；

6ofor(j=0；j<5；j++)

oif（w_finish_timeEj]〈w[j+1]、arrive_time）

oow_finish_timeEj+1]=w[j+1]、arrive_time+

wEj+1]>work_time；

>}

oooeIse

ooow_finish_time[j+1]=w_finish_time[j]+

w[j+l]、work_time；

0}

6for（j=0；j<5；j++）

oow_rel_time[j]=w_finish_time[j]-w[j]、

arrive_time；

6for（j=0；j<5；j++）

，（

o3rel_time+=w_rel_timeEj]；

6for（j=0；j<5；j++）

printf(”第％(1个系统执行得作业到达时间：％d”

arrive_time)；

sprintf("编号就是：％d",w[j]、id)；

sprintf("服务时间就是：%d",w[j]>work_time)；

oooprintf("完成时间就是：％d",w_finish_time

LjD；

printf("周转时间就是：%d”,w_re1—time

EjD；

®»printf("\n")；

)

printf("平均周转时间：%f\n",re1_time/5)；

)

voidSJF()

{

intw_rel_time[10]；

»intw_finish_time[10]；

*f1oatre1time0；

srand(time(O))；

»inti；

ointj=0；

。PNODEpHead=(PNODE)mal1oc(sizeof(NODE))；

oif(NULL==pHead)

(

printf("分配失败,程序终止!\n")；

oexit(-1)；

}

PNODEpTai1=pHead；

spTail->pNext=NULL；〃定义该链表有头结点,

且第一个节点初始化为空

»for(i=0；i<10；i++)

。{

PNODEpNew=(PNODE)mal1oc(sizeof(NODE))；

if(NULL==pNew)

oooprintf("分配失败，程序终止!\n")；

»t>t>exit(-1)；

}

oopNew—>s_work、id=rand()%100；

，pNew->s_work^arrive_time=rand()%10；

opNew—>s_work,work_time=rand()%10+l；

opTai1—>pNext=pNew；

spNew->pNext=NULL；

»»pTai1=pNew；

}

PNODEp=pHead—〉pNext；//p指向第一个节点

owhile(NULL!=p)

>(

ooprintf("第％d个作业得编号就是：%d\t”,j+1,p—〉

s_work、id)；

printf(”第%(1个作业到达时间：%d\t",j+l,p—〉s_w

ork、arrive_time)；

ooprintf("第％d个作业服务时间：%d\t",j+l,p->s_wo

rk、work_time)；

ooprintf("\n")；

oop=p—>pNext；

»printf("\n")；

6j++;

。}

>p=pHead"—>pNext；

sPNODEq=p;〃p,q都指向第一个节点

p=p->pNext；

owhile(p!=NULL)

(

if(p—〉s_work、arrive_time〈q->s—work、

arrive_time)

q=P；

p=p—>pNext；

}

PNODErpHead—>pNext；//r也指向第一个节点

»intcnt=0；〃记录所有节点数据域中到达时间最

短且相等得个数

whi1e(r!=NULL)

9{

oif(r—>s_work、arrive_time==q-)s_work、

arrive_time)

&cnt++;

or=r->pNext；

}

>p=pHead-)pNext；

owhile(p!=NULL)//在相等到达时间得作业中找服

务时间最短得作业

(

oif(ent>1)

ddt

>if(p—〉s_work>arrive_time==q->s_work、

arrivetime)

ooif（p—>s_work>work_time〈q-）s_work>

work_time）

>q=P；

op=p->pNext；

}

else

ooop=NULL；

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

ow_finish_time[0]=q->s_work、arrive_time+q

—>s__work^work_time；

»w_re1_time[0]=w_finish_time[01—q—〉

s_work、arrive_time；

。printf（"第1个系统执行得作业到达时间：%d",q->

s_work、arrive_time）；

printf（w编号就是：%d”,q-〉s_work、id）；

printf（”服务时间就是:％d\n”，q—〉s_work>work_ti

me）；

printf（"完成时间就是：%d",w_finish_time[0]）；

printf(”周转时间就是：%d\n”,w_rel_time[0])；

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

while(p->pNext!=q)

o(

op=p->pNext；

}

op一〉pNext=q—>pNext；

free(q)；

。q=NULL；

ofor(i=0；i〈9&&!Is_empty(pHead)；i++)

>{

»printf("现在系统还剩%d个作业!\n",cnt_work(pHe

ad))；

ooq=do_work(pHead,w_finish_time,i)；

oshow(w_finish_time,i,q»w_rel—time)；

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

while(p—>pNext!=q)

op=p->pNext；

&&}

»p—〉pNext=q->pNext；

>free(q)；

oq=NULL；

。}

for(j=0；j<10；j++)

(

»re1_time+=w_rel_time[j]；

}

oprintf(”平均周转时间：％f\n",re/10)；

)

boolIs_empty(PNODEpHead)//判断作业就是否做

完

»PNODEp；

。p=pHead一＞pNext；

int1en=0；

while(p!=NULL)

(

，1en++；

®»p=p一＞pNext;

}

if(1en==0)

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

else

returnfalse；

}

intcnt_work(PNODEpHead)〃计算当前还剩多少作

业

(

PNODEp；

p=pHead-〉pNext；

intlen=0；

»whi1e(p!=NULL)

>(

o1en++；

>>p=p->pNext；

o}

return1en；

}

PNODEdo_work(PNODEpHead,int*w_fini

sh_time,inti)

(

oPNODEp,q；

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

中有多少个作业已经到达

p=pHead—>pNext；

q=p；

whi1e(p!=NULL)

if(p-〉s_work>arrive_time<=w_finish_time

Ei])

oocnt++；

q=p；

p=p->pNext；

3}

oe1se

bop=p->pNext；

&&)

。｝//q指向当前到达时间小于刚刚完成得作业,但不一

定就是服务时间最短得（如果有得话）

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

\n”,cnt)；

0p=pHead—〉pNext；

while(p!=NULL)

。if（ent〉1）//执行此次判断后，q现在指向所有条件都

满足得作业（如果有得话）

oif(p—>s_work^arrive_time<=w_finish_time

[i])

(

o>if(p->s_work、work—time〈q->s_work^wor

k_time)

(

9>q=p；

ooaop=p—〉pNext；

&&}

&&selse

sop=p-〉pNext；

60b}

ooelse

oop=p->pNext；

。else//当前作业完成时，没有作业到达得情况

。。p=p->pNext;//用q来接收最先到达得，用p来

遍历

owhile(p!=NULL)

dd{

ooif(p->s_work>arrive_time〈q->s_work>ar

rive_time)

…q=P；

»p=p->pNext；

3}

w_finish_timeLi+l]=q->s_work、arrive—tim

e+q—〉s_work、work_time；

bb}

o}

ow_finish_time[i+1]=w_finish_time[i]+q—>

s_work、work_time；

returnq；

）

voidshow（int*w_finish_time,inti,PNODEq,

int*w_rel_time）

{

»w_finish_time[i+1]=w_finish_time[i]+q

—）s_work、work_time；

»w_re1_time[i+l]=w_finish_time[i+l]-q->s_

work、arrive_time；

printf（"第％（1个系统执行得作业到达时间：%d",i+

2,q—>s_work、arrive_time）；

oprintf（”编号就是：%d",q—〉s_work、id）；

printf（"服务时间就是：％d\n",q—〉s_work、work_ti

me）；

printf（”完成时间就是：%d"，w_finish_tim

e[i+1]）;

printf（"周转时间就是：%d\n",w_rel_time[i+1]）；

）

voidshowmenu（）

printf（"*************************

*********\n"）；

。printf（"请选择您要执行得命令〜：\n"）;

printf（"1：先来先服务算法\n"）；

。printf（"2：短作业优先算法\n”）；

printf（”3：高响应比优先算法\n”）；

oprintf（"0：退出菜单""）；

printf（"****************************

******\n"）；

}

voidHRRN（）

（

»intw_re1_time[10]；

intw_finish_time[10];

floatreltime=0；

floatpriority；〃计算优先权

»srand(time(0))；

inti；

intj=0；

PNODEpHead=(PNODE)ma1loc(sizeof(NODE))；

if(NULL==pHead)

(

。printf("分配失败，程序终止!\n")；

»exit(—1)；

9}

oPNODEpTai1=pHead；

pTai1-)pNext=NULL；//定义该链表有头结点,

且第一个节点初始化为空

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

。{

o>PNODEpNew=(PNODE)ma1loc(sizeof(NODE))；

if(NULL==pNew)

。。printf("分配失败，程序终止!\n”)；

oexit(-1)；

3}

opNew—〉s_work>id=rand()%100；

»pNew—>s_work、arrive_time=rand()%10；

o»pNew—>s_work、work_time=rand()%10+1；

»pTail—>pNext=pNew；

opNew—>pNext=NULL；

»opTai1=pNew；

)

oPNODEp=pHead-)pNext；//p指向第一个节点

while(NULL!=p)

(

oprintf("第%d个作业得编号就是：%d\t”，j+l,p—>s_wo

rk、id)；

bprintf("第％(1个作业至U达时间：%d\t",j+l,—>S_W0

rk、arrive_time)；

oprintf("第%d个作业服务时间：%d\t",j1,p-)

s_work、work_time)；

oprintf("\n")；

op=p->pNext；

»»printf("\n")；

j++；

}

p=pHead—>pNext；

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

p=p-〉pNext；

»whi1e(p!=NULL)

0{

oif(p-)s_work、arrive_time<q一〉work、

arrive_time)

&q=P；

op=p—>pNext；

}

t>PNODEr=pHead—>pNext；〃1*也指向第一个

节点

，intent=0；//记录所有节点数据域中到达时间最

短且相等得个数

owhile(r!=NULL)

3{

if(r->s_work^arrive—time==q->s_work>arrive

—time)

cnt++；

r=r->pNext；

)

»p=pHead—>pNext；

，while(p!=NULL)//在相等到达时间得作业中找服

务时间最短得作业

,if(cnt)1)

ooif(p->s_work>arrive_time==q->s_work>

arrive_time)

o>oif(p->s_work>work_time<q->s_work>work_ti

me)

q=P；

»op=p->pNext；

3}

bselse

…p=NULL；

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

>w_finish_timeEO]=q->s_work、arrive_time+q-

>s_work、work_time；

»w_re1_time[0]=w_finish_time[0]-q—〉

s_work、arrive_time；

。printf("第1个系统执行得作业到达时间：%dn,q->

s_work>arrive—time)；

printf(”编号就是:%d",q—>s_work、id)；

printf("服务时间就是：%d\n",q->s_work>work_tim

e);

printf("完成时间就是：％d",w_finish_time[0])；

oprintf("周转时间就是：%d\n,w_rel_time[0])；

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

while(p—>pNext!=q)

3{

>>p=p->pNext；

)

op—>pNext=q—>pNext;

ofree(q)；

3q=NULL；〃已经找到并执行第一个进程，执行完之后

又将其删除了

ofor(i=0；i<9&&!Is—empty(pHead)；i++)

上

oprintf("现在系统还剩%d个作业！\n",cnt_wor

k(pHead))；

odo_work_1(pHead,w_finish_time,i)；

oq=priorit(pHead)；

»oshow(w_finish_time,i,q,w_rel_time)；

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

节点

»»whi1e(p—〉pNext!=q)

3{

op=p—〉pNext；

3}

p->pNext=q->pNext；

o>free(q)；

>q=NULL；

)

for(j=0；j<10；j++)

3{

orel_time+=w—rel_time[j]；

>}

printf(“平均周转时间：%f\n",re1—time/10)；

)

voiddo_work_l(PNODEpHead,int*w_finish_t

ime,inti)

(

PNODEp,q；

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

统中有多少个作业已经到达

p=pHead—>pNext；

q=P；

3whi1e(p!=NULL)

3{

ooif(p->s_work、arrive_time〈=w_finish

_timeEi])

o(

§。ent++；

…q=P；

p=p-)pNext;

else

p=p—〉pNext；

)

}//q指向当前到达时间小于刚刚完成得作业,但有可

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

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

n"，ent)；

p=pHead-)pNext；

§while(p!=NULL)

3{

if(cnt>l)//说明此时有好几个都已经到达了

。(

®if(p->s_work、arrive_time<=w_finish

_timeEi])

0{

op->s_work、wait=w_finish_time[i]一p

->s_work、arrive_time；

p=p—〉pNext；

sselse

od{

Osop->s_work>wait=0；

»»p=p->pNext；

6b}

3}

。else〃当前作业完成时，没有作业到达得情况

3{

。p=p->pNext；//此时p指向第一个节点，q指

向第二个节点，还就是找最先到达得

sbwhi1e(p!=NULL)

。(

ooif(p->s_work、arrive—time<q—〉s_work>

arrive_time)

oooq=p；

dpp->pNext；

)

w_finish_time[i+1]=q->s_work>arrive_time

+q->s_work>work—time；

oreturn；

3)

}

»w_finish_time[i+1]=w_finish_time[i]+

q->s_work、work_time；

)

PNODEpriorit(PNODEpHead)

PNODEp=pHead—〉pNext；

whi1e(p!=NULL)

if(p->s_work>wait〉0)

p->s_work>priority=(p—>s_work、wait+

p—>s_workwork_time)/p->s_work>work_time；

〃计算每一个已经等待得进程得优先等级

p=p—〉pNext；

»}

oe1se

op=p->pNext；

9}

p=pHead—>pNext；

oPNODEq；

>q=p；

p=p->pNext；//p已经指向第二个节点

»while(p!=NULL)

{

sif(p->s_work、wait>0)

。(

sot)if(p->s_work^priority>q->s_work^priori

ty)

dq=P；

t>bbbp=p->pNext；

&）

oelse

op=p—>pNext；

3}

oelse

ooop=p—>pNext；

}

6printf（"该进程优先级最高，为：%f\n",q—〉s_w

ork、priority）；

oreturnq；

}

实验结果：

系统自动为每个算法模拟分配五个作业，同时随机生成作业得

编号，作业得到达时间，作业估计运行得时间。

1、先来先服务算法

回

■1・E:\C语言练习\Debug\100L

▲一

***********************

-M--M--M--M-一

1

三

望

解

务

行

糊

n算法

R:

』

日

号

业

务

A业~f-

用

业m

2151二10

.6-sp-灯0

pA-二

否T.

业

号

务

业.

22二2

第.5g1pm-

业JB

pTap-J一

否.

业

号

务

.业-.

弟7-

833:^-pm-10

厅B

业Ta-

否.ap-p-

业

业

务

号

第

HA二-m-3

3424二^-

厅Tr

.•B

否

灯

业arap-.

业

p业

号

.务

第H-

15T05-nm8

Ar匚

厅1-

a-'灯

p二

AEap-

堂系统执行的作业到达时间：0编号是：工服务时间是:8完成时间是：8周转时

7争E系：8统执行的作业到达时间

11编号是：5服务时间是:2完成时间是：10周转时

辞或统执行的作业到达时间：2

编号是：3服务时间是:3完成时间是：13周转时

於养统执行的作业到达时间：

5编号是：2服务时间是:10完成时间是：23周转

|Bj#：18

售统执行的作业到达时间：

g7编号是：8服务时间是:10完成时间是：33周转

间是：26

均周转时间：14.400000

退出***™*™**™*

该算法严格按照各作业到达时间来为其分配进程与资源，实

验得结果见截图，最后算出该算法五个作业得平均周转时间。

2、短作业优先

短作业优先算法考虑得比较多，系统先找出最先到达得作业,

若有多个相同时间到达得作业，则按照其运行时间长短先为时间

短得服务。

T・E:\C语言练习\Debug\1001.exe-1=1回

手髓尤暨法嬴个作业到达时间:

1第1个作业服务时间:6

12第2个作业到达时间:第2个作业服务时间:4

26第3个作业到达时间:3第3个作业服务时间:4

83第4个作业到达时间:8第4个作业服务时间:1

19第5个作业到达时间:9第5个作业服务时间:7

第6个作业到达时间:1第6个作业服务时间:2

18第7个作业到达时间:8第7个作业服务时间:1

56第8个作业到达时间:4第8个作业服务时间:6

31第9个作业到达时间:7第9个作业服务时间:10

：84第10个作业到达时间：9第10个作业服务时间：4

卜系维执行的作业到达时间11编号是I46服务时间是：2

，时间鼠3周转时间息2

系统还乘19个作业！

蟠2个作业在当前隹业完成时已经至悭!

卜冢妹知才〒的花业到状日由扎3维号皂，264

,E:\C语言练习\Debug\1001.exe'I=1回

：84第个作业到达时间：9第10个作业服务时间：4

扁是

达瞿

的

业

号

盾

号

wT-HI司1

H:46服务时间是：2

间

转i

3S2

个

间

7E9业I

还

，

成

一

乍

业

北

业

时

当4

i即J

尚

一

间

的

业K9

—

图

丁3

间

h：26服务时间是：4

转i

7S■,4

个

^业I

7E87E

还,

成

时

幺

摩

魁

乍

当

已

^业f

一■

扁

由

有

业

的

丁5

丽

4','：

曾12服务时间是：4

间

11髀6

个

7业1

，

乍

当

7E业

还,

刖

间

一

业

M的

丁83服务时间是：1

盾

12会

个

W6业I

，

成

时

幺

乍

已

业

7E当^I

g还

一5■

扁

有

业

的

丁8

〉

^：18服务时间是：工

间

13患5

图.

个

^5当I

，

・

幺

乍

已

至

业

业□8Xn

^刖m

AE一M

还■

4三

扁

夺

莓

日

琳

的

丁M9

U84服务时间是：4

间

17业5^8

业^

由

落-

个

—

4一!

，

务

幺

北

乍

成

时

蟒

已

善

业'-4

刖

间

一