作業(yè)調(diào)度算法(先來先服務(wù)算法,短作業(yè)算法)

《振作系統(tǒng)》賣臉報(bào)告

題目:作業(yè)調(diào)度算法

班級(jí):網(wǎng)絡(luò)工程

姓名:朱錦濤

學(xué)號(hào):E31314037

一、實(shí)驗(yàn)?zāi)康?/p>

用代碼實(shí)現(xiàn)頁面調(diào)度算法,即先來先服務(wù)（FCFS調(diào)度算法

、短作業(yè)優(yōu)先算法、高響應(yīng)比優(yōu)先調(diào)度算法。通過代碼的具體實(shí)現(xiàn),

加深對(duì)算法的核心的理解。

二、實(shí)驗(yàn)原理

1.先來先服務(wù)（FCFS調(diào)度算法

FCFS是最簡(jiǎn)單的調(diào)度算法，該算法既可用于作業(yè)調(diào)度，也可用于進(jìn)

程調(diào)度。當(dāng)在作業(yè)調(diào)度中采用該算法時(shí),系統(tǒng)將按照作業(yè)到達(dá)的先后

次序來進(jìn)行調(diào)度，或者說它是優(yōu)先考慮在系統(tǒng)中等待時(shí)間最長(zhǎng)的作業(yè),

而不管該作業(yè)所需執(zhí)行的時(shí)間的長(zhǎng)短，從后備作業(yè)隊(duì)列中選擇幾個(gè)最

先進(jìn)入該隊(duì)列的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源和創(chuàng)建進(jìn)程。

然后把它放入就緒隊(duì)列。

2.短作業(yè)優(yōu)先算法

SJF算法是以作業(yè)的長(zhǎng)短來計(jì)算優(yōu)先級(jí)，作業(yè)越短，其優(yōu)先級(jí)越高。

作業(yè)的長(zhǎng)短是以作業(yè)所要求的運(yùn)行時(shí)間來衡量的。SJF算法可以分別

用于作業(yè)和進(jìn)程調(diào)度。在把短作業(yè)優(yōu)先調(diào)度算法用于作業(yè)調(diào)度時(shí)，它

將從外存的作業(yè)后備隊(duì)列中選擇若干個(gè)估計(jì)運(yùn)行時(shí)間最短的作業(yè)，優(yōu)

先將它們調(diào)入內(nèi)存。

3、高響應(yīng)比優(yōu)先調(diào)度算法

高響應(yīng)比優(yōu)先調(diào)度算法則是既考慮了作業(yè)的等待時(shí)間，又考慮了作業(yè)

的運(yùn)行時(shí)間的算法，因此既照顧了短作業(yè)，又不致使長(zhǎng)作業(yè)等待的時(shí)

間過長(zhǎng)，從而改善了處理機(jī)調(diào)度的性能。

如果我們引入一個(gè)動(dòng)態(tài)優(yōu)先級(jí)，即優(yōu)先級(jí)是可以改變的令它隨等待的

時(shí)間的延長(zhǎng)而增加,這將使長(zhǎng)作業(yè)的優(yōu)先級(jí)在等待期間不斷地增加，

等到足夠的時(shí)間后，必然有機(jī)會(huì)獲得處理機(jī)。該優(yōu)先級(jí)的變化規(guī)律可

以描述為：

優(yōu)先權(quán)=（等待時(shí)間+要求服務(wù)時(shí)間/要求服務(wù)時(shí)間

三、實(shí)驗(yàn)內(nèi)容

源程序:

#include<stdio.h>

#include<stdlib.h>

#include<time.h>

structwork

(

intid；

intarrive_time；

intwork_time；

intwait；

floatpriority；

);

typedefstructsjf_work

(

structworks_work；〃數(shù)據(jù)域

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；〃設(shè)置選擇數(shù)

showmenuO；〃顯示菜單

scanf<n%d",&choice>；

while<choice!=0>〃選擇算法

switch<choice>

case1：

printf＜"您選擇的是先來先服務(wù)算法:\n"＞；

FCFSO；

break；

case2：

printf＜"您選擇的是短作業(yè)優(yōu)先算法:\n"＞；

SJFO；

break；

case3：

printf＜"您選擇的是高響應(yīng)比優(yōu)先調(diào)度算法\n"＞；

HRRNO；

break；

default：

printf〈"請(qǐng)重新選擇！"＞；

break；

)

printf＜M\n"＞；

printf＜"下面是菜單，請(qǐng)繼續(xù),或者按‘0'退出"＞；

showmenuO；

scanf＜"%d”,&choice＞；

}

