動態(tài)優(yōu)先權(quán)算法模擬

1、東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院操作系統(tǒng)課程設(shè)計(jì)設(shè)計(jì)題目動態(tài)優(yōu)先權(quán)算法模擬專業(yè)名稱計(jì)算機(jī)科學(xué)與技術(shù)班級學(xué)號學(xué)生姓名指導(dǎo)教師設(shè)計(jì)時(shí)間課程設(shè)計(jì)任務(wù)書專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù) 學(xué)號：學(xué)生姓名（簽名）：設(shè)計(jì)題目：動態(tài)優(yōu)先權(quán)算法模擬一、設(shè)計(jì)實(shí)驗(yàn)條件綜合樓808二、設(shè)計(jì)任務(wù)及要求模擬單處理機(jī)環(huán)境下的進(jìn)程調(diào)度模型，調(diào)度采用基于動態(tài)優(yōu)先權(quán)的調(diào)度算法。三、設(shè)計(jì)報(bào)告的內(nèi)容設(shè)計(jì)題目與設(shè)計(jì)任務(wù)設(shè)計(jì)題目：動態(tài)優(yōu)先權(quán)算法模擬設(shè)計(jì)任務(wù)：模擬單處理機(jī)環(huán)境下的進(jìn)程調(diào)度模型，調(diào)度采用基于動態(tài)優(yōu)先權(quán)的調(diào) 度算法。前言（緒論）在操作系統(tǒng)中調(diào)度算法的實(shí)質(zhì)是一種資源的分配，因而調(diào)度算法是指“根據(jù) 系統(tǒng)資源分配策略所規(guī)定的資源分配算法

2、”。對于不同的操作系統(tǒng)和系統(tǒng)目標(biāo)，通 常采用不同的調(diào)度算法。為了照顧緊迫作業(yè)，使之在進(jìn)入系統(tǒng)后便獲得優(yōu)先處理，引入了最高優(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)算法。對于最高優(yōu)先權(quán)優(yōu)先調(diào)度算法，其關(guān)鍵在于：它是使用靜態(tài)優(yōu)先權(quán)還是動態(tài) 優(yōu)先權(quán)，以及如何確定進(jìn)程的優(yōu)先權(quán)。本次課程設(shè)計(jì)所實(shí)現(xiàn)的算法就是動態(tài)優(yōu)先 權(quán)算法的搶占式優(yōu)先權(quán)調(diào)度算法和非搶占式動態(tài)優(yōu)先權(quán)算法。動態(tài)優(yōu)先權(quán)擁有其特有的靈活優(yōu)點(diǎn)，同時(shí)，若所有的進(jìn)程都具有相同的優(yōu)先 權(quán)初值，則顯然是最先進(jìn)入就緒隊(duì)列的進(jìn)程，將因其動態(tài)優(yōu)先權(quán)變得高而優(yōu)先獲 得處理

3、機(jī)，此即FCFS算法。若所有的就緒進(jìn)程具有各不相同優(yōu)先權(quán)初值，那么， 對于優(yōu)先權(quán)初值低的進(jìn)程，在等待了足夠長的時(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è)長作業(yè)長期壟斷處理機(jī)。這里，我們采用高響應(yīng)比來決定每個(gè)進(jìn)程的優(yōu)先權(quán)。設(shè)計(jì)主體（各部分設(shè)計(jì)內(nèi)容、分析、結(jié)論等）【設(shè)計(jì)內(nèi)容】動態(tài)優(yōu)先權(quán)是指在創(chuàng)建進(jìn)程時(shí)所賦予的優(yōu)先權(quán)，是可以隨進(jìn)程的推進(jìn)或隨其 等待時(shí)間的增加而改變的，以便獲得更好的調(diào)度性能。非搶占式優(yōu)先權(quán)調(diào)度算法。在這種方式下，系統(tǒng)一旦把處理機(jī)分配給就緒隊(duì) 列中優(yōu)先權(quán)最高的進(jìn)程后，該進(jìn)程便一直執(zhí)行下去，直至完

