..《操作系統(tǒng)》實驗報告題目：作業(yè)調(diào)度算法班級：網(wǎng)絡(luò)工程姓名：朱錦濤學號：E31314037一、實驗?zāi)康挠么a實現(xiàn)頁面調(diào)度算法,即先來先服務(wù)〔FCFS調(diào)度算法、短作業(yè)優(yōu)先算法、高響應(yīng)比優(yōu)先調(diào)度算法。通過代碼的具體實現(xiàn),加深對算法的核心的理解。二、實驗原理1.先來先服務(wù)〔FCFS調(diào)度算法FCFS是最簡單的調(diào)度算法,該算法既可用于作業(yè)調(diào)度,也可用于進程調(diào)度。當在作業(yè)調(diào)度中采用該算法時,系統(tǒng)將按照作業(yè)到達的先后次序來進行調(diào)度,或者說它是優(yōu)先考慮在系統(tǒng)中等待時間最長的作業(yè),而不管該作業(yè)所需執(zhí)行的時間的長短,從后備作業(yè)隊列中選擇幾個最先進入該隊列的作業(yè),將它們調(diào)入內(nèi)存,為它們分配資源和創(chuàng)建進程。然后把它放入就緒隊列。2.短作業(yè)優(yōu)先算法SJF算法是以作業(yè)的長短來計算優(yōu)先級,作業(yè)越短,其優(yōu)先級越高。作業(yè)的長短是以作業(yè)所要求的運行時間來衡量的。SJF算法可以分別用于作業(yè)和進程調(diào)度。在把短作業(yè)優(yōu)先調(diào)度算法用于作業(yè)調(diào)度時,它將從外存的作業(yè)后備隊列中選擇若干個估計運行時間最短的作業(yè),優(yōu)先將它們調(diào)入內(nèi)存。3、高響應(yīng)比優(yōu)先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法則是既考慮了作業(yè)的等待時間,又考慮了作業(yè)的運行時間的算法,因此既照顧了短作業(yè),又不致使長作業(yè)等待的時間過長,從而改善了處理機調(diào)度的性能。如果我們引入一個動態(tài)優(yōu)先級,即優(yōu)先級是可以改變的令它隨等待的時間的延長而增加,這將使長作業(yè)的優(yōu)先級在等待期間不斷地增加,等到足夠的時間后,必然有機會獲得處理機。該優(yōu)先級的變化規(guī)律可以描述為：優(yōu)先權(quán)=〔等待時間+要求服務(wù)時間/要求服務(wù)時間三、實驗內(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;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;//設(shè)置選擇數(shù) showmenu<>;//顯示菜單 scanf<"%d",&choice>; while<choice!=0>//選擇算法 { switch<choice> { case1: printf<"您選擇的是先來先服務(wù)算法:\n">; FCFS<>; break; case2: printf<"您選擇的是短作業(yè)優(yōu)先算法:\n">; SJF<>; break; case3: printf<"您選擇的是高響應(yīng)比優(yōu)先調(diào)度算法\n">; HRRN<>; break; default: printf<"請重新選擇！">; break; } printf<"\n">; printf<"下面是菜單,請繼續(xù),或者按‘0’退出">; showmenu<>; scanf<"%d",&choice>; } printf<"感謝您使用本系統(tǒng),再見！">; 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個作業(yè)的編號是：%d\t",j+1,w[j].id>; printf<"第%d個作業(yè)到達時間：%d\t",j+1,w[j].arrive_time>; printf<"第%d個作業(yè)服務(wù)時間：%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個系統(tǒng)執(zhí)行的作業(yè)到達時間：%d",j+1,w[j].arrive_time>; printf<"編號是：%d",w[j].id>; printf<"服務(wù)時間是：%d",w[j].work_time>; printf<"完成時間是：%d",w_finish_time[j]>; printf<"周轉(zhuǎn)時間是：%d",w_rel_time[j]>; printf<"\n">; }printf<"平均周轉(zhuǎn)時間：%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;//定義該鏈表有頭結(jié)點,且第一個節(jié)點初始化為空 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指向第一個節(jié)點 while<NULL!=p> { printf<"第%d個作業(yè)的編號是：%d\t",j+1,p->s_work.id>; printf<"第%d個作業(yè)到達時間：%d\t",j+1,p->s_work.arrive_time>; printf<"第%d個作業(yè)服務(wù)時間：%d\t",j+1,p->s_work.work_time>; printf<"\n">; p=p->pNext; printf<"\n">; j++; } p=pHead->pNext; PNODEq=p;//p,q都指向第一個節(jié)點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也指向第一個節(jié)點 intcnt=0;//記錄所有節(jié)點數(shù)據(jù)域中到達時間最短且相等的個數(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>//在相等到達時間的作業(yè)中找服務(wù)時間最短的作業(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è)最先到達且服務(wù)時間最短 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個系統(tǒng)執(zhí)行的作業(yè)到達時間：%d",q->s_work.arrive_time>; printf<"編號是：%d",q->s_work.id>; printf<"服務(wù)時間是：%d\n",q->s_work.work_time>; printf<"完成時間是：%d",w_finish_time[0]>; printf<"周轉(zhuǎn)時間是：%d\n",w_rel_time[0]>; p=pHead;//尋找q的前一個節(jié)點,方便刪掉q節(jié)點 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)還剩%d個作業(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的前一個節(jié)點,方便刪掉q節(jié)點 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)時間：%f\n",rel_time/10>;}boolIs_empty<PNODEpHead>//判斷作業(yè)是否做完{ PNODEp; p=pHead->pNext; intlen=0; while<p!=NULL> { len++; p=p->pNext; } if<len==0> returntrue;//當沒有作業(yè)時,返回為真 else returnfalse;}intcnt_work<PNODEpHead>//計算當前還剩多少作業(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; intcnt=0;//計數(shù)器清0,計算當前作業(yè)完成時,系統(tǒng)中有多少個作業(yè)已經(jīng)到達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指向當前到達時間小于剛剛完成的作業(yè),但不一定是服務(wù)時間最短的<如果有的話> printf<"系統(tǒng)中有%d個作業(yè)在當前作業(yè)完成時已經(jīng)到達！\n",cnt>; p=pHead->pNext; while<p!=NULL> { if<cnt>1>//執(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//當前作業(yè)完成時,沒有作業(yè)到達的情況 { 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+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個系統(tǒng)執(zhí)行的作業(yè)到達時間：%d",i+2,q->s_work.arrive_time>; printf<"編號是：%d",q->s_work.id>; printf<"服務(wù)時間是：%d\n",q->s_work.work_time>; printf<"完成時間是：%d",w_finish_time[i+1]>; printf<"周轉(zhuǎn)時間是：%d\n",w_rel_time[i+1]>;}voidshowmenu<>{printf<"**********************************\n">; printf<"請選擇你要執(zhí)行的命令~:\n">; printf<"1：先來先服務(wù)算法\n">; printf<"2：短作業(yè)優(yōu)先算法\n">; printf<"3:高響應(yīng)比優(yōu)先算法\n">; printf<"0:退出菜單\n">; printf<"**********************************\n">;}voidHRRN<>{ intw_rel_time[10]; intw_finish_time[10]; floatrel_time=0; floatpriority;//計算優(yōu)先權(quán) srand<time<0>>; inti; intj=0; PNODEpHead=<PNODE>malloc<sizeof<NODE>>; if<NULL==pHead> { printf<"分配失敗,程序終止!\n">; exit<-1>; } PNODEpTail=pHead; pTail->pNext=NULL;//定義該鏈表有頭結(jié)點,且第一個節(jié)點初始化為空 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指向第一個節(jié)點 while<NULL!=p> { printf<"第%d個作業(yè)的編號是：%d\t",j+1,p->s_work.id>; printf<"第%d個作業(yè)到達時間：%d\t",j+1,p->s_work.arrive_time>; printf<"第%d個作業(yè)服務(wù)時間：%d\t",j+1,p->s_work.work_time>; printf<"\n">; p=p->pNext; printf<"\n">; j++; } p=pHead->pNext; PNODEq=p;//p,q都指向第一個節(jié)點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也指向第一個節(jié)點 intcnt=0;//記錄所有節(jié)點數(shù)據(jù)域中到達時間最短且相等的個數(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>//在相等到達時間的作業(yè)中找服務(wù)時間最短的作業(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è)最先到達且服務(wù)時間最短 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個系統(tǒng)執(zhí)行的作業(yè)到達時間：%d",q->s_work.arrive_time>; printf<"編號是：%d",q->s_work.id>; printf<"服務(wù)時間是：%d\n",q->s_work.work_time>; printf<"完成時間是：%d",w_finish_time[0]>; printf<"周轉(zhuǎn)時間是：%d\n",w_rel_time[0]>; p=pHead;//尋找q的前一個節(jié)點,方便刪掉q節(jié)點 while<p->pNext!=q> { p=p->pNext; } p->pNext=q->pNext; free<q>; q=NULL;//已經(jīng)找到并執(zhí)行第一個進程,執(zhí)行完之后又將其刪除了 for<i=0;i<9&&!Is_empty<pHead>;i++> { printf<"現(xiàn)在系統(tǒng)還剩%d個作業(yè)！\n",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的前一個節(jié)點,方便刪掉q節(jié)點 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)時間：%f\n",rel_time/10>;}voiddo_work_1<PNODEpHead,int*w_finish_time,inti>{ PNODEp,q; intcnt=0;//計數(shù)器清0,計算當前作業(yè)完成時,系統(tǒng)中有多少個作業(yè)已經(jīng)到達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指向當前到達時間小于剛剛完成的作業(yè),但有可能有另外幾個進程也已經(jīng)到達了,所以要進行下面的判斷 printf<"系統(tǒng)中有%d個作業(yè)在當前作業(yè)完成時已經(jīng)到達！\n",cnt>; p=pHead->pNext; while<p!=NULL> { if<cnt>1>//說明此時有好幾個都已經(jīng)到達了 { 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//當前作業(yè)完成時,沒有作業(yè)到達的情況 { p=p->pNext;