printf〈"感謝您使用本系統(tǒng),再見！"＞；

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個(gè)作業(yè)的編號(hào)是：%d\t",j+l,w[j].id>；

printf<"第%d個(gè)作業(yè)到達(dá)時(shí)

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

printf〈”第％d個(gè)作業(yè)服務(wù)時(shí)

間：%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個(gè)系統(tǒng)執(zhí)行的作業(yè)到達(dá)時(shí)間：%d

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

printf〈"編號(hào)是：%dn,w[j].id>；

printf〈"服務(wù)時(shí)間是：%dn,w[jLwork_time>；

printf<"完成時(shí)間是:%d",w_finish_time[j]>；

printf〈"周轉(zhuǎn)時(shí)間是：%dn,w_rel_time[j]>；

printf<n\n">；

}

printf<"平均周轉(zhuǎn)時(shí)間：%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；〃定義該鏈表有頭結(jié)點(diǎn)，且第一個(gè)節(jié)點(diǎn)

初始化為空

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指向第一個(gè)節(jié)點(diǎn)

while<NULL!=p>

(

printf<"第％d個(gè)作業(yè)的編號(hào)是：%d\t",j+1,p->s_work.id>；

printf<"第％d個(gè)作業(yè)到達(dá)時(shí)

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

printf<"第%d個(gè)作業(yè)服務(wù)時(shí)

間：％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都指向第一個(gè)節(jié)點(diǎn)

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也指向第一個(gè)節(jié)點(diǎn)

intent=0；〃記錄所有節(jié)點(diǎn)數(shù)據(jù)域中到達(dá)時(shí)間最短且相等的

個(gè)數(shù)

while<r!=NULL>

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

cnt++；

r=r->pNext；

)

p=pHead->pNext；

while<p!=NULL>〃在相等到達(dá)時(shí)間的作業(yè)中找服務(wù)時(shí)間最

短的作業(yè)

(

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所指作業(yè)最先到達(dá)且服務(wù)時(shí)間最短

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個(gè)系統(tǒng)執(zhí)行的作業(yè)到達(dá)時(shí)間：%d

n,q->s_work.arrive_time>；

printf<"編號(hào)是：%dn,q->s_work.id>；

printf<"服務(wù)時(shí)間是：%d\nn,q->s_work.work_time>；

printf<"完成時(shí)間是：%d",w_finish_time[0]>；

printf〈"周轉(zhuǎn)時(shí)間是：%d\n",w_rel_time[0]>；

p=pHead;〃尋找q的前一個(gè)節(jié)點(diǎn)，方便刪掉q節(jié)點(diǎn)

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<"現(xiàn)在系統(tǒng)還剩％(1個(gè)作業(yè)！\n",cnt_work<pHead>>；

q=do_work<pHead,w_finish_time,i>；

show<w_finish_time,i,q,w_rel_time>；

p=pHead;〃尋找q的前一個(gè)節(jié)點(diǎn)，方便刪掉q節(jié)點(diǎn)

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<"平均周轉(zhuǎn)時(shí)間:%f\n'*,rel_time/10>；

)

boolIs_empty<PN0DEpHead>〃判斷作業(yè)是否做完

(

PNODEp；

p=pHead->pNext；

intlen=0；

while<p!=NULL>

(

len++；

p=p->pNext；

)

if<len==0>

returntrue；〃當(dāng)沒有作業(yè)時(shí)，返回為真

else

returnfalse；

)

intcnt_work<PNODEpHead>〃計(jì)算當(dāng)前還剩多少作業(yè)

