時間片輪轉(zhuǎn)RR進程調(diào)度算法

1、實驗二 時間片輪轉(zhuǎn) RR 進程調(diào)度算法 【實驗?zāi)康摹?通過這次實驗，加深對進程概念的理解，進一步掌握進程狀態(tài)的 轉(zhuǎn)變、進程調(diào)度的策略及對系統(tǒng)性能的評價方法。 【實驗內(nèi)容】 問題描述： 設(shè)計程序模擬進程的時間片輪轉(zhuǎn) RR調(diào)度過程。假設(shè)有n個進程 分別在 ，Tn時刻到達系統(tǒng)，它們需要的服務(wù)時間分別為 Si,，S。分別利用不同的時間片大小 q,采用時間片輪轉(zhuǎn)RR進程 調(diào)度算法進行調(diào)度，計算每個進程的完成時間、周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn) 時間,并且統(tǒng)計 n 個進程的平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。 程序要求： 1 ）進程個數(shù)n;每個進程的到達時間 Ti,，Tn和服務(wù)時間 Si,，S輸入時間片大小q。 2）要求

2、時間片輪轉(zhuǎn)法 RR 調(diào)度進程運行,計算每個進程的周轉(zhuǎn) 時間和帶權(quán)周轉(zhuǎn)時間,并且計算所有進程的平均周轉(zhuǎn)時間和帶權(quán)平均 周轉(zhuǎn)時間; 3）輸出：要求模擬整個調(diào)度過程,輸出每個時刻的進程運行狀 態(tài),如“時刻 3：進程 B 開始運行”等等; 4）輸出：要求輸出計算出來的每個進程的周轉(zhuǎn)時間、帶權(quán)周轉(zhuǎn) 時間、所有進程的平均周轉(zhuǎn)時間以及帶權(quán)平均周轉(zhuǎn)時間。 實驗要求： 1) 上機前認(rèn)真復(fù)習(xí)時間片輪轉(zhuǎn) RR 進程調(diào)度調(diào)度算法，熟悉進 程調(diào)度的執(zhí)行過程； 2) 上機時獨立編程、調(diào)試程序； 3) 根據(jù)具體實驗要求，完成好實驗報告(包括實驗的目的、內(nèi) 容、要求、源程序、實例運行結(jié)果截圖、發(fā)現(xiàn)的問題以及解決方法) 【實驗

3、分析】 需求分析： (1) 按提示輸入進程個數(shù)，不得大于 MaxNum ；依次輸入進程隊 列標(biāo)識 ,到達時間 ,服務(wù)時間，一個進程占一行 ;輸入時間片的大小。 (2) 輸出的形式： 先輸出時刻，正在運行的進程，再總的輸出所 有進程的完成時間，周轉(zhuǎn)時間，帶權(quán)周轉(zhuǎn)時間。最后輸出平均周轉(zhuǎn)時 間與平均帶權(quán)周轉(zhuǎn)時間。 (3) 程序所能達到的功能：根據(jù)時間片輪轉(zhuǎn) RR進程調(diào)度調(diào)度算 法調(diào)度進程運行， 模擬整個調(diào)度過程， 計算每個進程的周轉(zhuǎn)時間和帶 權(quán)周轉(zhuǎn)時間，并且計算所有進程的平均周轉(zhuǎn)時間和帶權(quán)平均周轉(zhuǎn)時 間。 (4) 測試數(shù)據(jù)： 輸入數(shù)據(jù)分別為： 5 a 0 4 b 1 3 輸出為： 時刻0:進程a開始

