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

1、<p><b>　　課程設(shè)計任務(wù)書</b></p><p>　　題 目: 進程調(diào)度模擬設(shè)計——先來先服務(wù)、非強占式短進程優(yōu)先算法 </p><p><b>　　初始條件：</b></p><p>　　1．預(yù)備內(nèi)容：閱讀操作系統(tǒng)的處理機管理章節(jié)內(nèi)容，對進程調(diào)度的功能以及進程調(diào)度算法有深入的理解

2、。</p><p>　　2．實踐準(zhǔn)備：掌握一種計算機高級語言的使用。</p><p>　　要求完成的主要任務(wù): （包括課程設(shè)計工作量及其技術(shù)要求，以及說明書撰寫等具體要求）</p><p>　　1．模擬進程調(diào)度，能夠處理以下的情形：</p><p>　?、?能夠選擇不同的調(diào)度算法（要求中給出的調(diào)度算法）；</p><p&g

3、t;　?、?能夠輸入進程的基本信息，如進程名、到達時間和運行時間等；</p><p>　　⑶ 根據(jù)選擇的調(diào)度算法顯示進程調(diào)度隊列；</p><p>　?、?根據(jù)選擇的調(diào)度算法計算平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。</p><p>　　2．設(shè)計報告內(nèi)容應(yīng)說明：</p><p>　?、?課程設(shè)計目的與功能；</p><p>

4、　　⑵ 需求分析，數(shù)據(jù)結(jié)構(gòu)或模塊說明(功能與框圖)；</p><p>　?、?源程序的主要部分；</p><p>　?、?測試用例，運行結(jié)果與運行情況分析；</p><p>　?、?自我評價與總結(jié)：</p><p>　　i）你認為你完成的設(shè)計哪些地方做得比較好或比較出色；</p><p>　　ii）什么地方做得不太好，

5、以后如何改正；</p><p>　　iii）從本設(shè)計得到的收獲（在編寫，調(diào)試，執(zhí)行過程中的經(jīng)驗和教訓(xùn)）；</p><p>　　iv）完成本題是否有其他方法（如果有，簡要說明該方法）；</p><p>　　v）對實驗題的評價和改進意見，請你推薦設(shè)計題目。</p><p><b>　　時間安排：</b></p>

6、<p>　　設(shè)計安排一周：周1、周2：完成程序分析及設(shè)計。</p><p>　　周2、周3：完成程序調(diào)試及測試。</p><p>　　周4、周5：驗收、撰寫課程設(shè)計報告。</p><p>　?。ㄗ⒁馐马棧簢?yán)禁抄襲，一旦發(fā)現(xiàn)，抄與被抄的一律按0分記）</p><p>　　指導(dǎo)教師簽名： 年

7、 月 日</p><p>　　系主任（或責(zé)任教師）簽名： 年 月 日</p><p><b>　　目錄</b></p><p>　　課程設(shè)計目的與功能……………………………………………3</p><p>　　實驗?zāi)康摹?</p>

8、<p>　　開發(fā)平臺…………………………………………………………3</p><p>　　需求分析，數(shù)據(jù)結(jié)構(gòu)或模塊說明………………………………3</p><p>　　問題描述………………………………………………………...3</p><p>　　實驗要求………………………………………………………..3</p><p>　　功能描述

9、………………………………………………………..4</p><p>　　程序框圖………………………………………………………..5</p><p>　　源程序的主要部分………………………………………………6</p><p>　　結(jié)構(gòu)體的創(chuàng)建…………………………………………………..6</p><p>　　主函數(shù)………………………………………………

10、…………..6</p><p>　　SJF調(diào)度算法的函數(shù)……………………………………………7</p><p>　　FCFS調(diào)度算法的函數(shù)………………………………………….9</p><p>　　測試用例，運行結(jié)果與運行情況分析…………………………10</p><p>　　自我評價與總結(jié)…………………………………………………11</p&g

11、t;<p>　　實驗優(yōu)點………………………………………………………11</p><p>　　實驗不足………………………………………………………11</p><p>　　收貨與體會……………………………………………………12</p><p>　　實驗改進方面…………………………………………………12</p><p>　　參考文獻…

12、………………………………………………………12</p><p>　　進程調(diào)度模擬設(shè)計——先來先服務(wù)、非強占式短進程優(yōu)先算法</p><p>　　一、課程設(shè)計目的與功能</p><p><b>　　1．實驗?zāi)康?lt;/b></p><p>　　模擬進程調(diào)度，能夠處理以下的情形：</p><p>　?、?

