操作系統(tǒng)_進(jìn)程調(diào)度算法課程設(shè)計(jì)報(bào)告

1、<p><b>　　操作系統(tǒng)原理</b></p><p><b>　　課程設(shè)計(jì)報(bào)告</b></p><p><b>　　題目：進(jìn)程調(diào)度算法</b></p><p>　　課程名稱：操作系統(tǒng) </p><p>　　姓 名：

2、 </p><p>　　學(xué) 號： </p><p>　　專 業(yè)：計(jì)算機(jī)科學(xué)與技術(shù) </p><p>　　學(xué) 校： </p><p>　　指導(dǎo)老師： </p><p>　　

3、日 期：2014.3.1 </p><p><b>　　目錄</b></p><p>　　設(shè)計(jì)要求--------------------------------------3</p><p>　　設(shè)計(jì)思想流程--------------------------------3</p><p&g

4、t;　　數(shù)據(jù)結(jié)構(gòu)--------------------------------------5</p><p>　　程序清單--------------------------------------6</p><p>　　運(yùn)行結(jié)果--------------------------------------9</p><p>　　實(shí)驗(yàn)體會(huì)--------------

5、------------------------11</p><p>　　設(shè)計(jì)心得--------------------------------------12</p><p>　　八． 參考文獻(xiàn)--------------------------------------12</p><p><b>　　進(jìn)程調(diào)度算法</b></p>

6、;<p><b>　　一.設(shè)計(jì)要求</b></p><p>　　1.編寫一個(gè)進(jìn)程調(diào)度程序，允許多個(gè)進(jìn)程并行執(zhí)行。</p><p>　　2.每個(gè)進(jìn)程有一個(gè)進(jìn)程控制塊（PCB）表示。進(jìn)程控制塊可以包含如下信息：進(jìn)程名、優(yōu)先數(shù)、到達(dá)時(shí)間、需要運(yùn)行時(shí)間、已用CPU時(shí)間、進(jìn)程狀態(tài)等等。</p><p>　　3.進(jìn)程的優(yōu)先數(shù)及需要的運(yùn)行時(shí)間可

7、以事先人為地指定（也可以由隨機(jī)數(shù)產(chǎn)生）。進(jìn)程的到達(dá)時(shí)間為輸入進(jìn)程的時(shí)間。</p><p><b>　　二．設(shè)計(jì)思想流程</b></p><p>　　1. 優(yōu)先權(quán)調(diào)度模擬流程圖</p><p><b>　　Y</b></p><p><b>　　N</b></p>

8、<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><

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

10、　　優(yōu)先權(quán)調(diào)度模擬流程圖</p><p>　　2.按時(shí)間片輪轉(zhuǎn)調(diào)度模擬流程圖</p><p><b>　　Y</b></p><p><b>　　N</b></p><p><b>　　N</b></p><p><b>　　Y</b&g

11、t;</p><p><b>　　Y</b></p><p><b>　　N</b></p><p><b>　　N</b></p><p><b>　　Y</b></p><p><b>　　Y</b>&l

12、t;/p><p><b>　　N</b></p><p><b>　　N</b></p><p><b>　　Y</b></p><p><b>　　Y</b></p><p>　　時(shí)間片輪轉(zhuǎn)調(diào)度模擬流程圖</p><

13、;p><b>　　三．?dāng)?shù)據(jù)結(jié)構(gòu)</b></p><p>　　1.進(jìn)程管理程序調(diào)試好后運(yùn)行進(jìn)程管理程序 </p><p><b>　　2.優(yōu)先權(quán)調(diào)度</b></p><p>　?。?）輸入1選擇優(yōu)先權(quán)調(diào)度算法模擬。</p><p>　?。?）輸入開始進(jìn)程個(gè)數(shù)n，創(chuàng)建n個(gè)PCB并加入就緒隊(duì)列re

14、ady_queue中。</p><p>　　（3）就緒隊(duì)列ready_queue不為空，調(diào)度就緒隊(duì)列中第一個(gè)進(jìn)程運(yùn)行，否則，從閑逛隊(duì)列idleprocess中調(diào)度閑逛進(jìn)程運(yùn)行。</p><p>　?。?）在運(yùn)行過程中，當(dāng)遇到阻塞，則該進(jìn)程插入到阻塞隊(duì)列block_queue中，且將該進(jìn)程從ready_queue中刪除。</p><p>　?。?）如果運(yùn)行時(shí)間CPUt

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

