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

1、實驗二 時間片輪轉(zhuǎn)RR進程調(diào)度算法一：需求分析程序的設(shè)計的任務(wù)和目的：設(shè)計程序模擬進程的時間片輪轉(zhuǎn)RR調(diào)度過程。假設(shè)有n個進程分別在T1,，Tn時刻到達系統(tǒng)，它們需要的效勞時間分別為S1,，Sn。分別利用不同的時間片大小q,采用時間片輪轉(zhuǎn) RR進程調(diào)度算法進行調(diào)度， 計算每個進程的完成時間、 周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間，并且統(tǒng)計n個進程的平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。通過這次實驗，加深對進程概念的理解，進一步掌握進程狀態(tài)的轉(zhuǎn)變、進程調(diào)度的策略及對系統(tǒng)性能的評價方法。(1) 輸入的形式和輸入值的范圍為防止測試時頻繁輸入數(shù)據(jù)，將測試數(shù)據(jù)放在txt文件中采用讀文件方法讀取數(shù)據(jù)。在同目錄下的txt文件中

2、輸入數(shù)據(jù)，第一行為進程到達時間，中間用空格隔開，第二行為進程 效勞時間，不同進程的效勞時間之間用空格隔開。(2) 輸出的形式輸出每個時刻的進程運行狀態(tài)，并且輸出計算出來的每個進程的周轉(zhuǎn)時間、帶權(quán)周轉(zhuǎn)時間、所有進程的平均周轉(zhuǎn)時間以及帶權(quán)平均周轉(zhuǎn)時間。(詳見運行截圖)(3) 程序所能到達的功能；能夠模擬進程的時間片輪轉(zhuǎn) RR調(diào)度過程，可以輸入時間片大小，然后采用時間片輪轉(zhuǎn) RR進程調(diào)度算法進行調(diào)度，可以模擬調(diào)度過程，輸出每個時刻的進程運行狀態(tài)，另外也實 現(xiàn)了輸出計算出來的每個進程的周轉(zhuǎn)時間、帶權(quán)周轉(zhuǎn)時間、所有進程的平均周轉(zhuǎn)時間以及帶權(quán)平均周轉(zhuǎn)時間。(4) 測試數(shù)據(jù)，包括正確的輸入及其輸出結(jié)果和含有

3、錯誤的輸入及其輸出結(jié)果。作業(yè)進程名ABCDE平均到達時間01234效勞時間435242完成時間813181017周轉(zhuǎn)時間8121671311.2帶權(quán)周轉(zhuǎn)時間53.194完成時間47181317周轉(zhuǎn)時間461610139.8帶權(quán)周轉(zhuǎn)時間9詳見運行結(jié)果截圖2、概要設(shè)計使用鏈表創(chuàng)立隊列，用鏈表方法實現(xiàn)時間片輪轉(zhuǎn)調(diào)度。主要有主函數(shù)，時間片輪轉(zhuǎn)調(diào)度函數(shù)void RR(int*ArrivalTime,int*ServiceTime,intn,int q,LinkQueue &Q)和輸出函數(shù) void print(intn,int array) , v

4、oid print(int n,double array);三：詳細設(shè)計時間片輪轉(zhuǎn)算法流程圖:開始分配給執(zhí)行隊列 隊首時間片時間片-1時間+1是否所有進程都完成時間片是否用完結(jié)束是否完成新進程是否到達I4 效勞時間-1+I將新到進程插入隊尾程序主要設(shè)計思想：1創(chuàng)立進程，使用鏈表的方法，鏈表中的每個結(jié)點相當于一個進程。2 讀入文件中進程數(shù)據(jù)進程的到達時間和效勞時間。3創(chuàng)立一個進程單鏈表，作為進程隊列。4請用戶輸入時間片大小。5創(chuàng)立執(zhí)行隊列。6定義時間軸，初始化時間軸和執(zhí)行隊列。7當進程數(shù)不為零時，分配給執(zhí)行隊列隊首一個時間片。繼續(xù)有未完成進程時進程隊列的隊首進程是否到達，假設(shè)到達，將其插入到執(zhí)行