13、能夠選擇不同的調(diào)度算法（要求中給出的調(diào)度算法）；</p><p>　　⑵ 能夠輸入進程的基本信息，如進程名、到達時間和運行時間等；</p><p>　?、?根據(jù)選擇的調(diào)度算法顯示進程調(diào)度隊列；</p><p>　　⑷ 根據(jù)選擇的調(diào)度算法計算平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。</p><p><b>　　2．開發(fā)平臺</b>

14、</p><p>　　Visual C++ 6.0、Windows XP</p><p>　　二、需求分析，數(shù)據(jù)結(jié)構(gòu)或模塊說明</p><p><b>　　1.問題描述：</b></p><p>　　設(shè)計程序模擬進程的先來先服務(wù)FCFS和短作業(yè)優(yōu)先SJF調(diào)度過程。假設(shè)有n個進程分別在T1, … ,Tn時刻到達系統(tǒng)，它們需

15、要的服務(wù)時間分別為S1, … ,Sn。分別采用先來先服務(wù)FCFS和短作業(yè)優(yōu)先SJF進程調(diào)度算法進行調(diào)度，計算每個進程的完成時間，周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間，并且統(tǒng)計n個進程的平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。</p><p><b>　　2.實驗要求：</b></p><p>　　1）進程個數(shù)n；每個進程的到達時間T1, … ,Tn和服務(wù)時間S1, … ,Sn；選擇算法1-

16、FCFS，2-SJF。</p><p>　　2）要求采用先來先服務(wù)FCFS和短作業(yè)優(yōu)先SJF分別調(diào)度進程運行，計算每個進程的周轉(zhuǎn)時間，帶權(quán)周轉(zhuǎn)時間，并且計算所有進程的平均周轉(zhuǎn)時間，帶權(quán)平均周轉(zhuǎn)時間；</p><p>　　3）輸出：要求模擬整個調(diào)度過程，輸出每個時刻的進程運行狀態(tài)，如“時刻3：進程B開始運行”等等；</p><p>　　4）輸出：要求輸出計算出來的每個

17、進程的周轉(zhuǎn)時間，帶權(quán)周轉(zhuǎn)時間，所有進程的平均周轉(zhuǎn)時間，帶權(quán)平均周轉(zhuǎn)時間。</p><p><b>　　3.功能描述</b></p><p>　　1）先來先服務(wù)(FCFS)調(diào)度算法</p><p>　　將用戶作業(yè)和就緒進程按提交順序或變?yōu)榫途w狀態(tài)的先后排成隊列，并按照先來先服務(wù)的方式進行調(diào)度處理，是一種最普遍和最簡單的方法。在沒有特殊理由要優(yōu)先調(diào)

18、度某類作業(yè)或進程時，從處理的角度來看，F(xiàn)CFS方式是一種最合適的方法，因為無論是追加還是取出一個隊列元素在操作上都是最簡單的。</p><p>　　先來先服務(wù)(FCFS)調(diào)度算法直觀看，該算法在一般意義下是公平的。即每個作業(yè)或進程都按照它們在隊列中等待時間長短來決定它們是否有限享受服務(wù)。</p><p>　　先來先服務(wù)(FCFS)調(diào)度算法不過對于那些執(zhí)行時間較短的作業(yè)或進程來說，如果它們在

19、某些執(zhí)行時間很長的作業(yè)或進程之后到達，則它們將等待很長時間。</p><p>　　在實際操作系統(tǒng)中，盡管很少單獨使用FCFS算法，但和其他一些算法配合起來，F(xiàn)CFS算法還是使用的相當(dāng)多的。例如基于優(yōu)先級的調(diào)度算法就是對具有同樣優(yōu)先級的作業(yè)或進程采用的FCFS方式。</p><p>　　2）最短作業(yè)優(yōu)先法（SJF）</p><p>　　在批處理為主的系統(tǒng)中，如果采用F

20、CFS的方式進程作業(yè)調(diào)度，雖然系統(tǒng)開銷小，算法簡單，但是，如果估計執(zhí)行時間很多的作業(yè)實在那些長作業(yè)的后面到達系統(tǒng)的話，則必須等待長作業(yè)執(zhí)行完成之后才有機會獲得執(zhí)行。這就造成不必要的等待和某種不公平。最短作業(yè)優(yōu)先發(fā)（SJF）就是選擇那些估計需要執(zhí)行時間最短的作業(yè)投入執(zhí)行，為他們創(chuàng)建進程和分配資源。</p><p>　　最短作業(yè)優(yōu)先法優(yōu)勢：直觀上說，采用最短作業(yè)有限的調(diào)度方法，可使得系統(tǒng)在同一時間內(nèi)處理的作業(yè)個數(shù)最多

