優(yōu)先級(jí)法、非強(qiáng)占式短進(jìn)程優(yōu)先算法

1、精選優(yōu)質(zhì)文檔-傾情為你奉上學(xué) 號(hào)： 課 程 設(shè) 計(jì)題 目進(jìn)程調(diào)度模擬設(shè)計(jì)優(yōu)先級(jí)法、非強(qiáng)占式短進(jìn)程優(yōu)先算法學(xué) 院計(jì)算機(jī)專 業(yè)班 級(jí)姓 名指導(dǎo)教師 吳利軍2013年1月16日課程設(shè)計(jì)任務(wù)書學(xué)生姓名： 指導(dǎo)教師： 吳利軍 工作單位： 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 題 目: 進(jìn)程調(diào)度模擬設(shè)計(jì)優(yōu)先級(jí)法、非強(qiáng)占式短進(jìn)程優(yōu)先算法初始條件：1預(yù)備內(nèi)容：閱讀操作系統(tǒng)的處理機(jī)管理章節(jié)內(nèi)容，對(duì)進(jìn)程調(diào)度的功能以及進(jìn)程調(diào)度算法有深入的理解。2實(shí)踐準(zhǔn)備：掌握一種計(jì)算機(jī)高級(jí)語言的使用。要求完成的主要任務(wù): （包括課程設(shè)計(jì)工作量及其技術(shù)要求，以及說明書撰寫等具體要求）1模擬進(jìn)程調(diào)度，能夠處理以下的情形： 能夠選擇不同的調(diào)度算法（要求

2、中給出的調(diào)度算法）； 能夠輸入進(jìn)程的基本信息，如進(jìn)程名、優(yōu)先級(jí)、到達(dá)時(shí)間和運(yùn)行時(shí)間等； 根據(jù)選擇的調(diào)度算法顯示進(jìn)程調(diào)度隊(duì)列； 根據(jù)選擇的調(diào)度算法計(jì)算平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。2設(shè)計(jì)報(bào)告內(nèi)容應(yīng)說明： 需求分析； 功能設(shè)計(jì)（數(shù)據(jù)結(jié)構(gòu)及模塊說明）； 開發(fā)平臺(tái)及源程序的主要部分； 測試用例，運(yùn)行結(jié)果與運(yùn)行情況分析； 自我評(píng)價(jià)與總結(jié)：i）你認(rèn)為你完成的設(shè)計(jì)哪些地方做得比較好或比較出色；ii）什么地方做得不太好，以后如何改正；iii）從本設(shè)計(jì)得到的收獲（在編寫，調(diào)試，執(zhí)行過程中的經(jīng)驗(yàn)和教訓(xùn)）；iv）完成本題是否有其他方法（如果有，簡要說明該方法）；時(shí)間安排：設(shè)計(jì)安排一周：周1、周2：完成程序分析及設(shè)

3、計(jì)。周2、周3：完成程序調(diào)試及測試。周4、周5：驗(yàn)收、撰寫課程設(shè)計(jì)報(bào)告。（注意事項(xiàng)：嚴(yán)禁抄襲，一旦發(fā)現(xiàn)，一律按0分記）指導(dǎo)教師簽名： 年 月 日系主任（或責(zé)任教師）簽名： 年 月 日 進(jìn)程調(diào)度模擬設(shè)計(jì) -優(yōu)先級(jí)法、非強(qiáng)占式短進(jìn)程優(yōu)先算法一問題描述 設(shè)計(jì)一程序模擬進(jìn)程調(diào)度，能夠選擇優(yōu)先級(jí)和非搶占短作業(yè)兩種算法對(duì)進(jìn)程調(diào)度?？梢暂斎胂嚓P(guān)進(jìn)程信息（進(jìn)程名，達(dá)到時(shí)間，執(zhí)行時(shí)間，優(yōu)先級(jí)），最終能顯示進(jìn)程調(diào)度的序列。并能顯示這些進(jìn)程的平均周轉(zhuǎn)時(shí)間和帶權(quán)平均周轉(zhuǎn)時(shí)間。二需求分析 通過設(shè)計(jì)一個(gè)模擬進(jìn)程調(diào)度的系統(tǒng)，來實(shí)現(xiàn)進(jìn)程調(diào)度，對(duì)進(jìn)程調(diào)度的功能以及進(jìn)程調(diào)度算法有一個(gè)更加深入的理解。 進(jìn)程PCB（包含進(jìn)程名、到達(dá)

