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

1、<p><b>　　計算機科學(xué)與應(yīng)用系</b></p><p><b>　　操作系統(tǒng)原理</b></p><p><b>　　課程設(shè)計報告</b></p><p>　　題目 進程調(diào)度算法 </p><p>　　學(xué)號 <

2、;/p><p>　　班級 </p><p>　　姓名 </p><p>　　專業(yè) 計算機科學(xué)與技術(shù) </p><p>　　指導(dǎo)教師 </p><p>　　完成日期 2013.6.12

3、 </p><p><b>　　進程調(diào)度算法</b></p><p><b>　　一.實驗?zāi)康?lt;/b></p><p>　　通過優(yōu)先權(quán)法與輪轉(zhuǎn)調(diào)度算法的模擬加深對進程概念和進程調(diào)度過程的理解，掌握進程狀態(tài)之間的切換，同時掌握進程調(diào)度算法的實現(xiàn)方法和技巧。</p><p><b>　　二.

4、實驗內(nèi)容</b></p><p>　　1.用C語言或C++語言來實現(xiàn)對N個進程采用優(yōu)先算法以及輪轉(zhuǎn)算法的進程調(diào)度。</p><p>　　2.每個用來標(biāo)示進程的進程控制塊PCB用結(jié)果來描述，包括以下字段</p><p>　　（1）進程標(biāo)識ID，其中0為閑逛進程，用戶進程的標(biāo)識數(shù)為1、2、3、、、、、、、。</p><p>　?。?）

5、進程優(yōu)先級Priority，閑逛進程（idle）的優(yōu)先級為0，用戶有進程的優(yōu)先級大于0，且隨機產(chǎn)生，標(biāo)識數(shù)越大，優(yōu)先級越高。</p><p>　?。?）進程占用的CPU時間CPUtime，進程每運一次，累積等于4.</p><p>　?。?）進程總共需要運行時間Alltime，利用隨機函數(shù)產(chǎn)生。</p><p>　?。?）進程狀態(tài)，0—就緒態(tài)，1—運行態(tài)，2—阻塞態(tài)

6、。</p><p>　?。?）隊列指針next，用來將多個進程控制塊PCB鏈接為隊列。</p><p>　　3.優(yōu)先數(shù)改變的原則</p><p>　?。?）進程在就緒隊列中每呆一個時間片，優(yōu)先數(shù)增加1.</p><p>　?。?）進程每運行一個時間片，優(yōu)先數(shù)增加1.</p><p>　　4.在調(diào)度前，系統(tǒng)中擁有的進程數(shù)

7、PCB_number有鍵盤輸入，進初始化后，所有的進程控制塊PCB連接成就緒隊列。</p><p>　　5.為了清楚的觀察諸進程的調(diào)度過程，程序應(yīng)將每個時間片內(nèi)的進程的情況顯示出來。</p><p><b>　　三.設(shè)計要求</b></p><p>　　1．需寫出設(shè)計說明；</p><p>　　2．設(shè)計實現(xiàn)代碼及說明；&

8、lt;/p><p><b>　　3．運行結(jié)果.</b></p><p><b>　　四.實驗步驟</b></p><p>　　1.進程管理程序調(diào)試好后運行進程管理程序</p><p>　　圖1 進程管理調(diào)試界面</p><p><b>　　Y</b><

9、/p><p><b>　　N</b></p><p><b>　　N</b></p><p><b>　　Y</b></p><p><b>　　Y</b></p><p><b>　　N</b></p&g

10、t;<p><b>　　N</b></p><p><b>　　Y</b></p><p><b>　　Y</b></p><p><b>　　N</b></p><p><b>　　N</b></p>&

11、lt;p><b>　　Y</b></p><p>　　優(yōu)先權(quán)調(diào)度模擬流程圖</p><p><b>　　2.優(yōu)先權(quán)調(diào)度</b></p><p>　?。?）輸入1選擇優(yōu)先權(quán)調(diào)度算法模擬。</p><p>　?。?）輸入開始進程個數(shù)n，創(chuàng)建n個PCB并加入就緒隊列ready_queue中。<

12、/p><p>　?。?）就緒隊列ready_queue不為空，調(diào)度就緒隊列中第一個進程運行，否則，從閑逛隊列idleprocess中調(diào)度閑逛進程運行。</p><p>　　（4）在運行過程中，當(dāng)遇到阻塞，則該進程插入到阻塞隊列block_queue中，且將該進程從ready_queue中刪除。</p><p>　?。?）如果運行時間CPUtime大于等于Alltime，

