1、、實驗目的多道程序系統中，當就緒進程數大于處理機數時，須按照某種策略決定哪些進程優先占用處理機。本實驗模擬實現進程調度，以加深對進程概念和不同進程調度算法的理解。二、實驗環境PC 微機。Windows 操作系統。C/C+/VB 等開發集成環境。三、實驗內容與步驟編程實現如下進程調度算法：時間片輪轉調度算法：時間片長度在運行時可從鍵盤輸入。多級反饋隊列調度算法：至少要有三個隊列，第i+1 隊列進程運行的時間片是第隊列的2 倍。高響應比優先調度算法：當調度響應比高的進程運行時，仍然是運行一個時間片，而不是完全結束，剛運行的進程，其以前的等待時間清零。實現提示：PCB 數據結構（參考）PCB 至少包

2、括：進程標識符、進程名、到達時間、服務時間、等待時間、完成時間、響應比等（可根據不同的算法增減）。假設多個PCB 利用鏈接方式進行組織。主要功能模塊（參考）進程初始化；顯示初始化后進程的基本信息；時間片輪轉調度算法；多級反饋隊列調度算法；高響應比優先調度算法；輸入要求：可將進程初始化信息事先存入文件中，程序運行從文件中讀取信息，避免從鍵盤輸入速度慢且易出錯。輸出要求：每種調度算法每次調度后應直觀顯示，進程調度的依據、各進程的各項參數。每種調度算法運行結束后，輸出各個進程對應的完成時間、周轉時間和帶權周轉時間，以及整體的平均帶權周轉時間。四、實驗結果與分析33、高響應比優先調度算法(1)程序的框

3、架說明I I沖H時比質*盾顯產量國取周方屁I I沖H時比質*盾顯產量國取周方屁3)幽質也猶無揖慢啤而(2)各調度算法的設計思想1、時間片輪轉算法該算法采取了非常公平的方式，即讓就緒隊列上的每個進程每次僅運行一個時間 片。如果就緒隊列上有N個進程，則每個進程每次大約都可獲得1/N的處理機時 問。時間片的大小對于系統性能有很大的影響。 若選擇很小的時間片，將有利于 短作業，但意味著會頻繁地執行進程調度和進程上下文的切換，這無疑會增加系統的開銷。反之，若時間片選擇得太長，且為使每個進程都能在一個時間片內完 成，RRB法便退化為FCFST法，無法滿足短作業和交互式用戶的需求。進程的 切換時機體現出RR

4、算法的特點。若一個進程在時間片還沒結束時就已完成，此 時立即激活調度程序，將它從執行隊列中刪除。若一個進程在時間片結束時還未 運行完畢，則調度程序將把它送往就緒隊列的末尾，等待下一次執行。2、多級反饋隊列調度算法1、進程在進入待調度的隊列等待時，首先進入優先級最高的Q1等待。2、首先調度優先級高的隊列中的進程。若高優先級中隊列中已沒有調度的進程， 則調度次優先級隊列中的進程。例如： Q1,Q2,Q3三個隊列，只有在Q1中沒有進 程等待時才去調度Q2,同理，只有Q1,Q2都為空時才會去調度Q33、對于同一個隊列中的各個進程，按照時間片輪轉法調度。比如Q1隊列的時間 片為N,那么Q1中的作業在經歷

5、了 N個時間片后若還沒有完成，則進入 Q2隊列 等待，若Q2的時間片用完后作業還不能完成，一直進入下一級隊列，直至完成。 4、在低優先級的隊列中的進程在運行時，又有新到達的作業，那么在運行完這 個時間片后，CPU上分配給新到達的作業(搶占式)。33、多級反饋隊列調度算法一種動態優先調度算法，它以相應比作為作業或進程的動態優先權， 其目的是既 照顧短作業，又考慮到作業的等待時間，使長作業不會長期等待；但每次調度前， 都要進行響應比計算，會增加系統開銷。(3)實驗結果1.RR算法 EMsudl ShJdid Prdjec t w占題 II n訊15由.201 ? I ftLexe青輸入時間片的大小

6、Y依行時闈片拈傳面傳呼法臟銀P2進入就緒隊列內等恃史程P進入過靖隊列內等侍回前時間為泮區小 進程曲P2；到達時皿為要求來?m聞5;刷余取勢時間工1 洸程.P3進人就端隊列內警恃當前時間為42報疔：迸程名：PS；到時間：4-要求服務時間I 7：剿奈噩務時間：3進程P1出.X西結隊列內等待，前時間為：16執行，進程作P3;到葩時回：8;要求服務時間：制和余服務時間；1 進程P4進入就緒網列內峰恃當M時間為t20執仔：道他名：P2;到班時間：2:要求服務時間：副剌*服務時間:0 心棺酎間為:M技廳：起程名1 Plr .利達時間r 10:轅求用；算時司：4: F除堰今葉I可：0 當前時間為：28執行；

