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

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

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

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

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

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

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

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

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

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

10、ty_call() /優(yōu)先數(shù)調(diào)度算法6.void cpu_round（）/處理器的工作狀態(tài)4.4 流程圖開始生成并按生成次序排列進(jìn)程控制塊鏈鏈?zhǔn)走M(jìn)程運(yùn)行時(shí)間片到，進(jìn)程時(shí)間片-1，優(yōu)先級(jí)-3撤銷該進(jìn)程運(yùn)行進(jìn)程退出，取鏈?zhǔn)走M(jìn)程運(yùn)行時(shí)間片=0？?jī)?yōu)先級(jí)隊(duì)列中優(yōu)先級(jí)最高的進(jìn)程？進(jìn)程隊(duì)列=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)算法運(yùn)行結(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)測(cè)試數(shù)據(jù)及結(jié)果圖 SEQ 圖 * ARABIC 1程序(chngx)測(cè)試數(shù)據(jù)圖 1運(yùn)用循環(huán)輪轉(zhuǎn)調(diào)度(diod)算法的執(zhí)行結(jié)果1圖 2運(yùn)用循環(huán)輪轉(zhuǎn)調(diào)度算法的執(zhí)行結(jié)果2圖 3運(yùn)用(ynyng)循環(huán)輪轉(zhuǎn)調(diào)度算法的執(zhí)行結(jié)果3圖 4運(yùn)用優(yōu)先數(shù)調(diào)度算法(sun f)的執(zhí)行結(jié)果1圖5運(yùn)用優(yōu)先數(shù)調(diào)度算法(sun f)的執(zhí)

15、行結(jié)果2圖 6運(yùn)用優(yōu)先(yuxin)數(shù)調(diào)度算法的執(zhí)行結(jié)果3五.設(shè)計(jì)(shj)總結(jié)通過本次試驗(yàn)，我了解到優(yōu)先數(shù)算法是一種以進(jìn)程(jnchng)優(yōu)先級(jí)作為參考來調(diào)度進(jìn)程的一種算法。這個(gè)算法的好處是能夠讓優(yōu)先級(jí)高的進(jìn)程得到更多的CPU占用時(shí)間，缺點(diǎn)是那些優(yōu)先級(jí)低的進(jìn)程可以永遠(yuǎn)得不到執(zhí)行。對(duì)于輪轉(zhuǎn)法是一種比較公平的算法，所有的進(jìn)程都有機(jī)會(huì)得到執(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