操作系統(tǒng)課程設(shè)計-莫黎(共29頁)

1、PAGE 課 程 設(shè) 計 報 告課程名稱 操作系統(tǒng)(co zu x tn) 課題(kt)名稱 進程(jnchng)調(diào)度算法的設(shè)計 專 業(yè) 通信工程 班 級 1101 學(xué) 號 201103020135 姓 名 莫 黎 指導(dǎo)教師 顏國風(fēng) 2014年 6 月 29 日湖南工程學(xué)院課 程 設(shè) 計 任 務(wù) 書課程名稱 操作系統(tǒng)(co zu x tn) 課 題 進程調(diào)度(diod)算法的設(shè)計 專業(yè)(zhuny)班級 通信1101 學(xué)生姓名 莫 黎 學(xué) 號 201103020135 指導(dǎo)老師 顏國風(fēng) 審 批 任務(wù)書下達日期 2014 年 6 月 23 日任務(wù)完成日期 2014 年 6 月 29 日1設(shè)計內(nèi)容

2、(nirng)與設(shè)計要求1.1設(shè)計(shj)內(nèi)容1.1.1 進程調(diào)度(diod)算法的設(shè)計 設(shè)計要求：設(shè)計進程控制塊PCB表結(jié)構(gòu)，分別適用于優(yōu)先數(shù)調(diào)度算法和循環(huán)輪轉(zhuǎn)調(diào)度算法。建立進程就緒隊列。對兩種不同算法編制入鏈子程序。編制兩種進程調(diào)度算法：1）優(yōu)先數(shù)調(diào)度；2）循環(huán)輪轉(zhuǎn)調(diào)度 設(shè)計技術(shù)參數(shù):本程序用兩種算法對五個進程進行調(diào)度，每個進程可有三個狀態(tài)，并假設(shè)初始狀態(tài)為就緒狀態(tài)。為了便于處理，程序中的某進程運行時間以時間片為單位計算。各進程的優(yōu)先數(shù)或輪轉(zhuǎn)時間數(shù)以及進程需運行的時間片數(shù)的初始值均由用戶給定。在優(yōu)先數(shù)算法中，優(yōu)先數(shù)的值為50與運行時間的差值，即P_TIME-process-needtim

3、e。進程每執(zhí)行一次，優(yōu)先數(shù)減3，CPU時間片數(shù)加1，進程還需要的時間片數(shù)減1。在輪轉(zhuǎn)算法中，采用固定時間片（即：每執(zhí)行一次進程，該進程的執(zhí)行時間片數(shù)為已執(zhí)行了2個單位），這時，CPU時間片數(shù)加2，進程還需要的時間片數(shù)減2，并排列到就緒隊列的尾上。對于遇到優(yōu)先數(shù)一致的情況，采用FIFO策略解決。 1.1.2 銀行家算法設(shè)計 設(shè)計要求：編制銀行家算法通用程序，并檢測所給狀態(tài)的系統(tǒng)安全性。設(shè)進程I提出請求RequestN，則銀行家算法按如下規(guī)則進行判斷。 (1)如果RequestN=NEEDI，N，則轉(zhuǎn)(2)；否則，出錯。 (2)如果RequestNneedtime。進程每執(zhí)行一次，優(yōu)先數(shù)減3，CP

4、U時間片數(shù)加1，進程還需要的時間片數(shù)減1。在輪轉(zhuǎn)算法中，采用固定時間片（即：每執(zhí)行一次進程，該進程的執(zhí)行時間片數(shù)為已執(zhí)行了2個單位），這時，CPU時間片數(shù)加2，進程還需要的時間片數(shù)減2，并排列到就緒隊列的尾上。對于遇到優(yōu)先數(shù)一致的情況，采用FIFO策略解決。 三.設(shè)計原理3.1 循環(huán)輪轉(zhuǎn)調(diào)度算法時間片輪轉(zhuǎn)調(diào)度是一種最古老，最簡單，最公平且使用最廣的算法。每個進程被分配一個時間段，稱作它的時間片，即該進程允許運行的時間。如果在時間片結(jié)束時進程還在運行，則CPU將被剝奪并分配給另一個進程。如果進程在時間片結(jié)束前阻塞或結(jié)束，則CPU當(dāng)即進行切換。調(diào)度程序所要做的就是維護一張就緒進程列表，當(dāng)進程用完它

