進(jìn)程調(diào)度 最高優(yōu)先數(shù)度算法

1、吉首大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院計(jì)算機(jī)操作系統(tǒng)課程設(shè)計(jì)報(bào)告課題名稱:進(jìn)程調(diào)度開發(fā)人員：肖海波學(xué)號(hào)：20054044029班級(jí)：2005級(jí)計(jì)算機(jī)科學(xué)與技術(shù)2班實(shí)現(xiàn)算法:最高優(yōu)先數(shù)度算法完成日期：2007年12月21日 指導(dǎo)老師：李必云計(jì)算機(jī)操作系統(tǒng)進(jìn)程調(diào)度模擬算法第一章緒論1第二章算法簡(jiǎn)介1最高優(yōu)先數(shù)算法第三章程序開發(fā)平臺(tái)及開發(fā)工具第四章 算法數(shù)據(jù)結(jié)構(gòu)及流程圖4. 1算法數(shù)據(jù)結(jié)構(gòu)4. 2算法流程圖第五章程序源代碼第六章測(cè)試數(shù)據(jù)及測(cè)試結(jié)果6. 1最高優(yōu)先數(shù)6. 1. 1測(cè)試數(shù)據(jù)6. 1. 2測(cè)試結(jié)果6. 2測(cè)試總結(jié)第七章算法分析結(jié)束語(yǔ)參考文獻(xiàn)第一章緒論進(jìn)程調(diào)度是操作系統(tǒng)中最基本的一種調(diào)度，在各種類型的

2、操作系統(tǒng)中 都必須設(shè)有進(jìn)程調(diào)度.進(jìn)程調(diào)度的基本方式可分為非搶占方式和搶占式方 式(也稱為剝奪方式)非搶占方式在這種進(jìn)程調(diào)度方式下，一旦一個(gè)進(jìn)程被選中投入運(yùn)行，它就一直運(yùn)行下去, 直至完成工作,自愿放棄CPU,或者因某個(gè)事件而被阻塞為止才把CPU讓 出給其他進(jìn)程，即得到CPU的進(jìn)程不會(huì)因?yàn)闀r(shí)鐘中斷等原因而被迫讓出 CPU.搶占方式與非搶占方式相反，搶占方式允許進(jìn)程調(diào)度程序根據(jù)某種策略終止當(dāng)前正 在運(yùn)行的進(jìn)程，將其移入就緒隊(duì)列，并再根據(jù)某種調(diào)度算法選擇另一個(gè)進(jìn)程 投入運(yùn)行.第二章算法簡(jiǎn)介1最高侁先數(shù)算法最簡(jiǎn)單的調(diào)度算法就是先來(lái)先服務(wù)，也可以稱為先進(jìn)先出(First In First Out)或嚴(yán)格

3、排隊(duì)方式.對(duì)于進(jìn)程調(diào)度算法來(lái)說(shuō)，先來(lái)先服務(wù)調(diào)度算法就 是從就緒隊(duì)列中選擇一個(gè)最先進(jìn)入隊(duì)列的進(jìn)程，將CPU分配于它，讓其運(yùn)行. 該進(jìn)程一直運(yùn)行下去直到完成或由于某事件而被阻塞入放棄CPU.這樣，當(dāng) 一個(gè)進(jìn)程進(jìn)入就緒隊(duì)列時(shí)，它的PCB就鏈入了該就緒隊(duì)列的末尾，排隊(duì)等待 分配CPU.一般來(lái)說(shuō)，先來(lái)先服務(wù)調(diào)度算法對(duì)于長(zhǎng)任務(wù)來(lái)說(shuō)比較短任務(wù)要好 一些.FCFS算法不考慮作業(yè)運(yùn)行時(shí)間的長(zhǎng)短，僅按作業(yè)進(jìn)入輸入井時(shí)間的 先后進(jìn)行調(diào)度，因此對(duì)所有的作業(yè)是公平合理的。第三章 程序開發(fā)平臺(tái)及開發(fā)工具Visual C+是一個(gè)功能強(qiáng)大的可視化軟件開發(fā)工具。自1993年Microsoft公司推出 Visual C+1.0后

