一、 實驗題目
本次試驗要求編寫的是進(jìn)程調(diào)度中的FCFS算法和RR算法（輪轉(zhuǎn)法）。
FCFS算法：最簡單的CPU調(diào)度算法，采取先到先服務(wù)的規(guī)則，不存在進(jìn)程優(yōu)先級之說，也不管進(jìn)程服務(wù)時間的長短，只有前面的進(jìn)程完成或者阻塞后面的進(jìn)程才會開始處理。這種算法不利于短進(jìn)程，因為短進(jìn)程要等待很久，而CPU繁忙進(jìn)程則比較適合這種調(diào)度算法。
RR算法：這是一種輪詢算法，每次將時間片給隊首的進(jìn)程去使用，如果該進(jìn)程在時間片內(nèi)結(jié)束的話，就切換到下一進(jìn)程；如果時間片用完該進(jìn)程仍未結(jié)束，把處理器給下一進(jìn)程，該進(jìn)程排到就緒隊列隊尾等待下一次被分配處理器；
當(dāng)時間片被分配的特別長的話，RR會變?yōu)榈腇CFS算法，當(dāng)時間片非常短的話，就會成為一種均等分配的算法，適用于IO繁忙型調(diào)度。
我們可以看一下示意圖
題目是：

下面是我畫的各個時間段的各種算法的執(zhí)行情況，今天我們主要講述FCFS和RR兩種，其余兩種類比也可以實現(xiàn)

二、 數(shù)據(jù)結(jié)構(gòu)及符號說明
因為這兩種算法中都有一個優(yōu)先的順序，FCFS中優(yōu)先級是到達(dá)的時刻，RR中優(yōu)先級也是到達(dá)的時間，因此我在算法中用的是優(yōu)先隊列priority_queue<proc,vector,cmp> q;
隊列中元素是一個結(jié)構(gòu)體，容器為vector，優(yōu)先定義方式為自己定義的cmp(見下)
?
struct cmp
{
bool operator()(proc a,proc b)
{
return a.arrive_time>b.arrive_time; //到達(dá)時間小的，優(yōu)先級高
}
};
每次添加結(jié)點的時候都會自動排序?qū)⒌竭_(dá)時間最小的進(jìn)程調(diào)到隊首
三、 源代碼
FCFS：

#include <iostream> #include <iomanip> #include <queue> using namespace std; //進(jìn)程結(jié)構(gòu)體，包含時間長度，進(jìn)程ID，到達(dá)時間，結(jié)束時間和開始時間等幾個屬性 struct proc {int time,arrive_time,end_time,start_time;char name; }; //重新定義優(yōu)先隊列的規(guī)則 struct cmp {bool operator()(proc a,proc b){return a.arrive_time>b.arrive_time; //到達(dá)時間小的，優(yōu)先級高 } }; //進(jìn)程個數(shù) int n; //當(dāng)前時間 int current_time; int main() {priority_queue<proc,vector<proc>,cmp> q;//聲明優(yōu)先隊列對象qcin>>n;proc p;for(int i=0;i<n;i++){ cin>>p.name>>p.arrive_time>>p.time;q.push(p);}current_time=0;cout<<"Process_ID Arrive_Time Start_Time Length End_Time Revolve_Time Right_Time"<<endl; //當(dāng)隊列非空的時候，說明尚有進(jìn)程未處理完畢，進(jìn)入循環(huán) while(!q.empty()){p=q.top(); //取優(yōu)先級最高的進(jìn)程進(jìn)入處理器（即到達(dá)時間最早的進(jìn)程） q.pop();//當(dāng)優(yōu)先級最高的進(jìn)程到達(dá)時間還高于當(dāng)前時間，我們就讓當(dāng)前時間往后加 while(current_time<p.arrive_time){current_time++;}//如果當(dāng)前時間比優(yōu)先級最高的要大，那么就可以進(jìn)行處理 if(current_time>=p.arrive_time){p.start_time=current_time; //設(shè)置p進(jìn)程的開始時間 p.end_time=p.start_time+p.time; //設(shè)置進(jìn)程的結(jié)束時間 current_time=p.end_time; //當(dāng)前時間往后移 }//設(shè)置輸出格式 cout<<setfill(' ')<<setw(5)<<p.name;cout<<setw(11)<<p.arrive_time;cout<<setw(11)<<p.start_time;cout<<setw(10)<<p.time;cout<<setw(8)<<p.end_time;cout<<setw(11)<<p.end_time-p.arrive_time;cout<<setw(14)<<setiosflags(ios::fixed)<<setprecision(2)<<(double)(p.end_time-p.arrive_time)/p.time<<endl;}return 0; }

RR：

