試驗(yàn)二時(shí)間片輪轉(zhuǎn)RR進(jìn)程調(diào)度算法

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

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

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

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

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

6、的txt文件中輸入進(jìn)程到達(dá)時(shí)間和服務(wù)時(shí)間，第一行為進(jìn)程到達(dá)時(shí)間，中間 用空格隔開，第二行為進(jìn)程服務(wù)時(shí)間，不同進(jìn)程的服務(wù)時(shí)間之間用空格隔開。2、 運(yùn)行時(shí)按指示輸入，如“請輸入時(shí)間片長度”時(shí)輸入時(shí)間片大小，若退出按0,繼續(xù) 則繼續(xù)輸入時(shí)間片大小。六：測試結(jié)果時(shí)間片長度為2時(shí)：時(shí)間片長度為4時(shí)：七：附錄源程序：#in clude<iostream>#in clude<ioma nip>#in clude<fstream>#in clude<sstream>using n amespace std;typedef int QEIemType;#defin

7、e OK 1#define ERROR 0#define OVERFLOW -1typedef int Status;typedef struct QNode定義隊(duì)列節(jié)點(diǎn)QElemType data;struct QNode *n ext;QNode,*QueuePtr;typedef struct定義隊(duì)列QueuePtr front;QueuePtr rear;Lin kQueue;Status Ini tQueue(Li nkQueue & Q);/ 初始化隊(duì)列Status DestroyQueue(L in kQueue & Q);/ 刪除隊(duì)列Status En Queu

8、e(L in kQueue & Q,QEIemType e);進(jìn)入隊(duì)列int DeQueue(Li nkQueue & Q,QElemType e);/離開隊(duì)列bool QueueEmpty(L in kQueue & Q);判讀隊(duì)列是否為空LinkQueue Q;創(chuàng)建隊(duì)列 Qstatic con st int MaxNum=100;intn ,q,ArrivalTimeMaxNum,ServiceTimeMaxNum,Fi ni shedTimeMaxNum,WholeTimeMaxNu m;/定義進(jìn)程調(diào)度中的時(shí)間變量double WeightWholeTimeMax

9、Num,Average_WT,Average_WWT;void prin t(i nt n ,i nt array);void prin t(i nt n, double array);void RR(i nt*ArrivalTime,i nt*ServiceTime,i nt n ,i nt q,L in kQueue & Q);void mai n()讀文件，到達(dá)時(shí)間和完成時(shí)間int ia,ib,i,q;ifstream in ("test.txt");stri ng s;getl in e(i n, s);istri ngstream si n(s);for(

10、i=0; sin> >ia;i+)ArrivalTimei=ia;getl in e(i n, s);istri ngstream sinn( s);for(i=0; sinn> >ib;i+)ServiceTimei=ib;int n=i;輸出進(jìn)程數(shù)、至U達(dá)時(shí)間、服務(wù)時(shí)間cout<<"輸入進(jìn)程數(shù)(n):"<<n<<endl;cout<<"Arrival time:"prin t(i,ArrivalTime);cout<<"Service time:"

11、prin t(i,ServiceTime);輸入時(shí)間片長度cout<<"請輸入時(shí)間片長度(q):"cin»q;cout<<"時(shí)間片輪轉(zhuǎn)算法 RR"<<endl;RR(ArrivalTime,ServiceTime, n, q,Q);while(q)/循環(huán)輸入時(shí)間片長度q,直到q=0結(jié)束cout<<endl<<"退出->0 or輸入時(shí)間片大?。?quot;；cin»q;if(q=0)return;RR(ArrivalTime,ServiceTime ,n ,q,

12、Q);void RR(i nt*ArrivalTime,i nt*ServiceTime,i nt n,i nt q,Lin kQueue &Q)/ 初始化模塊 int coun tTime=0,e;int STimeMaxNum,pushedMaxNum;for(i nt i=0;i< n; i+)STimei=ServiceTimei;pushedi=0;Ini tQueue(Q);En Queue(Q,0);pushed0=1;int time=0;/時(shí)間片輪轉(zhuǎn)模塊while(QueueEmpty(Q)=false)e=DeQueue(Q,e);if(STimee>q

13、)STimee=STimee-q;coun tTime+=q;elsecou ntTime+=STimee;STimee=0;Fin ishedTimee=cou ntTime;while(time<co un tTime)if(STime>0)cout<<"時(shí)刻"<<setw(2)<<time<<":進(jìn)程"<<e<<"正在運(yùn)行"<<endl; time+;for(i=1;i< n;i+)if(STime!=0&&i!

14、=e&&ArrivalTimei<cou ntTime&&pushedi=O|STime!=O&&i !=e&&A rrivalTimei=co un tTime)En Queue(Q,i);pushedi=1;if(STimee>0)En Queue(Q,e);/計(jì)算模塊Average_WT=O,Average_WWT=O;for(i=0;i <n ;i+)WholeTimei=Fi nishedTimei-ArrivalTimei;WeightWholeTimei=(double)(WholeTimei*1.

15、000000/ServiceTimei);Average_WT+=WholeTimei; Average_WWT+=WeightWholeTimei;Average_WT/ =n;Average_WWT/= n;/輸出模塊cout<<"完成:"；print(n,Fini shedTime);cout<<"周轉(zhuǎn):"prin t( n, WholeTime);cout<<"帶權(quán)周轉(zhuǎn)時(shí)間："prin t( n, WeightWholeTime);cout<<"平均周轉(zhuǎn)時(shí)間為：&quo

16、t;<<Average_WT<<e ndl;cout<<"平均帶權(quán)周轉(zhuǎn)時(shí)間為:"<<Average_WWT<<e ndl;DestroyQueue(Q);Status Ini tQueue(Li nkQueue & Q)Q.fro nt=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.fro nt)exit(OVERFLOW);Q.fron t-> next=NULL;return OK;Status DestroyQueue(L in kQueue &

17、Q)while(Q.fro nt)Q.rear=Q.fro nt-> next;free(Q.fro nt);Q.fr on t=Q.rear;return OK;Status En Queue(L in kQueue & Q,QElemType e)QueuePtr p=(QueuePtr)malloc(sizeof(QNode);if(!p) exit(OVERFLOW); p->data=e;p->n ext=NULL; Q.rear- >n ext=p;Q.rear=p;return OK;int DeQueue(L in kQueue & Q,QEIemType e)QueuePtr p;if(Q.fr on t=Q.rear)return ERROR;p=Q.fr ont->n ext;e=p->data;Q.front->n ext=p->n ext;if(Q.rear=p)Q.rear=Q.fro nt;free(p);return e;bool QueueEmpty(L in kQueue &