操作系統(tǒng)課程設(shè)計進(jìn)程調(diào)度模擬設(shè)計

1、武漢理工大學(xué)操作系統(tǒng)課程設(shè)計說明書課程設(shè)計任務(wù)書 題 目: 進(jìn)程調(diào)度模擬設(shè)計先來先服務(wù)、非強占式短進(jìn)程優(yōu)先算法 初始條件：1預(yù)備內(nèi)容：閱讀操作系統(tǒng)的處理機管理章節(jié)內(nèi)容，對進(jìn)程調(diào)度的功能以及進(jìn)程調(diào)度算法有深入的理解。2實踐準(zhǔn)備：掌握一種計算機高級語言的使用。要求完成的主要任務(wù): （包括課程設(shè)計工作量及其技術(shù)要求，以及說明書撰寫等具體要求）1模擬進(jìn)程調(diào)度，能夠處理以下的情形： 能夠選擇不同的調(diào)度算法（要求中給出的調(diào)度算法）； 能夠輸入進(jìn)程的基本信息，如進(jìn)程名、到達(dá)時間和運行時間等； 根據(jù)選擇的調(diào)度算法顯示進(jìn)程調(diào)度隊列； 根據(jù)選擇的調(diào)度算法計算平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。2設(shè)計報告內(nèi)容應(yīng)說明：

2、課程設(shè)計目的與功能； 需求分析，數(shù)據(jù)結(jié)構(gòu)或模塊說明(功能與框圖)； 源程序的主要部分； 測試用例，運行結(jié)果與運行情況分析； 自我評價與總結(jié)：i）你認(rèn)為你完成的設(shè)計哪些地方做得比較好或比較出色；ii）什么地方做得不太好，以后如何改正；iii）從本設(shè)計得到的收獲（在編寫，調(diào)試，執(zhí)行過程中的經(jīng)驗和教訓(xùn)）；iv）完成本題是否有其他方法（如果有，簡要說明該方法）；v）對實驗題的評價和改進(jìn)意見，請你推薦設(shè)計題目。時間安排：設(shè)計安排一周：周1、周2：完成程序分析及設(shè)計。周2、周3：完成程序調(diào)試及測試。周4、周5：驗收、撰寫課程設(shè)計報告。（注意事項：嚴(yán)禁抄襲，一旦發(fā)現(xiàn)，抄與被抄的一律按0分記）指導(dǎo)教師簽名：

3、年 月 日系主任（或責(zé)任教師）簽名： 年 月 日目錄課程設(shè)計目的與功能3實驗?zāi)康?開發(fā)平臺3需求分析，數(shù)據(jù)結(jié)構(gòu)或模塊說明3 問題描述.3 實驗要求.3 功能描述.4程序框圖.5源程序的主要部分6 結(jié)構(gòu)體的創(chuàng)建.6 主函數(shù).6 sjf調(diào)度算法的函數(shù)7 fcfs調(diào)度算法的函數(shù).9測試用例，運行結(jié)果與運行情況分析10自我評價與總結(jié)11實驗優(yōu)點11實驗不足11收貨與體會12實驗改進(jìn)方面12參考文獻(xiàn)12進(jìn)程調(diào)度模擬設(shè)計先來先服務(wù)、非強占式短進(jìn)程優(yōu)先算法一、課程設(shè)計目的與功能1實驗?zāi)康哪M進(jìn)程調(diào)度，能夠處理以下的情形： 能夠選擇不同的調(diào)度算法（要求中給出的調(diào)度算法）； 能夠輸入進(jìn)程的基本信息，如進(jìn)程名、到