21、，從而吞吐量也就大于其他的調(diào)度方式。但是，對于一個不斷有作業(yè)進入的批處理系統(tǒng)來說。</p><p>　　最短作業(yè)優(yōu)先法缺點：最短作業(yè)優(yōu)先法有可能使得那些長作業(yè)永遠得不到調(diào)度執(zhí)行的機會。</p><p><b>　　4.程序框圖</b></p><p><b>　　注釋：</b></p><p>&l

22、t;b>　　預(yù)定義：</b></p><p>　　包括程序結(jié)構(gòu)體等，程序結(jié)構(gòu)體設(shè)計到后面函數(shù)所用的作業(yè)號、提交時間、運行時間、開始時間、結(jié)束時間、周轉(zhuǎn)時間、帶權(quán)周轉(zhuǎn)時間、執(zhí)行順序等內(nèi)容</p><p><b>　　FCFS調(diào)度方法：</b></p><p>　　程序重要的組成函數(shù)，將輸入的N個程序結(jié)構(gòu)體用鏈表的方式重新排序，按

23、照函數(shù)給定的計算方法，列出作業(yè)從新計算過的作業(yè)號、提交時間、運行時間、開始時間、結(jié)束時間、周轉(zhuǎn)時間、帶權(quán)周轉(zhuǎn)時間、執(zhí)行順序等內(nèi)容</p><p><b>　　SJF調(diào)度方法：</b></p><p>　　采用最短優(yōu)先法，將輸入的N個程序結(jié)構(gòu)體用鏈表的方式重新排序，列出作業(yè)從新計算過的作業(yè)號、提交時間、運行時間、開始時間、結(jié)束時間、周轉(zhuǎn)時間、帶權(quán)周轉(zhuǎn)時間、執(zhí)行順序等內(nèi)容

24、</p><p><b>　　主函數(shù)：</b></p><p>　　先進行輸入操作，將輸入的pro結(jié)構(gòu)體存儲起來，再調(diào)用兩個算法函數(shù)，將FCFS調(diào)度方法所列出的作業(yè)結(jié)構(gòu)體和SJF調(diào)度方法所列出的結(jié)構(gòu)體整合表示出來，最后方便輸出。</p><p>　　三、源程序的主要部分</p><p><b>　　1、結(jié)構(gòu)體的