16、。</p><p>　　3.按時(shí)間片輪轉(zhuǎn)調(diào)度</p><p>　?。?）輸入2選擇優(yōu)先權(quán)調(diào)度算法模擬。</p><p>　　（2）輸入開始進(jìn)程個(gè)數(shù)n，創(chuàng)建n個(gè)PCB并加入就緒隊(duì)列ready_queue中。</p><p>　?。?）就緒隊(duì)列ready_queue不為空，調(diào)度就緒隊(duì)列中第一個(gè)進(jìn)程運(yùn)行，否則，從閑逛隊(duì)列idleprocess中調(diào)度

17、閑逛進(jìn)程運(yùn)行。</p><p>　?。?）在運(yùn)行過程中，當(dāng)遇到阻塞，則該進(jìn)程插入到阻塞隊(duì)列block_queue中，且將該進(jìn)程從ready_queue中刪除。</p><p>　?。?）如果運(yùn)行時(shí)間CPUtime大于等于Alltime，該進(jìn)程運(yùn)行完畢，釋放該進(jìn)程；否則插入到就緒隊(duì)列中。</p><p>　?。?）隨機(jī)對阻塞隊(duì)列block_queue中的進(jìn)程PCB詢問

18、是否要喚醒，喚醒，即從喚醒隊(duì)列中選擇第一個(gè)進(jìn)程，且插入就緒隊(duì)列中；阻塞隊(duì)列中沒有阻塞進(jìn)程返回。</p><p>　?。?）如果時(shí)間到，本次調(diào)度結(jié)束，否則重復(fù)上述步驟，直到本次調(diào)度結(jié)束。</p><p><b>　　四. 源程序代碼</b></p><p>　　#include <stdio.h></p><p&g

19、t;　　#include <stdlib.h></p><p>　　#include <time.h></p><p>　　#define N 5 //進(jìn)程個(gè)數(shù)，可改變</p><p>　　int rt[N]; //到達(dá)時(shí)間</p><p>　　int st[N]; //服務(wù)時(shí)間</p><

20、p>　　int ct[N]; //完成時(shí)間</p><p>　　int cyt[N]; //周轉(zhuǎn)時(shí)間</p><p>　　float rct[N]; //帶權(quán)周轉(zhuǎn)時(shí)間</p><p>　　float av[2];</p><p>　　int n,m,c=1,which;</p><p>　　void line(

21、) //美化程序，使程序運(yùn)行時(shí)更加明朗美觀</p><p><b>　　{</b></p><p>　　printf("------------------------------------------------------------------\n");</p><p><b>　　}</b&

22、gt;</p><p>　　void start() //表示FCFS算法開始</p><p><b>　　{</b></p><p><b>　　line();</b></p><p>　　printf(" FCFS算法開始\n&quo

23、t;);</p><p>　　printf(" ——Designed by Zhang Hong\n");</p><p><b>　　line();</b></p><p><b>　　}</b></p><p&g

24、t;　　void end() //表示FCFS算法結(jié)束</p><p><b>　　{</b></p><p><b>　　line();</b></p><p>　　printf(" FCFS算法結(jié)束,謝謝使用\n");</p><p