13、該進程運行完畢，釋放該進程；否則插入到就緒隊列中。</p><p>　?。?）更新就緒隊列中的優(yōu)先級數(shù)。</p><p>　?。?）隨機對阻塞隊列block_queue中的進程PCB詢問是否要喚醒，喚醒，即從喚醒隊列中選擇第一個進程，且插入就緒隊列中；阻塞隊列中沒有阻塞進程返回。</p><p>　?。?）重復(fù)上述步驟，直到本次調(diào)度結(jié)束。</p>&l

14、t;p>　　圖2 優(yōu)先調(diào)度運行結(jié)果</p><p><b>　　3.輪轉(zhuǎn)調(diào)度</b></p><p>　?。?）輸入2選擇優(yōu)先權(quán)調(diào)度算法模擬。</p><p>　　（2）輸入開始進程個數(shù)n，創(chuàng)建n個PCB并加入就緒隊列ready_queue中。</p><p>　?。?）就緒隊列ready_queue不為空，調(diào)度

15、就緒隊列中第一個進程運行，否則，從閑逛隊列idleprocess中調(diào)度閑逛進程運行。</p><p>　　（4）在運行過程中，當(dāng)遇到阻塞，則該進程插入到阻塞隊列block_queue中，且將該進程從ready_queue中刪除。</p><p>　?。?）如果運行時間CPUtime大于等于Alltime，該進程運行完畢，釋放該進程；否則插入到就緒隊列中。</p><p&

16、gt;　　（6）隨機對阻塞隊列block_queue中的進程PCB詢問是否要喚醒，喚醒，即從喚醒隊列中選擇第一個進程，且插入就緒隊列中；阻塞隊列中沒有阻塞進程返回。</p><p>　?。?）如果時間到，本次調(diào)度結(jié)束，否則重復(fù)上述步驟，直到本次調(diào)度結(jié)束。</p><p>　　圖3 輪轉(zhuǎn)調(diào)度運行結(jié)果</p><p><b>　　Y</b><

17、;/p><p><b>　　N</b></p><p><b>　　N</b></p><p><b>　　Y</b></p><p><b>　　Y</b></p><p><b>　　N</b></p&

18、gt;<p><b>　　N</b></p><p><b>　　Y</b></p><p><b>　　Y</b></p><p><b>　　N</b></p><p><b>　　N</b></p>

19、<p><b>　　Y</b></p><p><b>　　Y</b></p><p><b>　　輪轉(zhuǎn)調(diào)度模擬流程圖</b></p><p>　　五.實驗過程中遇到的問題及解決方案</p><p>　　1、請仔細閱讀動態(tài)優(yōu)先權(quán)的進程調(diào)度算法的模擬實現(xiàn)代碼,說明該算法

20、與教材中介紹的算法做了哪些簡單化處理.</p><p>　　優(yōu)先權(quán)模擬時優(yōu)先權(quán)是隨機產(chǎn)生，在實際的系統(tǒng)中，系統(tǒng)進程的優(yōu)先權(quán)高于一般用戶進程的優(yōu)先權(quán)。</p><p>　　2、為什么對進程的優(yōu)先數(shù)可按上述原則進行修改?</p><p>　　最高優(yōu)先權(quán)調(diào)度算法僅照顧了優(yōu)先權(quán)高的進程，當(dāng)不斷有優(yōu)先權(quán)高的進程需調(diào)度時，而優(yōu)先權(quán)低的進程將很難得到處理機的調(diào)度，所以進程在就緒隊

21、列中每呆一個時間片，優(yōu)先數(shù)增加1，使優(yōu)先權(quán)低的進程不總是忙等。</p><p>　　3、請給出設(shè)計實現(xiàn)的輪轉(zhuǎn)發(fā)進程調(diào)度算法的設(shè)計思想.</p><p>　　時間輪轉(zhuǎn)調(diào)度算法：系統(tǒng)將所有的就像進程按先來先服務(wù)的原則，排成一個隊列，每次調(diào)度時，把CPU分配給首進程，并令其執(zhí)行一個時間片。當(dāng)執(zhí)行的時間片用完時，發(fā)出中斷請求，調(diào)度程序便據(jù)此信號來停止該進程的執(zhí)行，并將其送到就緒隊列的末尾，如此反復(fù)

22、，就可以保證就緒隊列中的所有進程在一個給定的時間內(nèi)，均能獲得一時間片處理機執(zhí)行時間。</p><p>　　4、在實際的進程調(diào)度中，除了按調(diào)度算法選擇下一個執(zhí)行的進程外,還應(yīng)處理哪些工作?</p><p>　　最高優(yōu)先權(quán)調(diào)度算法，常用于批處理系統(tǒng)中，作為作業(yè)調(diào)度算法，也作為多種操作系統(tǒng)中的進程調(diào)度算法，還可以用于實時系統(tǒng)中：時間輪轉(zhuǎn)調(diào)度算法，一般用于分時系統(tǒng)中。</p><