4、運行 時刻1進程b開始運行 時刻2：進程a開始運行 時刻3:進程c開始運行 時刻4:進程b開始運行 時刻5:進程d開始運行 時刻6:進程a開始運行 時刻7：進程e開始運行 時刻8進程c開始運行 時刻9:進程b開始運行 時刻10:進程d開始運行 時刻11:進程a開始運行 時刻12：進程e開始運行 時刻13:進程c開始運行 時刻14：進程e開始運行 時刻15:進程c開始運行 時刻16:進程e開始運行 時刻17:進程c開始運行 b 的完成時間為 10 周轉(zhuǎn)時間為 9 帶權(quán)周轉(zhuǎn)時間為 3 c 的完成時間為 18 周轉(zhuǎn)時間為 16 帶權(quán)周轉(zhuǎn)時間為 3.2 d 的完成時間為 11 周轉(zhuǎn)時間為 18 帶權(quán)周

5、轉(zhuǎn)時間為 4 e 的完成時間為 17 周轉(zhuǎn)時間為 13 帶權(quán)周轉(zhuǎn)時間為 3.25 平均周轉(zhuǎn)時間 11.6 平均帶權(quán)周轉(zhuǎn)時間 3.29 輸入數(shù)據(jù)分別為： 5 a 0 4 b 1 3 c 2 5 d 3 2 e 4 4 4 輸出為：時刻0:進程a開始運行 時刻4：進程b開始運行 時刻7:進程c開始運行 時刻11:進程d開始運行 時刻13:進程c開始運行 時刻14：進程e開始運行 a 的完成時間為 4 周轉(zhuǎn)時間為 4 帶權(quán)周轉(zhuǎn)時間為 1 b 的完成時間為 7 周轉(zhuǎn)時間為 6 帶權(quán)周轉(zhuǎn)時間為 2 c 的完成時間為 18 周轉(zhuǎn)時間為 16 帶權(quán)周轉(zhuǎn)時間為 3.2 d 的完成時間為 13 周轉(zhuǎn)時間為 10

6、 帶權(quán)周轉(zhuǎn)時間為 5 e 的完成時間為 17 周轉(zhuǎn)時間為 13 帶權(quán)周轉(zhuǎn)時間為 3.25 平均周轉(zhuǎn)時間 9.8 平均帶權(quán)周轉(zhuǎn)時間 2.89 概要設(shè)計： (1) 本程序中用到的抽象數(shù)據(jù)類型的定義： class process public: char name;/ 標(biāo)識 int ArrivalTime;/ 到達時間 int ServiceTime;/ 服務(wù)時間 int FinishTime;/ 完成時間 int WholeTime;/ 周轉(zhuǎn)時間 double WeightWholeTime;/ 帶權(quán)周轉(zhuǎn)時間 int PServiceTime;/ 剩余的服務(wù)時間 ;/ 表示一個進程的類 (2) 主

7、程序的流程 : 輸入進程個數(shù) =輸入進程，到達時間，服務(wù)時間 =輸入時 間片 =按到達時間的前后放入進程數(shù)組中 =將分別第一個進程加入 等待序列 =將隊首進程壓出等待序列 =判斷是否所有元素都加入過 等待序列，若沒有，將其中序號最小的元素壓入等待序列 =判斷被 壓出的元素的剩余服務(wù)時間是否小于時間片 =若大于，總的完成時 間為之前的時間片的時間， 并將次進程壓入序列尾部； 若小于或等于， 完成時間為之前總的完成時間加剩余服務(wù)時間， / 找到進程在進程數(shù) 組中的位置，修改其完成時間 =輸出完成時間，周轉(zhuǎn)時間，帶權(quán)周 轉(zhuǎn)時間 =輸出平均周轉(zhuǎn)時間與平均帶權(quán)周轉(zhuǎn)時間 (3) 各程序模塊之間的層次 (

8、調(diào)用) 關(guān)系。 主程序調(diào)用輸入模塊， 進程進等待隊列模塊， 計算完成時間， 周轉(zhuǎn)時間，帶權(quán)周轉(zhuǎn)時間模塊 詳細(xì)設(shè)計 實現(xiàn)程序模塊的具體算法。 #include #include using namespace std; const int MaxNum=100;/ 進程個數(shù)的最大值 class process public: char name; int ArrivalTime; int ServiceTime; int FinishTime; int WholeTime; double WeightWholeTime; int PServiceTime; ;/ 表示一個進程的類， 包括其標(biāo)識

