..《操作系統》實驗報告題目：作業調度算法班級：網絡工程姓名：朱錦濤學號：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->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_time<q->s_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->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+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_time<q->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_time<q->s_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>>; do_work_1<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_1<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>//說明此時有好幾個都已經到達了 { 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;