進程調(diào)度模擬設(shè)計――先來先服務(wù)、優(yōu)先級法

1、學(xué) 號： 2課 程 設(shè) 計題 目進程調(diào)度模擬設(shè)計先來先服務(wù)、優(yōu)先級法學(xué) 院計算機科學(xué)與技術(shù)學(xué)院專 業(yè)計算機科學(xué)與技術(shù)專業(yè)班 級計算機009班姓 名 永指導(dǎo)教師 汪祥莉 2012年01月13日 目錄課程設(shè)計任務(wù)書.21.需求分析.3 1.1設(shè)計目的.3 1.2設(shè)計要求.32.功能設(shè)計.3 2.1數(shù)據(jù)結(jié)構(gòu).3 2.2先來先服務(wù)算法設(shè)計.4 2.2.1先來先服務(wù)算法的定義及說明.4 2.3優(yōu)先級算法的設(shè)計.6 2.3.1優(yōu)先級算法的定義及說明.6 2.3.2優(yōu)先級進程調(diào)度及實現(xiàn)過程.6 2.3.3優(yōu)先級調(diào)度流程圖.10 2.4進程參數(shù)的輸入.11 2.5調(diào)度結(jié)果的輸出.123.源程序的主要部分.12

2、4.程序測試.14 4.1先來先服務(wù)測試用例.14 4.2先來先服務(wù)運行結(jié)果.15 4.3優(yōu)先級算法測試用例.15 4.4優(yōu)先級算法運行結(jié)果.165.程序流程圖.176.自我評價與總結(jié).187.源程序清單.19課程設(shè)計任務(wù)書學(xué)生姓名： 永 專業(yè)班級： 計算機0909班 指導(dǎo)教師： 汪祥莉 工作單位： 計算機科學(xué)與技術(shù)學(xué)院 題 目: 進程調(diào)度模擬設(shè)計先來先服務(wù)、優(yōu)先級法 初始條件：1預(yù)備內(nèi)容：閱讀操作系統(tǒng)的處理機管理章節(jié)內(nèi)容，對進程調(diào)度的功能以及進程調(diào)度算法有深入的理解。2實踐準備：掌握一種計算機高級語言的使用。要求完成的主要任務(wù): （包括課程設(shè)計工作量及其技術(shù)要求，以及說明書撰寫等具體要求）1

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

4、果有，簡要說明該方法）；v）對實驗題的評價和改進意見，請你推薦設(shè)計題目。時間安排：設(shè)計安排一周：周1、周2：完成程序分析及設(shè)計。周2、周3：完成程序調(diào)試及測試。周4、周5：驗收、撰寫課程設(shè)計報告。（注意事項：嚴禁抄襲，一旦發(fā)現(xiàn)，抄與被抄的一律按0分記）指導(dǎo)教師簽名： 年 月 日系主任（或責(zé)任教師）簽名： 年 月 日進程調(diào)度模擬設(shè)計先來先服務(wù)、優(yōu)先級法1.需求分析 1.1設(shè)計目的(1)閱讀操作系統(tǒng)的處理機管理章節(jié)內(nèi)容，對進程調(diào)度的功能以及進程調(diào)度算法有深入的理解。(2)掌握一種計算機高級語言的使用。要求完成的主要任務(wù): （包括課程設(shè)計工作量及其技術(shù)要求，以及說明書撰寫等具體要求） 1.2設(shè)計要求

5、(1)能夠選擇不同的調(diào)度算法（要求中給出的調(diào)度算法）；(2)能夠輸入進程的基本信息，如進程名、優(yōu)先級、到達時間和運行時間等；(3)根據(jù)選擇的調(diào)度算法顯示進程調(diào)度隊列；(4)根據(jù)選擇的調(diào)度算法計算平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。2.功能設(shè)計 2.1數(shù)據(jù)結(jié)構(gòu)1. 進程的結(jié)構(gòu)定義： struct Process /定義進程控制塊 char name10;/ 進程名int priority; /進程優(yōu)先級float arive; /進程到達時間float run; /進程運行時間float finish; /進程完成時間float zz; /進程周轉(zhuǎn)時間float dqzz; /進程帶權(quán)周轉(zhuǎn)時間boo