4、時(shí)間、預(yù)計(jì)運(yùn)行時(shí)間） 調(diào)度算法（優(yōu)先級(jí)、非強(qiáng)占式短進(jìn)程優(yōu)先） 模擬進(jìn)程調(diào)度，能夠處理以下的情形： 能夠選擇不同的調(diào)度算法（要求中給出的調(diào)度算法）； 能夠輸入進(jìn)程的基本信息，如進(jìn)程名、到達(dá)時(shí)間和運(yùn)行時(shí)間等； 根據(jù)選擇的調(diào)度算法顯示進(jìn)程調(diào)度隊(duì)列； 根據(jù)選擇的調(diào)度算法計(jì)算平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。 此次做的進(jìn)程調(diào)度模擬系統(tǒng)，用戶可以輸入各進(jìn)程信息（包含進(jìn)程名、到達(dá)時(shí)間、運(yùn)行時(shí)間）。輸入進(jìn)程數(shù)，然后輸入進(jìn)程的提交時(shí)間和運(yùn)行時(shí)間，顯示優(yōu)先級(jí)和非強(qiáng)占式短進(jìn)程優(yōu)先調(diào)度算法的進(jìn)程名、提交時(shí)間、運(yùn)行時(shí)間、開始時(shí)間、結(jié)束時(shí)間、周轉(zhuǎn)時(shí)間、帶權(quán)周轉(zhuǎn)時(shí)間、執(zhí)行時(shí)間、平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。 優(yōu)先級(jí)法： 優(yōu)

5、先級(jí)法可被用做作業(yè)或進(jìn)程的調(diào)度策略。首先，系統(tǒng)或用戶按某種原則為作業(yè)或進(jìn)程指定一個(gè)優(yōu)先級(jí)來表示該進(jìn)程或作業(yè)所享有的優(yōu)先權(quán)。改算法的核心是確定進(jìn)程或作業(yè)的優(yōu)先級(jí)。 確定優(yōu)先級(jí)的方法可分為兩類。即靜態(tài)法和動(dòng)態(tài)法。 靜態(tài)法根據(jù)作業(yè)的或進(jìn)程的靜態(tài)特性，在作業(yè)或進(jìn)程開始執(zhí)行前就確定它們的優(yōu)先級(jí)，一旦開始執(zhí)行之后就不能改變。動(dòng)態(tài)法則不然，它把作業(yè)或進(jìn)程的靜態(tài)特性結(jié)合起來確定作業(yè)或進(jìn)程的優(yōu)先級(jí)，隨著作業(yè)或進(jìn)程的執(zhí)行過程，其優(yōu)先級(jí)不斷變化。 非搶占短作業(yè)優(yōu)先法： 不可搶占式 Non-preemptive（非剝奪式）：某一進(jìn)程被調(diào)度運(yùn)行后，除非由于它自身的原因不能運(yùn)行，否則一直運(yùn)行下去。 短作業(yè)優(yōu)先調(diào)度算法(S

6、JF, Shortest Job First)，又稱為“短進(jìn)程優(yōu)先”SPN(Shortest Process Next)；這是對(duì)FCFS算法的改進(jìn)，其目標(biāo)是減少平均周轉(zhuǎn)時(shí)間?；舅枷耄簩?duì)預(yù)計(jì)執(zhí)行時(shí)間短的作業(yè)（進(jìn)程）優(yōu)先處理。通常后來的短作業(yè)不搶先正在執(zhí)行的作業(yè)。在一般情況下這種調(diào)度算法比先來先服務(wù)調(diào)度算法的效率要高一些。實(shí)現(xiàn)相對(duì)先來先服務(wù)調(diào)度算法要困難些，如果作業(yè)的到來順序及運(yùn)行時(shí)間不合適，會(huì)出現(xiàn)餓死現(xiàn)象，例如，系統(tǒng)中有一個(gè)運(yùn)行時(shí)間很長的作業(yè)J，和幾個(gè)運(yùn)行時(shí)間小的作業(yè)，然后，不斷地有運(yùn)行時(shí)間小于J的作業(yè)的到來，這樣，作業(yè)J就得不可調(diào)度而餓死。另外，作業(yè)運(yùn)行的估計(jì)時(shí)間也有問題。三功能設(shè)計(jì) 1.數(shù)

7、據(jù)結(jié)構(gòu) 在此次課程設(shè)計(jì)中主要采用了結(jié)構(gòu)體數(shù)組的存儲(chǔ)方式，將一個(gè)進(jìn)程信息存儲(chǔ)在一個(gè)結(jié)構(gòu)體中，包括進(jìn)程名稱、進(jìn)程優(yōu)先級(jí)、進(jìn)程提交時(shí)間、進(jìn)程運(yùn)行時(shí)間、進(jìn)程周轉(zhuǎn)時(shí)間。具體實(shí)現(xiàn)如下：struct PROchar name10;/進(jìn)程名float arrivetime;進(jìn)程時(shí)間float servicetime;/進(jìn)程執(zhí)行時(shí)間float starttime;/開始時(shí)間float finishtime;/完成時(shí)間int xy; /優(yōu)先級(jí)float zztime;/周轉(zhuǎn)時(shí)間float dqzztime;/帶權(quán)周轉(zhuǎn)時(shí)間; 2.程序流程框圖 優(yōu)先級(jí) 非搶占式短作業(yè)優(yōu)先 綜合流程圖 3.模塊說明 本次課程設(shè)計(jì)中一共

