操作系統(tǒng)進(jìn)程調(diào)算法的模擬

1、操作系統(tǒng)實(shí)驗(yàn)題目進(jìn)程調(diào)度算法模擬一、實(shí)驗(yàn)?zāi)康?通過對進(jìn)程調(diào)度算法的模擬，進(jìn)一步理解進(jìn)程的基本概念，加深對進(jìn)程運(yùn)行狀態(tài)和進(jìn)程調(diào)度過程、調(diào)度算法的理解。二、設(shè)備與環(huán)境（1）硬件設(shè)備：PC機(jī)一臺（2）軟件環(huán)境：安裝Windows操作系統(tǒng)或者Linux操作系統(tǒng)，并安裝相關(guān)的程序開發(fā)環(huán)境，如C C+Java 等編程語言環(huán)境。三、實(shí)驗(yàn)內(nèi)容（1）用C、C+、Java語言編程實(shí)現(xiàn)對5個進(jìn)程采用動態(tài)優(yōu)先權(quán)調(diào)度算法進(jìn)行調(diào)度的過程。數(shù)據(jù)如下：5個進(jìn)程的到達(dá)時刻和服務(wù)時間見下表，忽略I/O以及其它開銷時間，使用動態(tài)優(yōu)先權(quán)算法進(jìn)行調(diào)度，優(yōu)先權(quán)初始值為100，請輸出各個進(jìn)程的完成時刻、周轉(zhuǎn)時間、帶權(quán)周轉(zhuǎn)時間。 進(jìn)程到達(dá)時

2、刻服務(wù)時間A03B26C44D65E82（2）每個用來標(biāo)識進(jìn)程的進(jìn)程控制塊PCB可用結(jié)構(gòu)來描述，包括以下字段（用不到的字段可以不定義）。² 進(jìn)程標(biāo)識數(shù)ID。² 進(jìn)程優(yōu)先數(shù)PRIORITY，并規(guī)定優(yōu)先數(shù)越大的進(jìn)程，其優(yōu)先權(quán)越高。² 進(jìn)程已占用CPU時間CPUTIME。² 進(jìn)程還需占用的CPU時間ALLTIME。當(dāng)進(jìn)程運(yùn)行完畢時，ALLTIME變?yōu)?。² 進(jìn)程的阻塞時間STARTBLOCK，表示當(dāng)進(jìn)程再運(yùn)行STARTBLOCK個時間片后，進(jìn)程將進(jìn)入阻塞狀態(tài)。² 進(jìn)程被阻塞的時間BLOCKTIME，表示已阻塞的進(jìn)程再等待BLOCKTIME個

3、時間片后，將轉(zhuǎn)換成就緒狀態(tài)。² 進(jìn)程狀態(tài)STATE。² 隊(duì)列指針NEXT，用來將PCB排成隊(duì)列。（3）優(yōu)先數(shù)改變的原則：² 進(jìn)程在就緒隊(duì)列中呆一個時間片，優(yōu)先數(shù)增加1。² 進(jìn)程每運(yùn)行一個時間片，優(yōu)先數(shù)減3。（4）為了清楚地觀察每個進(jìn)程的調(diào)度過程，程序應(yīng)將每個時間片內(nèi)的進(jìn)程的情況顯示出來，包括正在運(yùn)行的進(jìn)程，處于就緒隊(duì)列中的進(jìn)程和處于阻塞隊(duì)列中的進(jìn)程。（5）分析程序運(yùn)行的結(jié)果，談一下自己的認(rèn)識。四、實(shí)驗(yàn)結(jié)果及分析（1）實(shí)驗(yàn)關(guān)鍵代碼 模擬PCB數(shù)據(jù)結(jié)構(gòu)定義： /枚舉進(jìn)程的狀態(tài)：新建、就緒、執(zhí)行、阻塞、終止 enum STATE_PROCESS New,Rea

4、dy,Run,Block,Finish; typedef enum STATE_PROCESS STATE; /建立PCB結(jié)構(gòu)體 struct PCB_NODE int id; /進(jìn)程標(biāo)識數(shù) int priority; /進(jìn)程優(yōu)先數(shù) int arriveTime; /進(jìn)程到達(dá)時間 int cpuTime; /進(jìn)程已占用 CPU 時間 int allTime; /進(jìn)程還需占用 CPU 時間 int blockTime; /進(jìn)程已阻塞時間 STATE state; /進(jìn)程狀態(tài) struct PCB_NODE *prev; /PCB 前指針 struct PCB_NODE *next; /PCB 后

