實(shí)驗(yàn)五 進(jìn)程調(diào)度算法模擬

1、實(shí)驗(yàn)五進(jìn)程調(diào)度算法模擬一、實(shí)驗(yàn)內(nèi)容選擇一個(gè)調(diào)度算法，模擬實(shí)現(xiàn)處理器調(diào)度。二、實(shí)驗(yàn)?zāi)康脑诓捎枚嗟莱绦蛟O(shè)計(jì)的系統(tǒng)中，往往有若十個(gè)進(jìn)程同時(shí)處于就緒狀態(tài)。當(dāng)就 緒狀態(tài)進(jìn)程個(gè)數(shù)大于處理器數(shù)時(shí)，就必須依照某種策略來決定哪些進(jìn)程優(yōu)先占用 處理器。本實(shí)驗(yàn)?zāi)M在單處理器情況下處理器調(diào)度，幫助自己加深了解處理器調(diào) 度的工作。三、實(shí)驗(yàn)題目本實(shí)驗(yàn)有兩個(gè)題，可選擇其中的一題做實(shí)驗(yàn)。第一題：設(shè)計(jì)一個(gè)按優(yōu)先數(shù)調(diào)度算法實(shí)現(xiàn)處理器調(diào)度的程序。提示:假定系統(tǒng)有五個(gè)進(jìn)程，每一個(gè)進(jìn)程用一個(gè)進(jìn)程控制塊PCB來代表，進(jìn)程 控制塊的格式為：一 進(jìn)程名一指針一要求運(yùn)行時(shí)間一 優(yōu)先數(shù)一狀態(tài)其中：進(jìn)程名一一作為進(jìn)程的標(biāo)識(shí)，假設(shè)五個(gè)進(jìn)程的進(jìn)程名分

2、別為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ù)。優(yōu)先數(shù)一一賦予進(jìn)程的優(yōu)先數(shù)，調(diào)度時(shí)總是選取優(yōu)先數(shù)大的進(jìn)程先執(zhí)行。狀態(tài)一一可假設(shè)有兩種狀態(tài)，“就緒8080”狀態(tài)和“結(jié)束”狀態(tài)。五個(gè) 進(jìn)程的初始狀態(tài)都為“就緒”，用“R”表示，當(dāng)一個(gè)進(jìn)程運(yùn)行結(jié)束后， 它的狀態(tài)為“結(jié)束”，用“E”表示。在每次運(yùn)行你所設(shè)計(jì)的處理器調(diào)度程序之前，為每個(gè)進(jìn)程任意確定它的 “優(yōu)先數(shù)”和“要求運(yùn)行時(shí)間”。本實(shí)驗(yàn)由于為了檢查的方便，優(yōu)先數(shù)和運(yùn)行時(shí) 間采用下表中的數(shù)值。為了調(diào)度方便，把

3、五個(gè)進(jìn)程按給定的優(yōu)先數(shù)從大到小連成隊(duì)列。用一單 元指出隊(duì)首進(jìn)程，用指針指出隊(duì)列的連接情況。例：隊(duì)首標(biāo)志PCB1PCB3PCB4PCB5處理器調(diào)度總是選隊(duì)首進(jìn)程運(yùn)行。采用動(dòng)態(tài)改變優(yōu)先數(shù)的辦法，進(jìn)程每 運(yùn)行一次優(yōu)先數(shù)就減“1”。由于本實(shí)驗(yàn)是模擬處理器調(diào)度，所以，對(duì)被選中的進(jìn) 程并不實(shí)際的啟動(dòng)運(yùn)行，而是執(zhí)行：優(yōu)先數(shù)-1要求運(yùn)行時(shí)間-1來模擬進(jìn)程的一次運(yùn)行。提醒注意的是：在實(shí)際的系統(tǒng)中，當(dāng)一個(gè)進(jìn)程被選中運(yùn)行時(shí)，必須恢復(fù)進(jìn)程 的現(xiàn)場(chǎng)，讓它占有處理器運(yùn)行，直到出現(xiàn)等待事件或運(yùn)行結(jié)束。在這里省去了這 些工作。進(jìn)程運(yùn)行一次后，若要求運(yùn)行時(shí)間0，則再將它加入隊(duì)列(按優(yōu)先數(shù)大 小插入，且置隊(duì)首標(biāo)志)；若要求運(yùn)行時(shí)