8、涉及五個(gè)模塊（結(jié)構(gòu)體定義，要處理進(jìn)程信息的輸入，兩種算法的實(shí)現(xiàn)，處理完畢后進(jìn)程信息的輸出，主函數(shù)） （1）結(jié)構(gòu)體定義如上所示 （2）進(jìn)程信息的輸入 void input(PRO *p,int n) P為結(jié)構(gòu)體數(shù)組名，n為進(jìn)程個(gè)數(shù)。 （3）兩種算法的實(shí)現(xiàn) 優(yōu)先級(jí)算法的具體實(shí)現(xiàn) void YX(PRO *p,int N)float arrivetime=0,servicetime=0,starttime=0,finishtime=0,zztime=0;float dqzztime;int xy=0;sortxy(p,N);/基于時(shí)間的排序同時(shí)處理多個(gè)進(jìn)程同時(shí)到達(dá)情況。 for(int m=0;m&

9、lt;N-1;m+) if(m=0) pm.finishtime=pm.arrivetime+pm.servicetime; else pm.finishtime=pm-1.finishtime+pm.servicetime; int i=0; for(int n=m+1;n<=N-1;n+) if(pn.arrivetime<=pm.finishtime) i+; float min=pm+1.xy; int next=m+1;/m+1=n for(int k=m+1;k<m+i;k+) if(pk+1.xy<min) min=pk+1.xy; next=k+1; P

10、RO temp; temp=pm+1; pm+1=pnext; pnext=temp; /令優(yōu)先級(jí)高的執(zhí)行deal(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N,xy); /將排好序的進(jìn)程處理計(jì)算出其周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間 print(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N,xy); /輸出處理完畢后進(jìn)程信息 非搶占式短作業(yè)優(yōu)先 void SJF(PRO *p,int N)float arrivetime=0,servicet

11、ime=0,starttime=0,finishtime=0,zztime=0;float dqzztime=0;int xy=0; sortt(p,N);/按到達(dá)時(shí)間進(jìn)行排序 printf(); for(int m=0;m<N-1;m+) if(m=0) pm.finishtime=pm.arrivetime+pm.servicetime; else pm.finishtime=pm-1.finishtime+pm.servicetime; int i=0; for(int n=m+1;n<=N-1;n+) if(pn.arrivetime<=pm.finis

12、htime) i+; /得出在第m+1個(gè)進(jìn)程執(zhí)行完之前有多少個(gè)進(jìn)程需要進(jìn)行比較float min=pm+1.servicetime; int next=m+1;/m+1=n for(int k=m+1;k<m+i;k+) if(pk+1.servicetime<min) min=pk+1.servicetime; next=k+1; / PRO temp; temp=pm+1; pm+1=pnext; pnext=temp; /將執(zhí)行時(shí)間最短的進(jìn)程放在數(shù)組最前面 deal(p,arrivetime,servicetime,starttime,finishtime,zztime,dq

13、zztime,N,xy); /將排好序的進(jìn)程處理計(jì)算出其周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間 print(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N,xy); /輸出處理完畢后進(jìn)程信息 （4）處理完進(jìn)程信息的輸出 void print(PRO *p,float arrivetime,float servicetime,float starttime,float finishtime,float zztime,float dqzztime,int N,int xy) （5）主函數(shù) 主要設(shè)計(jì)一個(gè)菜單功能。四開發(fā)平臺(tái)及源代碼主要部

14、分 1.開發(fā)平臺(tái) Visual Stdio 2010 2.源代碼主要部分 五測試用例，運(yùn)行結(jié)果與運(yùn)行情況分析 1.測試優(yōu)先級(jí)進(jìn)程在同一時(shí)刻到達(dá)進(jìn)程名進(jìn)程到達(dá)時(shí)間進(jìn)程執(zhí)行時(shí)間進(jìn)程優(yōu)先級(jí)a023b042c071可以得出當(dāng)進(jìn)程同時(shí)到達(dá)時(shí)，按優(yōu)先級(jí)順序執(zhí)行。當(dāng)進(jìn)程不是同時(shí)到達(dá)，且優(yōu)先級(jí)高的到的比較晚。進(jìn)程名進(jìn)程到達(dá)時(shí)間進(jìn)程執(zhí)行時(shí)間優(yōu)先級(jí)a033b142c651從這個(gè)實(shí)例可以得出盡管c的優(yōu)先級(jí)最高，但它最后到達(dá)，所以在c之前會(huì)執(zhí)行已到達(dá)的進(jìn)程。當(dāng)進(jìn)程不是全部同時(shí)到達(dá)，但有部分同時(shí)到達(dá)。進(jìn)程名進(jìn)程到達(dá)時(shí)間進(jìn)程執(zhí)行時(shí)間優(yōu)先級(jí)a122b063c171盡管b的優(yōu)先級(jí)最低，但其最先到達(dá)，所以最先執(zhí)行，由于a，c進(jìn)

