動(dòng)態(tài)優(yōu)先權(quán)算法模擬-操作系統(tǒng)課程設(shè)計(jì)

1、<p>　　計(jì)算機(jī)與通信工程學(xué)院</p><p><b>　　操作系統(tǒng)課程設(shè)計(jì)</b></p><p>　　設(shè)計(jì)題目 動(dòng)態(tài)優(yōu)先權(quán)算法模擬 </p><p><b>　　課程設(shè)計(jì)任務(wù)書(shū)</b></p><p>　　專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù) 學(xué)號(hào)：

2、 學(xué)生姓名（簽名）： </p><p>　　設(shè)計(jì)題目：動(dòng)態(tài)優(yōu)先權(quán)算法模擬</p><p><b>　　一、設(shè)計(jì)實(shí)驗(yàn)條件</b></p><p><b>　　綜合樓808</b></p><p><b>　　二、設(shè)計(jì)任務(wù)及要求</b></p><p>

3、　　模擬單處理機(jī)環(huán)境下的進(jìn)程調(diào)度模型，調(diào)度采用基于動(dòng)態(tài)優(yōu)先權(quán)的調(diào)度算法。</p><p><b>　　三、設(shè)計(jì)報(bào)告的內(nèi)容</b></p><p><b>　　設(shè)計(jì)題目與設(shè)計(jì)任務(wù)</b></p><p>　　設(shè)計(jì)題目：動(dòng)態(tài)優(yōu)先權(quán)算法模擬</p><p>　　設(shè)計(jì)任務(wù)：模擬單處理機(jī)環(huán)境下的進(jìn)程調(diào)度模型，

4、調(diào)度采用基于動(dòng)態(tài)優(yōu)先權(quán)的調(diào)度算法。</p><p><b>　　前言（緒論）</b></p><p>　　在操作系統(tǒng)中調(diào)度算法的實(shí)質(zhì)是一種資源的分配，因而調(diào)度算法是指“根據(jù)系統(tǒng)資源分配策略所規(guī)定的資源分配算法”。對(duì)于不同的操作系統(tǒng)和系統(tǒng)目標(biāo)，通常采用不同的調(diào)度算法。</p><p>　　為了照顧緊迫作業(yè)，使之在進(jìn)入系統(tǒng)后便獲得優(yōu)先處理，引入了最

5、高優(yōu)先權(quán)先調(diào)度算法。在作為進(jìn)程調(diào)度算法時(shí)，該算法是把處理機(jī)分配給就緒隊(duì)列優(yōu)先權(quán)最高的進(jìn)程。這可以分為搶占式優(yōu)先權(quán)算法和非搶占式優(yōu)先權(quán)算法。</p><p>　　對(duì)于最高優(yōu)先權(quán)優(yōu)先調(diào)度算法，其關(guān)鍵在于：它是使用靜態(tài)優(yōu)先權(quán)還是動(dòng)態(tài)優(yōu)先權(quán)，以及如何確定進(jìn)程的優(yōu)先權(quán)。本次課程設(shè)計(jì)所實(shí)現(xiàn)的算法就是動(dòng)態(tài)優(yōu)先權(quán)算法的搶占式優(yōu)先權(quán)調(diào)度算法和非搶占式動(dòng)態(tài)優(yōu)先權(quán)算法。</p><p>　　動(dòng)態(tài)優(yōu)先權(quán)擁有其特有

6、的靈活優(yōu)點(diǎn)，同時(shí)，若所有的進(jìn)程都具有相同的優(yōu)先權(quán)初值，則顯然是最先進(jìn)入就緒隊(duì)列的進(jìn)程，將因其動(dòng)態(tài)優(yōu)先權(quán)變得高而優(yōu)先獲得處理機(jī)，此即FCFS算法。若所有的就緒進(jìn)程具有各不相同優(yōu)先權(quán)初值，那么，對(duì)于優(yōu)先權(quán)初值低的進(jìn)程，在等待了足夠長(zhǎng)的時(shí)間后，其優(yōu)先權(quán)便可能升為最高，從而獲得處理機(jī)。當(dāng)采用搶占式優(yōu)先權(quán)調(diào)度算法時(shí)，如果規(guī)定當(dāng)前進(jìn)程的優(yōu)先權(quán)以一定速率下降，則可防止一個(gè)長(zhǎng)作業(yè)長(zhǎng)期壟斷處理機(jī)。</p><p>　　這里，我們采