7、進程名：P6；型/時間：生要求噩棄時間：7；剁余眼符時間二0當前時間為：32執仃；出程加 M 刎達時啊】乳驍求戰外時間；瓢上氽服務時間:0 當R時間為：36執廳;進程名：P3；勤電時間：的 要求里得時間：5;剩余里務時間：O乩741 44*444*4*4*+144*4*444中一*31441*啊*44祖坦名到總時間版著時間完應時間封轉時間鬲杖周拈時間 TOC o 1-5 h z P22520183P5472R243P3E53C285F110424143P413232199平應忙出sm時聞46卜* *444 *1*申* 申*+4l44*中*4* * 卡2、HRN算法11入n卜”丫 11 ；髭M網

8、席泡:；： ；而叫不出防丐口出“市：*X調質鼻啟尚久出就需隊則內呼梏鼎碼明比伏兀凋庠*沆號前時間為:？覽L:進程名工期到達附畫.E：鎏求黑多忖間:加熱雜H尊時間13ififfPS 4時玷逆再咻科i前時司內門尚久出就需隊則內呼梏鼎碼明比伏兀凋庠*沆號前時間為:？覽L:進程名工期到達附畫.E：鎏求黑多忖間:加熱雜H尊時間13ififfPS 4時玷逆再咻科i前時司內門tfi遇桂名士園F馴店忖間工備要求鵬招時向：篇親M存時刊：叱FTP避人前擊隊列內等片11m時同去饋ffl.tr；題程名=P2；到店時皿2；費或總務時詠融朝能2落時期 3比膽”期人斷幫認則內事梢h超時同為;】。帆行；ififiSi F2j

9、到5f同：Z;要里齦弄時呵：依泰(余K等時臥2 口地，倒人就璃丸皿內幕帶行而忖列內;1、 他上：進標南：寸翻時間為:黑 枸斤；今苒時間為：24 他杷出超唐二 1ti肝時間內!29 次七二港程招工 當命時同育:熱 他.打：電/名I到達時間;P1:到也時間:到工節同二Z：要求般務時間：5：抱親能務時間：0I3i 0戲解學時間：3j嘉余孤務時憫:010.要求雅委附間翼宗腥器時間二0利上財同：4：要求m勢所近1 71 M津n用時網 0kttt + f* + t + *1*t*+=* * *，I- T T r T T忸程名物達時向 鼬勢酎問 之成時何 閨線時間 用打展轉打回I& 酒 J1.24 2Die

10、1?2111平均帶權周轉時同;獴4* * * *事*1 *事事革單單 * * * * * A * * *U濟輸入以卜一數丁（1： 響片輪到7度津法：2： 白繳反胃隊列用咬算法：3：點則它比比 3請輸入第級隊列的時間片的大小:2m程P2理人就盤隊列內等行名或反笛認列謂變克法當前時間為：2執行：進程名：P2t到達時間：2；要求般分時間: 5；刎余版務時間：3進程Pa進入就緒隊列內等待當前時間為:4執了：進程名：P5；到達時間：4：理求職務時間：7：刊登出號時間；5當前時間為：11執行；進程名；P2;到達時間：2；要求版務時間* 5:剩余康務時間；0進程3進入就緒隊列內等待進程P1進入就緒隊列內等待

11、當前時間為：口執行;進程名：P3；到達時間；3;要求服務時間，5；剩余期務時間；3進程F4.也入徜繩隊列內等恃當前時間為：L3執行；進程名：P1；到達時間：10；要求服務時間：4;剩余服務時間：2當前時間為：15執行，進隹名：P*到達時間t 11要求服勢時間：2：剩余服務時間，0當前時間為：17執仃：避程名：PS；到達時間：丸要求般蘇時間：7;剌余用.務時間：1當薊時間為:26執才門進程名: P3:到達忖間；8要求員外時間* 5:剌余昵為時間：0 當前時間為加執廳上進程名：Ph到達時間：1口：要求服務時間：4；劇余藤務時間:。當前時網為:賽執行二迸程名:P/到達時間；13;要求服務時間：2:超

12、余服務時間：。節前時間為：39執行F進程左 國器到達時間：工要求服務時間f 1則奈暇莠時間：0，*1|*1|*相仁*率*1|8*率*事*率進程到達時間服務時間定成時間冏轉時網帶被冏轉時間P2591困739355P352&183PL)0430205P413232199怦均帶氣周轉時間:4. 6*#，：*會后率4年+字字導豐字學辛豐奉學學學學豐字*+*零辛*4=*奈率號*+*(4)實驗源程序#include #include algorithm#include vector#include #include string using namespacestd;class JCB public :i