4、達(dá)時間和運行時間等； 根據(jù)選擇的調(diào)度算法顯示進(jìn)程調(diào)度隊列； 根據(jù)選擇的調(diào)度算法計算平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。2開發(fā)平臺visual c+ 6.0、windows xp二、需求分析，數(shù)據(jù)結(jié)構(gòu)或模塊說明1.問題描述：設(shè)計程序模擬進(jìn)程的先來先服務(wù)fcfs和短作業(yè)優(yōu)先sjf調(diào)度過程。假設(shè)有n個進(jìn)程分別在t1, ,tn時刻到達(dá)系統(tǒng)，它們需要的服務(wù)時間分別為s1, ,sn。分別采用先來先服務(wù)fcfs和短作業(yè)優(yōu)先sjf進(jìn)程調(diào)度算法進(jìn)行調(diào)度，計算每個進(jìn)程的完成時間，周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間，并且統(tǒng)計n個進(jìn)程的平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。2.實驗要求：1）進(jìn)程個數(shù)n；每個進(jìn)程的到達(dá)時間t1, ,tn和服

5、務(wù)時間s1, ,sn；選擇算法1-fcfs，2-sjf。2）要求采用先來先服務(wù)fcfs和短作業(yè)優(yōu)先sjf分別調(diào)度進(jìn)程運行，計算每個進(jìn)程的周轉(zhuǎn)時間，帶權(quán)周轉(zhuǎn)時間，并且計算所有進(jìn)程的平均周轉(zhuǎn)時間，帶權(quán)平均周轉(zhuǎn)時間；3）輸出：要求模擬整個調(diào)度過程，輸出每個時刻的進(jìn)程運行狀態(tài)，如“時刻3：進(jìn)程b開始運行”等等；4）輸出：要求輸出計算出來的每個進(jìn)程的周轉(zhuǎn)時間，帶權(quán)周轉(zhuǎn)時間，所有進(jìn)程的平均周轉(zhuǎn)時間，帶權(quán)平均周轉(zhuǎn)時間。3.功能描述1）先來先服務(wù)(fcfs)調(diào)度算法 將用戶作業(yè)和就緒進(jìn)程按提交順序或變?yōu)榫途w狀態(tài)的先后排成隊列，并按照先來先服務(wù)的方式進(jìn)行調(diào)度處理，是一種最普遍和最簡單的方法。在沒有特殊理由要優(yōu)先

6、調(diào)度某類作業(yè)或進(jìn)程時，從處理的角度來看，fcfs方式是一種最合適的方法，因為無論是追加還是取出一個隊列元素在操作上都是最簡單的。先來先服務(wù)(fcfs)調(diào)度算法直觀看，該算法在一般意義下是公平的。即每個作業(yè)或進(jìn)程都按照它們在隊列中等待時間長短來決定它們是否有限享受服務(wù)。先來先服務(wù)(fcfs)調(diào)度算法不過對于那些執(zhí)行時間較短的作業(yè)或進(jìn)程來說，如果它們在某些執(zhí)行時間很長的作業(yè)或進(jìn)程之后到達(dá)，則它們將等待很長時間。 在實際操作系統(tǒng)中，盡管很少單獨使用fcfs算法，但和其他一些算法配合起來，fcfs算法還是使用的相當(dāng)多的。例如基于優(yōu)先級的調(diào)度算法就是對具有同樣優(yōu)先級的作業(yè)或進(jìn)程采用的fcfs方式。2）最

7、短作業(yè)優(yōu)先法（sjf） 在批處理為主的系統(tǒng)中，如果采用fcfs的方式進(jìn)程作業(yè)調(diào)度，雖然系統(tǒng)開銷小，算法簡單，但是，如果估計執(zhí)行時間很多的作業(yè)實在那些長作業(yè)的后面到達(dá)系統(tǒng)的話，則必須等待長作業(yè)執(zhí)行完成之后才有機會獲得執(zhí)行。這就造成不必要的等待和某種不公平。最短作業(yè)優(yōu)先發(fā)（sjf）就是選擇那些估計需要執(zhí)行時間最短的作業(yè)投入執(zhí)行，為他們創(chuàng)建進(jìn)程和分配資源。最短作業(yè)優(yōu)先法優(yōu)勢：直觀上說，采用最短作業(yè)有限的調(diào)度方法，可使得系統(tǒng)在同一時間內(nèi)處理的作業(yè)個數(shù)最多，從而吞吐量也就大于其他的調(diào)度方式。但是，對于一個不斷有作業(yè)進(jìn)入的批處理系統(tǒng)來說。最短作業(yè)優(yōu)先法缺點：最短作業(yè)優(yōu)先法有可能使得那些長作業(yè)永遠(yuǎn)得不到調(diào)度