7、用高響應(yīng)比來(lái)決定每個(gè)進(jìn)程的優(yōu)先權(quán)。</p><p>　　設(shè)計(jì)主體（各部分設(shè)計(jì)內(nèi)容、分析、結(jié)論等）</p><p><b>　　【設(shè)計(jì)內(nèi)容】</b></p><p>　　動(dòng)態(tài)優(yōu)先權(quán)是指在創(chuàng)建進(jìn)程時(shí)所賦予的優(yōu)先權(quán)，是可以隨進(jìn)程的推進(jìn)或隨其等待時(shí)間的增加而改變的，以便獲得更好的調(diào)度性能。</p><p>　　非搶占式優(yōu)先權(quán)調(diào)度

8、算法。在這種方式下，系統(tǒng)一旦把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程后，該進(jìn)程便一直執(zhí)行下去，直至完成；或因發(fā)生某事件使該進(jìn)程放棄處理機(jī)時(shí)，系統(tǒng)方可再將處理機(jī)重新分配給另一優(yōu)先權(quán)最高的進(jìn)程。</p><p>　　搶占式優(yōu)先權(quán)算法。系統(tǒng)同樣把處理機(jī)分配給優(yōu)先權(quán)最高的進(jìn)程，使之執(zhí)行。但在其執(zhí)行期間，只要又出現(xiàn)了另一個(gè)優(yōu)先權(quán)更高的進(jìn)程，進(jìn)程調(diào)度程序就立即停止當(dāng)前進(jìn)程的執(zhí)行，重新將進(jìn)程分配給優(yōu)先權(quán)最高的進(jìn)程。</p

9、><p>　　在批處理系統(tǒng)中，段作業(yè)優(yōu)先算法是一種比較好的算法，其主要不足之處，是長(zhǎng)作業(yè)的運(yùn)行得不到保證。如果我們?yōu)槊總€(gè)作業(yè)引入動(dòng)態(tài)優(yōu)先權(quán)，并使作業(yè)優(yōu)先級(jí)隨著等待時(shí)間的增加而以一定速率提高，則可以解決這個(gè)問(wèn)題。優(yōu)先權(quán)的變化規(guī)律可描述為：</p><p>　　優(yōu)先權(quán)=（等待時(shí)間+要求服務(wù)時(shí)間）/要求服務(wù)時(shí)間</p><p>　　對(duì)優(yōu)先權(quán)計(jì)算完畢之后，要能夠通過(guò)正確的調(diào)度函

10、數(shù)，完成相應(yīng)進(jìn)程的每個(gè)變量的更新，其中等待時(shí)間加一，運(yùn)行進(jìn)程的CPU時(shí)間減一，如果這時(shí)候運(yùn)行的進(jìn)程結(jié)束，則改變其狀態(tài)并記錄完成時(shí)間。</p><p><b>　　【算法分析】</b></p><p>　　模擬動(dòng)態(tài)優(yōu)先權(quán)算法，在主函數(shù)中選擇采用搶占式進(jìn)程調(diào)度算法還是非搶占式進(jìn)程調(diào)度算法，進(jìn)而調(diào)用對(duì)應(yīng)的函數(shù)完成模擬。</p><p><b&g