6、l run_flag; /進程是否運行標(biāo)志2.2先來先服務(wù)算法設(shè)計 2.2.1先來先服務(wù)算法的定義及說明 將用戶作業(yè)和就緒進程按提交順序或變?yōu)榫途w狀態(tài)的先后排成隊列，并按照先來先服務(wù)的方式進行調(diào)度處理，是一種最普遍和最簡單的方法。在該算法中，每個作業(yè)或進程按照它們在隊列中等待時間長短來決定它們是否優(yōu)先享受服務(wù)。在沒有特殊理由要優(yōu)先調(diào)度某類作業(yè)或進程時，從處理的角度來看，F(xiàn)CFS方式是一種最合適的方法，因為無論是追加還是取出一個隊列元素在操作上都是最簡單的。 2.2.2進程調(diào)度及實現(xiàn)過程void fcfs(Process pro,int k)/先來先服務(wù)法 for(int i = 0 ; i =

7、k-2;i+)int min = i;for(int j = i+1;jk;j+)if(proj.arive promin.arive)min = j;Process tmpPrp;memcpy(&tmpPrp,&proi,sizeof(Process);memcpy(&proi,&promin,sizeof(Process);memcpy(&promin,&tmpPrp,sizeof(Process);int n;cout進程調(diào)度順序為:;for(n = 0;n = k-1;n+) ;coutendl;pro0.finish = pro0.arive+pro0.r

8、un; pro0.zz = pro0.finish - pro0.arive;pro0.dqzz = pro0.zz/pro0.run;for(n=1;n = k;n+)pron.finish = pron.run+pron-1.finish;pron.zz = pron.finish-pron.arive;float averagezz,averagedqzz;averagezz=0;averagedqzz=0;for(n=0;n=k-1;n+) averagezz+=pron.zz;averagezz=averagezz/k; cout平均周轉(zhuǎn)時間為:averagezzendl;for(n

9、=0;n=k-1;n+)pron.dqzz=pron.zz/pron.run;averagedqzz += pron.dqzz;averagedqzz=averagedqzz/k; cout帶權(quán)平均周轉(zhuǎn)時間為:averagedqzzendl;2.3 優(yōu)先級算法的設(shè)計 2.3.1優(yōu)先級算法的定義及說明 優(yōu)先級法可被用作作業(yè)或進程的調(diào)度策略。首先，系統(tǒng)或用戶按某種原則為作業(yè)或進程指定一個優(yōu)先級來表示該作業(yè)或進程所享有的調(diào)度優(yōu)先權(quán)。該算法的核心是確定進程或作業(yè)的優(yōu)先級。 確定優(yōu)先級的方法可分為兩類。即動態(tài)法和靜態(tài)法靜態(tài)法根據(jù)作業(yè)或進程的靜態(tài)特性，在作業(yè)或進程開始執(zhí)行之前就確定它們的優(yōu)先級，一旦開始執(zhí)

10、行之后就不能改變。動態(tài)法則不然，它把作業(yè)或進程的靜態(tài)特性和動態(tài)特性結(jié)合起來確定作業(yè)或進程的優(yōu)先級，隨著作業(yè)或進程的執(zhí)行過程，其優(yōu)先級不斷變化。 靜態(tài)優(yōu)先級中，可以由用戶自己根據(jù)作業(yè)的緊急程度輸入一個適當(dāng)?shù)膬?yōu)先級，為防止各用戶都將自己的作業(yè)冠以高優(yōu)先級，系統(tǒng)應(yīng)對高優(yōu)先級用戶收取較高的費用；也可以由系統(tǒng)或操作員根據(jù)作業(yè)類型指定優(yōu)先級。動態(tài)優(yōu)先級中，基于靜態(tài)優(yōu)先級的調(diào)度算法實現(xiàn)簡單，系統(tǒng)開銷小，但由于靜態(tài)優(yōu)先級一旦確定之后，直到執(zhí)行結(jié)束為止始終保持不變，從而系統(tǒng)效率較低，調(diào)度性能不高?，F(xiàn)在的操作系統(tǒng)中，如果使用優(yōu)先級調(diào)度的話，則大多采用動態(tài)優(yōu)先級的調(diào)度策略。 2.3.2優(yōu)先級進程調(diào)度及實現(xiàn)過程首先是

11、判定優(yōu)先級并返回在進程表中索引int FindShouldBeRun(Process pro,int n)/判定優(yōu)先級并返回在進程表中索引int index = -1; for(int i = 0 ; i n; i+)if(proi.arive = finish & proi.run_flag = false)index = i;if(i n-1)for(i = i+1; i = n-1;i+)if(proi.arive proindex.priority & proi.run_flag = false)index = i;return index;return index;return in

12、dex;然后是進行優(yōu)先級調(diào)度void pri(Process pro,int n)/優(yōu)先級法int i , j;int min = 0;/找出提交時間最早的與第一個交換數(shù)據(jù)for(i =1; i n;i+)if(proi.arivepromin.arive)min = i;Process tmpPrp;memcpy(&tmpPrp,&pro0,sizeof(Process);memcpy(&pro0,&promin,sizeof(Process);memcpy(&promin,&tmpPrp,sizeof(Process);cout進程調(diào)度順序為:; ;pro0.f

13、inish = pro0.arive+pro0.run;pro0.zz = pro0.finish - pro0.arive;pro0.dqzz = pro0.zz/pro0.run;pro0.run_flag = true; finish = pro0.finish;for(i = 1;i = n-1; i+ )int index = FindShouldBeRun(pro,n);if(index = -1)coutERRORendl;return; ;proindex.run_flag = true;proindex.finish = finish + p

14、roindex.run;proindex.zz = proindex.finish - proindex.arive;proindex.dqzz = proindex.zz /proindex.run; finish += proindex.run;float zzTime = 0.0f;float dqzzTime = 0.0f;for(j = 0 ; j n ; j+)zzTime += proj.zz;dqzzTime += proj.dqzz;zzTime /= n;dqzzTime /= n;cout平均周轉(zhuǎn)時間：zzTimeendl;cout平均帶全周轉(zhuǎn)時間：dqzzTimeend

15、l;return ;2.3.3優(yōu)先級調(diào)度流程圖開始大于進程數(shù)？是 否查找第一個被調(diào)度的進程，對第一個被調(diào)度的進程求相應(yīng)的參數(shù)開始時間=達到時間結(jié)束時間=開始時間+執(zhí)行時間系統(tǒng)時間=結(jié)束時間計算周轉(zhuǎn)時間和帶權(quán)時間大于進程數(shù)？ 是結(jié)束查找下一個被調(diào)度的進程，對找到的下一個被調(diào)度的進程求相應(yīng)的參數(shù) 否 開始時間=達到時間結(jié)束時間=開始時間+執(zhí)行時間系統(tǒng)時間=結(jié)束時間標(biāo)記為已執(zhí)行計算周轉(zhuǎn)時間和帶權(quán)時間2.4進程參數(shù)的輸入 該過程主要完成各數(shù)據(jù)的輸入，包括進程個數(shù)、各進程的名稱、各進程的到達時間，各進程的運行時間和各進程的優(yōu)先級，以及完成初始化各數(shù)據(jù)。int pinput( ) int i;printf

16、(請輸入進程個數(shù):);scanf(%d,&counter);printf(請輸入各進程名稱:);for(i=0;icounter;i+) scanf(%s,);printf(請輸入各進程的到達時間:);for(i=0;icounter;i+) scanf(%f,&e_time);printf(請輸入各進程的運行時間:);for(i=0;icounter;i+) scanf(%f,&tasksi.run_time);printf(請輸入各進程的優(yōu)先級:);for(i=0;icounter;i+) scanf(%d,&tasksi.priority);fo

17、r(i=0;icounter;i+)proi.arive=0;proi.finish=0;proi.order=0;ti.run_flag=0;return 0;2.5調(diào)度結(jié)果的輸出該過程主要完成各數(shù)據(jù)的輸出，包括進程名、到達時間、運行時間、優(yōu)先級、執(zhí)行順序，以及將結(jié)果顯示在界面上。void print(Process pro,int n)/顯示進程for(int i=0;i=n-1;i+)cout進程i+1: endl; cout進程i+1優(yōu)先級:proi.priority endl;cout進程i+1到達時間:proi.arive endl;cout進程i+1運行時間:p

18、roi.run endl;3. 源程序的主要部分 主程序主要完成調(diào)用各個函數(shù)完成相應(yīng)的功能，以及選擇調(diào)度算法的輸出提示，根據(jù)提示并完成相應(yīng)的算法實現(xiàn)過程。 int main()while(true)int i,j;int n;coutn;Process *pro = new Processn;for(i = 0 ; i n; i+)memset(&proi,0,sizeof(Process); cout請輸入進程名:;for(i=0;;cout請輸入進程優(yōu)先級:;for(i=0;iproi.priority;cout請輸入各進程到達時間:;for(i=0;iproi.ari

19、ve;cout請輸入各進程運行時間:;for(i=0;iproi.run; cout請選擇您要使用的進程調(diào)度算法endl;cout1.先來先服務(wù)法:endl;cout2.優(yōu)先級法:endl;cout其他.退出:j;if(j=1) print(pro,n);fcfs(pro,n);else if(j=2) print(pro,n); pri(pro,n);else return 0;4.程序測試 4.1先來先服務(wù)測試用例進程序號進程名稱到達時間執(zhí)行時間1a042b133c224d334.2先來先服務(wù)運行結(jié)果4.3優(yōu)先級算法測試用例進程序號進程名稱優(yōu)先級到達時間執(zhí)行時間1a1042b4163c22

20、44d3354.4優(yōu)先級算法運行結(jié)果5.程序流程圖 開始 請輸入進程個數(shù)請輸入各進程名稱請輸入各進程的到達時間請輸入各進程的運行時間請輸入各進程的優(yōu)先級請選擇調(diào)度算法 優(yōu)先級調(diào)度先來先服務(wù)退出 執(zhí)行完 執(zhí)行完6.自我評價與總結(jié) 本次課程設(shè)計的內(nèi)容基本上是老師在課堂上所講的，所以我還是比較熟悉先來先服務(wù)算法和優(yōu)先級算法。看到這個題目時，我還是感覺相當(dāng)輕松的，因為我還是比較熟悉該內(nèi)容，比較熟悉算法思想。設(shè)計過程中要注意流程的條理清晰，易于讀懂和規(guī)劃，程序編寫完成以后，實現(xiàn)了預(yù)期的效果，達到了設(shè)計的要求。界面設(shè)計比較清晰明了，易于閱讀和理解。本程序中，有些地方有重復(fù)，可以通過設(shè)計函數(shù)來簡化程序，例如

21、程序的創(chuàng)建，可以通過函數(shù)調(diào)用來實現(xiàn)，從而不必在兩個算法中分別編寫。編寫程序時要先畫出程序的流程圖是非常有必要的，根據(jù)流程圖的順序來實現(xiàn)程序，并要注意合理的使用函數(shù)調(diào)用來使程序得到簡化，并且易讀易懂。 通過課程設(shè)計的實際上機操作，它有助于我們更好地掌握和理解知識，更有利于我們查漏補缺。要知道知識是死的，能夠運用起來它將具有很大的活力。在平時的學(xué)習(xí)中，由于受一些因素影響，學(xué)的不是很好。但通過上機操作完成一項完整的程序設(shè)計以后，加深了我對這門課的認識，進一步較好地掌握所學(xué)的內(nèi)容，并要做到完善自己的知識體系，然后從中找出自己的不足。 這次課程設(shè)計使得我受益匪淺，尤其是對優(yōu)先級調(diào)度分析方法有了更深的理解

22、和掌握。通過這次課程設(shè)計，我的編程能力又得到了進一步的提高，同時也培養(yǎng)了我的思維能力?？偟恼f來，這次課程設(shè)計不僅豐富了我的理論知識，也加強了我的動手能力，還鍛煉了我的思維能力。在實驗程序編寫和調(diào)試過程中我學(xué)會了很多，也認識到了自己的不足，我還需要進一步的努力，以致取得更大的進步。我需要的就是要對自己有信心，腳踏實地，持之以恒，遇到困難時要冷靜思考，勇敢面對，直到得出結(jié)果。在實驗設(shè)計過程中，我也養(yǎng)成了較好地習(xí)慣，先有框架，然后跟著框架發(fā)展，最后就是要注重細節(jié)，要做到嚴謹和縝密。不可否認這種好習(xí)慣讓我受益無限，我也必須擁有它，以致我獲得更多。7.源程序清單#includeusing namespa

23、ce std;struct Process/定義進程控制塊 char name10;/ 進程名int priority; /進程優(yōu)先級float arive; /進程到達時間float run; /進程運行時間float finish; /進程完成時間float zz; /進程周轉(zhuǎn)時間float dqzz; /進程帶權(quán)周轉(zhuǎn)時間bool run_flag; /進程是否運行標(biāo)志;float finish = 0.0f;void print(Process pro,int n)/顯示進程 for(int i=0;i=n-1;i+) cout進程i+1: endl; cout進程i+

24、1優(yōu)先級:proi.priority endl;cout進程i+1到達時間:proi.arive endl;cout進程i+1運行時間:proi.run endl;void fcfs(Process pro,int k)/先來先服務(wù)法 for(int i = 0 ; i =k-2;i+) int min = i;for(int j = i+1;jk;j+) if(proj.arive promin.arive) min = j; Process tmpPrp;memcpy(&tmpPrp,&proi,sizeof(Process);memcpy(&proi,&promin,sizeof(Pro

25、cess);memcpy(&promin,&tmpPrp,sizeof(Process); int n;cout進程調(diào)度順序為:;for(n = 0;n = k-1;n+) ;coutendl;pro0.finish = pro0.arive+pro0.run; pro0.zz = pro0.finish - pro0.arive;pro0.dqzz = pro0.zz/pro0.run;for(n=1;n = k;n+) pron.finish = pron.run+pron-1.finish;pron.zz = pron.finish-pron.arive;fl

26、oat averagezz,averagedqzz;averagezz=0;averagedqzz=0;for(n=0;n=k-1;n+) averagezz+=pron.zz; averagezz=averagezz/k; cout平均周轉(zhuǎn)時間為:averagezzendl;for(n=0;n=k-1;n+) pron.dqzz=pron.zz/pron.run;averagedqzz += pron.dqzz;averagedqzz=averagedqzz/k; cout帶權(quán)平均周轉(zhuǎn)時間為:averagedqzzendl; int ShouldRun(Process pro,int n)/

27、判定優(yōu)先級并返回在進程表中索引 int index = -1;for(int i = 0 ; i n; i+) if(proi.arive = finish & proi.run_flag = false) index = i;if(i n-1) for(i = i+1; i = n-1;i+) if(proi.arive proindex.priority & proi.run_flag = false) index = i;return index;return index;return index;void pri(Process pro,int n)/優(yōu)先級法 int i , j;in

28、t min = 0;/找出提交時間最早的與第一個交換數(shù)據(jù)for(i =1; i n;i+) if(proi.arivepromin.arive) min = i;Process tmpPrp;memcpy(&tmpPrp,&pro0,sizeof(Process);memcpy(&pro0,&promin,sizeof(Process);memcpy(&promin,&tmpPrp,sizeof(Process); cout進程調(diào)度順序為:; ;pro0.finish = pro0.arive+pro0.run;pro0.zz = pro0.finish - pro0.arive;pro0.dqzz = pro0.zz/pro0.run;pro0.run_flag = true; finish = pro0.finish; for(i = 1;i = n-1; i+ ) int index = ShouldRun(pro,n);if(index = -1) coutERRORendl;return; ;proindex.run_flag = tr