5、隊列的隊尾。執(zhí)行隊列不為空時，執(zhí)行隊列的隊首進程的，判斷是否執(zhí)行完。執(zhí)行完，該進程退出執(zhí)行隊列。8執(zhí)行隊列隊首是否得到過一個完整的時間片，假設(shè)有那么該進程插入到執(zhí)行隊列的隊尾。9執(zhí)行隊列不為空時， 轉(zhuǎn)到第7步。當執(zhí)行隊列和進程隊列都為空時，轉(zhuǎn)到第6步。當兩隊列都為空時，所有進程運行完，模擬結(jié)束。四：調(diào)試分析調(diào)試過程中遇到的問題即在時間片輪轉(zhuǎn)算法中由于循環(huán)使用不當導(dǎo)致無法實現(xiàn)預(yù)期的結(jié)果，后通過問同學(xué)，網(wǎng)上查找資料解決。算法改良：可加一個循環(huán)將讀入的進程按到達時 間從先至后排列。經(jīng)驗體會：通過這次實驗，又熟悉了鏈表的使用方法，加深了對進程概念的理解，進一步掌握了進程狀態(tài)的轉(zhuǎn)變、進程調(diào)度的策略及對系

6、統(tǒng)性能的評價方法。五：用戶使用說明1、在同目錄的txt文件中輸入進程到達時間和效勞時間，第一行為進程到達時間，中間用空格隔開，第二行為進程效勞時間，不同進程的效勞時間之間用空格隔開。2、 運行時按指示輸入，如“請輸入時間片長度時輸入時間片大小，假設(shè)退出按0,繼續(xù) 那么繼續(xù)輸入時間片大小。六：測試結(jié)果時間片長度為2時：321S3運運運運-«匹運運運運運運運運運運運運1?3SRR罷WWW在在在在在在在在番o 1長洋定正正正正正正正正正正正正正正正正正1 7 ne嵐耳S1 LJI4 lz 間t 為Bj1 I lrtl JI J rj In I I" I l« ! 1 I

7、rt “IT I nli 1 i 1 I 1 ' JIT 畳時&謹詭謚儲謚灌遊澆啦泄詭謎謎幣:s012礙蕭一 嚀 輸間韻刻覲灘熬5>14<,為 77-1TI可-l-l.Tnr.鑄17詢均 訐時時時SXEI時時時1:1完凰帝¥平22S30 H 1 12 2 0 0 3 3 4 4 I 2 2 4> 4 2 8 王 口zEJiuT口T口王口 T 口TDTQhwTB£ 口I口X口董°工 口SNJ. 253+M卄輸入時閭片大小;時間片長度為4時:大 片VJ* VIA JlTJ- _TJ Tx WJ - TJ TJ M運運運運運運運運運迄運

8、罡逗運運運運一曰 sA在在枉在www在在在在在在左trnti P正正正正正正正正正正正正正正正正正11Lfl畚 rayHH 口±曇口室口王口工口至cllmlH 口圭口玉口王£至口至口王口壬口至口壬8 ill 電 L F #=fl.龍.玉于那-*-遜-劌,1J44MJS- 唔進選逛注進逛選選9 6 > =z F - * 4=監(jiān)畫徑 ± ¥= =*» ferFXT 0 1 2 3 4 5 6 7 8 9 w s MI4SF®心市七：附錄源程序：#in clude<iostream>#in clude<ioma ni

9、p>#in clude<fstream>#in clude<sstream> using n amespace std;typedef int QEIemType;#defi ne OK 1#defi ne ERROR 0#defi ne OVERFLOW -1 typedef int Status;typedef struct QNode定義隊列節(jié)點QElemType data; struct QNode *n ext;QNode,*QueuePtr;typedef struct定義隊列QueuePtr front; QueuePtr rear;Lin kQue