4、間=0，則把它的狀態(tài)修改成“結(jié)束”(E)， 且退出隊(duì)列。若“就緒”狀態(tài)的進(jìn)程隊(duì)列不為空，則重復(fù)上面(4)和(5)的步驟， 直到所有進(jìn)程都成為“結(jié)束”狀態(tài)。在所設(shè)計(jì)的程序中應(yīng)有顯示或打印語句，能顯示或打印每次被選中進(jìn)程 的進(jìn)程名以及運(yùn)行一次后進(jìn)程隊(duì)列的變化。選作部分為五個(gè)進(jìn)程任意確定一組“優(yōu)先數(shù)”和“要求運(yùn)行時(shí)間”，啟動(dòng)所設(shè)計(jì) 的處理器調(diào)度程序，顯示或打印逐次被選中進(jìn)程的進(jìn)程名以及進(jìn)程控制塊的動(dòng)態(tài) 變化過程。第二題：設(shè)計(jì)一個(gè)按時(shí)間片輪轉(zhuǎn)法實(shí)現(xiàn)處理器調(diào)度的程序。提示:假定系統(tǒng)有五個(gè)進(jìn)程，每一個(gè)進(jìn)程用一個(gè)進(jìn)程控制塊PCB來代表。進(jìn)程 控制塊的格式為：一 進(jìn)程名一 指針 一要求運(yùn)行時(shí)間已運(yùn)行時(shí)間狀態(tài)其

5、中：進(jìn)程名一一作為進(jìn)程的標(biāo)識(shí)，假設(shè)五個(gè)進(jìn)程的進(jìn)程名分別為QQ2, 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”表示。每次運(yùn)行所設(shè)計(jì)的處理器調(diào)度程序前，為每個(gè)進(jìn)程任意確定它的“要求 運(yùn)行時(shí)間”。把五個(gè)進(jìn)程按順序排成循環(huán)隊(duì)列，用指針指出隊(duì)列連接情況。另用一標(biāo) 志單元記錄輪到運(yùn)行的進(jìn)

6、程。例如，當(dāng)前輪到P2執(zhí)行，則有：標(biāo)志單元QiK2Q2K3Q3K4Q4K5Q5K2K3JK4K5K12312410000RRRRRPCB1PCB2PCB3PCB4PCB5處理器調(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í)間。注意：在實(shí)際的系統(tǒng)中，當(dāng)一個(gè)進(jìn)程被選中運(yùn)行時(shí)，必須置上該進(jìn)程可以運(yùn) 行的時(shí)間片值，以及恢復(fù)進(jìn)程的現(xiàn)場(chǎng)，讓它占有處理器運(yùn)行，直到出現(xiàn)等待事件 或運(yùn)行滿一個(gè)時(shí)間片。在這時(shí)省去了這些工作，僅用“已運(yùn)行時(shí)間+1”來表示進(jìn) 程已經(jīng)運(yùn)行滿一個(gè)時(shí)

7、間片。（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ù)上面的0）和（5）的步驟， 直到所有的進(jìn)程都成為“結(jié)束”狀態(tài)。（7）在所設(shè)計(jì)的程序中應(yīng)有顯示或打印語句，能顯示或打印每次選中進(jìn)程的 進(jìn)程名以及運(yùn)行一

8、次后進(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í)驗(yàn)五報(bào)告內(nèi)容及要求實(shí)驗(yàn)報(bào)告內(nèi)容：實(shí)驗(yàn)五要求的程序之一的源代碼。實(shí)驗(yàn)報(bào)告要求：由于本實(shí)驗(yàn)的源程序可能較長(zhǎng)，故在書寫實(shí)驗(yàn)報(bào)告時(shí)只需給出程 序的大致框架，著重給出核心部分的代碼（但是要求給出盡可能詳細(xì)地注釋）， 對(duì)于初始化及界面設(shè)計(jì)等內(nèi)容可以省略不寫（或僅以一句注釋說明）。程序中使用的數(shù)據(jù)結(jié)構(gòu)示例typedef struct _proc /* 進(jìn)程結(jié)構(gòu)體*/char name32;/* 進(jìn)程名 */int run_time; /*要求運(yùn)行總時(shí)間*/