4、，隨著其新版本的不斷問(wèn)世，Visual C+已成為專業(yè)程序員進(jìn)行軟件 開發(fā)的首選工具。雖然微軟公司推出了 Visual C+.NET(Visual C+7.0)，但它的應(yīng)用的很大的局限性， 只適用于Windows 2000,Windows XP和Windows NT4.0。所以實(shí)際中，更多的是以 Visual C+6.0 為平臺(tái)。Visual C+6.0不僅是一個(gè)C+編譯器，而且是一個(gè)基于Windows操作系統(tǒng)的可視化集 成開發(fā)環(huán)境(integrated development environment,IDE)。Visual C+6.0 由許多組件組 成，包括編輯器、調(diào)試器以及程序向?qū)ppW

5、izard、類向?qū)lass Wizard等開發(fā)工具。 這些組件通過(guò)一個(gè)名為Developer Studio的組件集成為和諧的開發(fā)環(huán)境。Visual C+它大概可以分成三個(gè)主要的部分：Developer Studio,這是一個(gè)集成開發(fā)環(huán)境，我們?nèi)粘９ぷ鞯?9%都是在它上面完 成的，再加上它的標(biāo)題赫然寫著“Microsoft Visual如+所以很多人理所當(dāng)然的認(rèn)為， 那就是Visual C+了。其實(shí)不然，雖然Developer Studio提供了一個(gè)很好的編輯器和很 多Wizard，但實(shí)際上它沒(méi)有任何編譯和鏈接程序的功能，真正完成這些工作的幕后英 雄后面會(huì)介紹。我們也知道，Developer

6、Studio并不是專門用于VC的，它也同樣用于 VB, VJ, VID等Visual Studio家族的其他同胞兄弟。所以不要把Developer Studio當(dāng) 成Visual C+,它充其量只是Visual C+的一個(gè)殼子而已。這一點(diǎn)請(qǐng)切記！ MFC。從理論上來(lái)講，MFC 也不是專用于 Visual C+, Borland C+, C+Builder 和Symantec C+同樣可以處理MFC。同時(shí)，用Visual C+編寫代碼也并不意味著一 定要用MFC,只要愿意，用Visual C+來(lái)編寫SDK程序，或者使用STL, ATL, 一樣 沒(méi)有限制。不過(guò)，Visual C+本來(lái)就是為MFC打

7、造的，Visual C+中的許多特征和語(yǔ) 言擴(kuò)展也是為MFC而設(shè)計(jì)的，所以用Visual C+W不用MFC就等于拋棄了 Visual C+ 中很大的一部分功能。但是，Visual C+也不等于MFC。Platform SDK。這才是Visual C+和整個(gè)Visual Studio的精華和靈魂，雖然我們 很少能直接接觸到它。大致說(shuō)來(lái)，Platform SDK是以Microsoft C/C+編譯器為核心(不 是Visual C+，看清楚了)，配合MASM,輔以其他一些工具和文檔資料。上面說(shuō)到 Developer Studio沒(méi)有編譯程序的功能，那么這項(xiàng)工作是由誰(shuí)來(lái)完成的呢？是CL,是 NMAKE

8、,和其他許許多多命令行程序，這些我們看不到的程序才是構(gòu)成Visual Studio 的基石。第四章 算法數(shù)據(jù)結(jié)構(gòu)及流程圖4. 1算法數(shù)據(jù)結(jié)構(gòu)每個(gè)進(jìn)程有一個(gè)進(jìn)程控制塊(PCB)表示。進(jìn)程控制塊可以包含如 下信息：進(jìn)程名、優(yōu)先數(shù)、進(jìn)程時(shí)間輪轉(zhuǎn)時(shí)間片、計(jì)數(shù)器、需要運(yùn)行 時(shí)間、已用CPU時(shí)間、進(jìn)程狀態(tài)。每個(gè)進(jìn)程的狀態(tài)可以是就緒 W(Wait)、運(yùn)行R (Run)、或完成F (Finish)三種狀態(tài)之一。4.2算法流程圖最高優(yōu)先數(shù)調(diào)度算法流程圖第五章程序源代碼代碼如下：#include stdio.h#include #include #define getpch(type) (type*)malloc