5、的時間片后，它被移到隊列的末尾。時間片輪轉(zhuǎn)調(diào)度中唯一有趣的一點是時間片的長度。從一個進程切換到另一個進程是需要一定時間的-保存和裝入寄存器值及內(nèi)存映像，更新各種表格和隊列等。在早期的時間片輪轉(zhuǎn)法中,系統(tǒng)將所有的就緒進程按先來先服務(wù)的原則,排成一個隊列,每次調(diào)度時,把CPU分配給隊首進程,并令其執(zhí)行一個時間片.時間片的大小從幾ms到幾百ms.當(dāng)執(zhí)行的時間片用完時,由一個計時器發(fā)出時鐘中斷請求,調(diào)度程序便據(jù)此信號來停止該進程的執(zhí)行,并將它送往就緒隊列的末尾;然后,再把處理機分配給就緒隊列中新的隊首進程,同時也讓它執(zhí)行一個時間片.這樣就可以保證就緒隊列中的所有進程,在一給定的時間內(nèi),均能獲得一時間片

6、的處理機執(zhí)行時間.3.2優(yōu)先(yuxin)數(shù)調(diào)度算法優(yōu)先數(shù)調(diào)度算法常用于批處理系統(tǒng)中。在進程調(diào)度中，每次調(diào)度時，系統(tǒng)把處理機分配(fnpi)給就緒隊列中優(yōu)先數(shù)最高的進程。它又分為兩種：非搶占式優(yōu)先數(shù)算法和搶占式優(yōu)先數(shù)算法。在非搶占式優(yōu)先數(shù)算法下，系統(tǒng)一旦把處理機分配給就緒隊列中優(yōu)先數(shù)最高的進程后，這個(zh ge)進程就會一直運行，直到完成或發(fā)生某事件使它放棄處理機，這時系統(tǒng)才能重新將處理機分配給就緒隊列中的另一個優(yōu)先數(shù)最高的進程。在搶占式優(yōu)先數(shù)算法下，系統(tǒng)先將處理機分配給就緒隊列中優(yōu)先數(shù)最高的進程度讓它運行，但在運行的過程中，如果出現(xiàn)另一個優(yōu)先數(shù)比它高的進程，它就要立即停止，并將處理機分配給

7、新的高優(yōu)先數(shù)進程。四設(shè)計步驟4.1 任務(wù)分析(1)PCB結(jié)構(gòu)通常包括以下信息：進程名，進程優(yōu)先數(shù)，輪轉(zhuǎn)時間片，進程已占用的CPU時間，進程還需要的CPU時間，進程的狀態(tài)，當(dāng)前隊列指針等?？筛鶕?jù)實驗的不同，PCB結(jié)構(gòu)的內(nèi)容可以作適當(dāng)?shù)脑鰟h(2)本程序用兩種算法對五個進程進行調(diào)度，每個進程可有三個狀態(tài)：就緒、執(zhí)行、完成。并假設(shè)初始狀態(tài)為就緒狀態(tài)。 (3)為了便于處理，程序中的某進程運行時間以時間片為單位計算。各進程的優(yōu)先數(shù)或輪轉(zhuǎn)時間數(shù)以及進程需運行的時間片數(shù)的初始值均由用戶給定。 (4)在優(yōu)先數(shù)算法中，優(yōu)先數(shù)可以先取值為一個常數(shù)減去進程所需要的時間片數(shù)目，進程每執(zhí)行一次，優(yōu)先數(shù)減3，CPU時間片數(shù)