5、指針 ; typedef struct PCB_NODE PCB; 模擬進(jìn)程隊(duì)列操作函數(shù)定義： /進(jìn)程入列 void queuePush(PCB *process, PCB *queueHead) /進(jìn)程出列 void queuePop(PCB *process, PCB *queueHead) /查看隊(duì)列中進(jìn)程信息 void queueWalk(PCB *queueHead) 模擬就緒隊(duì)列操作函數(shù)定義： /進(jìn)程插入到就緒隊(duì)列 void readyQueuePush(PCB *process) /優(yōu)先數(shù)最大的進(jìn)程出列 PCB * readyQueuePop() /每個時間片更新就緒隊(duì)列中的進(jìn)程

6、信息 void readyQueueUpdate(int timeSlice,PCB *pcb) /返回就緒隊(duì)列最大優(yōu)先數(shù)的值 int readyMaxPriority() /查看就緒隊(duì)列中的進(jìn)程信息 void readyQueueWalk() 模擬阻塞隊(duì)列操作函數(shù)定義： /進(jìn)程插入到阻塞隊(duì)列 void blockQueuePush(PCB *process) /優(yōu)先數(shù)最大的進(jìn)程出列 PCB * blockQueuePop() /每個時間片更新阻塞隊(duì)列中進(jìn)程的信息 void blockQueueUpdate() /查看阻塞隊(duì)列中的進(jìn)程信息 void blockQueueWalk() 模擬動態(tài)優(yōu)

7、先權(quán)進(jìn)程調(diào)度函數(shù)定義： /初始化進(jìn)程PCB數(shù)據(jù)，返回PCB頭指針 PCB * initData() /模擬 CPU 執(zhí)行1個時間片的操作 void cpuWord(PCB *cpuProcess) 主函數(shù)關(guān)鍵代碼： int timeSlice = 0; /模擬CPU時間片 int cpuBusy = 0; /模擬CPU狀態(tài) PCB *cpuProcess = NULL; /當(dāng)前CPU執(zhí)行的進(jìn)程 PCB *pHead,*pro; /進(jìn)程PCB 頭指針 pHead = initData(); /初始化進(jìn)程PCB,返回進(jìn)程頭指針 pro = pHead + 1; /pro 指向PCB中第一個進(jìn)程 r

8、eadyQueueUpdate(timeSlice,pro); /根據(jù)進(jìn)程到達(dá)時間將新建進(jìn)程加入緒隊(duì)列 /模擬動態(tài)優(yōu)先權(quán)進(jìn)程調(diào)度 while(true) if(readyQueueNum = 0 && blockQueueNum = 0 && cpuBusy = 0) printf("就緒隊(duì)列、阻塞隊(duì)列和 CPU 當(dāng)前無進(jìn)程運(yùn)行,退出n"); break; /end if if(cpuBusy = 0) /CPU空閑,選擇一個進(jìn)程進(jìn)入CPU if(readyQueueNum > 0) /選擇就緒隊(duì)列優(yōu)先級最高的進(jìn)程作為CPU運(yùn)行進(jìn)程 c

9、puProcess = readyQueuePop(); else /就緒隊(duì)列中沒有進(jìn)程,改為選擇阻塞隊(duì)列優(yōu)先級最高的進(jìn)程 cpuProcess = blockQueuePop(); cpuProcess->cpuTime = 0; /設(shè)置當(dāng)前運(yùn)行進(jìn)程占用CPU時間 cpuProcess->state = Run; /設(shè)置當(dāng)前運(yùn)行進(jìn)程的狀態(tài) cpuBusy = 1; /設(shè)置 CPU 當(dāng)前狀態(tài)為忙 /end if timeSlice +; /當(dāng)前時間片加1 printf("n第 %d 個時間片后:n",timeSlice); cpuWord(cpuProcess)