4、成；或因發(fā)生某事件 使該進(jìn)程放棄處理機(jī)時(shí)，系統(tǒng)方可再將處理機(jī)重新分配給另一優(yōu)先權(quán)最高的進(jìn)程。搶占式優(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)程。在批處理系統(tǒng)中，段作業(yè)優(yōu)先算法是一種比較好的算法，其主要不足之處， 是長作業(yè)的運(yùn)行得不到保證。如果我們?yōu)槊總€(gè)作業(yè)引入動態(tài)優(yōu)先權(quán)，并使作業(yè)優(yōu) 先級隨著等待時(shí)間的增加而以一定速率提高，則可以解決這個(gè)問題。優(yōu)先權(quán)的變 化規(guī)律可描述為：優(yōu)先權(quán)=（等待時(shí)間+要求服務(wù)時(shí)間）/要求服務(wù)時(shí)間對優(yōu)先權(quán)計(jì)算完畢之后，要能夠通過正確

5、的調(diào)度函數(shù)，完成相應(yīng)進(jìn)程的每個(gè) 變量的更新，其中等待時(shí)間加一，運(yùn)行進(jìn)程的CPU時(shí)間減一，如果這時(shí)候運(yùn)行的 進(jìn)程結(jié)束，則改變其狀態(tài)并記錄完成時(shí)間?！舅惴ǚ治觥磕M動態(tài)優(yōu)先權(quán)算法，在主函數(shù)中選擇采用搶占式進(jìn)程調(diào)度算法還是非搶占 式進(jìn)程調(diào)度算法，進(jìn)而調(diào)用對應(yīng)的函數(shù)完成模擬。設(shè)置進(jìn)程結(jié)構(gòu)體，struct PROCESSint id;進(jìn)程 iddouble response_rate; 優(yōu)先權(quán)int cputime;要求服務(wù)時(shí)間int waittime;等待時(shí)間int endtime;進(jìn)程完成時(shí)間，未完成時(shí)標(biāo)記-1int STATE;進(jìn)程當(dāng)前狀態(tài);記錄完成的進(jìn)程id，使用數(shù)組pro_list10功能函數(shù)

6、display()打印各進(jìn)程當(dāng)前狀態(tài)init()初始化進(jìn)程狀態(tài)change()搶占式調(diào)度算法進(jìn)程狀態(tài)更新no_change()非搶占式調(diào)度算法進(jìn)程狀態(tài)更新函數(shù)調(diào)用順序如圖1：圖1函數(shù)調(diào)用順序圖采用高響應(yīng)比作為進(jìn)程調(diào)度的優(yōu)先權(quán)，其特點(diǎn)如下：如果作業(yè)的等待時(shí)間相同，則要求服務(wù)時(shí)間愈短，其優(yōu)先權(quán)愈高，因而該算 法有利于短作業(yè)；當(dāng)服務(wù)時(shí)間相同時(shí)，作業(yè)的優(yōu)先權(quán)決定于其等待時(shí)間，等待時(shí)間愈長，其優(yōu) 先權(quán)愈高，因而它實(shí)現(xiàn)的是先來先服務(wù)。對于長作業(yè)，作業(yè)的優(yōu)先級可以隨等待時(shí)間的增加而提高，當(dāng)其等待時(shí)間足 夠長時(shí)，其優(yōu)先級便可以升到很高，從而也可以獲得處理機(jī)?！敬a實(shí)現(xiàn)】#include#include#inc

7、lude#includeusing namespace std;#define num 6#define RUN 1#define READY 0#define RUNOUT -1int time=0;struct PROCESSint id;double response_rate;int cputime;int waittime;int endtime;int STATE;pro10;int pro_list10,q=0;void display()coutTime:timeendl;cout=endl;coutIDtt0t1t2t3t4t5endl;coutrespone_ratet”;

8、for(int i=0;inum;i+)coutproi.response_ratet;coutendl;coutcputimett”;for(int i=0;inum;i+)coutproi.cputimet;coutendl;coutwaittimet”;for(int i=0;inum;i+)coutproi.waittimet;coutendl;coutendtimett”;for(int i=0;inum;i+)coutproi.endtimet;coutendl;coutSTATEtt;for(int i=0;inum;i+)if(proi.STATE=RUN)coutRUNt;e

9、lse if(proi.STATE=READY)coutREADYt”;else coutRUNOUTt;coutendl;coutthe end process:;for(int i=0;iq;i+)coutpro_listipropro_listi.endtime;coutendl;cout=endl; void init()for(int i=0;inum;i+)proi.id=i;proi.response_rate=1;proi.waittime=0;proi.endtime=-1;proi.STATE=0;pro0.cputime=5;pro1.cputime=3;pro2.cpu

