作业调度算法先来先服务算法短作业算法.docx

作业调度算法先来先服务算法短作业算法.docx

《作业调度算法先来先服务算法短作业算法.docx》由会员分享，可在线阅读，更多相关《作业调度算法先来先服务算法短作业算法.docx（28页珍藏版）》请在冰点文库上搜索。

作业调度算法先来先服务算法短作业算法

《操作系统》实验报告

题目:

作业调度算法

班级:

网络工程

姓名：

朱锦涛

学号:

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;

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

voidHRRN（）；

PNODEpriorit（PNODEpHead）;

voiddo_work_1（PNODEpHead,int＊w_finish_time，inti）;

intmain（）

{

intchoice;//设置选择数

showmenu（）；//显示菜单

scanf（"%d”，＆choice）;

while（choice！

=0）//选择算法

{

switch（choice）

｛

case1:

printf（”您选择的是先来先服务算法:

\n”）；

FCFS（）;

break；

case2：

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

\n"）;

SJF（）;

break;

case3：

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

HRRN（）；

break；

default:

printf（”请重新选择!

"）;

break;

｝

printf（”\n”）；

printf（”下面是菜单，请继续,或者按‘0’退出”）；

showmenu（）；

scanf（"%d",＆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+1；

｝

for（j=0；j〈5;j++）

{

printf（”第%d个作业的编号是：

％d\t",j+1,w[j]。

id）；

printf（”第％d个作业到达时间：

％d\t"，j+1，w[j].arrive_time）；

printf（”第%d个作业服务时间:

%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］.arrive_time>w[k+1］。

arrive_time）

{

temp=w［k］;

w[k]=w［k+1］；

w［k+1］=temp;

｝

｝

printf（”\n”）；

w_finish_time［0］=w[0］。

arrive_time+w[0].work_time；

for（j=0;j〈5；j++）

｛

if（w_finish_time[j]〈w［j+1］.arrive_time）

{

w_finish_time［j+1]=w［j+1]。

arrive_time+w[j+1］。

work_time;

}

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]。

arrive_time；

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

{

rel_time+=w_rel_time［j］；

｝

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

｛

printf（”第％d个系统执行的作业到达时间：

%d"，j+1,w[j］。

arrive_time）;

printf（”编号是：

%d”,w[j]。

id）；

printf（"服务时间是：

%d”,w［j].work_time）;

printf（"完成时间是:

％d",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];

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+1；

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\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=p;

p=p—〉pNext;

}

PNODEr=pHead—>pNext;//r也指向第一个节点

intcnt=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_times_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[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\n”，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（”现在系统还剩%d个作业!

\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（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；

intcnt=0;//计数器清0,计算当前作业完成时,系统中有多少个作业已经到达

p=pHead-〉pNext；

q=p；

while（p!

=NULL）

｛

if（p—>s_work.arrive_time<=w_finish_time[i］）

｛

cnt++;

q=p；

p=p—〉pNext；

}

else

｛

p=p—〉pNext；

｝

｝//q指向当前到达时间小于刚刚完成的作业，但不一定是服务时间最短的（如果有的话）

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

\n”,cnt）;

p=pHead->pNext;

while（p！

=NULL）

｛

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

｛

if（p-〉s_work.arrive_time<=w_finish_time[i］）

｛

if（p->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

arrive_time）

q=p；

p=p->pNext;

｝

w_finish_time［i+1]=q-〉s_work.arrive_time+q—>s_work.work_time;

}

｝

w_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_rel_time[i+1]=w_finish_time[i+1］-q-〉s_work.arrive_time;

printf（”第%d个系统执行的作业到达时间:

％d",i+2,q—〉s_work。

arrive_time）;

printf（”编号是：

%d",q-〉s_work.id）;

printf（”服务时间是：

%d\n",q—>s_work.work_time）;

printf（”完成时间是：

%d"，w_finish_time［i+1］）；

printf（”周转时间是:

％d\n",w_rel_time［i+1]）;

}

voidshowmenu（）

｛

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

printf（"请选择你要执行的命令~:

\n”）；

printf（"1:

先来先服务算法\n”）；

printf（”2：

短作业优先算法\n”）；

printf（"3：

高响应比优先算法\n"）；

printf（"0:

退出菜单\n”）;

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

}

voidHRRN（）

｛

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+1；

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\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_times_work。

arrive_time）

q=p;

p=p—>pNext；

｝

PNODEr=pHead—〉pNext；//r也指向第一个节点

intcnt=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

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［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\n"，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（”现在系统还剩％d个作业！

\n”，cnt_work（pHead））；

do_work_1（pHead,w_finish_tim