11、t;　　設(shè)置進(jìn)程結(jié)構(gòu)體，</b></p><p>　　struct PROCESS</p><p><b>　　{</b></p><p>　　int id; //進(jìn)程id</p><p>　　double response_rate; //優(yōu)先權(quán)</p><

12、p>　　int cputime; //要求服務(wù)時(shí)間</p><p>　　int waittime; //等待時(shí)間</p><p>　　int endtime; //進(jìn)程完成時(shí)間，未完成時(shí)標(biāo)記-1</p><p>　　int STATE; //進(jìn)程當(dāng)前狀態(tài)</p><p&g

13、t;<b>　　};</b></p><p>　　記錄完成的進(jìn)程id，使用數(shù)組pro_list[10]</p><p><b>　　功能函數(shù)</b></p><p>　　display() 打印各進(jìn)程當(dāng)前狀態(tài)</p><p>　　init() 初始化進(jìn)程狀態(tài)</p>

14、<p>　　change() 搶占式調(diào)度算法進(jìn)程狀態(tài)更新</p><p>　　no_change() 非搶占式調(diào)度算法進(jìn)程狀態(tài)更新</p><p>　　函數(shù)調(diào)用順序如圖1：</p><p>　　圖1 函數(shù)調(diào)用順序圖</p><p>　　采用高響應(yīng)比作為進(jìn)程調(diào)度的優(yōu)先權(quán)，其特點(diǎn)如下：</p><p&

15、gt;　　如果作業(yè)的等待時(shí)間相同，則要求服務(wù)時(shí)間愈短，其優(yōu)先權(quán)愈高，因而該算法有利于短作業(yè)；</p><p>　　當(dāng)服務(wù)時(shí)間相同時(shí)，作業(yè)的優(yōu)先權(quán)決定于其等待時(shí)間，等待時(shí)間愈長(zhǎng)，其優(yōu)先權(quán)愈高，因而它實(shí)現(xiàn)的是先來(lái)先服務(wù)。</p><p>　　對(duì)于長(zhǎng)作業(yè)，作業(yè)的優(yōu)先級(jí)可以隨等待時(shí)間的增加而提高，當(dāng)其等待時(shí)間足夠長(zhǎng)時(shí)，其優(yōu)先級(jí)便可以升到很高，從而也可以獲得處理機(jī)。</p><p

16、><b>　　【代碼實(shí)現(xiàn)】</b></p><p>　　#include<iostream></p><p>　　#include<cstring></p><p>　　#include<stdio.h></p><p>　　#include<cstdlib><

17、/p><p>　　using namespace std;</p><p>　　#define num 6</p><p>　　#define RUN 1</p><p>　　#define READY 0</p><p>　　#define RUNOUT -1</p><p>　　int time

18、=0;</p><p>　　struct PROCESS</p><p><b>　　{</b></p><p><b>　　int id;</b></p><p>　　double response_rate;</p><p>　　int cputime;</p>

19、;<p>　　int waittime;</p><p>　　int endtime;</p><p>　　int STATE;</p><p><b>　　}pro[10];</b></p><p>　　int pro_list[10],q=0;</p><p>　　void di