25、創(chuàng)建</b></p><p>　　struct pro</p><p><b>　　{</b></p><p>　　double handtime;</p><p>　　double asktime;</p><p>　　double starttime;</p><

26、;p>　　double endtime;</p><p>　　double usetime;</p><p>　　double right;</p><p>　　int runorder;</p><p><b>　　int num;</b></p><p>　　pro *next;<

27、/p><p><b>　　2、主函數(shù)</b></p><p>　　int main()</p><p><b>　　{</b></p><p>　　pro p[20];</p><p>　　cout<<"請輸入進程的個數(shù):";</p>

28、<p>　　cin>>pronum;</p><p>　　cout<<"按時間先后順序輸入進程的提交時間和運行時間"<<endl;</p><p>　　for(int i=0;i<pronum;i++)</p><p><b>　　{</b></p><

29、;p>　　p[i].num=i+1;</p><p>　　cout<<"第"<<i+1<<"個進程:";</p><p>　　cin>>p[i].handtime>>p[i].asktime;</p><p>　　while(p[i].handtime<p

30、[i-1].handtime)</p><p><b>　　{</b></p><p>　　cout<<"請從新輸入第"<<i+1<<"個進程:";</p><p>　　cin>>p[i].handtime>>p[i].asktime;</

31、p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　FCFS(p,pronum);</p><p>　　SJF(p,pronum);</p><p><b>　　return 0;</b></p>&

32、lt;p>　　//cout<<p1->handtime <<p1->asktime<<endl;</p><p><b>　　}</b></p><p>　　3、SJF調(diào)度算法的函數(shù)</p><p>　　void SJF(pro p[],int n)</p><p>

33、<b>　　{</b></p><p>　　int i,order=1;</p><p>　　pro *now=&p[0];</p><p>　　pro *temp,*nextrun;</p><p>　　p[0].starttime=p[0].handtime;</p><p>　　p[

34、0].endtime=p[0].handtime+p[0].asktime;</p><p>　　p[0].usetime=p[0].asktime;</p><p>　　p[0].right=1.0;</p><p>　　p[0].runorder=order;</p><p><b>　　++order;</b>&l

35、t;/p><p>　　for(i=0;i<n-1;i++)</p><p><b>　　{</b></p><p>　　p[i].next=&p[i+1];</p><p><b>　　}</b></p><p>　　//cout<<now->n

36、ext->num<<endl;</p><p>　　p[n-1].next=NULL;</p><p>　　/*while(now!=NULL)</p><p><b>　　{</b></p><p>　　cout<<now->num<<"\t"<

37、;<now->handtime<<endl;</p><p>　　now=now->next;</p><p><b>　　}*/</b></p><p>　　while(now->next!=NULL)</p><p><b>　　{</b></p>

38、<p>　　nextrun=now->next;</p><p>　　//cout<<nextrun->handtime<<"\t"<<nextrun->asktime<<"asdfafdsa"<<endl;</p><p>　　//while(nex

39、trun!=NULL) //確定nextrun </p><p><b>　　//{</b></p><p>　　if(nextrun->handtime>=now->endtime)</p><p><b>　　{</b>

40、;</p><p>　　nextrun->starttime=nextrun->handtime;</p><p><b>　　} </b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>

41、;　　if(nextrun->next!=NULL)</p><p><b>　　{</b></p><p>　　temp=nextrun->next;</p><p>　　while(temp->handtime<=now->endtime) //用來確定nextrun是否改變</

42、p><p><b>　　{</b></p><p>　　if(temp->asktime<nextrun->asktime)</p><p>　　nextrun=temp;</p><p>　　if(temp->next!=NULL)</p><p>　　temp=temp-&

43、gt;next;</p><p><b>　　else </b></p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　nextrun-

44、>starttime=now->endtime;</p><p>　　} //確定nextrun完畢</p><p>　　if(nextrun!=now->next)</p><p><b>　　{</b></p><p>　　temp=now; //修

45、改鏈表</p><p>　　while(temp->next!=nextrun)</p><p>　　temp=temp->next;</p><p>　　temp->next=nextrun->next;</p><p>　　temp=now->next; </p&

46、gt;<p>　　now->next=nextrun;</p><p>　　nextrun->next=temp; </p><p>　　} //鏈表修改完畢 </p><p>　　nextrun->endtime=nextrun->starttime+nextrun->a

47、sktime;</p><p>　　nextrun->usetime=nextrun->endtime-nextrun->handtime;</p><p>　　nextrun->right=nextrun->usetime/nextrun->asktime;</p><p>　　nextrun->runorder=orde

48、r;</p><p><b>　　++order;</b></p><p>　　//進程信息修改完畢</p><p>　　now=nextrun;</p><p><b>　　}</b></p><p>　　double sumtime=0,sumright=0;</p

49、><p>　　cout<<"SJF"<<endl;</p><p>　　cout<<"作業(yè)號\t提交\t運行\(zhòng)t開始\t結(jié)束\t周轉(zhuǎn)\t帶權(quán)\t執(zhí)行"<<endl;</p><p>　　for(i=0;i<n;i++)</p><p><b>

50、　　{</b></p><p>　　sumtime+=p[i].usetime;</p><p>　　sumright+=p[i].right;</p><p>　　cout<<p[i].num<<"\t"<<p[i].handtime<<"\t"<<p[

51、i].asktime<<"\t"<<p[i].starttime<<"\t"<<p[i].endtime<<"\t"<<p[i].usetime<<"\t"<<p[i].right<<"\t"<<p[i].runorde

52、r<<endl;</p><p><b>　　}</b></p><p>　　cout<<"平均\t\t\t\t\t"<<sumtime/n<<"\t"<<sumright/n<<endl;</p><p><b>　　}&

53、lt;/b></p><p>　　4、FCFS調(diào)度算法的函數(shù)</p><p>　　void FCFS(pro p[],int n)</p><p><b>　　{</b></p><p><b>　　int i;</b></p><p>　　p[0].starttime

54、=p[0].handtime;</p><p>　　p[0].endtime=p[0].handtime+p[0].asktime;</p><p>　　p[0].usetime=p[0].asktime;</p><p>　　p[0].right=1.0;</p><p>　　p[0].runorder=1;</p><

55、p>　　for(i=1;i<n;i++)</p><p><b>　　{</b></p><p>　　if(p[i].handtime<p[i-1].endtime)</p><p>　　p[i].starttime=p[i-1].endtime;</p><p><b>　　else<

56、/b></p><p>　　p[i].starttime=p[i].handtime;</p><p>　　p[i].endtime=p[i].starttime+p[i].asktime;</p><p>　　p[i].usetime=p[i].endtime-p[i].handtime;</p><p>　　p[i].right=p

57、[i].usetime/p[i].asktime;</p><p>　　p[i].runorder=i+1;</p><p><b>　　}</b></p><p>　　double sumtime=0,sumright=0;</p><p>　　cout<<"FCFS"<<e

58、ndl;</p><p>　　cout<<"作業(yè)號\t提交\t運行\(zhòng)t開始\t結(jié)束\t周轉(zhuǎn)\t帶權(quán)\t執(zhí)行"<<endl;</p><p>　　for(i=0;i<n;i++)</p><p><b>　　{</b></p><p>　　sumtime+=p[i].use

59、time;</p><p>　　sumright+=p[i].right;</p><p>　　cout<<p[i].num<<"\t"<<p[i].handtime<<"\t"<<p[i].asktime<<"\t"<<p[i].starttim

60、e<<"\t"<<p[ i].endtime<<"\t"<<p[i].usetime<<"\t"<<p[i].right<<"\t"<<p[i].runorder<<endl;</p><p><b>　　}&l

61、t;/b></p><p>　　cout<<"平均\t\t\t\t\t"<<sumtime/n<<"\t"<<sumright/n<<endl<<endl;</p><p><b>　　}</b></p><p>　　四、測試用

62、例，運行結(jié)果與運行情況分析</p><p>　?。▓D1：運行3個進程數(shù)的情況下程序結(jié)果）</p><p>　?。▓D2：運行5個進程數(shù)的情況下程序結(jié)果）</p><p>　　（圖3：提交時間錯誤的情況下，程序自動糾正的運行結(jié)果）</p><p><b>　　五、自我評價與總結(jié)</b></p><p>

63、;<b>　　實驗優(yōu)點</b></p><p>　　我認為我的實驗重在進程調(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í)行

64、次序。平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間，整體看上去符合課程設(shè)計題目要求，又非常詳細。</p><p><b>　　實驗不足</b></p><p>　　我認為還有不足，在于如果第一個作業(yè)和第二個作業(yè)同時提交，無論二者所用的時間如何，都是先完成第一個作業(yè)，默認第一個作業(yè)先運行，對于后面的作業(yè)才會比較運行時間和提交時間，這在程序設(shè)計上出現(xiàn)了邏輯問題，雖然不影響使用，但是這還

65、是算是美中不足，是在SJF函數(shù)的時間運算比較中出現(xiàn)問題，在鏈表的表頭以后應(yīng)該要改正。</p><p><b>　　收貨與體會</b></p><p>　　本次課程設(shè)計可以說是對操作系統(tǒng)課程本學(xué)期所學(xué)內(nèi)容的一次綜合應(yīng)用，雖然稱不上一個完整的操作系統(tǒng)進程調(diào)度程序，但已經(jīng)展現(xiàn)了一個完整作業(yè)調(diào)度的雛形。通過本次課程設(shè)計，不僅進一步熟悉了操作系統(tǒng)所涉及的各方面知識，更掌握了一個

66、進程調(diào)度的整體架構(gòu)方式以及作業(yè)調(diào)度構(gòu)造的整體流程。并且，從中認識到，進程調(diào)度模塊化(先來先服務(wù)、輪轉(zhuǎn)法、優(yōu)先級法、最短作業(yè)優(yōu)先法、最高響應(yīng)比優(yōu)先法)的重要，更是程序設(shè)計模塊化的重要。但，在其過程中也暴漏了自身知識的匱乏，包括，C++知識學(xué)習(xí)不扎實，不能很好的運用鏈表；關(guān)于函數(shù)運用不熟練，導(dǎo)致在做兩個函數(shù)的算法，用if else語句進行鏈表的重新排列（有點像冒泡排序）耗費大量時間等等。但總的來說，本次編程還是收獲不少，不僅僅是實現(xiàn)了課程設(shè)

67、計所要求的內(nèi)容，更為以后深入的學(xué)習(xí)（包括課程相關(guān)與不相關(guān)）打下了堅實的基礎(chǔ)。</p><p><b>　　實驗改進方面</b></p><p>　　可以在以后的課程實驗中，結(jié)合實際，將先來先服務(wù)與最短作業(yè)優(yōu)先法結(jié)合起來，完整的繪制一個應(yīng)用程序，模擬進程調(diào)度，不僅更加真實，也更能鍛煉我們的動手能力。</p><p><b>　　六、參考

68、文獻</b></p><p>　　（1） 《計算機操作系統(tǒng)教程（第3版）》 張堯?qū)W 史美林 張高編著</p><p>　?。?） 《計算機操作系統(tǒng)教程（第2版）》 張堯?qū)W 史美林編著</p><p>　?。?） 《計算機操作系統(tǒng)（第3版）》 湯小丹 梁紅兵 哲鳳屏編著</p><p>　?。?） 《C++程序設(shè)計教