8、加1，進程還需要的時間片數(shù)減1。在輪轉(zhuǎn)算法中，采用固定時間片（即：每執(zhí)行一次進程，該進程的執(zhí)行時間片數(shù)為已執(zhí)行了2個單位），這時，CPU時間片數(shù)加2，進程還需要的時間片數(shù)減2，并排列到就緒隊列的尾上。(5)對于遇到優(yōu)先數(shù)一致(yzh)的情況，采用FIFO策略(cl)解決。4.2 概要(giyo)設(shè)計1.本程序用兩種算法對五個進程進行調(diào)度，每個進程可有三個狀態(tài)，并假設(shè)初始狀態(tài)為就緒狀態(tài)。2.為了便于處理，程序中的某進程運行時間以時間片為單位計算。各進程的優(yōu)先數(shù)或輪轉(zhuǎn)時間數(shù)以及進程需運行的時間片數(shù)的初始值均由用戶給定。3.在優(yōu)先數(shù)算法中，優(yōu)先數(shù)的值為50與運行時間的差值，即P_TIME-proce

9、ss-needtime。進程每執(zhí)行一次，優(yōu)先數(shù)減3，CPU時間片數(shù)加1，進程還需要的時間片數(shù)減1。在輪轉(zhuǎn)算法中，采用固定時間片（即：每執(zhí)行一次進程，該進程的執(zhí)行時間片數(shù)為已執(zhí)行了2個單位），這時，CPU時間片數(shù)加2，進程還需要的時間片數(shù)減2，并排列到就緒隊列的尾上。4.對于遇到優(yōu)先數(shù)一致的情況，采用FIFO策略解決。4.3 詳細(xì)設(shè)計1.struct pcb（） / 定義pcb塊2.Void display（） /顯示結(jié)果信息函數(shù)3.int process_finished(pcb *q) /進程完成標(biāo)示4.void display_round（） /顯示循環(huán)輪轉(zhuǎn)調(diào)度算法運行結(jié)果5.priori

10、ty_call() /優(yōu)先數(shù)調(diào)度算法6.void cpu_round（）/處理器的工作狀態(tài)4.4 流程圖開始生成并按生成次序排列進程控制塊鏈鏈?zhǔn)走M程運行時間片到，進程時間片-1，優(yōu)先級-3撤銷該進程運行進程退出，取鏈?zhǔn)走M程運行時間片=0？優(yōu)先級隊列中優(yōu)先級最高的進程？進程隊列=null？結(jié)束4.5 源程序源程序過程(guchng)如下(rxi)：#include#include #define P_TIME 50enum state ready, execute, block, finish;struct pcb/ 定義(dngy)pcb塊 char name4; pcb * next;pcb

11、 * get_process();pcb * get_process() pcb *q; pcb *t; pcb *p; i+; /while return p;void display(pcb *p) /顯示(xinsh)結(jié)果信息函數(shù) coutname cputime needtime coutneedtime=0; q=q-next; return bl;void cpuexe(pcb *q) pcb *t=q; int tp=0; t-cputime+; void priority_call()/優(yōu)先數(shù)調(diào)度(diod)算法 pcb * p; p=get_process(); int cp

12、u=0; ); getch();void display_menu()/顯示(xinsh)菜單 coutCHOOSE THE ALGORITHM:endl; cout1 PRIORITYendl; cout2 ROUNDROBINendl; cout3 EXITendl;pcb * get_process_round()/顯示循環(huán)輪轉(zhuǎn)調(diào)度(diod)算法運行結(jié)果 pcb *q; pcb *t; pcb *p; int i=0; coutinput name and timecputime+=2; q-needtime-=2; q-process=execute;pcb * get_next(p

13、cb * k,pcb * head) pcb * t; t=k; return t;void set_state(pcb *p) while(p) if (p-needtime=0) p-process=finish; if (p-process=execute) p-process=ready; p=p-next; void display_round(pcb *p) coutNAME CPUTIME NEEDTIME COUNT ROUND STATEnext; void round_cal() pcb * p; set_state(p); void main() display_menu