23、;p><b>　　六.實驗體會</b></p><p>　　1、當(dāng)把該算法用于作業(yè)調(diào)度時，系統(tǒng)將從后備隊列中選擇若干個優(yōu)先權(quán)最高的作業(yè)，裝入內(nèi)存，當(dāng)用于進程調(diào)度算法時，該算法是把處理及分配給就緒隊列中優(yōu)先權(quán)最高的進程。</p><p>　　2、當(dāng)系統(tǒng)空閑（就緒隊列為空）時，系統(tǒng)運行閑逛進程，否則運行其他進程，發(fā)生變遷（就緒運行）</p><p

24、>　　3、在運行進程（包括閑逛進程）的過程中，可能發(fā)生變遷2(運行阻塞)，即將運行進程插入到阻塞隊列（閑逛進程不能不被阻塞），可能有其他的進程創(chuàng)建PCB，還可能喚醒阻塞隊列中的某些進程PCB，發(fā)生變遷3（阻塞就緒），即從阻塞隊列中插入就緒隊列中。</p><p>　　4、時間片運行結(jié)束后，若進程累積占用CPU時間大于等于進程需要運行時間，則進程執(zhí)行結(jié)束，釋放其PCB。若進程累積占用CPU時間小于進程需要運行

25、時間，發(fā)生變遷4（運行就緒），即將當(dāng)前運行的進程插入就緒隊列中。</p><p><b>　　七.參考資料</b></p><p><b>　　《計算機操作系統(tǒng)》</b></p><p>　　《計算機操作系統(tǒng)實驗指導(dǎo)書》</p><p><b>　　《C程序設(shè)計》</b><

26、;/p><p>　　《C語言程序設(shè)計_現(xiàn)代方法》</p><p><b>　　八.源代碼</b></p><p>　　#include <stdio.h></p><p>　　#include <stdlib.h></p><p>　　#include <time.h&g

27、t;</p><p>　　#define N 5 //進程個數(shù)，可改變</p><p>　　int rt[N]; //到達時間</p><p>　　int st[N]; //服務(wù)時間</p><p>　　int ct[N]; //完成時間</p><p>　　int cyt[N]; //周轉(zhuǎn)時間</p&

28、gt;<p>　　float rct[N]; //帶權(quán)周轉(zhuǎn)時間</p><p>　　float av[2];</p><p>　　int n,m,c=1,which;</p><p>　　void line() //美化程序，使程序運行時更加明朗美觀</p><p><b>　　{</b></

29、p><p>　　printf("------------------------------------------------------------------\n");</p><p><b>　　}</b></p><p>　　void start() //表示FCFS算法開始</p><p>

