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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上操作系統(tǒng)實(shí)驗(yàn)題目進(jìn)程調(diào)度算法模擬一、實(shí)驗(yàn)?zāi)康?通過對(duì)進(jìn)程調(diào)度算法的模擬，進(jìn)一步理解進(jìn)程的基本概念，加深對(duì)進(jìn)程運(yùn)行狀態(tài)和進(jìn)程調(diào)度過程、調(diào)度算法的理解。二、設(shè)備與環(huán)境（1）硬件設(shè)備：PC機(jī)一臺(tái)（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)對(duì)5個(gè)進(jìn)程采用動(dòng)態(tài)優(yōu)先權(quán)調(diào)度算法進(jìn)行調(diào)度的過程。數(shù)據(jù)如下：5個(gè)進(jìn)程的到達(dá)時(shí)刻和服務(wù)時(shí)間見下表，忽略I/O以及其它開銷時(shí)間，使用動(dòng)態(tài)優(yōu)先權(quán)算法進(jìn)行調(diào)度，優(yōu)先權(quán)初始值為100，請(qǐng)輸出各個(gè)進(jìn)程的完成時(shí)刻、周轉(zhuǎn)時(shí)間、

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

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

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

5、*next; /PCB 后指針 ; 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() /每個(gè)

6、時(shí)間片更新就緒隊(duì)列中的進(jìn)程信息 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() /每個(gè)時(shí)間片更新阻塞隊(duì)列中進(jìn)程的信息 void blockQueueUpdate() /查看阻塞隊(duì)列中的進(jìn)程信息 void blockQueu

7、eWalk() 模擬動(dòng)態(tài)優(yōu)先權(quán)進(jìn)程調(diào)度函數(shù)定義： /初始化進(jìn)程PCB數(shù)據(jù)，返回PCB頭指針 PCB * initData() /模擬 CPU 執(zhí)行1個(gè)時(shí)間片的操作 void cpuWord(PCB *cpuProcess) 主函數(shù)關(guān)鍵代碼： int timeSlice = 0; /模擬CPU時(shí)間片 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

8、指向PCB中第一個(gè)進(jìn)程 readyQueueUpdate(timeSlice,pro); /根據(jù)進(jìn)程到達(dá)時(shí)間將新建進(jìn)程加入緒隊(duì)列 /模擬動(dòng)態(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空閑,選擇一個(gè)進(jìn)程進(jìn)入CPU if(readyQueueNum > 0) /選擇就緒隊(duì)列優(yōu)先級(jí)最高的

9、進(jìn)程作為CPU運(yùn)行進(jìn)程 cpuProcess = readyQueuePop(); else /就緒隊(duì)列中沒有進(jìn)程,改為選擇阻塞隊(duì)列優(yōu)先級(jí)最高的進(jìn)程 cpuProcess = blockQueuePop(); cpuProcess->cpuTime = 0; /設(shè)置當(dāng)前運(yùn)行進(jìn)程占用CPU時(shí)間 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)前時(shí)間片加1 printf("n第 %d 個(gè)時(shí)間片后:n",timeSlice); cpuWor

10、d(cpuProcess); /模擬CPU執(zhí)行1個(gè)時(shí)間片的操作 if(cpuProcess->allTime = 0) /若當(dāng)前執(zhí)行進(jìn)程還需CPU時(shí)間片為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();

11、blockQueueWalk(); 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í)最高的進(jìn)程運(yùn)行 /end if printf("n模擬進(jìn)程動(dòng)態(tài)優(yōu)先權(quán)調(diào)度算法結(jié)束.n"); return 0;（2） 動(dòng)態(tài)優(yōu)先權(quán)調(diào)度算法流程圖（2）

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

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