《操作系统》实验版告

《操作系统》实验版告

题目：作业调度算法

班级：网络工程

姓名：朱锦涛

学号：E31314037

一、实验目的

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

、短作业优先算法、高响应比优先调度算法.通过代码的具体实现，加深对算法

的核心的理解。

二、实验原理

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

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

在作业调度中采用该算法时，系统将按照作业到达的先后次序来进行调度,或者说

它是优先考虑在系统中等待时间最长的作业，而不管该作业所需执行的时间的长短,

从后备作业队列中选择几个最先进入该队列的作业，将它们调入内存，为它们分配

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

2.短作业优先算法

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

以作业所要求的运行时间来衡量的。SJF算法可以分别用于作业和进程调度。在把

短作业优先调度算法用于作业调度时，它将从外存的作业后备队列中选择若干个估

计运行时间最短的作业，优先将它们调入内存。

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

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

的算法，因此既照顾了短作业，又不致使长作业等待的时间过长，从而改善了处理

机调度的性能。

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

而增加，这将使长作业的优先级在等待期间不断地增加，等到足够的时间后，必然

有机会获得处理机。该优先级的变化规律可以描述为：

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

三、实验内容

源程序：

#include<stdiooh）

#include<stdIib.h>

#include<time.h>

structwork

(

intid;

intarrivetime;

intwork_time;

intwait;

floatpriority;

｝；

intmain()

intchoice;〃设置选择数

showmenu();〃显示菜单

scanf("％d“，&choice);

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

(

switch(choice)

(

case1:

printf(w您选择的是先来先服务算法:\n");

FCFS0;

break;

case2:

printf("您选择的是短作业优先算法：\nn);

SJF();

break;

case3:

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

HRRN0;

break;

default:

printf（"请重新选择！”）;

break;

}

printf（”\n“）；

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

showmenu（）;

scanf（"%dH,&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]oid=rand()%10;

w[i]oarrive_time=rand()%10;

w[i]owork_time=rand()%10+1;

}

for(j=0;j<5;j++)

(

printf("第％d个作业的编号是：j+1,w[j]©id);

w

printf(第％(^个作业到达时间：％d\t”，j+1,w[j]oarrive_time);

printf("第％(1个作业服务时间：％d\t”，j+1,w[j].work_time);

printf(”\n”)；

}

for(j=1;j<5;j++)

for(k=0;k<5—j;k++)

(

if(w[k]oarrive_time>w[k+1].arrive_time)

temp=w[k];

w[k]=w[k+1];

w[k+1]=temp;

1

}

printf("\n");

w_finish_time[0]=w[0].arrive_time+w[0]owork_time;

for(j=0;j<5;j++)

(

if(w_finish_time[j]〈w[j+1]oarrive_time)

(

w_finish_time[j+1]=w[j+1]oarrive_time+w[j+1]owork_time;

1

else

w_finish_time[j+1]=w_finish_time[j]+w[j+1]。work_time;

）

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

w_rel_time[j]=w_finish_time[j]-w[j]oarrive_time;

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

（

reI_time+=w_rel_time[j];

}

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

（

printf（"第％（1个系统执行的作业到达时间：%dH,j+1,w[j]o

arrive_time）;

printf（"编号是：%d",w[j].id）;

printf（w服务时间是：%d",w[j].work_time）;

printf（”完成时间是：％dw,w_finish_time[j]）;

printf（“周转时间是：%d",w_rel_time[j]）;

printf(“\n");

}

printf("平均周转时间：%f\n”,rel_time/5);

}

voidSJF()

{

intw_rel_time[10];

intw_finish_time[10];

floatreItime=0;

srand(time(0));

inti;

intj=0；

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

if(NULL=pHead)

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

exit(-1);

}

PNODEpTaiI=pHead;

pTail->pNext=NULL;〃定义该链表有头结点，且第一个节点初始化为空

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

|

PNODEpNew=(PNODE)ma11oc(sizeof(NODE));

if(NULL==pNew)

(

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

exit(—1);

}

pNew—>s_work.id=rand()%100;

pNew->s_work.arrive_time=rand()%10;

pNew->s_work.work_time=rand()%10+1;

pTail->pNext=pNew;

pNew->pNext=NULL;

pTaiI=pNew;

)

PNODEp=pHead-〉pNext;//p指向第一个节点

while(NULL!=p)

(

printf("第％d个作业的编号是：%d\tM,j+1,p->s_work.id);

printf("第％d个作业到达时间：％d\t”，j+1,p")s_workoarrive_time);

printf("第％d个作业服务时间：%d\tw,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_workoarrive_time〈q—>s_work.arrive_time)

q=P；

p=p—>pNext;

)

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

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

while(r!=NULL)

(

if(r->s_workoarrive_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[0]=q—>s_workoarrive_time+q—>s_workowork_time;

w_rel_time[0]=w_finish_time[0]—q—〉s_work.arrive_time;

printf("第1个系统执行的作业到达时间：%d”,q-〉s_work<>

arrive_time);

printf("编号是：%d”,q—>s_work.id);

printf("服务时间是：%d\nH,q—)s_work.work_time);

printf("完成时间是：%dn,w_finish_time[0]);

printf("周转时间是：%d\nH,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个作业！\nw,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(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;

whiIe(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_workoarrive_time<=w_finish_time[i])

(

ent++;

q=P；

p=p—〉pNext;

}

else

p=p-〉pNext;

}

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

短的(如果有的话)

printf("系统中有％(1个作业在当前作业完成时已经到达！\nH,cnt);

p=pHead->pNext;

whiIe(p!=NULL)

(

if(cnt>1)//执行此次判断后，q现在指向所有条件都满足的作业(如

果有的话)

(

if(p->s_workoarrive_time〈=w_finish_time[i])

(

if(p-〉s_workowork_time<q->s_workowork_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_workoarrive_time〈q-〉s_workoarrive_time)

q=p;

p=p-〉pNext;

)

w_fini8h_time[i+1]=q—>s_workoarrive_time+q—>8_worko

work_time;

)

}

w_finish_time[i+1]=w_finish_time[i]+q-〉s_workowork_time;

returnq;

}

voidshow（int*w_finish_time,inti9PNODEq,int*w_rel_time）

{

w_finish_time[i+1]=w_finish_time[i]+q->s_work.work_time;

w_rel_time[i+1]=w_finish_time[i+1]-q—〉s_work.arrive_time;

19

printf第％d个系统执行的作业到达时间：%d,i+2,q-）s_worko

arrive_time）;

printf（"编号是:％d"，q-〉s_workoid）;

printf（"服务时间是：％d\n”,q—>s_workowork-time）;

printf（w完成时间是：%du,w_finish_time[i+1]）;

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

）

voidshowmenu（）

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

\n"）;

printf（w请选择你要执行的命令〜：\n"）;

printf（7:先来先服务算法\n“）；

printfC^2:短作业优先算法\n”）；

printf（w3:高响应比优先算法\n”）；

printf（H0:退出菜单\n”）；

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

}

voidHRRN（）

{

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(-1);

)

PNODEpTail=pHead;

pTail—>pNext=NULL;〃定义该链表有头结点，且第一个节点初始化为

空

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

(

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

if(NULL==pNew)

printf（w分配失败，程序终止！\n"）;

exit(—1);

)

pNew—>s_workoid=rand()%100;

pNew->s_workoarrive_time=rand()%10;

pNew->s_workowork_time=rand()%10+1;

pTaiI—〉pNext=pNew;

pNew->pNext=NULL;

pTaiI=pNew;

}

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

while(NULL!=p)

(

printf("第%d个作业的编号是:%d\t”，j+1,p—〉s_work.id);

printf("第％d个作业到达时间：％d\t”,j+1,p—>s_workoarrive_time);

printf("第％d个作业服务时间：%d\tM,j+1,p—〉s_work.work_time);

printf(n\nH);

p=p->pNext;

printf("\n");

}

p=pHead—>pNext;

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

p=p->pNext;

whiIe(p!=NULL)

|

if(p—>s_work.arrive_time〈s_work.arrive_time)

q=p;

p=p->pNext；

)

PNODEr=pHead—〉pNext;〃r也指向第一个节点

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

while(r!=NULL)

(

if(r——〉s_workoarrive_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_workoarrive_time)

if(p-〉s_workowork_time<q—〉s_workowork_time)

q=p;

p=p—〉pNext;

}

else

p=NULL;

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

w_finish_time[0]=q->s_workoarrive_time+q->s_work.work_time;

w_rel_time[0]=w_finish_time[0]-q->s_work.arrive_time;

printf(”第1个系统执行的作业到达时间：%dn,q->s_worko

arrive_time）;

printf（"编号是：%d",q—〉s_work.id）;

printf（"服务时间是：%d\n”，q-〉s_workowork_time）;

printf（"完成时间是：％d"，w_finish_time[0]）;

printf周转时间是：%d\nw,w_rel_time[0]）;

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

whiIe（p—〉pNext!=q）

（

p=p—>pNext;

pNext=q-〉pNext;

free(q);

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

for(i=0;i<9&&!Is_empty(pHead);i++)

(

printf(w现在系统还剩％(1个作业！\nn,cnt_work(pHead));

do_work_1(pHead,w_finish_time,i);

q=priorit(pHead);

show(w_finish_time,i,q,w_rel_time);

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

whiIe(p->pNext!=q)

(

p=p->pNext;

)

p-〉pNext=q->pNext;

free(q);

q=NULL;

}

for(j=0;j<1O;j++)

(

reI_time+=w_rel_time[j];

}

printf(”平均周转时间：%f\nw,rel_time/10);

)

voiddo_work_1(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;

1

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

也已经到达了，所以要进行下面的判断

printf("系统中有％(1个作业在当前作业完成时已经到达！\n"，ent);

p=pHead->pNext;

whiIe(p!=NULL)

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

if(p-〉s_work.arrive_time(=w_finish_time[i])

I

p-〉s_work.wait=w_finish_time[i]一p->s_workoarrive_time;

p=p—〉pNext;

1

else

(

p->s_work.wait=0;

p=p->pNext;

1

)

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

(

p=P—>pNext;//此时p指向第一个节点，q指向第二个节点，还是

我最先到达的

while(p!=NULL)

if(p-〉s_workoarrive_time<q—>s_workoarrive_time)

q=p;

p=p—>pNext;

1

w_finish_time[i+1]=q-〉s_workoarrive_time+q->s_worko

work_time;

return;

)

]

w_finish_time[i+1]=w_finish_time[i]+q-〉s_workowork_time;

}

PNODEpriorit(PNODEpHead)

{

PNODEp=pHead—〉pNext;

while(p!=NULL)

if(p->s_workowait)0)

p->s_workopriority=(p->s_work,wait+p->s_work.work_time)

/p—>s_workowork_time;//计算每一^个已经等待的进程的优先等级

p=p->pNext;

}

else

p=p->pNext;

)

p=pHead-〉pNext;

PNODEq;

q=p；

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

while(p!=NULL)

if(p->s_workowait)0)

if(p->s_workopriority>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;

}

实验结果：

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

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

1o先来先服务算法

1'E:\C诒言练习\Debu9\1001.exe，回

退出菜单

XX——————W-

1

你

戈

科

影曹

务

，■

-

=

业

务

、

篝

编

浮

号

到达

一

I」XlD-

1?2151-i二■B

_AL7n又:|

r二

T，

业

」

业

务

第

编

浮

到达\

号

「

一

2/>52IBJ12七kDr1B-

(又

FT:、

.L二1

，

、

业

业

到达

务

第

编

浮-

号7n1

3L833/nJ:・

又

TIBfJ"、

AT二1

L，

、

业

到达

业

务

第

编

香

F.号klF1

4F34524七n:■0

X又

L^FI、1

、

L，

、

业

到达

业x

号

务

第

编

5F心15I05VnF「;1♦|

火I

L1m"-

IBfJ*，

*s2

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

患童系统执行的作业到达时间।1编号是:5服务时间是:2完成时间是:10周转时

要熟家统执行的作业到达时间.

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

舟括统执行的作业到达时间,

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

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

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

时间是：26

平均周转时间：14.400000

下面是尽单工请缴缀或者按，。‘退出

请选择你要椀亍语清令

1：龙榭屣募篁法

2：短传、I港先置法

3：鬲南应比优先算法

0：鬼田菜单

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

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

2o短作业优先

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

时间到达的作业，则按照其运行时间长短先为时间短的服务.

■0c语言练习\Debu9\lOOLexe回

0：退出菜单

XXXXAXMMXWXWXMWWXXWM************

2

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

第2个作业的编号是:12第2个作业到达时间:5第2个作业服务时间:4

第3个作业的编号是:26第3个作业到达时间:第3个作业服务时间:4

第4个作业的编号是:83第4个作业到达时间:第4个作业服务时间:1

第5个作业的编号是:19第5个作业到达时间;9第5个作业服务时间:?

第6个作业的编号是:46第6个作业到达时间:1第6个作业服务时间:2

第7个作业的编号是:18第7个作业到达时间:8第7个作业服务时间:1

第8个作业的编号是:第8个作业到达时间:第8个作业服务时间:

第9个作业的编号是：31第9个作业到达时间：7第9个作业服务时间：10

第10个作业的编号是：84第10个作业到达时间：9第10个作业服务时间：4

编是

国

幅有

盾如

的

作业

达

号

重

-至8

T:

转服务时间是：

司

周

N间2

元

3个2

业0-

黑

作

充I

7E还9

翼

t业L

当

誉

大

普

业

士国戈

修

有

40簟

JF目

第

的-

业

无

时尚

编

多-

^至

超32

T：

ItB-：4

业

重

级

窜

行

的

达瞿间

编是

方

至

_号

微—:

二

_间

3转82

复

、

：

一

个

业.

I7瞿L7:£

还

号

前

臣

业添

成

业

II9对度

^当

241-

塞>

的

J编

_到

生

业

曾

仃3

间

：

麟

兀_

转4

间

7：

中01,

个'

w咛!

/业ZE

还

成

时

号

前

ll^s业•

当

外§

L:

的

筮5

复

田

业

1;：

f1f1-6

酹1

中

^个!

业

翳

成

间

时

JI作7^

^业t

传^1

当*

行

的

^3—8

恫,

复

输i

^12x04

业

个

中

——

心

当

百

翳

成

时

Jl^s业q

传L

钞,

L业

的I8

恫

间

：

复

理)

节

1Bf1f31.日5

元

个!

中

羹

JI5」

翳

成

^业

刖

冷k

基

行

的

鬻9

54恫

.w：

兀17

^B个!

到

时

中

强

成

业□0

;l^l4刖

mj瞥