實驗四 進程調(diào)度

1、實驗四 進程調(diào)度一、實驗?zāi)康?. 理解有關(guān)進程控制塊、進程隊列的概念。2. 掌握進程優(yōu)先權(quán)調(diào)度算法和時間片輪轉(zhuǎn)調(diào)度算法的處理邏輯。二、實驗內(nèi)容1. 設(shè)計進程控制塊 PCB 表結(jié)構(gòu)，分別適用于優(yōu)先權(quán)調(diào)度算法和時間片輪轉(zhuǎn)調(diào)度算法。2. 建立進程就緒隊列。對兩種不同算法編制子程序。3. 編制兩種進程調(diào)度算法：1）優(yōu)先權(quán)調(diào)度；2）時間片輪轉(zhuǎn)調(diào)度。三、實驗準備1. 優(yōu)先權(quán)調(diào)度算法 為了照顧緊迫型進程獲得優(yōu)先處理，引入了優(yōu)先權(quán)調(diào)度算法。它從就緒隊列中選擇一個優(yōu)先權(quán)最高的進程，讓其獲得處理器并執(zhí)行。這時，又進一步把該算法分為兩種方式： 1）非搶占式優(yōu)先權(quán)調(diào)度算法 在這種方式下，系統(tǒng)一旦把處理器分配給就緒隊列

2、中優(yōu)先權(quán)最高的進程后，該進程就占有處理器一直運行下去，直到該進程完成或因發(fā)生事件而阻塞，才退出處理器。系統(tǒng)這時才能將處理器分配給另一個優(yōu)先權(quán)高的進程。這種方式實際上是每次將處理器分配給當前就緒隊列中優(yōu)先權(quán)最高的進程。它常用于批處理系統(tǒng)中，也可用于某些對時間要求不嚴格的實時系統(tǒng)中。2）搶占式優(yōu)先權(quán)調(diào)度算法 在這種方式下，系統(tǒng)同樣把處理器分配給當前就緒隊列中優(yōu)先權(quán)最高的進程，使之執(zhí)行。但在其執(zhí)行期間，仍然會不斷有新的就緒進程進入就緒隊列，如果出現(xiàn)某個進程，其優(yōu)先權(quán)比當前正在執(zhí)行的進程的優(yōu)先權(quán)還高時，進程調(diào)度程序就會立即暫停當前進程的執(zhí)行，而將 處理器收回，并將處理器分配給新出現(xiàn)的優(yōu)先權(quán)更高的進程，

3、讓其執(zhí)行。這種方式實際上永 遠都是系統(tǒng)中優(yōu)先權(quán)最高的進程占用處理器執(zhí)行。因此，它能更好地滿足緊迫進程的要求， 故常用于要求比較嚴格的實時系統(tǒng)中，以及對性能要求較高的批處理和分時系統(tǒng)中。對于優(yōu)先權(quán)調(diào)度算法，其關(guān)鍵在于是采用靜態(tài)優(yōu)先權(quán)，還是動態(tài)優(yōu)先權(quán)，以及如何確定 進程的優(yōu)先權(quán)。1) 靜態(tài)優(yōu)先權(quán) 靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進程時確定的，并且規(guī)定它在進程的整個運行期間保持不變。一般來說，優(yōu)先權(quán)是利用某個范圍內(nèi)的一個整數(shù)來表示的，如 07，或 0255 中的某個整數(shù)， 所以又稱為優(yōu)先數(shù)。在使用時，有的系統(tǒng)用“0”表示最高優(yōu)先權(quán)，數(shù)值越大優(yōu)先權(quán)越小， 而有的系統(tǒng)則恰恰相反。2) 動態(tài)優(yōu)先權(quán) 動態(tài)優(yōu)先權(quán)要配合搶占

4、調(diào)度方式使用，它是指在創(chuàng)建進程時所賦予的優(yōu)先權(quán)，可以隨著進程的推進而發(fā)生改變，以便獲得更好的調(diào)度性能。在就緒隊列中等待調(diào)度的進程，可以隨 著其等待時間的增加，其優(yōu)先權(quán)也以某個速率增加。因此，對于優(yōu)先權(quán)初值很低的進程，在 等待足夠長的時間后，其優(yōu)先權(quán)也可能升為最高，從而獲得調(diào)度，占用處理器并執(zhí)行。同樣 規(guī)定正在執(zhí)行的進程，其優(yōu)先權(quán)將隨著執(zhí)行時間的增加而逐漸降低，使其優(yōu)先權(quán)可能不再是 最高，從而暫停其執(zhí)行，將處理器回收并分配給其他優(yōu)先權(quán)更高的進程。這種方式能防止一 個長進程長期占用處理器的現(xiàn)象。2. 時間片輪轉(zhuǎn)調(diào)度算法 在分時系統(tǒng)中，為了保證人機交互的及時性，系統(tǒng)使每個進程依次按時間片方式輪流地執(zhí)

5、行，即時間片輪轉(zhuǎn)調(diào)度算法。在該算法中，系統(tǒng)將所有的就緒進程按進入就緒隊列的先后 次序排列。每次調(diào)度時把 CPU 分配給隊首進程，讓其執(zhí)行一個時間片，當時間片用完，由計時器發(fā)出時鐘中斷，調(diào)度程序則暫停該進程的執(zhí)行，使其退出處理器，并將它送到就緒隊列 的末尾，等待下一輪調(diào)度執(zhí)行。然后，把 CPU 分配給就緒隊列中新的隊首進程，同時也讓它 執(zhí)行一個時間片。這樣就可以保證就緒隊列中的所有進程，在一定的時間（可接受的等待時 間）內(nèi)，均能獲得一個時間片的執(zhí)行時間。在時間片輪轉(zhuǎn)調(diào)度算法中，時間片的大小對系統(tǒng)的性能有很大影響。如果時間片太大，大到每個進程都能在一個時間片內(nèi)執(zhí)行結(jié)束，則時間片輪轉(zhuǎn)調(diào)度算法退化為先