8、執(zhí)行的機會。4.程序框圖預(yù)定義fcfs調(diào)度方法sjf調(diào)度方法主函數(shù)輸出注釋：預(yù)定義：包括程序結(jié)構(gòu)體等，程序結(jié)構(gòu)體設(shè)計到后面函數(shù)所用的作業(yè)號、提交時間、運行時間、開始時間、結(jié)束時間、周轉(zhuǎn)時間、帶權(quán)周轉(zhuǎn)時間、執(zhí)行順序等內(nèi)容fcfs調(diào)度方法：程序重要的組成函數(shù)，將輸入的n個程序結(jié)構(gòu)體用鏈表的方式重新排序，按照函數(shù)給定的計算方法，列出作業(yè)從新計算過的作業(yè)號、提交時間、運行時間、開始時間、結(jié)束時間、周轉(zhuǎn)時間、帶權(quán)周轉(zhuǎn)時間、執(zhí)行順序等內(nèi)容sjf調(diào)度方法：采用最短優(yōu)先法，將輸入的n個程序結(jié)構(gòu)體用鏈表的方式重新排序，列出作業(yè)從新計算過的作業(yè)號、提交時間、運行時間、開始時間、結(jié)束時間、周轉(zhuǎn)時間、帶權(quán)周轉(zhuǎn)時間、執(zhí)

9、行順序等內(nèi)容主函數(shù)：先進(jìn)行輸入操作，將輸入的pro結(jié)構(gòu)體存儲起來，再調(diào)用兩個算法函數(shù)，將fcfs調(diào)度方法所列出的作業(yè)結(jié)構(gòu)體和sjf調(diào)度方法所列出的結(jié)構(gòu)體整合表示出來，最后方便輸出。三、源程序的主要部分1、結(jié)構(gòu)體的創(chuàng)建struct prodouble handtime;double asktime;double starttime;double endtime;double usetime;double right;int runorder;int num;pro *next;2、主函數(shù) int main()pro p20;coutpronum;cout按時間先后順序輸入進(jìn)程的提交時間和運行時間

10、endl;for(int i=0;ipronum;i+)pi.num=i+1; cout第i+1pi.handtimepi.asktime;while(pi.handtimepi-1.handtime)cout請從新輸入第i+1pi.handtimepi.asktime; fcfs(p,pronum); sjf(p,pronum); return 0; /couthandtime asktimeendl;3、sjf調(diào)度算法的函數(shù)void sjf(pro p,int n)int i,order=1;pro *now=&p0;pro *temp,*nextrun;p0.starttime=p0.h

11、andtime;p0.endtime=p0.handtime+p0.asktime;p0.usetime=p0.asktime;p0.right=1.0;p0.runorder=order;+order;for(i=0;in-1;i+)pi.next=&pi+1;/coutnext-numendl;pn-1.next=null;/*while(now!=null)coutnumthandtimenext;*/while(now-next!=null)nextrun=now-next;/couthandtimetasktimeasdfafdsahandtime=now-endtime)nextr

12、un-starttime=nextrun-handtime; elseif(nextrun-next!=null)temp=nextrun-next; while(temp-handtimeendtime) /用來確定nextrun是否改變 if(temp-asktimeasktime)nextrun=temp; if(temp-next!=null)temp=temp-next;else break; nextrun-starttime=now-endtime; /確定nextrun完畢 if(nextrun!=now-next)temp=now; /修改鏈表while(temp-next!

13、=nextrun)temp=temp-next;temp-next=nextrun-next;temp=now-next; now-next=nextrun;nextrun-next=temp; /鏈表修改完畢 nextrun-endtime=nextrun-starttime+nextrun-asktime;nextrun-usetime=nextrun-endtime-nextrun-handtime;nextrun-right=nextrun-usetime/nextrun-asktime;nextrun-runorder=order;+order; /進(jìn)程信息修改完畢 now=next