10、ue;初始化隊列刪除隊列/進入隊列離開隊列判讀隊列是否為空Status Ini tQueue(Li nkQueue & Q);Status DestroyQueue(L in kQueue &Q);Status En Queue(L in kQueue & Q,QElemType e); int DeQueue(L in kQueue & Q,QElemType e); bool QueueEmpty(L in kQueue &Q);LinkQueue Q;/創(chuàng)立隊列 Qstatic const int MaxNum=100;int n,q,Arriva

11、lTimeMaxNum,ServiceTimeMaxNum,FinishedTimeMaxNum,WholeTimeMaxNu m;/ 定義進程調(diào)度中的時間變量double WeightWholeTimeMaxNum,Average_WT,Average_WWT;void print(int n,int array);void print(int n,double array);void RR(int*ArrivalTime,int*ServiceTime,int n,int q,LinkQueue &Q);void main()/讀文件，到達時間和完成時間int ia,ib,i,q;

12、ifstream in("test.txt");string s;getline(in, s);istringstream sin(s);for(i=0; sin>>ia;i+)ArrivalTimei=ia;getline(in, s);istringstream sinn(s);for(i=0; sinn>>ib;i+)ServiceTimei=ib;int n=i;/輸出進程數(shù)、到達時間、效勞時間cout<<" 輸入進程數(shù) (n):"<<n<<endl; cout<<"

13、;Arrival time:"print(i,ArrivalTime);cout<<"Service time:" print(i,ServiceTime);/輸入時間片長度cout<<" 請輸入時間片長度 (q):"cin>>q;cout<<" 時間片輪轉(zhuǎn)算法 RR"<<endl;RR(ArrivalTime,ServiceTime,n,q,Q);while(q)/循環(huán)輸入時間片長度 q,直到q=0結(jié)束cout<<endl<<"

14、退出 ->0 or 輸入時間片大小 :" cin>>q;if(q=0)return;RR(ArrivalTime,ServiceTime,n,q,Q);void RR(int*ArrivalTime,int*ServiceTime,int n,int q,LinkQueue &Q)/ 初始化模塊 int countTime=0,e;int STimeMaxNum,pushedMaxNum;for(int i=0;i<n;i+)STimei=ServiceTimei;pushedi=0; InitQueue(Q);EnQueue(Q,0); pushed

15、0=1;int time=0;/ 時間片輪轉(zhuǎn)模塊 while(QueueEmpty(Q)=false)e=DeQueue(Q,e);if(STimee>q) STimee=STimee-q; countTime+=q;else countTime+=STimee; STimee=0; FinishedTimee=countTime;while(time<countTime)if(STime>0)cout<<" 時刻 "<<setw(2)<<time<<": 進程 "<<e<

16、;<" 正在運行 "<<endl; time+;for(i=1;i<n;i+)if(STime!=0&&i!=e&&ArrivalTimei<countTime&&pushedi=0|STime!=0&&i!=e&&A rrivalTimei=countTime)EnQueue(Q,i);pushedi=1;if(STimee>0)EnQueue(Q,e);/ 計算模塊 Average_WT=0,Average_WWT=0;for(i=0;i<n;i+)

17、WholeTimei=FinishedTimei-ArrivalTimei;WeightWholeTimei=(double)(WholeTimei*1.000000/ServiceTimei);Average_WT+=WholeTimei;Average_WWT+=WeightWholeTimei;Average_WT/=n;Average_WWT/=n;/ 輸出模塊 cout<<" 完成 :"print(n,FinishedTime);cout<<" 周轉(zhuǎn) :"print(n,WholeTime);cout<<&q

18、uot; 帶權(quán)周轉(zhuǎn)時間： "print(n,WeightWholeTime);cout<<" 平均周轉(zhuǎn)時間為： "<<Average_WT<<endl;cout<<" 平均帶權(quán)周轉(zhuǎn)時間為 :"<<Average_WWT<<endl;DestroyQueue(Q);Status InitQueue(LinkQueue &Q) Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode); if(!Q.front)exit(OVERFLOW);Q.front->next=NULL;return OK;Status DestroyQueue(LinkQueue &Q) while(Q.front)Q.rear=Q.front->next;free(Q.front);Q.front=Q.rear;return OK;Status EnQueue(LinkQueue &Q,QElem