6、來先服務(wù)調(diào)度 算法，用戶將不能獲得滿意的響應(yīng)時間。若時間片過小，連用戶鍵入的簡單常用命令都要花 費多個時間片，那么系統(tǒng)將頻繁地進行進程的切換，同樣難以保證用戶對響應(yīng)時間的要求。2.4 程序示例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，進程每執(zhí)行一次，優(yōu)先數(shù)減 3，CPU 時間片 數(shù)加 1，進程還需要的時間片數(shù)減 1。在輪轉(zhuǎn)算法中，采用固定時間片（即：每執(zhí)行一次進程

7、，該進程的執(zhí)行時間片數(shù)為已執(zhí)行了2個單位），這時，CPU 時間片數(shù)加 2，進程還需要的時間片數(shù)減2，并排列到就緒隊列的尾上。4. 對于遇到優(yōu)先數(shù)一致的情況，采用 FIFO 策略解決。#include#include #include#include#include#include#define P_NUM 5#define P_TIME 50enum stateready, execute, block, finish;/定義進程狀態(tài) struct pcb char name4;/進程名 int priority;/優(yōu)先權(quán) int cputime;/CPU 運行時間 int needtime;

8、/進程運行所需時間 int count;/進程執(zhí)行次數(shù) int round;/時間片輪轉(zhuǎn)輪次 state process;/進程狀態(tài)pcb * next;/定義進程 PCBpcb *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-next=NULL; if (i=0) p=q; t=q; else t-nex

9、t=q;/創(chuàng)建就緒進程隊列t=q; i+; /while return p;/輸入模擬測試的進程名和執(zhí)行所需時間，初始設(shè)置可模擬5個進程的調(diào)度voiddisplay(pcb *p) coutnamecputime needtime priority stateendl; while(p) coutname; cout; coutcputime; cout; coutneedtime; cout; coutpriority; coutprocess) case ready:coutreadyendl;break; case execute:coutexecuteendl;break; case

10、block:coutblockendl;break; case finish:coutfinishnext; /顯示模擬結(jié)果，包含進程名、CPU 時間、運行所需時間以及優(yōu)先級int process_finish(pcb *q) int bl=1; while(bl&q) bl=bl&q-needtime=0; q=q-next; return bl;/結(jié)束進程，即將隊列中各進程的所需時間設(shè)置為0void cpuexe(pcb *q) pcb *t=q; int tp=0; while(q) if (q-process!=finish) q-process=ready; if(q-needtim

11、e=0) q-process=finish; if(tppriority&q-process!=finish) tp=q-priority; t=q; q=q-next; if(t-needtime!=0) t-priority-=3; t-needtime-; t-process=execute; t-cputime+;/選擇某一進程，給它分配CPU/計算進程優(yōu)先級 void priority_cal() pcb *p; system(cls); /clrscr(); p=get_process(); int cpu=0; system(cls); /clrscr(); while(!pro

12、cess_finish(p) cpu+; coutcputime:cpuendl; cpuexe(p); display(p); Sleep(2); /system(cls); /clrscr(); printf(All processes have finished,press any key to exit); getch();void display_menu() coutCHOOSE THE ALGORITHM:endl; cout1 PRIORITYendl; cout2 ROUNDROBINendl; cout3 EXITendl;/顯示調(diào)度算法菜單，可供用戶選擇優(yōu)先權(quán)調(diào)度算法和時

13、間片輪轉(zhuǎn)調(diào)度算法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; if (i=0) p=q; t=q; else t-next=q; t=q; i+; /while return p;/時間片輪轉(zhuǎn)調(diào)度算法創(chuàng)建就緒進程隊列 void cpu_round(pcb *q) q-cputi

14、me+=2; q-needtime-=2; if(q-needtimeneedtime=0; q-count+; q-round+; q-process=execute;/采用時間片輪轉(zhuǎn)調(diào)度算法執(zhí)行某一進程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

15、) while(p) if (p-needtime=0) p-process=finish;/如果所需執(zhí)行時間為0，則設(shè)置運行狀態(tài)為結(jié)束 if (p-process=execute) p-process=ready;/如果為執(zhí)行狀態(tài)則設(shè)置為就緒 p=p-next;/設(shè)置隊列中進程執(zhí)行狀態(tài) void display_round(pcb *p) coutNAMECPUTIMENEEDTIME COUNT ROUNDSTATEendl; while(p) coutname; cout ; coutcputime; cout; coutneedtime; cout ; coutcount; cout

16、; coutround; coutprocess) case ready:coutreadyendl;break; case execute:coutexecuteendl;break; case finish:coutfinishnext;/時間片輪轉(zhuǎn)調(diào)度算法輸出調(diào)度信息void round_cal() pcb * p; pcb * r; system(cls); /clrscr(); p=get_process_round(); int cpu=0; system(cls); /clrscr(); r=p; while(!process_finish(p) cpu+=2; cpu_round(r); r=get_next(r,p); coutcpu