13、nt id; /進程標識符string name; / 進程名int arriveTime; / 到達時間int serveTime; /要求服務時間int waitTime; /等待時間，只用于最高響應比優先調度算法中int finshTime; / 完成時間int roundTime; / 周轉時間double clock = 0; /記錄該進程真實服務時間已經用時的時長，用于在時間輪轉調度算法中比 較當前進程能否在當前時間片執行完畢double weightingRoundTime; / 帶權周轉時間JCB() JCB(string name, int arriveTime , int

14、serveTime , double priority ) this -name = name;this -arriveTime = arriveTime ;this -serveTime = serveTime ;this -waitTime = 0; / 初始等待時間置0void printInf() cout 進程名： name ；到達時間： arriveTime ；要求服務時間： serveTime ；剩余服務時間： (serveTime - clock) 0 ? 0 : (serveTime - clock) endl;/ 按照到達時間升序bool cmp_arrvieTime_as

15、cend( JCB j1 , JCB j2 ) return j1 .arriveTime j2 .weightingRoundTime;/ 作業調度基礎類class JobScheduling public :vector process; / 存放所有進程JCBnowPro; / 當前應執行進程int k = 0; / process 中的進程遍歷時的下標int nowTime = 0; / 當前時間void printProcess() double aveRoundTime = 0;cout *cout * endl;cout 進程名到達時間服務時間完成時間周轉時間帶權周轉時間 end

16、l;for ( int i = 0; i process.size(); +i) aveRoundTime += process i .weightingRoundTime; cout process i .name process i .arriveTime process i .serveTime process i .finshTime process i .roundTimeprocess i .weightingRoundTime endl;cout 平均帶權周轉時間: aveRoundTime / process.size() endl;process.clear();cout ”

17、*”cout ”*” endl;/ 時間片輪轉調度算法class RR: public JobScheduling public :queue RRQueue;/ 就緒隊列 double sliceTime;RR(vector jcb , double sliceTime ) this -process = jcb ; this -sliceTime = sliceTime ; / 初始對所有進程按到達時間進行排序 sort(process.begin(), process.end(), cmp_arrvieTime_ascend); void run() cout 執行時間片輪轉調度算法 e

