RR算法總體思路流程圖

主要數據結構及參數

typedef struct PCB {char name;//進程名int arrive_time;//到達時間float cpu_burst;//服務時間float surplus;//剩余服務時間int start_time;//開始執行時間int finish_time;//完成時間int wait_time;//等待時間float turn_time;//周轉時間float weighted_ttime;//帶權周轉時間bool over;//標記進程是否執行完畢float response;//響應比 }PCB;//定義進程數據結構int pcb_num;//進程個數int time_p;//時間片大小

主要函數

//將進程按照到達先后順序排序 void sort_arrival(PCB pcb[],int pcb_num){}//計算周轉時間和帶權周轉時間 void calculator_rr(PCB pcb[],int pcb_num){}//RR調度算法 void rr(PCB pcb[],int pcb_num,float time_p){}//計算平均周轉時間、平均帶權周轉時間、平均等待時間 void cal_avg(PCB pcb[],int pcb_num){}//輸出各進程 void show(PCB pcb[],int pcb_num){}//主函數測試RR調度算法 int main(){}

①sort_arrival()函數：輸入進程順序表pcb[]和進程個數pcb_num作為函數參數，然后將順序表pcb[]按照到達的先后順序排序。

②calculator_rr()函數：輸入進程順序表pcb[]和進程個數pcb_num作為函數參數，用于在rr()函數中反復調用，根據順序表pcb[]中已知的到達時間、完成時間、服務時間，計算周轉時間和帶權周轉時間

③rr()函數：輸入進程順序表pcb[]和進程個數pcb_num作為函數參數，主要是實現RR調度算法，將經RR調度算法計算后的開始執行時間、完成時間、等待時間、周轉時間、帶權周轉時間存入進程順序表中。

④cal_avg()函數：輸入進程順序表pcb[]和進程個數pcb_num作為函數參數，通過進程順序表中的等待時間、周轉時間、帶權周轉時間計算出平均等待時間、平均周轉時間、平均帶權周轉時間，然后輸出。

⑤show()函數：輸入進程順序表pcb[]和進程個數pcb_num作為函數參數，以表格的形式輸出進程順序表中的各參數信息。

⑥main()函數：主函數中輸入進程順序表，測試FCFS調度函數和SJF調度函數，輸出測試結果。

代碼

#include<iostream> #include<iomanip> #include<queue> #include<algorithm>using namespace std;typedef struct PCB {char name;//進程名int arrive_time;//到達時間float cpu_burst;//服務時間float surplus;//剩余服務時間int start_time;//開始執行時間int finish_time;//完成時間int wait_time;//等待時間float turn_time;//周轉時間float weighted_ttime;//帶權周轉時間bool over;//標記進程是否執行 }PCB;//定義進程數據結構//將進程按照到達先后順序排序 void sort_arrival(PCB pcb[],int pcb_num) {PCB temp;for(int i=0;i<pcb_num-1;i++){for(int j=i+1;j<pcb_num;j++){if(pcb[i].arrive_time>pcb[j].arrive_time){temp = pcb[i];pcb[i] = pcb[j];pcb[j] = temp;}}} }//計算周轉時間和帶權周轉時間 void calculator_rr(PCB pcb[],int pcb_num) {for(int i=0;i<pcb_num;i++){pcb[i].turn_time = pcb[i].finish_time-pcb[i].arrive_time;//周轉時間 = 完成時間-到達時間pcb[i].weighted_ttime = pcb[i].turn_time/pcb[i].cpu_burst;//帶權周轉時間 = 周轉時間/服務時間} }//RR調度算法 void rr(PCB pcb[],int pcb_num,float time_p) {for(int i=0;i<pcb_num;i++){pcb[i].surplus = pcb[i].cpu_burst;pcb[i].finish_time = 0;pcb[i].start_time = 0;pcb[i].turn_time = 0;pcb[i].wait_time = 0;pcb[i].weighted_ttime = 0;}//初始化進程信息queue<int> wait_q;//定義進程等待隊列sort_arrival(pcb,pcb_num);//將所有進程按照到達的先后順序排列int t = pcb[0].arrive_time;//時間從第一個進程到達開始wait_q.push(0);//將第一個進程加入等待隊列while(wait_q.empty() == false){int t0 =t;//記錄需要進行進程切換的時刻int run;run = wait_q.front();wait_q.pop();if(pcb[run].over == false)//進程第一次執行時{pcb[run].start_time = t;//記錄第一次開始執行的時間pcb[run].wait_time = pcb[run].wait_time+t-pcb[run].arrive_time;//累加計算等待時間pcb[run].over = true;}else//進程非第一次執行時{pcb[run].wait_time = pcb[run].wait_time+t-pcb[run].finish_time;//累加計算等待時間}t = t+min(pcb[run].surplus,time_p);//將時間切換到下個時間片，或進程執行完畢pcb[run].finish_time = t;//更新每次進程執行結束的時間pcb[run].surplus = pcb[run].surplus-min(pcb[run].surplus,time_p);//更新進程剩余服務時間if(t0<pcb[pcb_num-1].arrive_time){for(int i=0;i<pcb_num;i++){if(pcb[i].arrive_time>t0 && pcb[i].arrive_time<=t){wait_q.push(i);}}//將所有在t0-t時間內到達的進程按照到達的先后順序加入等待隊列}if(pcb[run].surplus != 0){wait_q.push(run);//若進程執行完畢則不再加入等待隊列}}calculator_rr(pcb,pcb_num);//計算進程周轉時間、帶權周轉時間 }//計算平均周轉時間、平均帶權周轉時間、平均等待時間 void cal_avg(PCB pcb[],int pcb_num) {float sum1 = 0,sum2 = 0, sum3 = 0;float avg_turn, avg_weight, avg_wait;for(int i=0;i<pcb_num;i++){sum1 = sum1+pcb[i].turn_time;sum2 = sum2+pcb[i].weighted_ttime;sum3 = sum3+pcb[i].wait_time;}avg_turn = sum1/pcb_num;avg_weight = sum2/pcb_num;avg_wait = sum3/pcb_num;cout<<"平均周轉時間為："<<avg_turn<<endl;cout<<"平均帶權周轉時間為："<<avg_weight<<endl;cout<<"平均等待時間為："<<avg_wait<<endl; }//輸出各進程 void show(PCB pcb[],int pcb_num) {cout<<"-----------------------------------------------------------------------------"<<endl;cout<<"進程名|到達時間|服務時間|開始執行時間|完成時間|周轉時間|帶權周轉時間|等待時間"<<endl;cout<<"-----------------------------------------------------------------------------"<<endl;for(int i=0;i<pcb_num;i++){cout<<pcb[i].name;cout<<"\t"<<pcb[i].arrive_time;cout<<"\t"<<pcb[i].cpu_burst;cout<<"\t"<<"\t"<<pcb[i].start_time;cout<<"\t"<<pcb[i].finish_time;cout<<"\t"<<pcb[i].turn_time;cout<<"\t"<<setprecision(3)<<pcb[i].weighted_ttime;cout<<"\t"<<pcb[i].wait_time<<endl;} }//主函數測試RR調度算法 int main() {int pcb_num;//進程個數cout<<"請輸入進程總個數："<<endl;cin>>pcb_num;PCB pcb[pcb_num];for(int i=0;i<pcb_num;i++){cout<<"請輸入進程名：";cin>>pcb[i].name;//輸入各進程名cout<<"請輸入進程到達時間：";cin>>pcb[i].arrive_time; //輸入各進程的到達時間cout<<"請輸入進程需要服務的時間：";cin>>pcb[i].cpu_burst; //輸入各進程需要服務的時間pcb[i].over = false;//初始時，所有進程執行狀態都為falsepcb[i].surplus = pcb[i].cpu_burst;//初始時，所有進程剩余服務時間都為服務時間pcb[i].finish_time = 0;pcb[i].start_time = 0;pcb[i].turn_time = 0;pcb[i].wait_time = 0;pcb[i].weighted_ttime = 0;}cout<<"--------------------------------"<<endl;cout<<" RR調度結果 "<<endl;cout<<"--------------------------------"<<endl;int time_p;//時間片大小bool goon = true;while(goon == true){cout<<"請輸入時間片大小：";cin>>time_p;rr(pcb,pcb_num,time_p);show(pcb,pcb_num);cout<<endl;cal_avg(pcb,pcb_num);cout<<"是否繼續測試RR調度結果（是則輸入1，否則輸入0）:";cin>>goon;}return 0; }

結果

結果分析

時間片輪轉RR調度算法很大程度上取決于時間片大小的選取，時間片的大小直接決定了時間片輪轉RR調度算法的效率，時間片選取過小，會頻繁發生終端，需要不斷進行上下文的切換，嚴重增加了系統的開銷；時間片選取過大則時間片輪轉RR調度算法直接退化為先來先服務FCFS調度算法。從表格可以看出，時間片輪轉RR調度算法的各參數值都較高，效率較其他算法不算高，而且明顯時間片輪轉RR調度算法對時間片的選取要求較高，需要實現知道各進程的參數情況才能夠選取合適的時間片大小。

總結

以上是生活随笔為你收集整理的操作系统——时间片轮转调度算法（RR）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。