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

《振作系统》卖脸报告

题目：作业调度算法

班级：网络工程

姓名：朱锦涛

学号：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；〃指针域

}N0DE,*PN0DE；

voidFCFSO；

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_rel_time)；

voidHRRNO；

PNODEpriorit(PNODEpHead)；

voiddo_work_l(PNODEpHead,int*w_finish_time,inti)；

intmain()

(

intchoice；〃设置选择数

showmenu()；〃显示菜单

scanf("%dn,&choice)；

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

(

switch(choice)

(

case1:

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

FCFS（）；

break；

case2：

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

SJF（）；

break；

case3：

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

HRRNO；

break；

default：

printf（"请重新选择！"）；

break；

）

printf（"\n"）；

printf（"下面是菜单，请继续，或者按'0"退出"）；

showmenu()；

scanf(n%dn,&choice)；

printf("感谢您使用本系统，再见！");

return0；

)

voidFCFS()

(

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\tw,j+1,w[j].id）；

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

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

printf（"第％d个作业服务时

问:%d\tn,j+l,w[j].work_time）；

printf（"\n"）；

）

for(j=l；j<5；j++)

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

(

if(w[k].arrive_time>w[k+l].arrive_time)

{

temp=wEk]；

w[k]=wEk+1]；

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+lLarrive_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_timeEj]；

）

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

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

”,j+l,w[j].arrive_time）；

printf（"编号是:%did）；

printf（"服务时间是：%dMwork_time）；

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

printf（"周转时间是：%dw,w_rel_time[j]）；

printf（n\n"）；

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

voidSJF()

intw_rel_time[10]；

intw_finish_time[10]；

floatrel_time=0；

srand(time(0))；

inti；

intj=0；

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

if(NULL==pHead)

(

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

exit(-1)；

)

PNODEpTail=pHead；

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

点初始化为空

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

(

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

if(NULL==pNew)

{

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

exit(-1)；

)

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+l,p->s_work.id)；

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

间：％d\t”,j+1,p->s_work.arrive_time)；

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

问:%d\t",j+1,p->s_work.work_time)；

printf("Xn")；

p=p->pNext；

printf('*\nw)；

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(ent>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[O]=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\nn,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))；

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\nn,rel_time/10)；

)

boolIs_empty(PNODEpHead)〃判断作业是否做完

(

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("系统中有%(1个作业在当前作业完成时已经到达！

\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_timeLi+l]=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+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（"编号是：%dn,q->s_work.id）；

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

printf（"完成时间是：%dn,w_finish_time[i+l]）；

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

voidshowmenu（）

printf（"**********************************\n"）；

printf（"请选择你要执行的命令工\n"）；

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

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

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

printf（"0：退出菜单\n"）；

printf（***********************************\n"）；

）

voidHRRNO

（

intw_rel_time[10]；

intw_finish_time[10]；

floatrel_time=0；

floatpriority；〃计算优先权

srand（time（0））；

inti；

intj=0；

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

if(NULL==pHead)

(

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

exit(-1)；

}

PNODEpTail=pHead；

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

点初始化为空

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

(

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

if(NULL==pNew)

(

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

exit(-1)；

)

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个作业服务时

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

printf("\n")；

p=p->pNext；

printf("\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(ent>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[O]-

q->s_work.arrive_time；

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

",q->s_work.arrive_time）；

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

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

printf（"完成时间是：%dn,w_finish_time[O]）；

printf（"周转时间是：%d\n",w_rel_time[01）；

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("现在系统还剩%d个作业！\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(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("系统中有%(1个作业在当前作业完成时已经到达！

\n",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指向第二

个节点，还是找最先到达的

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；

return；

}

)

w_finish_timeEi+l]=w_finish_time[i]+

q->s_work.work_time；

)

PNODEpriorit(PNODEpHead)

(

PNODEp=pHead->pNext；

while(p!=NULL)

if(p->s_work.wait>0)

p->s_work.priority=(p->s_work.wait+

p->s_work.work_time)/p->s_work.work_time；〃计算每

一个已经等待的进程的优先等级

p=p->pNext；

}

else

p=p->pNext；

)

p=pHead->pNext；

PNODEq；

q=P；

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

while(p!=NULL)

if(p->s_work.wait>0)

if(p->s_work.priority>q->s_work.priority)

q=P；

p=p->pNext；

)

else

p=p->pNext；

)

else

p=p->pNext；

)

printf("该进程优先级最高，

为：%f\n”,q->s_work.priority)；

returnq；

实验结果:

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

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

1.先来先服务算法

•E:\C语言绦习\Debug\1001.exe”

退出菜单

务法

哂

算

戈--mQ

nc-:

工

号

八

方B

业

bg业

否

1\21m一51

—

l.p、p

厅

」

、

算S10

号

业

业

寸

2八2

2\得5m1

二

——

.工sp-ap-

」

务

、H：2

号

业

业

〈g

厅7

m一

3\否833

一

.——

La-、p

写

、

p务10

号

业

b业5HFs

4\34Tm一24

香

厅

L、

写ap-

Js-、：

业

业

号3

p」

个

m一

首

5,\1孽505

二

g、ap-

一7Ep.:8

__，'-'-XII■■***V---V，V0编号是:1服务时间是:8完成时间是:8周转时

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

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

裁系统执行的作业到达时间:

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

悬11

储统执行的作业到达时间:

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

间18

5得统执行的作业到达时间:

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

间是：26

均周转时间：14.400000

疆

受

S乳请

'0'退出

叩

先

翱

华

篡

,「

法.

业

笈

先

舁

法

应

B比

优

先

算

法

菜

单

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

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

2.短作业优先

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

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

为时间短的服务。

•・E:\C语言练习\Debug\1001.exe-|。|回Zwl

退出菜单

%*垢个作业到达时间:

1第1个作业服务时间:

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

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

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

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

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

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

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

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

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

编

是

也即

的

号

T-到0-1

X:服务时间是：2

3间由246

个H1-

、

9！

坐

成时

达

幺

乍

已

一

，r-

・'E:\Ci言言练》Debug\1001.exe・OI回

：84

编

是

达

机旬

业

播

的

iJ号

n-到1

ET:服务时间是：

TJ间击462

-3转2

L：

Ms个07!

/9业

间

幺

成

t士

普

业

前

乍

业

已

空

R引

i当

一

-一

加

到

的

n编£

尚

臂

3扁

丁2

间

E业•服务时间是：4

n7时4

：

间B

L转

M个!

K8AE

t业

成

时

」

乍

^业■

村

I刖

l一

■当

钞

的

E子

丁512

间

r：服务时间是：4

业

-11旧6

Ls

个

M7患

KK

成

时

幺

管

」

乍

治

已

寿

业

间

当

I刖9

nj一

编

号

的

丁883

r业

：V-0

Jm扁服务时间是：

-1241

Ls患

M^6个

ut当

成

时幺

」

乍

已

业I

n^刖r

一

一

E■业

钞

笄

的

品

r丁818

：

-聊服务时间是：

悯

间1

B135

业

t5个

幺

乍

已

至

业

r当

间

一

，

三

扁

省

的

能

j丁984

服务时间是：

u排4

L17业8

间

MB4个

K当

成

幺

」

乍

t已

业

仄

&刖

恫

业

E■一(