25、><b>　　line();</b></p><p><b>　　}</b></p><p>　　void input()</p><p><b>　　{</b></p><p>　　printf("請輸入%d個(gè)進(jìn)程的到達(dá)時(shí)間：",N);</p&

26、gt;<p>　　for (n=0;n<N;n++)</p><p>　　scanf("%d",&rt[n]);</p><p>　　printf("請輸入%d個(gè)進(jìn)程對應(yīng)的服務(wù)時(shí)間：",N);</p><p>　　for (n=0;n<N;n++)</p><p>　　

27、scanf("%d",&st[n]);</p><p><b>　　}</b></p><p>　　void random()</p><p><b>　　{</b></p><p>　　srand((unsigned)time(NULL));</p>&l

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

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

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

31、gt;<p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void ordination() //重新排序，應(yīng)對出現(xiàn)輸入的到達(dá)時(shí)間為亂序的情況</p><p><b>

32、　　{</b></p><p><b>　　int temp;</b></p><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>&

33、lt;b>　　{</b></p><p>　　temp=rt[m+1];</p><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&g

34、t;　　st[m]=temp;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void fcfs() //執(zhí)行fcfs算法</p><p><b>　　{</b></p><p><b&

35、gt;　　av[0]=0;</b></p><p><b>　　av[1]=0;</b></p><p>　　ct[0]=rt[0]+st[0];</p><p>　　for (n=1;n<N;n++)</p><p><b>　　{</b></p><p>

36、;　　if (ct[n-1]>=rt[n]) //考慮當(dāng)前一個(gè)進(jìn)程完成而后一個(gè)進(jìn)程還沒有到達(dá)的情況</p><p>　　ct[n]=ct[n-1]+st[n];</p><p><b>　　else</b></p><p>　　ct[n]=rt[n]+st[n];</p><p><b>　　}&l

37、t;/b></p><p>　　for (n=0;n<N;n++)</p><p>　　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

38、(n=0;n<N;n++)</p><p><b>　　{</b></p><p>　　av[0]+=(float)cyt[n]/N;</p><p>　　av[1]+=rct[n]/N;</p><p><b>　　}</b></p><p><b>　　}

39、</b></p><p>　　void output() //輸出結(jié)果</p><p><b>　　{</b></p><p><b>　　line();</b></p><p>　　printf("進(jìn)程名\t");</p><p>　　f

40、or (n=0;n<N;n++)</p><p>　　printf("\t%c",65+n);</p><p>　　printf("\t平均\n到達(dá)時(shí)間");</p><p>　　for (n=0;n<N;n++)</p><p>　　printf("\t%d",rt[n

41、]);</p><p>　　printf("\n服務(wù)時(shí)間");</p><p>　　for (n=0;n<N;n++)</p><p>　　printf("\t%d",st[n]);</p><p>　　printf("\n完成時(shí)間");</p><p>

42、;　　for (n=0;n<N;n++)</p><p>　　printf("\t%d",ct[n]);</p><p>　　printf("\n周轉(zhuǎn)時(shí)間");</p><p>　　for (n=0;n<N;n++)</p><p>　　printf("\t%d",cyt

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

44、p><p>　　printf("\t%0.1f",av[1]);</p><p>　　printf("\n");</p><p><b>　　line();</b></p><p><b>　　}</b></p><p>　　void ma

45、in()</p><p><b>　　{</b></p><p><b>　　start();</b></p><p>　　for (;c==1;)</p><p><b>　　{</b></p><p><b>　　for (;;)</

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

47、ch==1)</p><p><b>　　{</b></p><p><b>　　input();</b></p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>

48、　　else</b></p><p>　　if (which==2)</p><p><b>　　{</b></p><p><b>　　random();</b></p><p><b>　　break;</b></p><p><b

49、>　　}</b></p><p>　　printf("輸入錯(cuò)誤，請重新輸入！");</p><p><b>　　}</b></p><p>　　ordination(); //進(jìn)程按照到達(dá)時(shí)間進(jìn)行排序</p><p><b>　　fcfs();</b>&l

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

51、gt;<b>　　end();</b></p><p><b>　　}</b></p><p><b>　　五．運(yùn)行結(jié)果</b></p><p>　　圖1 進(jìn)程管理調(diào)試界面</p><p>　　圖2 優(yōu)先調(diào)度運(yùn)行結(jié)果</p><p>　　圖3 輪轉(zhuǎn)調(diào)

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

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

54、若進(jìn)程累積占用CPU時(shí)間小于進(jìn)程需要運(yùn)行時(shí)間，發(fā)生變遷4（運(yùn)行就緒），即將當(dāng)前運(yùn)行的進(jìn)程插入就緒隊(duì)列中。</p><p><b>　　七．設(shè)計(jì)心得</b></p><p>　　通過做本實(shí)驗(yàn)，我在以前學(xué)過的知識(shí)的基礎(chǔ)上有了提高，學(xué)到了很多新知識(shí)：比如將用戶作業(yè)和就緒進(jìn)程按提交的順序或變?yōu)榫途w狀態(tài)的先后排成隊(duì)列，并按照先來先服務(wù)的方式進(jìn)行調(diào)度。調(diào)度時(shí)從后備隊(duì)列中選擇若干優(yōu)

55、先權(quán)最高的個(gè)作業(yè)進(jìn)入內(nèi)存；或從就緒隊(duì)列中選擇優(yōu)先權(quán)最高的進(jìn)程，將處理機(jī)分配給它。對進(jìn)程優(yōu)先、進(jìn)程或作業(yè)先來先服務(wù)、按時(shí)間片輪轉(zhuǎn)調(diào)度算法以及進(jìn)程調(diào)度的概念和算法，有了更深入的認(rèn)識(shí)！初步理解了操作系統(tǒng)對于作業(yè)處理的基本思想！了解到算法很重要，又更加明白算法本身可以節(jié)約時(shí)間，而且不同的函數(shù)之間在調(diào)用的時(shí)候要注意很多的問題。在動(dòng)手操作過程中，體會(huì)到了成功的喜悅和遇到問題自己解決的能力，對于我來說是一次提高，讓自己多多的在實(shí)踐中可以加深對理論的理

56、解，也讓我明白了以后應(yīng)該如何更好，更高效的學(xué)習(xí)。</p><p><b>　　七.參考文獻(xiàn)</b></p><p><b>　　《計(jì)算機(jī)操作系統(tǒng)》</b></p><p>　　《計(jì)算機(jī)操作系統(tǒng)實(shí)驗(yàn)指導(dǎo)書》</p><p><b>　　《C程序設(shè)計(jì)》</b></p>