20、splay()</p><p><b>　　{</b></p><p>　　cout<<"Time:"<<time<<endl;</p><p>　　cout<<"==========================================="<

21、;<endl;</p><p>　　cout<<"ID\t\t0\t1\t2\t3\t4\t5"<<endl;</p><p>　　cout<<"respone_rate\t";</p><p>　　for(int i=0;i<num;i++)</p><p&

22、gt;<b>　　{</b></p><p>　　cout<<pro[i].response_rate<<'\t';</p><p><b>　　}</b></p><p>　　cout<<endl;</p><p>　　cout<<&

23、quot;cputime\t\t";</p><p>　　for(int i=0;i<num;i++)</p><p><b>　　{</b></p><p>　　cout<<pro[i].cputime<<'\t';</p><p><b>　　}<

24、;/b></p><p>　　cout<<endl;</p><p>　　cout<<"waittime\t";</p><p>　　for(int i=0;i<num;i++)</p><p><b>　　{</b></p><p>　　c

25、out<<pro[i].waittime<<'\t';</p><p><b>　　}</b></p><p>　　cout<<endl;</p><p>　　cout<<"endtime\t\t";</p><p>　　for(int

26、i=0;i<num;i++)</p><p><b>　　{</b></p><p>　　cout<<pro[i].endtime<<'\t';</p><p><b>　　}</b></p><p>　　cout<<endl;</p&

27、gt;<p>　　cout<<"STATE\t\t";</p><p>　　for(int i=0;i<num;i++)</p><p><b>　　{</b></p><p>　　if(pro[i].STATE==RUN)</p><p>　　cout<<

28、"RUN\t";</p><p>　　else if(pro[i].STATE==READY)</p><p>　　cout<<"READY\t";</p><p>　　else cout<<"RUNOUT\t";</p><p><b>　　}&l

29、t;/b></p><p>　　cout<<endl;</p><p>　　cout<<"the end process<end time>: ";</p><p>　　for(int i=0;i<q;i++)</p><p><b>　　{</b>&l

30、t;/p><p>　　cout<<"->"<<pro_list[i]<<'<'<<pro[pro_list[i]].endtime<<'>';</p><p><b>　　}</b></p><p>　　cout<

31、<endl;</p><p>　　cout<<"==========================================="<<endl;</p><p><b>　　}</b></p><p>　　void init()</p><p><b>　

32、　{</b></p><p>　　for(int i=0;i<num;i++)</p><p><b>　　{</b></p><p>　　pro[i].id=i;</p><p>　　pro[i].response_rate=1;</p><p>　　pro[i].waitti

33、me=0;</p><p>　　pro[i].endtime=-1;</p><p>　　pro[i].STATE=0;</p><p><b>　　}</b></p><p>　　pro[0].cputime=5;</p><p>　　pro[1].cputime=3;</p>&

34、lt;p>　　pro[2].cputime=1;</p><p>　　pro[3].cputime=2;</p><p>　　pro[4].cputime=4;</p><p>　　pro[5].cputime=6;</p><p><b>　　}</b></p><p>　　void ch