10、; /模擬CPU執(zhí)行1個時間片的操作 if(cpuProcess->allTime = 0) /若當(dāng)前執(zhí)行進(jìn)程還需CPU時間片為0 cpuProcess->state = Finish; /設(shè)置當(dāng)前進(jìn)程狀態(tài)為終止 free(cpuProcess); /釋放該進(jìn)程的PCB內(nèi)存空間 cpuBusy = 0; /CPU狀態(tài)設(shè)置為空閑 /end if /更新就緒隊(duì)列和阻塞隊(duì)列中的進(jìn)程信息 blockQueueUpdate(); readyQueueUpdate(timeSlice,pro); /查看就緒隊(duì)列和阻塞隊(duì)列的進(jìn)程信息 readyQueueWalk(); blockQueueWal

11、k(); if(cpuBusy = 1 && readyQueueNum > 0 && cpuProcess->priority < readyMaxPriority() blockQueuePush(cpuProcess); /需搶占CPU,當(dāng)前執(zhí)行的進(jìn)程調(diào)入阻塞隊(duì)列 cpuProcess = readyQueuePop(); /從就緒隊(duì)列中選擇優(yōu)先級最高的進(jìn)程運(yùn)行 /end if printf("n模擬進(jìn)程動態(tài)優(yōu)先權(quán)調(diào)度算法結(jié)束.n"); return 0;（2） 動態(tài)優(yōu)先權(quán)調(diào)度算法流程圖（2）實(shí)驗(yàn)結(jié)果 第1個時間片后：

12、 第2個時間片后： 第3個時間片后： 第4個時間片后： 第5個時間片后： 第6個時間片后： 第7個時間片后： 第8個時間片后： 第9個時間片后： 第10個時間片后： 第11個時間片后： 第12個時間片后： 第13個時間片后： 第14個時間片后： 第15個時間片后： 第16個時間片后： 第17個時間片后： 第18個時間片后： 第19個時間片后： 第20個時間片后：（3） 實(shí)驗(yàn)結(jié)果分析 調(diào)度算法開始之前進(jìn)程PCB信息為： 調(diào)度算法結(jié)束之后進(jìn)程PCB信息為： 調(diào)度算法分析：進(jìn)程ID到達(dá)時間服務(wù)時間結(jié)束時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間00310103.312620183.024416123.036518122

13、.44821352.5（4）實(shí)驗(yàn)心得 通過進(jìn)程動態(tài)優(yōu)先權(quán)調(diào)度算法的模擬，對進(jìn)程的運(yùn)行狀態(tài)，進(jìn)程PCB數(shù)據(jù)結(jié)構(gòu)，進(jìn)程調(diào)度算法有了更深的理解。動態(tài)優(yōu)先權(quán)調(diào)度算法為了防止高優(yōu)先級進(jìn)程無休止地運(yùn)行下去，調(diào)度程序在每個時鐘滴答（即每個時鐘中斷）降低當(dāng)前進(jìn)程的優(yōu)先級。如果這個動作導(dǎo)致該進(jìn)程的優(yōu)先級低于次高優(yōu)先級的進(jìn)程，則進(jìn)行進(jìn)程切換，可以避免低優(yōu)先級進(jìn)程長時間的饑餓等待。此外，優(yōu)先級可以由系統(tǒng)動態(tài)確定。例如有些進(jìn)程為I/O密集型，其多數(shù)時間用來等待I/O結(jié)束。當(dāng)這樣的進(jìn)程需要CPU時，應(yīng)立即分配給它CPU，以便啟動下一個I/O請求，這樣就可以在另一個進(jìn)程計(jì)算的同時執(zhí)行I/O操作。使這類I/O密集型進(jìn)程長時間等待只會造成它無謂地長時間占用內(nèi)存。使I/O密集型進(jìn)程獲得較好服務(wù)的一種簡單算法是，將其優(yōu)先級設(shè)為1/f ，f 為該進(jìn)程在上一時間片中所占的部分。如果一個在其50ms 的時間片中只使用1ms 的進(jìn)程的優(yōu)先級為50，而在阻塞之前用掉25ms 的進(jìn)程優(yōu)先級為2，使用掉全部時間片的進(jìn)程優(yōu)先級為1。這樣，可以很方便地將一組進(jìn)程按優(yōu)先級分成若干類，并在各類之間采用優(yōu)先級調(diào)度，而在各類進(jìn)程的內(nèi)部采用輪轉(zhuǎn)調(diào)度。如下圖為一個具有4類優(yōu)先級的系統(tǒng)，其調(diào)度算法如下：只要存在優(yōu)先級為第4類的可運(yùn)行進(jìn)程，就按照輪轉(zhuǎn)法為