(

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；〃計(jì)數(shù)器清0,計(jì)算當(dāng)前作業(yè)完成時(shí)，系統(tǒng)中有

多少個(gè)作業(yè)已經(jīng)到達(dá)

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指向當(dāng)前到達(dá)時(shí)間小于剛剛完成的作業(yè)，但不一定是

服務(wù)時(shí)間最短的<如果有的話》

printf<"系統(tǒng)中有%d個(gè)作業(yè)在當(dāng)前作業(yè)完成時(shí)已經(jīng)到達(dá)！

\n",cnt>；

p=pHead->pNext；

while<p!=NULL>

(

if<cnt>l>〃執(zhí)行此次判斷后,q現(xiàn)在指向所有條件都滿足

的作業(yè)(如果有的話

(

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〃當(dāng)前作業(yè)完成時(shí),沒有作業(yè)到達(dá)的情況

p=p->pNext;〃用q來接收最先到達(dá)的，用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個(gè)系統(tǒng)執(zhí)行的作業(yè)到達(dá)時(shí)間：%d

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

printf〈"編號(hào)是：%d°,q->s_work.id>；

printf〈”服務(wù)時(shí)間是：%d\nn,q->s_work.work_time>；

printf〈”完成時(shí)間是：%dn,w_finish_time[i+l]>；

printf〈"周轉(zhuǎn)時(shí)間是：%d\n",w_rel_time[i+l]＞；

)

voidshowmenuO

(

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

printf＜"請(qǐng)選擇你要執(zhí)行的命令1\n"＞；

printf＜"l：先來先服務(wù)算法\n"＞；

printf＜n2：短作業(yè)優(yōu)先算法\n"＞；

printf＜"3：高響應(yīng)比優(yōu)先算法\n"＞；

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

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

)

voidHRRNO

(

intw_rel_time[10]；

intw_finish_time[10]；

floatreltime=0：

floatpriority；〃計(jì)算優(yōu)先權(quán)

srand<time<0?；

inti；

intj=0；

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

if<NULL==pHead>

（

printf<"分配失敗，程序終止!\n">；

exit<-l>；

）

PNODEpTail=pHead；

pTail->pNext=NULL；〃定義該鏈表有頭結(jié)點(diǎn)，且第一個(gè)節(jié)點(diǎn)

初始化為空

for<i=0；i<10；i++>〃定義了十個(gè)進(jìn)程

{

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指向第一個(gè)節(jié)點(diǎn)

while<NULL!=p>

(

printf〈"第％d個(gè)作業(yè)的編號(hào)是：%d\tn,j+1,p->s_work.id>；

printf<"第％d個(gè)作業(yè)到達(dá)時(shí)

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

printf〈"第刎個(gè)作業(yè)服務(wù)時(shí)

間：%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都指向第一個(gè)節(jié)點(diǎn)

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也指向第一個(gè)節(jié)點(diǎn)

intent=0；〃記錄所有節(jié)點(diǎn)數(shù)據(jù)域中到達(dá)時(shí)間最短且相等的

個(gè)數(shù)

while<r!=NULL>

(

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

cnt++；

r=r->pNext；

)

p=pHead->pNext；

while<p!=NULL>〃在相等到達(dá)時(shí)間的作業(yè)中找服務(wù)時(shí)間最

短的作業(yè)

(

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所指作業(yè)最先到達(dá)且服務(wù)時(shí)間最短

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個(gè)系統(tǒng)執(zhí)行的作業(yè)到達(dá)時(shí)間：%d

",q->s_work.arrive_time>；

printf<"編號(hào)是：%dn,q->s_work.id>；

printf<"服務(wù)時(shí)間是：%d\n",q->s_work.work_time>；

printf〈”完成時(shí)間是：%dn,w_finish_time[0]>；

printf<"周轉(zhuǎn)時(shí)間是：%d\n",w_rel_time[0]>；

p=pHead;〃尋找q的前一個(gè)節(jié)點(diǎn)，方便刪掉q節(jié)點(diǎn)

while<p->pNext!=q>

p=p->pNext；

p->pNext=q->pNext；

free<q>；

q=NULL;〃已經(jīng)找到并執(zhí)行第一個(gè)進(jìn)程，執(zhí)行完之后又將其

刪除了

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

(

printf<"現(xiàn)在系統(tǒng)還剩％(1個(gè)作業(yè)！\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的前一個(gè)節(jié)點(diǎn)，方便刪掉q節(jié)點(diǎn)

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<"平均周轉(zhuǎn)時(shí)間:%f\n",rel_time/10>；

)

voiddo_work_l<PN0DEpHead,int*w_finish_time,inti>

(

PNODEp,q；

intent=0；〃計(jì)數(shù)器清0,計(jì)算當(dāng)前作業(yè)完成時(shí)，系統(tǒng)中有

多少個(gè)作業(yè)已經(jīng)到達(dá)

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指向當(dāng)前到達(dá)時(shí)間小于剛剛完成的作業(yè)，但有可能有

另外幾個(gè)進(jìn)程也已經(jīng)到達(dá)了，所以要進(jìn)行下面的判斷

printf<"系統(tǒng)中有%d個(gè)作業(yè)在當(dāng)前作業(yè)完成時(shí)已經(jīng)到達(dá)！

\nB,cnt>；

p=pHead->pNext；

while<p!=NULL>

if<cnt>l>〃說明此時(shí)有好幾個(gè)都已經(jīng)到達(dá)了

(

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〃當(dāng)前作業(yè)完成時(shí),沒有作業(yè)到達(dá)的情況

p=p->pNext；〃此時(shí)p指向第一個(gè)節(jié)點(diǎn),q