35、ange()</p><p><b>　　{</b></p><p>　　double runflag=0;</p><p>　　int runprocess=0;</p><p>　　for(int i=0;i<num;i++)</p><p><b>　　{</b>

36、</p><p>　　if(pro[i].STATE!=RUNOUT)</p><p><b>　　{</b></p><p>　　pro[i].response_rate=1.0*(pro[i].waittime+pro[i].cputime)/pro[i].cputime;</p><p>　　if(pro[i].r

37、esponse_rate>runflag)</p><p><b>　　{</b></p><p>　　runflag=pro[i].response_rate;</p><p>　　runprocess=i;</p><p><b>　　}</b></p><p>&

38、lt;b>　　}</b></p><p><b>　　}</b></p><p>　　for(int i=0;i<num;i++)</p><p><b>　　{</b></p><p>　　if(pro[i].STATE==RUN)</p><p>

39、<b>　　{</b></p><p>　　pro[i].STATE=READY;</p><p>　　pro[i].waittime=-1;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　pro[r

40、unprocess].cputime--;</p><p>　　pro[runprocess].waittime=-1;</p><p>　　pro[runprocess].STATE=RUN;</p><p>　　for(int i=0;i<num;i++)</p><p><b>　　{</b></p&g

41、t;<p>　　if(pro[i].STATE==RUNOUT)</p><p><b>　　{</b></p><p><b>　　continue;</b></p><p><b>　　}</b></p><p>　　pro[i].waittime++;<

42、;/p><p>　　if(pro[i].cputime==0)</p><p><b>　　{</b></p><p>　　pro[i].endtime=time;</p><p>　　pro[i].STATE=RUNOUT;</p><p>　　pro[i].response_rate=0;<

43、/p><p>　　pro_list[q++]=i;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void no_change()</p><p

44、><b>　　{</b></p><p>　　int runprocess=0,flag=0;</p><p>　　double runflag=0;</p><p>　　for(int i=0;i<num;i++)</p><p><b>　　{</b></p><

45、p>　　if(pro[i].STATE==RUNOUT)</p><p><b>　　{</b></p><p><b>　　continue;</b></p><p><b>　　}</b></p><p>　　pro[i].response_rate=1.0*(pro

46、[i].waittime+pro[i].cputime)/pro[i].cputime;</p><p>　　if(pro[i].response_rate>runflag)</p><p><b>　　{</b></p><p>　　runflag=pro[i].response_rate;</p><p>　　

47、runprocess=i;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　for(int i=0;i<num;i++)</p><p><b>　　{</b></p><p>　　if(pro[

48、i].STATE==RUNOUT)</p><p><b>　　{</b></p><p><b>　　continue;</b></p><p><b>　　}</b></p><p>　　if(pro[i].STATE==RUN)</p><p>&

49、lt;b>　　{</b></p><p><b>　　flag=1;</b></p><p>　　pro[i].cputime--;</p><p>　　pro[i].waittime=-1;</p><p>　　for(int j=0;j<num;j++)</p><p>

50、;<b>　　{</b></p><p>　　if(pro[j].STATE==RUNOUT)</p><p><b>　　{</b></p><p><b>　　continue;</b></p><p><b>　　}</b></p>&

51、lt;p>　　pro[j].waittime++;</p><p><b>　　}</b></p><p>　　if(pro[i].cputime==0)</p><p><b>　　{</b></p><p>　　pro[i].STATE=RUNOUT;</p><p&g

52、t;　　pro[i].endtime=time;</p><p>　　pro[i].response_rate=0;</p><p>　　pro_list[q++]=i;</p><p><b>　　}</b></p><p><b>　　break;</b></p><p>

53、;<b>　　}</b></p><p><b>　　}</b></p><p><b>　　if(!flag)</b></p><p><b>　　{</b></p><p>　　pro[runprocess].cputime--;</p>

54、<p>　　pro[runprocess].waittime=-1;</p><p>　　pro[runprocess].STATE=RUN;</p><p>　　for(int j=0;j<num;j++)</p><p><b>　　{</b></p><p>　　if(pro[j].STATE==

55、RUNOUT)</p><p><b>　　{</b></p><p><b>　　continue;</b></p><p><b>　　}</b></p><p>　　pro[j].waittime++;</p><p><b>　　}&l

56、t;/b></p><p>　　if(pro[runprocess].cputime==0)</p><p><b>　　{</b></p><p>　　pro[runprocess].STATE=RUNOUT;</p><p>　　pro[runprocess].endtime=time;</p>

57、<p>　　pro[runprocess].response_rate=0;</p><p>　　pro_list[q++]=runprocess;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b>

58、</p><p>　　int main()</p><p><b>　　{</b></p><p>　　int flag=0,type;</p><p>　　cout<<"selecet type£¨1.preemptive scheduling 2.non-preemptiv

59、e scheduling£©£º";</p><p>　　cin>>type;</p><p><b>　　init();</b></p><p><b>　　while(1)</b></p><p><b>　　{</b

60、></p><p><b>　　flag=0;</b></p><p>　　display();</p><p>　　for(int i=0;i<num;i++)</p><p><b>　　{</b></p><p>　　if(pro[i].STATE!=RUN

61、OUT)</p><p><b>　　{</b></p><p><b>　　flag=1;</b></p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}

62、</b></p><p>　　if(!flag) break;</p><p><b>　　time++;</b></p><p>　　if(type==1)</p><p><b>　　{</b></p><p><b>　　change();<

63、/b></p><p><b>　　}</b></p><p><b>　　else</b></p><p>　　no_change();</p><p>　　cout<<endl;</p><p>　　getchar();</p><p

64、><b>　　}</b></p><p>　　cout<<endl<<endl;</p><p>　　cout<<"All processes have runed out!!"<<endl;</p><p><b>　　}</b></p>

65、;<p><b>　　【結(jié)果截圖】</b></p><p>　　搶占式優(yōu)先權(quán)調(diào)度算法</p><p>　　非搶占式優(yōu)先調(diào)度算法</p><p><b>　　結(jié)束語(yǔ)</b></p><p>　　本次課程設(shè)計(jì)是由小組合作完成，大家一同討論算法的可行性、實(shí)現(xiàn)流程、結(jié)構(gòu)安排等，一起討論交流使得

66、大家對(duì)這個(gè)算法了解得更加深刻，從各個(gè)不同的角度對(duì)它有了不同的認(rèn)識(shí)，也發(fā)現(xiàn)了很多自己思考的死角，學(xué)到算法的同時(shí)也體會(huì)到團(tuán)隊(duì)合作的重要性，培養(yǎng)了我們團(tuán)隊(duì)合作的意識(shí)和能力。</p><p>　　在代碼的編寫(xiě)過(guò)程中還遇到很多設(shè)計(jì)是沒(méi)有考慮到的問(wèn)題，都需要當(dāng)場(chǎng)解決，應(yīng)對(duì)各種突發(fā)事件，想到比較全面的解決方案。因?yàn)檫M(jìn)程的結(jié)構(gòu)體內(nèi)有較多的變量，寫(xiě)更新函數(shù)的時(shí)候必須要注意力集中，細(xì)心耐心的處理每一個(gè)變量。對(duì)于時(shí)間變量的每一次改變，

67、注意到各個(gè)進(jìn)程狀態(tài)的變化，對(duì)于RUNOUT的進(jìn)程是不參與這些更新的，等等諸如此類(lèi)的問(wèn)題，都需要在調(diào)試中發(fā)現(xiàn)和解決。代碼運(yùn)行基本沒(méi)有問(wèn)題的時(shí)候還需要進(jìn)一步測(cè)試，有些隱藏的問(wèn)題對(duì)于一組數(shù)據(jù)也許是表現(xiàn)不出來(lái)的，多次更改數(shù)據(jù)對(duì)代碼運(yùn)行測(cè)試，解決發(fā)現(xiàn)了的隱藏bug，這一環(huán)節(jié)也是必不可少的。</p><p>　　動(dòng)態(tài)優(yōu)先權(quán)算法保證了緊急任務(wù)的高優(yōu)先權(quán)先處理，同時(shí)彌補(bǔ)了靜態(tài)優(yōu)先權(quán)事先設(shè)置數(shù)值不能完全適合每一個(gè)時(shí)刻的缺點(diǎn)，動(dòng)態(tài)賦

68、值，更加的靈活。通過(guò)多次的嘗試討論，代碼的實(shí)現(xiàn)，我們更加深刻的意識(shí)到了這一點(diǎn)，紙上得來(lái)終覺(jué)淺，絕知此事要躬行，尤其是作為計(jì)算機(jī)專業(yè)的我們，必須不斷地通過(guò)動(dòng)手實(shí)踐來(lái)培養(yǎng)自己編程能力，才能寫(xiě)出更加漂亮的算法。</p><p><b>　　參考資料</b></p><p>　　[1] 戴仕明，姚昌順．電子學(xué)發(fā)展史研究[M] ．北京：科學(xué)出版社，2011．</p>

69、<p><b>　　四、設(shè)計(jì)時(shí)間與安排</b></p><p>　　1、設(shè)計(jì)時(shí)間： 2周</p><p>　　2、設(shè)計(jì)時(shí)間安排： </p><p>　　熟悉實(shí)驗(yàn)設(shè)備、收集資料： 5 天</p><p>　　設(shè)計(jì)圖紙、實(shí)驗(yàn)、計(jì)算、程序編寫(xiě)調(diào)試： 6 天</p><p&