14、run;double sumtime=0,sumright=0;coutsjfendl;cout作業(yè)號t提交t運行t開始t結(jié)束t周轉(zhuǎn)t帶權(quán)t執(zhí)行endl;for(i=0;in;i+)sumtime+=pi.usetime;sumright+=pi.right;coutpi.numtpi.handtimetpi.asktimetpi.starttimetpi.endtimetpi.usetimetpi.righttpi.runorderendl;cout平均tttttsumtime/ntsumright/nendl;4、fcfs調(diào)度算法的函數(shù)void fcfs(pro p,int n)int i

15、;p0.starttime=p0.handtime;p0.endtime=p0.handtime+p0.asktime;p0.usetime=p0.asktime;p0.right=1.0;p0.runorder=1;for(i=1;in;i+)if(pi.handtimepi-1.endtime) pi.starttime=pi-1.endtime;elsepi.starttime=pi.handtime;pi.endtime=pi.starttime+pi.asktime;pi.usetime=pi.endtime-pi.handtime;pi.right=pi.usetime/pi.as

16、ktime;pi.runorder=i+1;double sumtime=0,sumright=0;coutfcfsendl;cout作業(yè)號t提交t運行t開始t結(jié)束t周轉(zhuǎn)t帶權(quán)t執(zhí)行endl;for(i=0;in;i+)sumtime+=pi.usetime;sumright+=pi.right;coutpi.numtpi.handtimetpi.asktimetpi.starttimetp i.endtimetpi.usetimetpi.righttpi.runorderendl;cout平均tttttsumtime/ntsumright/nendlendl;四、測試用例，運行結(jié)果與運行情況

17、分析（圖1：運行3個進(jìn)程數(shù)的情況下程序結(jié)果）（圖2：運行5個進(jìn)程數(shù)的情況下程序結(jié)果）（圖3：提交時間錯誤的情況下，程序自動糾正的運行結(jié)果）五、自我評價與總結(jié)1. 實驗優(yōu)點我認(rèn)為我的實驗重在進(jìn)程調(diào)度的算法，使用到最常用的fcfs調(diào)度算法和sjf最短作業(yè)優(yōu)先法，在程序編輯上，程序比較簡明，使觀看者能一眼分析出整個程序的脈絡(luò)和構(gòu)架，方便閱讀。在程序結(jié)果顯示上，也非常簡明扼要，通過輸入作業(yè)的提交時間和運行時間，可以用fcfs調(diào)度算法和sjf最短作業(yè)優(yōu)先法分辨顯示出，開始時間，結(jié)束時間，周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間，和執(zhí)行次序。平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間，整體看上去符合課程設(shè)計題目要求，又非常詳細(xì)。2.

18、實驗不足我認(rèn)為還有不足，在于如果第一個作業(yè)和第二個作業(yè)同時提交，無論二者所用的時間如何，都是先完成第一個作業(yè)，默認(rèn)第一個作業(yè)先運行，對于后面的作業(yè)才會比較運行時間和提交時間，這在程序設(shè)計上出現(xiàn)了邏輯問題，雖然不影響使用，但是這還是算是美中不足，是在sjf函數(shù)的時間運算比較中出現(xiàn)問題，在鏈表的表頭以后應(yīng)該要改正。3. 收貨與體會本次課程設(shè)計可以說是對操作系統(tǒng)課程本學(xué)期所學(xué)內(nèi)容的一次綜合應(yīng)用，雖然稱不上一個完整的操作系統(tǒng)進(jìn)程調(diào)度程序，但已經(jīng)展現(xiàn)了一個完整作業(yè)調(diào)度的雛形。通過本次課程設(shè)計，不僅進(jìn)一步熟悉了操作系統(tǒng)所涉及的各方面知識，更掌握了一個進(jìn)程調(diào)度的整體架構(gòu)方式以及作業(yè)調(diào)度構(gòu)造的整體流程。并且，從中認(rèn)識到，進(jìn)程調(diào)度模塊化(先來先服務(wù)、輪轉(zhuǎn)法、優(yōu)先級法、最短作業(yè)優(yōu)先法、最高響應(yīng)比優(yōu)先法)