18、ndl;Enqueue(); while (!RRQueue.empty() | k process.size() Dequeue(); / 出隊， 因為如果時間片結束當前進程未執行完又到達了新的進程，需要讓剛到達的進程先進隊列，再讓當前進程進隊列，所以進隊操作寫在這個函數里了 / 輸出進程運行信息 printProcess(); void Enqueue() / 進程進入就緒隊列while (k process.size() / 當遍歷完jcb 中的所有進程時結束if (process k .arriveTime = nowTime) / 已經到達的進程按到達時間先后進入隊process k

19、 .id = k;cout 進程 process k .name 進入就緒隊列內等待 endl;RRQueue.push(process k );k+;else break; / 如果該進程還未到達，結束遍歷。void Dequeue() nowTime += sliceTime; / 更新當前時間/ 如果就緒隊列不為空if (!RRQueue.empty() nowPro = RRQueue.front(); / 獲取隊首元素RRQueue.pop(); / 移除隊列的隊首元素nowPro.clock += sliceTime; / 更新當前進程的實際服務時間cout 當前時間為: nowT

20、ime endl;cout = nowPro.serveTime) nowPro.finshTime = nowTime; / 計算該進程完成時間nowPro.roundTime = nowPro.finshTime - nowPro.arriveTime; / 計算周轉時間nowPro.weightingRoundTime = nowPro.roundTime / nowPro.serveTime; / 計算 帶權周轉process nowPro.id = nowPro; / 更新 jcb 中的進程信息else / 當前進程未運行完Enqueue(); / 已到達的進程先入隊RRQueue.

21、push(nowPro);/ 上一輪出的再緊接著進入隊尾 else / 如果就緒隊列為空，則執行入隊Enqueue();class HRN: public JobScheduling public :vector HRNQueue;/ 就緒隊列HRN(vector jcb ) process = jcb ;/ 初始化帶權輪轉時間為1for ( int i = 0; i process.size(); i+) process i .weightingRoundTime = 1;/ 按到達時間升序排序sort(process.begin(), process.end(), cmp_arrvieTi

22、me_ascend);void run() / 最高響應比優先調度算法nowTime = process 0 .arriveTime;Enqueue();cout 最高響應比優先調度算法 endl;while (!HRNQueue.empty()|kprocess.size() / 如果將要執行的進程執行完畢之前，下一個進程都不會到來if (k = process.size() | nowTime + (HRNQueue 0 .serveTime -HRNQueue0 .clock) process k .arriveTime) Dequeue(); / 出隊/ 下一個進程執行到一半，會出現被

23、新到來的進程搶占的可能else int time = process k .arriveTime - nowTime;Dequeue(time);Enqueue(); / 已到達的進程入隊sort(HRNQueue.begin(),HRNQueue.end(),cmp_weightingRoundTime_descend); / 隊列中的進程按響應比進行排序printProcess();void Enqueue() / 進程入隊，可一次進多個while (k process.size() / 當遍歷完jcb 中的所有進程時結束if (process k .arriveTime = nowTim

24、e) / 已經到達的進程按到達時間先后進入隊列process k .id = k;cout 進程 process k .name 進入就緒隊列內等待 endl;HRNQueue.push_back(process k );k+;else break;/如果該進程還未入隊，即先結束遍歷，保留當前下標k值，注意：此處不要k- ；void Dequeue() if (!HRNQueue.empty() nowPro = HRNQueue0 ;/ 移除隊列的隊首元素并且返回該對象元素HRNQueue.erase(HRNQueue.begin();/nowProess.beginTime = nowTi

25、me;/ 計算開始時間，即為上一個進程的結束時間nowPro.finshTime = nowTime + nowPro.serveTime; / 計算結束時間，該進程開始時 間 +服務時間nowPro.roundTime = nowPro.finshTime - nowPro.arriveTime; / 計算周轉時間 nowPro.weightingRoundTime = nowPro.roundTime / nowPro.serveTime; / 計算帶權 周轉時間nowTime = nowPro.finshTime; / 獲得結束時間，即當前時間，方便判斷剩下的進程是否已到達nowPro.

26、clock = nowPro.serveTime;cout 當前時間為: nowTime endl;cout 執行： ;nowPro.printInf();process nowPro.id = nowPro;for ( int i = 0; i HRNQueue.size(); +i) HRNQueuei .waitTime += nowPro.serveTime; / 所有進入等待隊列的進程等待時間 +1HRNQueuei .weightingRoundTime = (HRNQueue i .waitTime + HRNQueuei .serveTime) / ( double )HRNQ

27、ueuei .serveTime;void Dequeue( int time ) if (!HRNQueue.empty() nowPro = HRNQueue0 ;/ 該進程不會執行完畢，無需移除nowPro.clock += time ;cout 當前時間為: nowTime endl;cout 執行： ;nowPro.printInf();nowTime += time ;process nowPro.id = nowPro;for ( int i = 0; i HRNQueue.size(); +i) HRNQueuei .waitTime += time ; / 所有進入等待隊列的

28、進程等待時間+1HRNQueuei .weightingRoundTime = (HRNQueue i .waitTime + HRNQueuei .serveTime) / ( double )HRNQueuei .serveTime;class MFQ: public JobScheduling public :queue queue3;double sliceTime3;int sign;MFQ(vector jcb , double sliceTime ) this -sliceTime0 = sliceTime ;this -sliceTime1 =this -sliceTime0

29、* 2;this -sliceTime2 =this -sliceTime1 * 2;process = jcb ;sort(process.begin(), process.end(), cmp_arrvieTime_ascend); void run() nowTime = process 0 .arriveTime;Enqueue(0);cout 多級反饋隊列調度算法 endl;while (k = sliceTime0) /cout 0 endl;Dequeue(sliceTime0);else /cout 1 endl;Dequeue();Enqueue(0);while (!que

30、ue1.empty() /cout 1 = sliceTime1) Dequeue(sliceTime1);else Dequeue();Enqueue(0);if (queue0.size() 0) break; / 如果第一級隊列中新到來了進程/ 到最后一個隊列，直接實行FCFSwhile (!queue2.empty() /cout 2 0) break; / 如果第一級隊列中新到來了進程printProcess();void Enqueue( int sign ) / 進程入隊，可一次進多個while (k process.size() / 當遍歷完jcb 中的所有進程時結束if (p

31、rocess k .arriveTime = nowTime) / 已經到達的進程按到達時間先后進入隊列process k .id = k;cout 進程 process k .name 進入就緒隊列內等待 endl;queue sign .push(process k );k+;else break;/如果該進程還未入隊，即先結束遍歷，保留當前下標k值，注意：此處不要 k- ；void Dequeue() if (!queuesign.empty() nowPro = queuesign.front(); / 移除隊列的隊首元素并且返回該對象元素queuesign.pop();/nowProess.beginTime = nowTime;/ 計算開始時間，即為上一個進程的結束時間nowPro.finshTime = nowTime + nowPro.serveTime; / 計算結束時間，該進程開始時 間 +服務時間nowPro.roundTime = nowPro.finshTime - nowPro.arriveTime; / 計算周轉時間nowPro.weightingRoundTime = nowPro.roundTime / nowPro.serveTime; / 計算帶權周轉時間nowTime = nowPro.fins