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

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

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

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

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

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

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

7、ef char string10; /* / 類型*/struct task 作業(yè)號*/作業(yè)到達(dá)時(shí)間*/ 作業(yè)要求服務(wù)時(shí)間*/ 等待時(shí)間*/開始運(yùn)行時(shí)間*/ 結(jié)束運(yùn)行時(shí)間*/周轉(zhuǎn)時(shí)間*/帶權(quán)周轉(zhuǎn)時(shí)間*/優(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(到達(dá)時(shí)間：);scanf(%d”,&JCBi.arrTime);printf(服務(wù)時(shí)間：);scanf(%d”,&JCBi.serTime);JCBi.priority = 0;JCBi.finish =0; int HRN(int pre)int current=1,i,j;/* 優(yōu)先權(quán)=(等待時(shí)間+服務(wù)時(shí)間)/服務(wù)時(shí)間*/ for

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

10、ime) /*如果作業(yè)在上一個(gè)作業(yè)完成之前到達(dá)*/if(JCBj.arrTimeJCBcurrent.priority )current=j;/*找出到達(dá)時(shí)間在上一個(gè)作業(yè)完成之前，優(yōu)先權(quán)高的作業(yè)*/else /*如果作業(yè)是在上一個(gè)作業(yè)完成之后到達(dá)*/if(JCBj.arrTimeJCBcurrent.priority) current=j;/* 找出服務(wù)時(shí)間比較短的一個(gè)*/ 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( 名稱 到達(dá)時(shí)間服務(wù)時(shí)間開始時(shí)間完成時(shí)間 周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間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è)達(dá)務(wù)1222X 2 1* * -業(yè)作 入卷務(wù)入業(yè)達(dá)務(wù) 2例作到壓 胃NO. 2 :：x3 ：32h- HRRN 名稱到達(dá)時(shí)間服務(wù)時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間xl11101121101x222122234121x328333466381計(jì)與平均值用 6目 201六、運(yùn)行結(jié)果分析：從運(yùn)行結(jié)果得到調(diào)度序列結(jié)果為:X1X2 X3X1到達(dá)時(shí)間最早，服務(wù)時(shí)間也最短，其響應(yīng)比最高;X2到達(dá)時(shí)間為22,但因X1早到達(dá)，所以開始時(shí)間為22,其服務(wù)時(shí)間為12,所 以響應(yīng)比X1?。籜3到達(dá)時(shí)間最遲，其響應(yīng)比最小，所以在最后。七、自我評價(jià)與總結(jié)：本次課程設(shè)計(jì)題目較為簡單，主要是對優(yōu)先級和最高響應(yīng)比這兩 個(gè)算法的理解和對進(jìn)程調(diào)度的功能以及進(jìn)程調(diào)度算法有深入的理解。在這次的課程設(shè)計(jì)中，讓我感覺較