14、(); int k; scanf(%d,&k); switch(k) case 1:priority_cal();break; case 2:round_cal();break; case 3:break; display_menu(); scanf(%d,&k); 4.6 程序(chngx)測試數(shù)據(jù)及結(jié)果圖 SEQ 圖 * ARABIC 1程序(chngx)測試數(shù)據(jù)圖 1運用循環(huán)輪轉(zhuǎn)調(diào)度(diod)算法的執(zhí)行結(jié)果1圖 2運用循環(huán)輪轉(zhuǎn)調(diào)度算法的執(zhí)行結(jié)果2圖 3運用(ynyng)循環(huán)輪轉(zhuǎn)調(diào)度算法的執(zhí)行結(jié)果3圖 4運用優(yōu)先數(shù)調(diào)度算法(sun f)的執(zhí)行結(jié)果1圖5運用優(yōu)先數(shù)調(diào)度算法(sun f)的執(zhí)

15、行結(jié)果2圖 6運用優(yōu)先(yuxin)數(shù)調(diào)度算法的執(zhí)行結(jié)果3五.設(shè)計(shj)總結(jié)通過本次試驗，我了解到優(yōu)先數(shù)算法是一種以進程(jnchng)優(yōu)先級作為參考來調(diào)度進程的一種算法。這個算法的好處是能夠讓優(yōu)先級高的進程得到更多的CPU占用時間，缺點是那些優(yōu)先級低的進程可以永遠得不到執(zhí)行。對于輪轉(zhuǎn)法是一種比較公平的算法，所有的進程都有機會得到執(zhí)行。六.附錄.#include#include #include#include#include#define P_NUM 5#define P_TIME 50enum state ready, execute, block, finish;struct pcb

16、 char name4; int priority; int cputime; int needtime; int count; int round; state process; pcb * next;pcb * get_process();pcb * get_process() pcb *q; pcb *t; pcb *p; int i=0; coutinput name and timeendl; while (iq-name; cinq-needtime; q-cputime=0; q-priority=P_TIME-q-needtime; q-process=ready; q-nex

17、t=NULL; if (i=0) p=q; t=q; else t-next=q; t=q; i+; /while return p;void display(pcb *p) coutname cputime needtime priority stateendl; while(p) coutname; cout ; coutcputime; cout ; coutneedtime; cout ; coutpriority; coutprocess) case ready:coutreadyendl;break; case execute:coutexecuteendl;break; case

18、 block:coutblockendl;break; case finish:coutfinishnext; int process_finish(pcb *q) int bl=1; while(bl&q) bl=bl&q-needtime=0; q=q-next; return bl;void cpuexe(pcb *q) pcb *t=q; int tp=0; while(q) if (q-process!=finish) q-process=ready; if(q-needtime=0) q-process=finish; if(tppriority&q-process!=finish

19、) tp=q-priority; t=q; q=q-next; if(t-needtime!=0) t-priority-=3; t-needtime-; t-process=execute; t-cputime+; void priority_cal() pcb * p; p=get_process(); int cpu=0; while(!process_finish(p) cpu+; coutcputime:cpuendl; cpuexe(p); display(p); printf(All processes have finished,press any key to exit);

20、getch();void display_menu() coutCHOOSE THE ALGORITHM:endl; cout1 PRIORITYendl; cout2 ROUNDROBINendl; cout3 EXITendl;pcb * get_process_round() pcb *q; pcb *t; pcb *p; int i=0; coutinput name and timeendl; while (iq-name; cinq-needtime; q-cputime=0; q-round=0; q-count=0; q-process=ready; q-next=NULL;

21、if (i=0) p=q; t=q; else t-next=q; t=q; i+; /while return p;void cpu_round(pcb *q) q-cputime+=2; q-needtime-=2; if(q-needtimeneedtime=0; q-count+; q-round+; q-process=execute;pcb * get_next(pcb * k,pcb * head) pcb * t; t=k; do t=t-next; while (t & t-process=finish); if(t=NULL) t=head; while (t-next!=k & t-process=finish) t=t-next; return t;void set_state(pcb *p) while(p) if (p-needtime=0) p-process=finish; if (p-process=execute) p-process=ready; p=p-next; void display_round(pcb *p) cout