30、;<b>　　{</b></p><p><b>　　line();</b></p><p>　　printf(" FCFS算法開始\n");</p><p>　　printf("

31、 ——Designed by Zhang Hong\n");</p><p><b>　　line();</b></p><p><b>　　}</b></p><p>　　void end() //表示FCFS算法結(jié)束</p><p><b>　　{</b>

32、;</p><p><b>　　line();</b></p><p>　　printf(" FCFS算法結(jié)束,謝謝使用\n");</p><p><b>　　line();</b></p><p><b>　　}</b&g

33、t;</p><p>　　void input()</p><p><b>　　{</b></p><p>　　printf("請輸入%d個進程的到達時間：",N);</p><p>　　for (n=0;n<N;n++)</p><p>　　scanf("%d

34、",&rt[n]);</p><p>　　printf("請輸入%d個進程對應(yīng)的服務(wù)時間：",N);</p><p>　　for (n=0;n<N;n++)</p><p>　　scanf("%d",&st[n]);</p><p><b>　　}</b&

35、gt;</p><p>　　void random()</p><p><b>　　{</b></p><p>　　srand((unsigned)time(NULL));</p><p>　　for (n=0;n<N;n++)</p><p><b>　　{</b>&

36、lt;/p><p>　　rt[n]=rand()%100;</p><p>　　for (m=0;m<n;m++)</p><p>　　if (n!=0 && rt[n]==rt[m])</p><p><b>　　{</b></p><p>　　rt[n]=rand()%100

37、;</p><p><b>　　m=0;</b></p><p><b>　　}</b></p><p>　　st[n]=rand()%98+1;</p><p>　　for (m=0;m<n;m++)</p><p>　　if (n!=0 && st[

38、n]==st[m])</p><p><b>　　{</b></p><p>　　st[n]=rand()%98+1;</p><p><b>　　m=0;</b></p><p><b>　　}</b></p><p><b>　　}<

39、/b></p><p><b>　　}</b></p><p>　　void ordination() //重新排序，應(yīng)對出現(xiàn)輸入的到達時間為亂序的情況</p><p><b>　　{</b></p><p><b>　　int temp;</b></p>

40、;<p>　　for (n=0;n<N;n++)</p><p>　　for (m=0;m<N-n-1;m++)</p><p>　　if (rt[m+1]<rt[m])</p><p><b>　　{</b></p><p>　　temp=rt[m+1];</p><

41、p>　　rt[m+1]=rt[m];</p><p>　　rt[m]=temp;</p><p>　　temp=st[m+1];</p><p>　　st[m+1]=st[m];</p><p>　　st[m]=temp;</p><p><b>　　}</b></p><

42、;p><b>　　}</b></p><p>　　void fcfs() //執(zhí)行fcfs算法</p><p><b>　　{</b></p><p><b>　　av[0]=0;</b></p><p><b>　　av[1]=0;</b>

43、</p><p>　　ct[0]=rt[0]+st[0];</p><p>　　for (n=1;n<N;n++)</p><p><b>　　{</b></p><p>　　if (ct[n-1]>=rt[n]) //考慮當(dāng)前一個進程完成而后一個進程還沒有到達的情況</p><p&

44、gt;　　ct[n]=ct[n-1]+st[n];</p><p><b>　　else</b></p><p>　　ct[n]=rt[n]+st[n];</p><p><b>　　}</b></p><p>　　for (n=0;n<N;n++)</p><p>　

45、　cyt[n]=ct[n]-rt[n];</p><p>　　for (n=0;n<N;n++)</p><p>　　rct[n]=(float)cyt[n]/(float)st[n];</p><p>　　for (n=0;n<N;n++)</p><p><b>　　{</b></p>&l

46、t;p>　　av[0]+=(float)cyt[n]/N;</p><p>　　av[1]+=rct[n]/N;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void output() //輸出結(jié)果</p><p&

47、gt;<b>　　{</b></p><p><b>　　line();</b></p><p>　　printf("進程名\t");</p><p>　　for (n=0;n<N;n++)</p><p>　　printf("\t%c",65+n);&

48、lt;/p><p>　　printf("\t平均\n到達時間");</p><p>　　for (n=0;n<N;n++)</p><p>　　printf("\t%d",rt[n]);</p><p>　　printf("\n服務(wù)時間");</p><p>

49、;　　for (n=0;n<N;n++)</p><p>　　printf("\t%d",st[n]);</p><p>　　printf("\n完成時間");</p><p>　　for (n=0;n<N;n++)</p><p>　　printf("\t%d",ct[

50、n]);</p><p>　　printf("\n周轉(zhuǎn)時間");</p><p>　　for (n=0;n<N;n++)</p><p>　　printf("\t%d",cyt[n]);</p><p>　　printf("\t%0.1f",av[0]);</p>

51、<p>　　printf("\n帶權(quán)周轉(zhuǎn)時間");</p><p>　　for (n=0;n<N;n++)</p><p>　　printf("\t%0.1f",rct[n]);</p><p>　　printf("\t%0.1f",av[1]);</p><p>

52、　　printf("\n");</p><p><b>　　line();</b></p><p><b>　　}</b></p><p>　　void main()</p><p><b>　　{</b></p><p><b

53、>　　start();</b></p><p>　　for (;c==1;)</p><p><b>　　{</b></p><p><b>　　for (;;)</b></p><p><b>　　{</b></p><p>　　pr

54、intf("輸入數(shù)據(jù)還是由系統(tǒng)隨機產(chǎn)生數(shù)據(jù)？\n1、輸入數(shù)據(jù)\t2、系統(tǒng)隨機產(chǎn)生數(shù)據(jù)\n請輸入：");</p><p>　　scanf("%d",&which);</p><p>　　if (which==1)</p><p><b>　　{</b></p><p><

55、;b>　　input();</b></p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p>　　if (which==2)</p><p>

56、<b>　　{</b></p><p><b>　　random();</b></p><p><b>　　break;</b></p><p><b>　　}</b></p><p>　　printf("輸入錯誤，請重新輸入！");&

57、lt;/p><p><b>　　}</b></p><p>　　ordination(); //進程按照到達時間進行排序</p><p><b>　　fcfs();</b></p><p><b>　　output();</b></p><p>　　p

58、rintf("繼續(xù)輸入，退出輸入。請輸入：");</p><p>　　scanf("%d",&c);</p><p><b>　　}</b></p><p><b>　　end();</b></p><p><b>　　}</b>