實現(xiàn)FCFS和SJF調(diào)度算法

1、操作系統(tǒng)實驗報告實驗一：作業(yè)調(diào)度學(xué)院：軟件學(xué)院專業(yè)：軟件工程班級：軟件工程12-01,*學(xué)號:541213460157實驗一：作業(yè)調(diào)度實現(xiàn)FCFSISJF調(diào)度算法【實驗題目】：編寫程序，實現(xiàn)FCFS和SJF算法，模擬作業(yè)調(diào)度過程，加深對作業(yè)調(diào)度的理解?！緦嶒瀮?nèi)容】實現(xiàn)FCF卻SJFM算法。-數(shù)據(jù)結(jié)構(gòu)設(shè)計JCB,后備作業(yè)隊列-算法實現(xiàn)與模擬排序、調(diào)度-輸出調(diào)度結(jié)果，展示調(diào)度過程并解釋【實驗要求】設(shè)計作業(yè)控制塊(JCB)的數(shù)據(jù)結(jié)構(gòu)-應(yīng)包含實驗必須的數(shù)據(jù)項，如作業(yè)ID、需要的服務(wù)時間、進入系統(tǒng)時間、完成時間，以及實驗者認為有必要的其他數(shù)據(jù)項。1. 實現(xiàn)排序算法將作業(yè)排隊-策略1:按“進入系統(tǒng)時間”對

2、作業(yè)隊列排序(FCFS)-策略2:按“需要的服務(wù)時間”對作業(yè)隊列排序SJF實現(xiàn)調(diào)度過程模擬1每個作業(yè)用一個JCB表示，如果模擬FCFS,按策略1將作業(yè)排隊,如果模擬SJF,按策略2將作業(yè)排隊2選擇隊首的作業(yè)，將其從后備隊列移出。3作業(yè)運行過程，在本實驗中，無需實現(xiàn)，可認為后備隊列上的作業(yè)一但被調(diào)度程序選出，就順利運行完畢，可以進入第4步4計算選中作業(yè)的周轉(zhuǎn)時間5進行下一次調(diào)度去往第2步-輸出作業(yè)狀態(tài)表，展示調(diào)度過程?初始作業(yè)狀態(tài)未調(diào)度時?每次調(diào)度后的作業(yè)狀態(tài)-包含實驗要求中14項內(nèi)容，要求有設(shè)計圖結(jié)構(gòu)圖/流程圖和源代碼。-注明使用的編程語言和環(huán)境。注意事項?實驗中注重實現(xiàn)算法本質(zhì)先來先服務(wù)，短

