Brian Warehouse

一、實驗內容

利用高級語言模擬進程的時間片輪轉調度算法，響應比高者優先調度算法。

二、實驗目的

在采用多道程序設計的系統中，往往有若干個進程同時處于就緒狀態。當就緒進程個數大于處理器數時，就必須依照某種策略來決定哪些進程優先占用處理器。本實驗模擬在單處理器情況下的處理器調度，幫助學生加深了解處理器調度的工作。

三、實驗環境

1．PC微機。

2．Windows 操作系統。

3．C/C++/VB開發集成環境。

四、實驗題目

本實驗有兩個小題。

第一題：設計一個按時間片輪轉法實現處理器調度的程序。

算法設計思想：

(1) 假定系統有五個進程，每一個進程用一個進程控制塊PCB來代表。進程控制塊的格式為：

其中，進程名——作為進程的標識，假設五個進程的進程名分別為Q₁，Q₂，Q₃，Q₄，Q₅。

指針——進程按順序排成循環隊列，用指針指出下一個進程的進程控制塊的首地址，最后一個進程的指針指出第一個進程的進程控制塊首地址。

要求運行時間——假設進程需要運行的單位時間數。

已運行時間——假設進程已經運行的單位時間數，初始值為“0”。

狀態——有兩種狀態，“就緒”和“結束”，初始狀態都為“就緒”，用“R”表示。當一個進程運行結束后，它的狀態為“結束”，用“E”表示。

(2) 每次運行所設計的進程調度程序前，為每個進程任意確定它的“要求運行時間”。

(3) 把五個進程按順序排成循環隊列，用指針指出隊列連接情況。另用一標志單元記錄輪到運行的進程。例如，當前輪到P₂執行，則有：

標志單元

         K₂   

(4) 處理器調度總是選擇標志單元指示的進程運行。由于本實驗是模擬處理器調度的功能，所以，對被選中的進程并不實際的啟動運行，而是執行：

已運行時間+1

來模擬進程的一次運行，表示進程已經運行過一個單位的時間。

請注意：在實際的系統中，當一個進程被選中運行時，必須置上該進程可以運行的時間片值，以及恢復進程的現場，讓它占有處理器運行，直到出現等待事件或運行滿一個時間片。在這時省去了這些工作，僅用“已運行時間+1”來表示進程已經運行滿一個時間片。

(5) 進程運行一次后，應把該進程的進程控制塊中的指針值送到標志單元，以指示下一個輪到運行的進程。同時，應判斷該進程的要求運行時間與已運行時間，若該進程的要求運行時間?已運行時間，則表示它尚未執行結束，應待到下一輪時再運行。若該進程的要求運行時間=已運行時間，則表示它已經執行結束，應指導它的狀態修改成“結束”（E）且退出隊列。此時，應把該進程的進程控制塊中的指針值送到前面一個進程的指針位置。

(6) 若“就緒”狀態的進程隊列不為空，則重復上面的（4）和（5）的步驟，直到所有的進程都成為“結束”狀態。

(7) 在所設計的程序中應有顯示或打印語句，能顯示或打印每次選中進程的進程名以及運行一次后進程隊列的變化。

(8) 為五個進程任意確定一組“要求運行時間”，啟動所設計的處理器調度程序，顯示或打印逐次被選中的進程名以及進程控制塊的動態變化過程。

第二題：設計一個按響應比高者優先調度算法實現進程調度的程序。

算法設計思想：

 (1) 假定系統有五個進程，每一個進程用一個進程控制塊PCB來代表，進程控制塊的格式為：

其中，進程名——作為進程的標識，假設五個進程的進程名分別為P₁，P₂，P₃，P₄，P₅。

指針——按優先數的大小把五個進程連成隊列，用指針指出下一個進程的進程控制塊的首地址，最后一個進程中的指針為“0”。

要求運行時間——假設進程需要運行的單位時間數。

等待時間——自最近一次調度運行至今等待的時間數，當進程被調度時等待時間清零。

響應比——進程調度程序運行前計算每個進程的響應比，調度時總是選取響應比大的進程先執行，每次執行一個固定的時間片。

狀態——可假設有兩種狀態，“就緒”狀態和“結束”狀態。五個進程的初始狀態都為“就緒”，用“R”表示，當一個進程運行結束后，它的狀態為“結束”，用“E”表示。

(2) 在每次運行你所設計的處理器調度程序之前，為每個進程任意確定它的“等待時間”和“要求運行時間”。

(3) 為了調度方便，把五個進程按給定的響應比從大到小連成隊列。用一單元指出隊首進程，用指針指出隊列的連接情況。例：

  隊首標志

         K₂   

(4) 處理器調度總是選隊首進程運行。采用動態改變響應比的辦法，進程每運行一次重新計算各進程的響應比。由于本實驗是模擬處理器調度，所以，對被選中的進程并不實際的啟動運行，而是執行：要求運行時間-1、等待時間為0。其它進程等待時間+1，重新計算各進程的響應比，并從大到小排序。

提醒注意的是：在實際的系統中，當一個進程被選中運行時，必須恢復進程的現場，讓它占有處理器運行，直到出現等待事件或運行結束。在這里省去了這些工作。

(5) 進程運行一次后，若要求運行時間?0，則再將它加入隊尾（因其響應比最小。）；若要求運行時間=0，則把它的狀態修改成“結束”（E），且退出隊列。

(6) 若“就緒”狀態的進程隊列不為空，則重復上面（4）和（5）的步驟，直到所有進程都成為“結束”狀態。

(7) 在所設計的程序中應有顯示或打印語句，能顯示或打印每次被選中進程的進程名以及運行一次后進程隊列的變化及各進程的參數。