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

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：14 大?。?82.00KB 人氣指數(shù)：12 舉報 版權(quán)申訴

已閱讀1頁，還剩13頁未讀，繼續(xù)免費閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領

文檔簡介

1、　　計算機與通信工程學院　　操作系統(tǒng)課程設計　　設計題目動態(tài)優(yōu)先權(quán)算法模擬 　　課程設計任務書　　專業(yè)：計算機科學與技術學號：

2、學生姓名（簽名）： 　　設計題目：動態(tài)優(yōu)先權(quán)算法模擬　　一、設計實驗條件　　綜合樓808　　二、設計任務及要求

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

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

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

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

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

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

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

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

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

12、p>　　int cputime; //要求服務時間　　int waittime; //等待時間　　int endtime; //進程完成時間，未完成時標記-1　　int STATE; //進程當前狀態(tài)<p&g

13、t;　　};　　記錄完成的進程id，使用數(shù)組pro_list[10]　　功能函數(shù)　　display() 打印各進程當前狀態(tài)　　init() 初始化進程狀態(tài)

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

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

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

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

18、=0;　　struct PROCESS　　{　　int id;　　double response_rate;　　int cputime;

19、;　　int waittime;　　int endtime;　　int STATE;　　}pro[10];　　int pro_list[10],q=0;　　void di

20、splay()　　{　　cout<<"Time:"<<time<<endl;　　cout<<"==========================================="<

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

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

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

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

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

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

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

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

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

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

31、<endl;　　cout<<"==========================================="<<endl;　　}　　void init()

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

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

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

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

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

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

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

39、　　{　　pro[i].STATE=READY;　　pro[i].waittime=-1;　　}　　}　　pro[r

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

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

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

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

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

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

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

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

48、i].STATE==RUNOUT)　　{　　continue;　　}　　if(pro[i].STATE==RUN)&

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

50、;　　{　　if(pro[j].STATE==RUNOUT)　　{　　continue;　　}&

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

52、t;　　pro[i].endtime=time;　　pro[i].response_rate=0;　　pro_list[q++]=i;　　}　　break;

53、;　　}　　}　　if(!flag)　　{　　pro[runprocess].cputime--;

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

55、RUNOUT)　　{　　continue;　　}　　pro[j].waittime++;　　}&l

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

57、　　pro[runprocess].response_rate=0;　　pro_list[q++]=runprocess;　　}　　}　　}

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

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

61、OUT)　　{　　flag=1;　　break;　　}　　}

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

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

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

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

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

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

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

69、　　四、設計時間與安排　　1、設計時間： 2周　　2、設計時間安排： 　　熟悉實驗設備、收集資料： 5 天　　設計圖紙、實驗、計算、程序編寫調(diào)試： 6 天<p&

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責。
6. 下載文件中如有侵權(quán)或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

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

文檔簡介

溫馨提示

最新文檔

評論

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

文檔簡介

溫馨提示

最新文檔

評論

免費下載