優(yōu)先級法、非強占式短進程優(yōu)先算法

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

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

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

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

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

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

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

8、涉及五個模塊（結構體定義，要處理進程信息的輸入，兩種算法的實現(xiàn)，處理完畢后進程信息的輸出，主函數(shù)） （1）結構體定義如上所示 （2）進程信息的輸入 void input(PRO *p,int n) P為結構體數(shù)組名，n為進程個數(shù)。 （3）兩種算法的實現(xiàn) 優(yōu)先級算法的具體實現(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);/基于時間的排序同時處理多個進程同時到達情況。 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)先級高的執(zhí)行deal(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N,xy); /將排好序的進程處理計算出其周轉時間和帶權周轉時間 print(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N,xy); /輸出處理完畢后進程信息 非搶占式短作業(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);/按到達時間進行排序 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個進程執(zhí)行完之前有多少個進程需要進行比較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ù)組最前面 deal(p,arrivetime,servicetime,starttime,finishtime,zztime,dq

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

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

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

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