一、實(shí)驗(yàn)內(nèi)容
利用高級(jí)語言模擬進(jìn)程的時(shí)間片輪轉(zhuǎn)調(diào)度算法，響應(yīng)比高者優(yōu)先調(diào)度算法。
二、實(shí)驗(yàn)?zāi)康?/span>
在采用多道程序設(shè)計(jì)的系統(tǒng)中，往往有若干個(gè)進(jìn)程同時(shí)處于就緒狀態(tài)。當(dāng)就緒進(jìn)程個(gè)數(shù)大于處理器數(shù)時(shí)，就必須依照某種策略來決定哪些進(jìn)程優(yōu)先占用處理器。本實(shí)驗(yàn)?zāi)M在單處理器情況下的處理器調(diào)度，幫助學(xué)生加深了解處理器調(diào)度的工作。
三、實(shí)驗(yàn)環(huán)境
1．PC微機(jī)。
2．Windows 操作系統(tǒng)。
3．C/C++/VB開發(fā)集成環(huán)境。
四、實(shí)驗(yàn)題目
本實(shí)驗(yàn)有兩個(gè)小題。
第一題：設(shè)計(jì)一個(gè)按時(shí)間片輪轉(zhuǎn)法實(shí)現(xiàn)處理器調(diào)度的程序。
算法設(shè)計(jì)思想：
(1) 假定系統(tǒng)有五個(gè)進(jìn)程，每一個(gè)進(jìn)程用一個(gè)進(jìn)程控制塊PCB來代表。進(jìn)程控制塊的格式為：
|
進(jìn)程名
|
|
指針
|
|
要求運(yùn)行時(shí)間
|
|
已運(yùn)行時(shí)間
|
|
狀態(tài)
|
其中，進(jìn)程名——作為進(jìn)程的標(biāo)識(shí)，假設(shè)五個(gè)進(jìn)程的進(jìn)程名分別為Q1，Q2，Q3，Q4，Q5。
指針——進(jìn)程按順序排成循環(huán)隊(duì)列，用指針指出下一個(gè)進(jìn)程的進(jìn)程控制塊的首地址，最后一個(gè)進(jìn)程的指針指出第一個(gè)進(jìn)程的進(jìn)程控制塊首地址。
要求運(yùn)行時(shí)間——假設(shè)進(jìn)程需要運(yùn)行的單位時(shí)間數(shù)。
已運(yùn)行時(shí)間——假設(shè)進(jìn)程已經(jīng)運(yùn)行的單位時(shí)間數(shù)，初始值為“0”。
狀態(tài)——有兩種狀態(tài)，“就緒”和“結(jié)束”，初始狀態(tài)都為“就緒”，用“R”表示。當(dāng)一個(gè)進(jìn)程運(yùn)行結(jié)束后，它的狀態(tài)為“結(jié)束”，用“E”表示。
(2) 每次運(yùn)行所設(shè)計(jì)的進(jìn)程調(diào)度程序前，為每個(gè)進(jìn)程任意確定它的“要求運(yùn)行時(shí)間”。
(3) 把五個(gè)進(jìn)程按順序排成循環(huán)隊(duì)列，用指針指出隊(duì)列連接情況。另用一標(biāo)志單元記錄輪到運(yùn)行的進(jìn)程。例如，當(dāng)前輪到P2執(zhí)行，則有：
標(biāo)志單元
K2
|
K1
|
Q1
|
K2
|
Q2
|
K3
|
Q3
|
K4
|
Q4
|
K5
|
Q5
|
|
|
K2
|
|
K3
|
|
K4
|
|
K5
|
|
K1
|
|
|
2
|
|
3
|
|
1
|
|
2
|
|
4
|
|
|
1
|
|
0
|
|
0
|
|
0
|
|
0
|
|
|
R
|
|
R
|
|
R
|
|
R
|
|
R
|
|
|
PCB1
|
|
PCB2
|
|
PCB3
|
|
PCB4
|
|
PCB5
|
(4) 處理器調(diào)度總是選擇標(biāo)志單元指示的進(jìn)程運(yùn)行。由于本實(shí)驗(yàn)是模擬處理器調(diào)度的功能，所以，對(duì)被選中的進(jìn)程并不實(shí)際的啟動(dòng)運(yùn)行，而是執(zhí)行：
已運(yùn)行時(shí)間+1
來模擬進(jìn)程的一次運(yùn)行，表示進(jìn)程已經(jīng)運(yùn)行過一個(gè)單位的時(shí)間。
請(qǐng)注意：在實(shí)際的系統(tǒng)中，當(dāng)一個(gè)進(jìn)程被選中運(yùn)行時(shí)，必須置上該進(jìn)程可以運(yùn)行的時(shí)間片值，以及恢復(fù)進(jìn)程的現(xiàn)場，讓它占有處理器運(yùn)行，直到出現(xiàn)等待事件或運(yùn)行滿一個(gè)時(shí)間片。在這時(shí)省去了這些工作，僅用“已運(yùn)行時(shí)間+1”來表示進(jìn)程已經(jīng)運(yùn)行滿一個(gè)時(shí)間片。
(5) 進(jìn)程運(yùn)行一次后，應(yīng)把該進(jìn)程的進(jìn)程控制塊中的指針值送到標(biāo)志單元，以指示下一個(gè)輪到運(yùn)行的進(jìn)程。同時(shí)，應(yīng)判斷該進(jìn)程的要求運(yùn)行時(shí)間與已運(yùn)行時(shí)間，若該進(jìn)程的要求運(yùn)行時(shí)間?已運(yùn)行時(shí)間，則表示它尚未執(zhí)行結(jié)束，應(yīng)待到下一輪時(shí)再運(yùn)行。若該進(jìn)程的要求運(yùn)行時(shí)間=已運(yùn)行時(shí)間，則表示它已經(jīng)執(zhí)行結(jié)束，應(yīng)指導(dǎo)它的狀態(tài)修改成“結(jié)束”（E）且退出隊(duì)列。此時(shí)，應(yīng)把該進(jìn)程的進(jìn)程控制塊中的指針值送到前面一個(gè)進(jìn)程的指針位置。
(6) 若“就緒”狀態(tài)的進(jìn)程隊(duì)列不為空，則重復(fù)上面的（4）和（5）的步驟，直到所有的進(jìn)程都成為“結(jié)束”狀態(tài)。
(7) 在所設(shè)計(jì)的程序中應(yīng)有顯示或打印語句，能顯示或打印每次選中進(jìn)程的進(jìn)程名以及運(yùn)行一次后進(jìn)程隊(duì)列的變化。
(8) 為五個(gè)進(jìn)程任意確定一組“要求運(yùn)行時(shí)間”，啟動(dòng)所設(shè)計(jì)的處理器調(diào)度程序，顯示或打印逐次被選中的進(jìn)程名以及進(jìn)程控制塊的動(dòng)態(tài)變化過程。
第二題：設(shè)計(jì)一個(gè)按響應(yīng)比高者優(yōu)先調(diào)度算法實(shí)現(xiàn)進(jìn)程調(diào)度的程序。
算法設(shè)計(jì)思想：
(1) 假定系統(tǒng)有五個(gè)進(jìn)程，每一個(gè)進(jìn)程用一個(gè)進(jìn)程控制塊PCB來代表，進(jìn)程控制塊的格式為：
|
進(jìn)程名
|
|
指針
|
|
要求運(yùn)行時(shí)間
|
|
等待時(shí)間
|
|
響應(yīng)比
|
|
狀態(tài)
|
其中，進(jìn)程名——作為進(jìn)程的標(biāo)識(shí)，假設(shè)五個(gè)進(jìn)程的進(jìn)程名分別為P1，P2，P3，P4，P5。
指針——按優(yōu)先數(shù)的大小把五個(gè)進(jìn)程連成隊(duì)列，用指針指出下一個(gè)進(jìn)程的進(jìn)程控制塊的首地址，最后一個(gè)進(jìn)程中的指針為“0”。
要求運(yùn)行時(shí)間——假設(shè)進(jìn)程需要運(yùn)行的單位時(shí)間數(shù)。
等待時(shí)間——自最近一次調(diào)度運(yùn)行至今等待的時(shí)間數(shù)，當(dāng)進(jìn)程被調(diào)度時(shí)等待時(shí)間清零。
響應(yīng)比——進(jìn)程調(diào)度程序運(yùn)行前計(jì)算每個(gè)進(jìn)程的響應(yīng)比，調(diào)度時(shí)總是選取響應(yīng)比大的進(jìn)程先執(zhí)行，每次執(zhí)行一個(gè)固定的時(shí)間片。
狀態(tài)——可假設(shè)有兩種狀態(tài)，“就緒”狀態(tài)和“結(jié)束”狀態(tài)。五個(gè)進(jìn)程的初始狀態(tài)都為“就緒”，用“R”表示，當(dāng)一個(gè)進(jìn)程運(yùn)行結(jié)束后，它的狀態(tài)為“結(jié)束”，用“E”表示。
(2) 在每次運(yùn)行你所設(shè)計(jì)的處理器調(diào)度程序之前，為每個(gè)進(jìn)程任意確定它的“等待時(shí)間”和“要求運(yùn)行時(shí)間”。
(3) 為了調(diào)度方便，把五個(gè)進(jìn)程按給定的響應(yīng)比從大到小連成隊(duì)列。用一單元指出隊(duì)首進(jìn)程，用指針指出隊(duì)列的連接情況。例：
隊(duì)首標(biāo)志
K2
|
K1
|
P1
|
K2
|
P2
|
K3
|
P3
|
K4
|
P4
|
K5
|
P5
|
|
|
0
|
|
K4
|
|
K5
|
|
K3
|
|
K1
|
|
|
2
|
|
3
|
|
1
|
|
2
|
|
4
|
|
|
1
|
|
5
|
|
3
|
|
4
|
|
2
|
|
|
R
|
|
R
|
|
R
|
|
R
|
|
R
|
|
|
PCB1
|
|
PCB2
|
|
PCB3
|
|
PCB4
|
|
PCB5
|
(4) 處理器調(diào)度總是選隊(duì)首進(jìn)程運(yùn)行。采用動(dòng)態(tài)改變響應(yīng)比的辦法，進(jìn)程每運(yùn)行一次重新計(jì)算各進(jìn)程的響應(yīng)比。由于本實(shí)驗(yàn)是模擬處理器調(diào)度，所以，對(duì)被選中的進(jìn)程并不實(shí)際的啟動(dòng)運(yùn)行，而是執(zhí)行：要求運(yùn)行時(shí)間-1、等待時(shí)間為0。其它進(jìn)程等待時(shí)間+1，重新計(jì)算各進(jìn)程的響應(yīng)比，并從大到小排序。
提醒注意的是：在實(shí)際的系統(tǒng)中，當(dāng)一個(gè)進(jìn)程被選中運(yùn)行時(shí)，必須恢復(fù)進(jìn)程的現(xiàn)場，讓它占有處理器運(yùn)行，直到出現(xiàn)等待事件或運(yùn)行結(jié)束。在這里省去了這些工作。
(5) 進(jìn)程運(yùn)行一次后，若要求運(yùn)行時(shí)間?0，則再將它加入隊(duì)尾（因其響應(yīng)比最小。）；若要求運(yùn)行時(shí)間=0，則把它的狀態(tài)修改成“結(jié)束”（E），且退出隊(duì)列。
(6) 若“就緒”狀態(tài)的進(jìn)程隊(duì)列不為空，則重復(fù)上面（4）和（5）的步驟，直到所有進(jìn)程都成為“結(jié)束”狀態(tài)。
(7) 在所設(shè)計(jì)的程序中應(yīng)有顯示或打印語句，能顯示或打印每次被選中進(jìn)程的進(jìn)程名以及運(yùn)行一次后進(jìn)程隊(duì)列的變化及各進(jìn)程的參數(shù)。
(8) 為五個(gè)進(jìn)程任意確定一組“等待時(shí)間”和“要求運(yùn)行時(shí)間”，啟動(dòng)所設(shè)計(jì)的進(jìn)程調(diào)度程序，顯示或打印逐次被選中進(jìn)程的進(jìn)程名以及進(jìn)程控制塊的動(dòng)態(tài)變化過程。