3、作業(yè)優(yōu)先。?兩個算法可以使用一套程序，差異只在隊列的排序方式。?這兩個算法也可適用于進程調(diào)度。關(guān)于作業(yè)調(diào)度和進程調(diào)度的區(qū)別，只要求概念上理解清楚，不要求實現(xiàn)。設(shè)計作業(yè)控制塊(JCB)的數(shù)據(jù)結(jié)構(gòu)每個作業(yè)由一個作業(yè)控制塊JC軟示，JC河以包含如下信息：作業(yè)名、提交時間、所需的運行時間、所需的資源、作業(yè)狀態(tài)、鏈指針等等。具體結(jié)構(gòu)如下：typedefstructjcb(charname10;/*作業(yè)名*/charstate;/*作業(yè)狀態(tài)*/intts;/*提交時間*/floatsuper;/*優(yōu)先權(quán)*/inttb;/*開始運行時間*/inttc;/*完成時間*/floatti;/*周轉(zhuǎn)時間*/floa

4、twi;/*帶權(quán)周轉(zhuǎn)時間*/intntime;/*作業(yè)所需運行時間*/charresource10;/*所需資源*/structjcb*next;/*結(jié)構(gòu)體指針*/JCB;JCB*p,*tail=NULL,*head=NULL;作業(yè)的狀態(tài)可以是等待W(Wait)、運行R(Run)和完成F(Finish)三種狀態(tài)之一。每個作業(yè)的最初狀態(tài)總是等待W,組成一個后備隊列等待，總是首先調(diào)度等待隊列中隊首的作業(yè)。本實驗采用鏈表的形式存放各后備隊列當中的作業(yè)控制塊，各個等待的作業(yè)按照提交時刻的先后次序排隊。當一個作業(yè)進入系統(tǒng)時，就為其動態(tài)建立一作業(yè)控制塊JCB1,掛入后備隊列尾部。當作業(yè)調(diào)度時，從后備隊列中

5、按某種調(diào)度算法選擇一作業(yè)，讓其進入主存以便占用CPUl行。每個作業(yè)完成后要打印該作業(yè)的開始運行時刻、完成時刻、周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間，這一組作業(yè)完成后要計算并打印這組作業(yè)的平均周轉(zhuǎn)時間、帶權(quán)平均周轉(zhuǎn)時間設(shè)計圖WSrttiftW&JJCB便JCE攜作業(yè)提交的時急I的走后I引THUR.7E0nrrgJKt的值:T；TH-FEkKJkz：?tiJ釬慌井打ED這鮑作業(yè)圈平均圈祜時間壓格杖司均同轉(zhuǎn)肘瓦編程語言：C+編程環(huán)境：程序代碼：FCFS:#includeusingnamespacestd;classFcfsprivate:intnum10;作業(yè)編號doublearriveTime10;到達時間do

6、ublestartTime10;/開始時間，進內(nèi)存時間doubleworkTime10;工作時間doublefinishTime10;完成時間doublecirTime10;存放每一個作業(yè)的周轉(zhuǎn)時間/doublefreeTime10;/上一個作業(yè)已結(jié)束，但下一個作業(yè)還未到，存放這一段空閑時間public:Fcfs(intn)/n為作業(yè)數(shù)目cout默認第一個作業(yè)的到達時間為0。endl;for(inti=0;in;i+)numi=i+1;給作業(yè)編號cout第numi”個作業(yè)：endl;coutarriveTimei;if(i=0)arriveTimei=0;默認第一個作業(yè)的到達時間為0coutw

7、orkTimei;if(i=0)startTimei=0;finishTimei=workTimei;/freeTimei=0;elseif(arriveTimeifinishTimei-1)/freeTimei=arriveTimei-finishTimei-1;/計算空閑時間，前一個作業(yè)已完成，但后一個作業(yè)還沒到，中間空閑時間startTimei=arriveTimei;/由于來的時候前一個作業(yè)已完成，則該作業(yè)的開始時間即為它的到達時間finishTimei=startTimei+workTimei;cirTimei=finishTimei-arriveTimei;/計算平均周轉(zhuǎn)時間dou

8、blegetAverageCir(intn)/n為作業(yè)數(shù)doubleaverageCir,sumCir=0;for(inti=0;in;i+)sumCir+=cirTimei;averageCir=sumCir/n;returnaverageCir;打印輸出voidprint(intn)/n為作業(yè)數(shù)coutnumtarrivetstarttworktfinishtcirtendl;for(inti=0;in;i+)coutnumitarriveTimeitstartTimeitworkTimeitfinishTimeitcirTimeitendl;coutendl;cout平均周轉(zhuǎn)時間：get

9、AverageCir(n)endl;intmain()intn;/n為作業(yè)數(shù)目coutn;Fcfsf=Fcfs(n);f.print(n);return0;SJF:#includeusingnamespacestd;classSJF(private:intnum10;作業(yè)編號doublearriveTime10;/到達時間doublestartTime10;/開始時間，進內(nèi)存時間doubleworkTime10;工作時間doublefinishTime10;/完成時間doublecirTime10;存放每一個作業(yè)的周轉(zhuǎn)時間public:SJF(intn)/n為作業(yè)數(shù)目(inti;cout默認第

10、一個作業(yè)的到達時間為0。endl;for(i=0;in;i+)(numi=i+1;/給作業(yè)編號cout第numi”個作業(yè)：endl;coutarriveTimei;if(i=0)arriveTimei=0;/默認第一個作業(yè)的到達時間為0coutworkTimei;if(i=0)(startTimei=0;finishTimei=workTimei;cirTimei=finishTimei-arriveTimei;else/排序(for(intj=1；ji；j+)/i=當前作業(yè)數(shù)目-1，這里不能用numi表示當前作業(yè)數(shù)起泡排序法(for(intk=1;kworkTimek+1)(doublete

11、mp;temp=numk;numk=numk+1;numk+1=temp;temp=arriveTimek;arriveTimek=arriveTimek+1;arriveTimek+1=temp;temp=workTimek;workTimek=workTimek+1;workTimek+1=temp;for(i=1;in;i+)/排序后計算各作業(yè)的開始、結(jié)束、周轉(zhuǎn)時間(startTimei=finishTimei-1;finishTimei=startTimei+workTimei;cirTimei=finishTimei-arriveTimei;/計算平均周轉(zhuǎn)時間doublegetAve

12、rageCir(intn)/n為作業(yè)數(shù)(doubleaverageCir,sumCir=0;for(inti=0;in;i+)sumCir+=cirTimei;averageCir=sumCir/n;returnaverageCir;打印輸出voidprint(intn)/n為作業(yè)數(shù)(coutnumtarrivetstarttworktfinishtcirtendl;for(inti=0;in;i+)(coutnumitarriveTimeitstartTimeitworkTimeitfinishTimeitcirTimeitendl;coutendl;cout平均周轉(zhuǎn)時間：getAverag

13、eCir(n)endl;intmain()(cout短作業(yè)優(yōu)先endl;intn;/n為作業(yè)數(shù)目coutn;SJFf=SJF(n);f.print(n);return0;實例截圖：五個進程，到達時間分別為5,10,13,20服務(wù)時間分別為6,2,4,6設(shè)置選擇量n,當n=1時，選擇FCFS當n=2時，選擇SJF當n=3時，同時分別調(diào)用FCFS和SJFn不為1或2或3時提示錯誤，重新輸入n;1-FCFS算法dp6Finishnle02尼r到執(zhí)tfjmk-xa該高該漆!-w口卜有有1-q配桐R!HH尼行到執(zhí)業(yè)業(yè)r:*K-+司tocontinue均周轉(zhuǎn)時功ressanpkesr2-SJF算法實驗總結(jié):本次實驗題目為作業(yè)調(diào)度。實現(xiàn)實現(xiàn)FCF拼日SJF調(diào)度算法。能初步掌握FCF+日SJF調(diào)度算法。對于FCF拚日SJF調(diào)度算法的思路清晰，只是將其轉(zhuǎn)化為代碼形式，在腦海中，沒有思路。經(jīng)過查閱資料和與同學(xué)們