10、time=1;pro3.cputime=2;pro4.cputime=4;pro5.cputime=6;void change()double runflag=0;int runprocess=0;for(int i=0;irunflag)runflag=proi.response_rate;runprocess=i;for(int i=0;inum;i+)if(proi.STATE=RUN)proi.STATE=READY;proi.waittime=-1;prorunprocess.cputime-;prorunprocess.waittime=-1;prorunprocess.STATE

11、=RUN;for(int i=0;inum;i+)if(proi.STATE=RUNOUT)continue;proi.waittime+;if(proi.cputime=0)proi.endtime=time;proi.STATE=RUNOUT;proi.response_rate=0;pro_listq+=i;void no_change()int runprocess=0,flag=0;double runflag=0;for(int i=0;irunflag)runflag=proi.response_rate;runprocess=i;for(int i=0;inum;i+)if(p

12、roi.STATE=RUNOUT)continue;if(proi.STATE=RUN)flag=1;proi.cputime-;proi.waittime=-1;for(int j=0;jnum;j+)if(proj.STATE=RUNOUT)continue;proj.waittime+;if(proi.cputime=0)proi.STATE=RUNOUT;proi.endtime=time;proi.response_rate=0;pro_listq+=i;break;if(田ag)prorunprocess.cputime-;prorunprocess.waittime=-1;pro

13、runprocess.STATE=RUN;for(int j=0;jnum;j+)if(proj.STATE=RUNOUT)continue;proj.waittime+;if(prorunprocess.cputime=0)prorunprocess.STATE=RUNOUT;prorunprocess.endtime=time;prorunprocess.response_rate=0;pro_listq+=runprocess;int main()int flag=0,type;2.non-preemptivecouttype;init();while(1)flag=0;display(

14、);for(int i=0;inum;i+)if(proi.STATE!=RUNOUT)flag=1;break;if(!flag) break;time+;if(type=1)change();elseno_change();coutendl;getchar();coutendlendl;coutAll processes have runed out!endl;【結(jié)果截圖】搶占式優(yōu)先權(quán)調(diào)度算法非搶占式優(yōu)先調(diào)度算法4.結(jié)束語本次課程設(shè)計(jì)是由小組合作完成，大家一同討論算法的可行性、實(shí)現(xiàn)流程、 結(jié)構(gòu)安排等，一起討論交流使得大家對這個(gè)算法了解得更加深刻，從各個(gè)不同的 角度對它有了不同的認(rèn)識，也發(fā)現(xiàn)

15、了很多自己思考的死角，學(xué)到算法的同時(shí)也體 會到團(tuán)隊(duì)合作的重要性，培養(yǎng)了我們團(tuán)隊(duì)合作的意識和能力。在代碼的編寫過程中還遇到很多設(shè)計(jì)是沒有考慮到的問題，都需要當(dāng)場解決， 應(yīng)對各種突發(fā)事件，想到比較全面的解決方案。因?yàn)檫M(jìn)程的結(jié)構(gòu)體內(nèi)有較多的變 量，寫更新函數(shù)的時(shí)候必須要注意力集中，細(xì)心耐心的處理每一個(gè)變量。對于時(shí) 間變量的每一次改變，注意到各個(gè)進(jìn)程狀態(tài)的變化，對于RUNOUT的進(jìn)程是不參 與這些更新的，等等諸如此類的問題，都需要在調(diào)試中發(fā)現(xiàn)和解決。代碼運(yùn)行基 本沒有問題的時(shí)候還需要進(jìn)一步測試，有些隱藏的問題對于一組數(shù)據(jù)也許是表現(xiàn) 不出來的，多次更改數(shù)據(jù)對代碼運(yùn)行測試，解決發(fā)現(xiàn)了的隱藏bug，這一環(huán)節(jié)也是 必不可少的。動態(tài)優(yōu)先權(quán)算法保證了緊急任務(wù)的高優(yōu)先權(quán)先處理，同時(shí)彌補(bǔ)了靜態(tài)優(yōu)先權(quán) 事先設(shè)置數(shù)值