1、操作系統實驗題目進程調度算法模擬一、實驗目的 通過對進程調度算法的模擬，進一步理解進程的基本概念，加深對進程運行狀態和進程調度過程、調度算法的理解。二、設備與環境（1）硬件設備：PC機一臺（2）軟件環境：安裝Windows操作系統或者Linux操作系統，并安裝相關的程序開發環境，如C C+Java 等編程語言環境。三、實驗內容（1）用C、C+、Java語言編程實現對5個進程采用動態優先權調度算法進行調度的過程。數據如下：5個進程的到達時刻和服務時間見下表，忽略I/O以及其它開銷時間，使用動態優先權算法進行調度，優先權初始值為100，請輸出各個進程的完成時刻、周轉時間、帶權周轉時間。 進程到達時

2、刻服務時間A03B26C44D65E82（2）每個用來標識進程的進程控制塊PCB可用結構來描述，包括以下字段（用不到的字段可以不定義）。² 進程標識數ID。² 進程優先數PRIORITY，并規定優先數越大的進程，其優先權越高。² 進程已占用CPU時間CPUTIME。² 進程還需占用的CPU時間ALLTIME。當進程運行完畢時，ALLTIME變為0。² 進程的阻塞時間STARTBLOCK，表示當進程再運行STARTBLOCK個時間片后，進程將進入阻塞狀態。² 進程被阻塞的時間BLOCKTIME，表示已阻塞的進程再等待BLOCKTIME個

3、時間片后，將轉換成就緒狀態。² 進程狀態STATE。² 隊列指針NEXT，用來將PCB排成隊列。（3）優先數改變的原則：² 進程在就緒隊列中呆一個時間片，優先數增加1。² 進程每運行一個時間片，優先數減3。（4）為了清楚地觀察每個進程的調度過程，程序應將每個時間片內的進程的情況顯示出來，包括正在運行的進程，處于就緒隊列中的進程和處于阻塞隊列中的進程。（5）分析程序運行的結果，談一下自己的認識。四、實驗結果及分析（1）實驗關鍵代碼 模擬PCB數據結構定義： /枚舉進程的狀態：新建、就緒、執行、阻塞、終止 enum STATE_PROCESS New,Rea

4、dy,Run,Block,Finish; typedef enum STATE_PROCESS STATE; /建立PCB結構體 struct PCB_NODE int id; /進程標識數 int priority; /進程優先數 int arriveTime; /進程到達時間 int cpuTime; /進程已占用 CPU 時間 int allTime; /進程還需占用 CPU 時間 int blockTime; /進程已阻塞時間 STATE state; /進程狀態 struct PCB_NODE *prev; /PCB 前指針 struct PCB_NODE *next; /PCB 后

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

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

7、先權進程調度函數定義： /初始化進程PCB數據，返回PCB頭指針 PCB * initData() /模擬 CPU 執行1個時間片的操作 void cpuWord(PCB *cpuProcess) 主函數關鍵代碼： int timeSlice = 0; /模擬CPU時間片 int cpuBusy = 0; /模擬CPU狀態 PCB *cpuProcess = NULL; /當前CPU執行的進程 PCB *pHead,*pro; /進程PCB 頭指針 pHead = initData(); /初始化進程PCB,返回進程頭指針 pro = pHead + 1; /pro 指向PCB中第一個進程 r

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

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

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

11、k(); if(cpuBusy = 1 && readyQueueNum > 0 && cpuProcess->priority < readyMaxPriority() blockQueuePush(cpuProcess); /需搶占CPU,當前執行的進程調入阻塞隊列 cpuProcess = readyQueuePop(); /從就緒隊列中選擇優先級最高的進程運行 /end if printf("n模擬進程動態優先權調度算法結束.n"); return 0;（2） 動態優先權調度算法流程圖（2）實驗結果 第1個時間片后：

12、 第2個時間片后： 第3個時間片后： 第4個時間片后： 第5個時間片后： 第6個時間片后： 第7個時間片后： 第8個時間片后： 第9個時間片后： 第10個時間片后： 第11個時間片后： 第12個時間片后： 第13個時間片后： 第14個時間片后： 第15個時間片后： 第16個時間片后： 第17個時間片后： 第18個時間片后： 第19個時間片后： 第20個時間片后：（3） 實驗結果分析 調度算法開始之前進程PCB信息為： 調度算法結束之后進程PCB信息為： 調度算法分析：進程ID到達時間服務時間結束時間周轉時間帶權周轉時間00310103.312620183.024416123.036518122

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