時間片輪轉(zhuǎn)算法

《時間片輪轉(zhuǎn)算法》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在行業(yè)資料-天天文庫。

1、一、實驗目的（1）在單處理器情況下按時間片輪轉(zhuǎn)算法實現(xiàn)處理器調(diào)度，輸出運行動態(tài)變化過程。（2）通過算法的實現(xiàn)加深了解處理器調(diào)度的工作。二、實驗內(nèi)容輸入實現(xiàn)處理器調(diào)度的幾個進程信息，任意確定一組“要求運行時間”，啟動所設計的處理器調(diào)度程序，顯示逐次被選中進程的進程名以及進程控制塊的動態(tài)變化過程。三、實驗步驟1、任務分析：時間片輪轉(zhuǎn)的主要思想就是按順序為每一個進程一次只分配一個時間片的時間。算法要完成的功能就是將各個進程按照時間片輪轉(zhuǎn)運行的動態(tài)過程顯示出來。時間片輪轉(zhuǎn)算法的主要實現(xiàn)過程是首先為每一個進程創(chuàng)建一個進程控制塊，定義數(shù)據(jù)結(jié)構，說明進程控制塊所包含的內(nèi)容，有進程名、進程

2、所需運行時間、已運行時間和進程的狀態(tài)以及指針的信息。實現(xiàn)的過程即運用指針指向某一個進程，判斷當前的進程是否是就緒狀態(tài)“r”，如果是，則為該進程分配一個時間片，同時，已運行時間加一且要求運行的時間減一，如此循環(huán)執(zhí)行，當某一個進程的所需要運行的時間減少至0時，則將該進程的狀態(tài)設置為“e”。然后，將指針指向下一個未運行完成的進程，重復判斷，直至所有的進程都運行結(jié)束。2、概要設計：（1）所用數(shù)據(jù)結(jié)構及符號說明typedefstructPCB{charname[10];//進程名structPCB*next;//循環(huán)鏈指針intneed_time;//要求運行時間intworked_

3、time;//已運行時間，初始為0charcondition;//進程狀態(tài)，只有“就緒”和“結(jié)束”兩種狀態(tài)intflag;//進程結(jié)束標志，用于輸出}PCB;PCB*front,*rear;//循環(huán)鏈隊列的頭指針和尾指針intN;//N為進程數(shù)（2）主程序的流程圖：開始輸入進程數(shù)N輸入各進程信息為每個進程創(chuàng)建PCB并初始化形成一個循環(huán)鏈隊列指針指向循環(huán)鏈隊列第一個進程進程是否’r’運行時間+1且剩余時間-1Y剩余時間=0？Y將進程狀態(tài)置為’e’（完成）指針指向隊列中下個進程所有進程是否完成N結(jié)束Y（3）程序說明：處理器調(diào)度總是選擇指針指示的進程運行。由于本實驗是模擬處理器調(diào)

4、度的功能，所以，對被選中的進程并不實際的啟動運行，而是執(zhí)行：已運行時間+1來模擬進程的一次運行，表示進程已經(jīng)運行過一個單位的時間。3、詳細設計（1）首先每一個進程用一個進程控制塊PCB來代表。進程控制塊的格式為：進程名指針要求運行時間已運行時間狀態(tài)其中，進程名——作為進程的標識，如Q1、Q2等。指針——進程按順序排成循環(huán)鏈隊列，用指針指出下一個進程的進程控制塊的首地址，最后一個進程的指針指出第一個進程的進程控制塊首地址。要求運行時間——假設進程需要運行的單位時間數(shù)。已運行時間——假設進程已經(jīng)運行的單位時間數(shù)，初始值為“0”。狀態(tài)——有兩種狀態(tài)，“就緒”和“結(jié)束”，初始狀態(tài)都

5、為“就緒”，用“R”表示。當一個進程運行結(jié)束后，它的狀態(tài)為“結(jié)束”，用“E”表示。（2）每次運行所設計的處理器調(diào)度程序前，為每個進程任意確定它的“要求運行時間”。把五個進程按順序排成循環(huán)鏈隊列，用指針指出隊列連接情況。用指針表示輪到運行的進程，如下圖描述所示：K1Q1K2Q2K3Q3K4Q4K5Q5?K2?K3?K4?K5?K1?2?4?3?1?2?0?0?0?0?0?R?R?R?R?R?PCB1?PCB2?PCB3?PCB4?PCB5（3）程序詳細設計步驟：a.首先建立PCB的數(shù)據(jù)結(jié)構，為了便于正確輸出，加上了進程結(jié)束標志flag。輸入進程信息（包括進程名和要求運行的時間

6、），并為每個進程創(chuàng)建一個PCB并初始化形成一個循環(huán)鏈隊列，用函數(shù)creatPCB()來實現(xiàn)。b.建立函數(shù)judge()用來判斷進程全部運行結(jié)束標志，即當所有進程的狀態(tài)變?yōu)椤痚’（即完成狀態(tài)）后，循環(huán)結(jié)束，表示所有進程都已運行成功。c.建立時間片輪轉(zhuǎn)算法creatProcess（）對進程進行輪轉(zhuǎn)運行，首先指針s指向第一個進程PCB，即s=front，判斷該進程的狀態(tài)是否為’r’（就緒狀態(tài)），即if(s->condition=='r')，若是則表示此進程尚未執(zhí)行結(jié)束，則執(zhí)行s->worked_time++且s->need_time--，if(s->need_time==0)，則

7、表示此進程已運行結(jié)束，將其狀態(tài)置為結(jié)束，即s->condition='e'，并根據(jù)狀態(tài)位輸出完成信息，且以后不會再運行此進程。將指針指向下個進程，s=s->next，并判斷所有進程是否已全部運行結(jié)束，沒有則重復上面算法。當所有進程的狀態(tài)位都變成’e’表示所有進程運行完成，則循環(huán)結(jié)束。d.建立主函數(shù)main(),輸入進程數(shù)N，調(diào)用初始化循環(huán)鏈隊列函數(shù)creatPCB()和時間片輪轉(zhuǎn)算法creatProcess(N)，每次選中進程的進程名以及運行一次后進程隊列的變化，實現(xiàn)處理器的調(diào)度。4、調(diào)試分析：a．調(diào)試過程中遇到的