操作系統(tǒng)--最高響應(yīng)比優(yōu)先調(diào)度算法實驗報告材料(廣西民大)

1、實用標(biāo)準(zhǔn)文案進程調(diào)度模擬設(shè)計最高響應(yīng)比優(yōu)先調(diào)度算法實驗報告一、實驗題目與要求1、實驗題目：加深對作業(yè)概念的理解。深入了解批處理系統(tǒng)如何組織作業(yè)、管 理作業(yè)和調(diào)度作業(yè)。2、實驗要求：編寫程序完成批處理系統(tǒng)中的作業(yè)調(diào)度，要求采用響應(yīng)比高者優(yōu) 先的作業(yè)調(diào)度算法。實現(xiàn)具體包括：首先確定作業(yè)控制塊的內(nèi)容和組成方式； 然 后完成作業(yè)調(diào)度；最后編寫主函數(shù)，對所做工作進行測試。二、總的設(shè)計思想及語言環(huán)境、工具1、總的設(shè)計思想：最高響應(yīng)比優(yōu)先法(HRRN是對FCF萌式和SJF方式的一種綜合平衡。HRRN 調(diào)度策略同時考慮每個作業(yè)的等待時間長短和估計需要的執(zhí)行時間長短，從中選出響應(yīng)比最高的作業(yè)投入執(zhí)行。響應(yīng)比R定

2、義如下：R=(W+T)/T=1+W/T其中T為該作業(yè)估計需要的執(zhí)行時間， W為作業(yè)在后備狀態(tài)隊列中的等待時間。每當(dāng)要進行作業(yè)調(diào)度時，系統(tǒng)計算每個作業(yè)的響應(yīng)比，選擇其中R最大者投 入執(zhí)行。這樣，即使是長作業(yè)，隨著它等待時間的增加，W/T也就隨著增加，也就有機會獲得調(diào)度執(zhí)行。這種算法是介于 FCFSf口 SJF之間的一種折中算法。由 于長作業(yè)也有機會投入運行，在同一時間內(nèi)處理的作業(yè)數(shù)顯然要少于SJF法，從而采用HRRNJ式時其吞吐量將小于采用 SJF法時的吞吐量。另外，由于每次 調(diào)度前要計算響應(yīng)比，系統(tǒng)開銷也要相應(yīng)增加。2、語言環(huán)境：計算機基本配置要求：操作系統(tǒng)：WIN 98/2000/XP/20

3、03 等 Windows平臺內(nèi)存：256MBs以上主存64KB （Memory （以KB為單位分酉己）開發(fā)語言：Visual C+ 6.03、工具：Windows平臺 + Visual C+ 6.0三、數(shù)據(jù)結(jié)構(gòu)與模塊說明（功能與框圖）作業(yè)調(diào)度的實現(xiàn)主要有兩個問題：一個是如何將系統(tǒng)中的作業(yè)組織起來； 另一個是如何進行作業(yè)調(diào)度。為了將系統(tǒng)中的作業(yè)組織起來，需要為每個進入系統(tǒng)的作業(yè)建立檔案以記 錄和作業(yè)相關(guān)的信息，例如，作業(yè)名、作業(yè)所需資源、作業(yè)執(zhí)行時間、作業(yè)進入 系統(tǒng)的時間、作業(yè)信息在存儲器中的位置、指向下一個作業(yè)控制塊的指針等信息。 這個記錄作業(yè)相關(guān)信息的數(shù)據(jù)塊稱為作業(yè)控制塊（JCB ）,并將系

4、統(tǒng)中等待作業(yè) 調(diào)度的作業(yè)控制塊組織成一個隊列，這個隊列稱為后備隊列。當(dāng)進行作業(yè)調(diào)度時， 從后備隊列中查找選擇作業(yè)。由于實驗中沒有實際作業(yè)，作業(yè)控制塊中的信息內(nèi)容只使用了實驗中需要 的數(shù)據(jù)。作業(yè)控制塊中首先應(yīng)該包括作業(yè)名；其次是作業(yè)所需資源（內(nèi)存大小、 打印機的數(shù)量和磁帶機的數(shù)量）；采用響應(yīng)比高者優(yōu)先作業(yè)調(diào)度算法，為了計算 響應(yīng)比，還需要有作業(yè)的估計執(zhí)行時間、作業(yè)在系統(tǒng)中的等待時間；另外，指向 下一個作業(yè)控制塊的指針必不可少。實驗中，作業(yè)控制塊及隊列的數(shù)據(jù)結(jié)構(gòu)定義如下:struct task string name; /*作業(yè)號 */int arrTime;/*作業(yè)到達時間*/int serTi

5、me; /*作業(yè)要求服務(wù)時間*/int waiTime; /*等待時間 */int begTime; /*開始運行時間*/int finTime; /*結(jié)束運行時間*/int turTime; /* 周轉(zhuǎn)時間 */int wTuTime; /* 帶權(quán)周轉(zhuǎn)時間*/int priority;/* 優(yōu)先權(quán) */int finish;/*是否已經(jīng)完成*/JCB10；存放作業(yè)控制塊的區(qū)域：#define n 10JCB jobtable10;int jobcount;將作業(yè)控制塊組織成一個隊列，實驗中采用靜態(tài)鏈表的方式模擬作業(yè)的后 備隊列，作業(yè)隊列頭指針定義為：int *head;實驗中，內(nèi)存采用可移動

6、的動態(tài)分區(qū)管理方法，即只要內(nèi)存空閑區(qū)總和比 作業(yè)大就可以滿足作業(yè)對內(nèi)存的需求；對打印機和磁帶機這兩種獨占設(shè)備采用靜 態(tài)分配法，即作業(yè)執(zhí)行前必須獲得所需資源，并且執(zhí)行完才歸還。采用響應(yīng)比高者優(yōu)先調(diào)度算法進行調(diào)度時，必須計算出系統(tǒng)中所有滿足必 要條件作業(yè)的響應(yīng)比，從中選擇響應(yīng)比最高的一個作業(yè)裝入主存儲器分配資源。 由于是實驗，所以就將作業(yè)控制塊出隊，并輸出作業(yè)名代替裝入處存儲器，同時 修改系統(tǒng)的資源數(shù)量。卜）文檔大全實用標(biāo)準(zhǔn)文案四、參考源程序:#include#include#include #include#include定義string為含有10個字符元素的字符數(shù)組#include typed

7、ef char string10; /* / 類型*/struct task 作業(yè)號*/作業(yè)到達時間*/ 作業(yè)要求服務(wù)時間*/ 等待時間*/開始運行時間*/ 結(jié)束運行時間*/周轉(zhuǎn)時間*/帶權(quán)周轉(zhuǎn)時間*/優(yōu)先權(quán)*/是否已經(jīng)完成*/string name; /* int arrTime; /* int serTime; /* int waiTime; /* int begTime; /* int finTime; /* int turTime; /* int wTuTime; /* int priority;/* int finish;/*JCB10;int num;void input()int

8、 i;system(cls);printf(n請輸入作業(yè)數(shù)量：);scanf(%d”, &num);for(i=0;inum;i+)printf(n請輸入作業(yè) NO.%d:n,i);printf(作業(yè)名稱：);scanf(%s,JCB);printf(到達時間：);scanf(%d”,&JCBi.arrTime);printf(服務(wù)時間：);scanf(%d”,&JCBi.serTime);JCBi.priority = 0;JCBi.finish =0; int HRN(int pre)int current=1,i,j;/* 優(yōu)先權(quán)=(等待時間+服務(wù)時間)/服務(wù)時間*/ for

9、(i=0; inum; i+)JCBi.waiTime=JCBpre.finTime-JCBi.arrTime; /*等待時間 =上一個作業(yè)的完成時間-到達時間*/JCBi.priority=(JCBi.waiTime+JCBi.serTime)/JCBi.serTime;for(i=0; inum; i+)if(!JCBi.finish) current=i; /*找到第一個還沒完成的作業(yè)*/break;for( j=i; jnum; j+) /*和后面的作業(yè)比較*/if( !JCBj.finish) /*還沒完成(運行)*/if(JCBcurrent.arrTime=JCBpre.finT

10、ime) /*如果作業(yè)在上一個作業(yè)完成之前到達*/if(JCBj.arrTimeJCBcurrent.priority )current=j;/*找出到達時間在上一個作業(yè)完成之前，優(yōu)先權(quán)高的作業(yè)*/else /*如果作業(yè)是在上一個作業(yè)完成之后到達*/if(JCBj.arrTimeJCBcurrent.priority) current=j;/* 找出服務(wù)時間比較短的一個*/ return current;/* 返回當(dāng)前作業(yè)*/void runing(int i, int times, int pre, int staTime, int endTime)if(times=0)JCBi.begTi

11、me=JCBi.arrTime;JCBi.finTime=JCBi.begTime+JCBi.serTime;JCBi.turTime=JCBi.serTime;JCBi.wTuTime=1.0;staTime=JCBi.begTime;elseif(JCBi.arrTimeJCBpre.finTime)JCBi.begTime=JCBi.arrTime;elseJCBi.begTime=JCBpre.finTime;JCBi.finTime=JCBi.begTime+JCBi.serTime;JCBi.turTime=JCBi.finTime-JCBi.arrTime;JCBi.wTuTim

12、e=JCBi.turTime/JCBi.serTime;if(times=num-1)endTime=JCBi.finTime;JCBi.finish=1;void print(int i,int times)if(times=0)printf( 名稱 到達時間服務(wù)時間開始時間完成時間 周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間n);printf(%9s%9d%9d%9d%9d%9d%9dn,JCB,JCBi.arrTime,JCBi.serTime,JCBi.begTime,JCBi.finTime,JCBi.turTime,JCBi.wTuTime);void check()int i;int st

13、aTime, endTime, sumTurTime=0.0, sumWTuTime=0.0, aveTurTime, aveWTuTime;int current=0, times=0, pre=0;JCBpre.finTime=0;for(i=0; inum; i+)JCBi.finish=0;staTime, endTime,sumTurTime=0.0, sumWTuTime=0.0, aveTurTime, aveWTuTime;current=0; times=0; pre=0;JCBpre.finTime=0;printf(n)；for(i=0; inum; i+) JCBi.f

14、inish=0; staTime, endTime,sumTurTime=0.0, sumWTuTime=0.0, aveTurTime, aveWTuTime;current=0; times=0; pre=0;JCBpre.finTime=0; printf(n-HRRNn) ; for(times=0; timesnum; times+) current=HRN(pre); runing(current, times, pre, staTime, endTime); print(current, times); pre=current; for(i=0; iMMC)NMDevggBinD

15、ebugCpp2,eiie”8 i 1 0No* 1 1 一- A- -作入業(yè)達務(wù)1222X 2 1* * -業(yè)作 入卷務(wù)入業(yè)達務(wù) 2例作到壓 胃NO. 2 :：x3 ：32h- HRRN 名稱到達時間服務(wù)時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間xl11101121101x222122234121x328333466381計與平均值用 6目 201六、運行結(jié)果分析：從運行結(jié)果得到調(diào)度序列結(jié)果為:X1X2 X3X1到達時間最早，服務(wù)時間也最短，其響應(yīng)比最高;X2到達時間為22,但因X1早到達，所以開始時間為22,其服務(wù)時間為12,所 以響應(yīng)比X1小；X3到達時間最遲，其響應(yīng)比最小，所以在最后。七、自我評價與總結(jié)：本次課程設(shè)計題目較為簡單，主要是對優(yōu)先級和最高響應(yīng)比這兩 個算法的理解和對進程調(diào)度的功能以及進程調(diào)度算法有深入的理解。在這次的課程設(shè)計中，讓我感覺較