15、程，c進(jìn)程的優(yōu)先級(jí)高，所以c先執(zhí)行。2.測試非搶占短作業(yè)優(yōu)先 當(dāng)進(jìn)程同時(shí)到達(dá)進(jìn)程名進(jìn)程到達(dá)時(shí)間進(jìn)程處理時(shí)間優(yōu)先級(jí)a051b012c023由于同時(shí)到達(dá)，那個(gè)進(jìn)程執(zhí)行時(shí)間短就先執(zhí)行。 當(dāng)進(jìn)程全部不是同時(shí)到達(dá)進(jìn)程名進(jìn)程到達(dá)時(shí)間進(jìn)程執(zhí)行時(shí)間優(yōu)先級(jí)a321b462c913盡管c的執(zhí)行時(shí)間最短，但因?yàn)槠渥詈蟮竭_(dá)，之前cpu空閑，所以就先執(zhí)行完前面到達(dá)的進(jìn)程。 當(dāng)進(jìn)程不是全部同時(shí)到達(dá)，但存在部分同時(shí)到達(dá)。 進(jìn)程名進(jìn)程到達(dá)時(shí)間進(jìn)程執(zhí)行時(shí)間優(yōu)先級(jí)a131b122c463當(dāng)有同時(shí)到達(dá)的進(jìn)程時(shí)，按照其執(zhí)行時(shí)間排序，讓執(zhí)行時(shí)間短的進(jìn)程先執(zhí)行。六自我評(píng)價(jià)與總結(jié)1.本系統(tǒng)的特點(diǎn) 本系統(tǒng)是在數(shù)據(jù)結(jié)構(gòu)上采用了結(jié)構(gòu)體數(shù)組，這樣

16、使得進(jìn)程的信息顯得簡單，明了，從而也為系統(tǒng)的設(shè)計(jì)降低了難度。再者本系統(tǒng)在設(shè)計(jì)的過程中，各個(gè)模塊結(jié)構(gòu)清晰，功能明確。在很多地方實(shí)現(xiàn)了代碼重用，從而減少了代碼的長度。并且本系統(tǒng)考慮到了諸多情況，相對(duì)比較完善。2.本系統(tǒng)的缺點(diǎn) 由于本系統(tǒng)采用的是結(jié)構(gòu)體數(shù)組，進(jìn)程的信息全部存與p這個(gè)數(shù)組中，導(dǎo)致輸入的信息最大不能超過p這個(gè)數(shù)組的初始長度。由于進(jìn)程的時(shí)間一般涉及的都是毫秒級(jí)或者更小的單位，所以本系統(tǒng)中時(shí)間采用的是邏輯上的時(shí)間。當(dāng)沒有進(jìn)程執(zhí)行時(shí)，CPU怎么利用沒有考慮。3.經(jīng)驗(yàn)與小結(jié)通過本次課程設(shè)計(jì)使我對(duì)進(jìn)程調(diào)度的算法在實(shí)踐中有重新學(xué)習(xí)了一遍，從而理解的也就更深刻。從而也就對(duì)各個(gè)算法的優(yōu)缺點(diǎn)有了更直觀的認(rèn)識(shí)。在測試用例中可以看到短進(jìn)程優(yōu)先法在處理時(shí)間問題上有很大的意義，可以有效地縮短平均周轉(zhuǎn)時(shí)間以及平均帶權(quán)周轉(zhuǎn)時(shí)間，而優(yōu)先級(jí)法卻可以讓某些重要的進(jìn)程優(yōu)先執(zhí)行，兩種方法各有所長。在本次設(shè)計(jì)中，發(fā)現(xiàn)小錯(cuò)誤不斷，耽誤了不少時(shí)間。比如比較運(yùn)算符和算術(shù)運(yùn)算符弄混，中英文輸入格式不對(duì)等等；這寫錯(cuò)誤的改正需要我們養(yǎng)成良好的編程習(xí)慣。通過本次課程設(shè)計(jì)也使我體會(huì)到了我們應(yīng)該怎樣解決問題。首先應(yīng)該分析問題，應(yīng)從哪里著手去解決問題，而不是一拿到問題就去寫代碼。只要分析正確，就可以使我們?cè)诤竺娴膶?shí)現(xiàn)過程中事半