#include <iostream> #include <iomanip> #include <queue> using namespace std; int n; int time_slice; //時間片 int current_time; //當(dāng)前時間 struct proc{int arr_time; //第一次入隊的時間 int arrive_time; //每一次的到達(dá)時間 int time; //剩余需要的時間 int start_time; //開始的時間 int end_time; //結(jié)束的時間 int haoshi; //總共需要的時間 char a; //進(jìn)程ID }; //重新定義隊列的優(yōu)先級 struct cmp{bool operator()(proc a,proc b){return a.arrive_time>=b.arrive_time;} }; int main() {priority_queue<proc,vector<proc>,cmp> q;cin>>n>>time_slice; //輸入時間片 current_time=0; //初始化當(dāng)前時間片 proc p;for(int i=0;i<n;i++){cin>>p.a>>p.arrive_time>>p.time;p.start_time=-1;p.end_time=-2;p.arr_time=p.arrive_time;p.haoshi=p.time;q.push(p);}cout<<"Process_ID Arrive_Time Start_Time Length End_Time Revolve_Time Right_Time"<<endl; while(!q.empty()) //只要隊列不為空，就說明還有進(jìn)程未處理完畢{p=q.top(); //獲取隊首元素q.pop(); //將隊首元素出隊列//若是當(dāng)前時間比隊首進(jìn)程的到達(dá)時間還小，那么我們就讓當(dāng)前時間自增while(current_time<p.arrive_time) {current_time++;}//如果start_time為-1，說明這個變量沒被賦值，我們就給他賦值，標(biāo)志該進(jìn)程開始處理了if(p.start_time==-1) p.start_time=current_time;if(time_slice>=p.time) //如果當(dāng)前時間片大于進(jìn)程p所需要的時間p.time，那么我們可以在本次時間片之內(nèi)結(jié)束該進(jìn)程 {current_time+=p.time; //當(dāng)前時間往后加 p.end_time=current_time; //結(jié)束時間改變 cout<<setw(5)<<setfill(' ')<<p.a; //輸出相關(guān)信息 cout<<setw(11)<<p.arr_time;cout<<setw(11)<<p.start_time;cout<<setw(11)<<p.haoshi;cout<<setw(11)<<p.end_time;cout<<setw(11)<<p.end_time-p.arr_time;cout<<setw(15)<<setiosflags(ios::fixed)<<setprecision(2)<<(double)(p.end_time-p.arr_time)/p.haoshi<<endl;}else if(time_slice<p.time) //如果p進(jìn)程所需時間大于時間片，那么我們本次尚不能完全結(jié)束p進(jìn)程，而把他重新放到就緒隊列中 {current_time+=time_slice; //當(dāng)前時間加上時間片的值 p.arrive_time=current_time; //p的到達(dá)時間(即此次到達(dá)就緒隊列的時間)改為當(dāng)前時間 p.time-=time_slice; //p進(jìn)程所需時間減去當(dāng)前時間片的大小變?yōu)樾碌乃钑r間 q.push(p); //重新把修改過相關(guān)參數(shù)的p進(jìn)程壓入隊列中 }}return 0; }

四、 運行結(jié)果
輸入次序依次為進(jìn)程ID，到達(dá)時間和耗費時間
FCFS

RR

五、 實驗思考
本次我們用模擬調(diào)度的辦法展現(xiàn)了CPU進(jìn)程調(diào)度的過程，計算了相對周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間，但是這并不能代表真正的CPU調(diào)度，因為在實際過程中，這個時間是非常快速的，而且我們要考慮阻塞的情況，應(yīng)該有一個阻塞隊列；并且還應(yīng)該有接收外部信號（比如IO或者時間）喚醒進(jìn)程的過程。實際的進(jìn)程調(diào)度中還包含搶占式的調(diào)度，即后來的進(jìn)程會根據(jù)優(yōu)先級強弱決定是否直接打斷當(dāng)前進(jìn)程。進(jìn)程調(diào)度算法使我進(jìn)一步對進(jìn)程調(diào)度有了深刻的思考。
思考題：FCFS算法是非搶占式的算法，易于實現(xiàn)，有利于CPU繁忙型作業(yè)不利于I/O繁忙型作業(yè)；RR算法如果是非搶占式的話，其優(yōu)劣程度取決于時間片的大小，如果時間片過大，那么所有進(jìn)程基本能在一個時間片內(nèi)完成則退化成了FCFS算法，如果時間片過小，需要頻繁的進(jìn)行上下文切換，會產(chǎn)生額外的開銷。RR算法比較適合分時系統(tǒng)。其他的：短進(jìn)程優(yōu)先算法總是讓時間耗費短的進(jìn)程優(yōu)先處理，這樣子周轉(zhuǎn)時間少，但是可能會導(dǎo)致饑餓；優(yōu)先級調(diào)度也會導(dǎo)致饑餓的情況發(fā)生。動態(tài)優(yōu)先級調(diào)度算法的優(yōu)先級會根據(jù)等待時間的延長而增加，這樣子兼顧了進(jìn)程的優(yōu)先級又不會出現(xiàn)饑餓的情況。
-----------------------------------今天也要加油鴨--------------------------------------

總結(jié)

以上是生活随笔為你收集整理的进程调度算法FCFS和RR的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。