9、,到達時間 , 服務(wù)時間，完成 時間，周轉(zhuǎn)時間，帶權(quán)周轉(zhuǎn)時間 , 以及剩余的服務(wù)時間 process prMaxNum;/ 進程數(shù)組 void main() queue L1;/ 表示等待隊列 cout 輸入進程個數(shù) len; cout 依次輸入進程隊列標(biāo)識 , 到達時間 , 服務(wù)時間 endl; for(int i=0;a.ArrivalTimea.ServiceTime; a.PServiceTime=a.ServiceTime; pri=a; int q;/ 表示時間片 cout 輸入時間片 q; L1.push(pr0);/ 先將第一個進程加入等待序列 int sum=0

10、;/ 總的完成時間 int n=1;/ 記錄加入等待序列的是數(shù)組中的第幾個元素 int y=0; while(L1.empty()!=1)/ 等待序列不為空，則循環(huán) process b=L1.front();/ 提出等待序列的首元素，并壓出 序列 L1.pop(); cout 時 刻 sum ： 進 程 開 始 運 行 endl; if(qb.PServiceTime)/ 判斷被壓出的元素的剩余服務(wù) 時間是否小于時間片 b.PServiceTime=b.PServiceTime-q;/ 若大于，總的完 成時間為之前的時間片的時間， 并將次進程壓入序列尾部， 剩余時間 sum=su

11、m+q; if(nsum) n+; L1.push(b); else / 若小于或等于，完成時間為之前總的完成時間加剩余服 務(wù)時間 sum=sum+b.PServiceTime; b.FinishTime=sum; for(int p=0;plen;p+) / 找到進程在進程數(shù)組 中的位置，修改其完成時間 if(=) prp=b; if(nsum) n+; int WT=0;/ 總的周期時間 double WWT=0;/ 總的帶權(quán)周期時間 for(int k=0;klen;+k) process b=prk; b.WholeTime=b.FinishTime-b.A

12、rrivalTime;/周 轉(zhuǎn) 時 間 為完成時間減到達時間 WT=WT+b.WholeTime; b.WeightWholeTime=double(b.WholeTime)/b.ServiceTime;/ 帶 權(quán)周轉(zhuǎn)時間為周轉(zhuǎn)時間除以服務(wù)時間 WWT=WWT+b.WeightWholeTime; 的完成時間為 b.FinishTime 周轉(zhuǎn) 時 間 為 b.WholeTime 帶 權(quán) 周 轉(zhuǎn) 時 間 為 b.WeightWholeTimeendl; cout endl; cout 平均周轉(zhuǎn)時間 double(WT)/lenendl;/ 平均周 轉(zhuǎn)時間為總周轉(zhuǎn)時間除以進程

13、數(shù) cout 平均帶權(quán)周轉(zhuǎn)時間 double(WWT)/lenendl;/ 平 均帶權(quán)周轉(zhuǎn)時間為總帶權(quán)周轉(zhuǎn)時間除以進程數(shù) 調(diào)試分析 1、執(zhí)行算法問前，要先創(chuàng)建抽象數(shù)據(jù)類型 process 。 2、執(zhí)行算法時， 要注意判斷被壓出的元素的剩余服務(wù)時間是否 小于時間片。 3、執(zhí)行算法后， 改變了進程的完成時間，要將修改后的加入到 進程數(shù)組中。 4、時間的復(fù)雜度是 O(n*m). 用戶使用說明 先輸出時刻，正在運行的進程，再輸出進程的完成時間，周轉(zhuǎn)時 間，帶權(quán)周轉(zhuǎn)時間。按提示信息依次輸入。 測試結(jié)果 輸入數(shù)據(jù)分別為： 5 a 0 4 b 1 3 c 2 5 1 輸出為： 時刻0:進程a開始運行 時刻1

14、進程b開始運行 時刻2：進程a開始運行 時刻3:進程c開始運行 時刻4:進程b開始運行 時刻5:進程d開始運行 時刻6:進程a開始運行 時刻7：進程e開始運行 時刻8進程c開始運行 時刻9:進程b開始運行 時刻10:進程d開始運行 時刻11:進程a開始運行 時刻12：進程e開始運行 時刻13:進程c開始運行 時刻14：進程e開始運行 時刻15:進程c開始運行 時刻16:進程e開始運行 時刻17:進程c開始運行 的完成時間為 12 周轉(zhuǎn)時間為 12 帶權(quán)周轉(zhuǎn)時間為 3 b 的完成時間為 10 周轉(zhuǎn)時間為 9 帶權(quán)周轉(zhuǎn)時間為 3 c 的完成時間為 18 周轉(zhuǎn)時間為 16 帶權(quán)周轉(zhuǎn)時間為 3.2 d

15、 的完成時間為 11 周轉(zhuǎn)時間為 18 帶權(quán)周轉(zhuǎn)時間為 4 e 的完成時間為 17 周轉(zhuǎn)時間為 13 帶權(quán)周轉(zhuǎn)時間為 3.25 平均周轉(zhuǎn)時間 11.6 平均帶權(quán)周轉(zhuǎn)時間 3.29 輸入數(shù)據(jù)分別為： 5 a 0 4 b 1 3 c 2 5 d 3 2 e 4 4 4 輸出為：時刻0:進程a開始運行 時刻4：進程b開始運行 時刻7:進程c開始運行 時刻11:進程d開始運行 時刻13:進程c開始運行 時刻14：進程e開始運行 a 的完成時間為 4 周轉(zhuǎn)時間為 4 帶權(quán)周轉(zhuǎn)時間為 1 b 的完成時間為 7 周轉(zhuǎn)時間為 6 帶權(quán)周轉(zhuǎn)時間為 2 c 的完成時間為 18 周轉(zhuǎn)時間為 16 帶權(quán)周轉(zhuǎn)時間為 3

16、.2 d 的完成時間為 13 周轉(zhuǎn)時間為 10 帶權(quán)周轉(zhuǎn)時間為 5 e 的完成時間為 17 周轉(zhuǎn)時間為 13 帶權(quán)周轉(zhuǎn)時間為 3.25 平均周轉(zhuǎn)時間 9.8 平均帶權(quán)周轉(zhuǎn)時間 2.89 D：攝作丟統(tǒng)賣驗抿告Dmbug0竣二訴丁 程 進 人 1T 3 5 2 4 R、 12 3 4 b ; I b zfl %l4fl4fyiTdT;IT;ITdITdTdTd ， 一一 45 1 B 0 o 0 日 B uu H nHM nM HMU nn nn B B nn Q D a An 一 丁一丁一丁一 J亍一丁亍一丁 丁一 丁Z 衷衷衷衷衷夬夬-; 閆曰日昌曰劉龍11_、|1唐1周 始始始始始始始始始壽黑霧節(jié)的2 開開開開開開開*訐內(nèi)耐用切嗎cflenenVI iili fl . 01234567 d 0丄2 3 4 5 6 ? 8 9丄f丄丄丄丄丄丄兀 劉刻刻刻刻刻刻刻 T:、 On p的完成時間為仙冃轡理乎 序挈周竺目間為3 莎元冠麗冠廠商忘麗頭語G弟無由帚一一 H MW W MW OKMB ”的完成時間為周轉(zhuǎn)時間為1?帶權(quán)彎皈間為2 金均周需時間11.6 忸:為帶權(quán)局轉(zhuǎn)吋間3-29 Press any key to cont iiiue 秋D:fi作磁湊驗報