9、(sizeof(type)#define NULL 0struct pcb /*定義進(jìn)程控制塊PCB */char name10;char state;int super;int ntime;int rtime;struct pcb* link;*ready=NULL,*p;typedef struct pcb PCB;sort() /*建立對(duì)進(jìn)程進(jìn)行優(yōu)先級(jí)排列函數(shù)*/PCB *first, *second;int insert=0;if(ready=NULL)ll(p-super)(ready-super) /*優(yōu)先級(jí)最大者，插入隊(duì)首*/(p-link=ready;ready=p;else

10、/*進(jìn)程比較優(yōu)先級(jí)，插入適當(dāng)?shù)奈恢弥?/(first=ready;second=first-link;while(second!=NULL)(if(p-s uper)(second-s uper) /*若插入進(jìn)程比當(dāng)前進(jìn)程優(yōu)先數(shù)大,*/( /*插入到當(dāng)前進(jìn)程前面*/p-link=second;first-link=p;second=NULL;insert=1;else /*插入進(jìn)程優(yōu)先數(shù)最低，則插入到隊(duì)尾*/(first=first-link;second=second-link;if(insert=0) first-link=p;input() /*建立進(jìn)程控制塊函數(shù)*/(int i,num

11、;printf(n please input n pcb?);scanf(%d,&num);for(i=0;iname);printf(n pcb super:);scanf(%d”,&p-super);printf(n pcb run time:);scanf(%d”,&p-ntime);printf(n);p-rtime=0;p-state=w;p-link=NULL;sort(); /* 調(diào)用 sort 函數(shù) */int space()(int l=0; PCB* pr=ready;while(pr!=NULL)(l+;pr=pr-link;return(l);disp(PCB * pr

12、) /*建立進(jìn)程顯示函數(shù)，用于顯示當(dāng)前進(jìn)程*/(printf(n qname t state t super t ndtime t runtime n);printf(|%st,pr-name);printf(|%ct,pr-state);printf(|%dt,pr-s uper);printf(|%dt,pr-ntime);printf(l%dt,pr-rtime);printf(n);check() /*建立進(jìn)程查看函數(shù)*/(PCB* pr;printf(n * now pcb running:%s,p-name); /* 顯示當(dāng)前運(yùn)行進(jìn)程*/ disp(p);pr=ready;prin

13、tf(n *now pcb waiting:n); /* 顯示就緒隊(duì)列狀態(tài) */while(pr!=NULL)(disp(pr);pr=pr-link;destroy() /*建立進(jìn)程撤消函數(shù)(進(jìn)程運(yùn)行結(jié)束,撤消進(jìn)程)*/(printf(n pcb %s successed.n,p-name);free(p);running() /*建立進(jìn)程就緒函數(shù)(進(jìn)程運(yùn)行時(shí)間到，置就緒狀態(tài)*/(p-rtime)+;if(p-rtime=p-ntime)destroy(); /* 調(diào)用 destroy 函數(shù) */else(p-super)-;p-state=w;sort(); /* 調(diào)用 sort 函數(shù) *

14、/main() /* 主函數(shù)*/(int len,h=0;char ch;input();len=space();while(len!=0)&(ready!=NULL)(ch=getchar();h+;printf(n The execute number:%d n,h);p=ready;ready=p-link;p-link=NULL;p-state=R;check();running();printf(n any key continue);ch=getchar();printf(nn pcb have succed.n);ch=getchar();第六章測(cè)試數(shù)據(jù)及測(cè)試結(jié)果最高優(yōu)先數(shù)進(jìn)程調(diào)

15、度算法模擬測(cè)試最高優(yōu)先數(shù)進(jìn)程調(diào)度算法模擬測(cè)試的輸入數(shù)據(jù)的及其結(jié)果如下：進(jìn)程名優(yōu)先級(jí)運(yùn)行時(shí)間a12b21c11d33e44please input n pcb?5pcb num No.1:pcb name:apcb super:1pcb run time:2pcb num No.2:pcb name:bpcb super:2pcb run time:1pcb num No.3:pcb name:cpcb super:1pcb num No.4:pcb name:dpcb super:3pcb run time:3pcb num No.5:pcb name:epcb super:4pcb run

16、time:4The execute number:1* now pcb running:eqnamestatesuperndtimeruntime|e|R|4|4|0*now pcb waiting:qnamestatesuperndtimeruntime|d|w|3|3|0qnamestatesuperndtimeruntime|b|w|2|1|0qnamestatesuperndtimeruntime|a|w|1|2|0qnamestatesuperndtimeruntime|c|w|1|1|0* now pcb running:dqnamestatesuperndtimeruntime|

17、d|R|3|3|0*now pcb waiting:qnamestatesuperndtimeruntime|e|w|3|4|1qnamestatesuperndtimeruntime|b|w|2|1|0qnamestatesuperndtimeruntime|a|w|1|2|0qnamestatesuperndtimeruntime|c|w|1|1|0any key continueThe execute number:3* now pcb running:eqnamestatesuperndtimeruntime|e|R|3|4|1*now pcb waiting:qnamestatesu

18、perndtimeruntime|b|w|2|1|0qnamestatesuperndtimeruntime|d|w|2|3|1qnamestatesuperndtimeruntime|a|w|1|2|0qnamestatesuperndtimeruntime|c|w|1|1|0The execute number:4* now pcb running:bqnamestatesuperndtimeruntime|b|R|2|1|0*now pcb waiting:qnamestatesuperndtimeruntime|d|w|2|3|1qnamestatesuperndtimeruntime

19、|e|w|2|4|2qnamestatesuperndtimeruntime|a|w|1|2|0qnamestatesuperndtimeruntime|c|w|1|1|0pcb b successed.any key continue.The execute number:5* now pcb running:dqnamestatesuperndtimeruntime|d|R|2|3|1*now pcb waiting:qnamestatesuperndtimeruntime|e|w|2|4|2qnamestatesuperndtimeruntime|a|w|1|2|0qnamestates

20、uperndtimeruntime|c|w|1|1|0The execute number:6* now pcb running:eqnamestatesuperndtimeruntime|e|R|2|4|2*now pcb waiting:qnamestatesuperndtimeruntime|a|w|1|2|0qnamestatesuperndtimeruntime|c|w|1|1|0qnamestatesuperndtimeruntime|d|w|1|3|2any key continueThe execute number:7* now pcb running:aqnamestate

21、superndtimeruntime|a|R|1|2|0*now pcb waiting:qnamestatesuperndtimeruntime|c|w|1|1|0qnamestatesuperndtimeruntime|d|w|1|3|2qnamestatesuperndtimeruntime|e|w|1|4|3any key continue* now pcb running:cqname state super|c|R|1ndtime|1|0runtime*now pcb waiting:qname state super|d|w|1ndtime|3|2runtimeqname sta

22、te super|e|w|1ndtime|4|3runtimeqname state super|a|w|0ndtime|2|1runtimepcb c successed.any key continueThe execute number:9* now pcb running:d qname state super|d|R|1ndtime|3|2runtime*now pcb waiting:qname state super|e|w|1ndtime|4|3runtimeqname state super|a|w|0ndtime|2|1runtimepcb d successed.any

23、key continue.The execute number:10* now pcb running:eqname state super|e |R |1ndtime|4runtime13*now pcb waiting:qname state super|a |w |0ndtime|2runtime11pcb e successed.any key continueThe execute number:11qname state super|e |R |1ndtime|4runtime13*now pcb waiting:qname state super|a |w |0ndtime|2runtime11pcb e successed.any key continueThe execute number:11* now pcb running:a qname state super|a |R |0ndtime|2runtime|1*now pcb waiting:pcb a successed.any key contin