一、 實驗題目
本次試驗要求編寫的是程序排程中的FCFS算法和RR算法（輪轉法）。
FCFS算法：最簡單的CPU排程算法，采取先到先服務的規則，不存在程序優先級之說，也不管程序服務時間的長短，隻有前面的程序完成或者阻塞後面的程序才會開始處理。這種算法不利于短程序，因為短程序要等待很久，而CPU繁忙程序則比較适合這種排程算法。
RR算法：這是一種輪詢算法，每次将時間片給隊首的程序去使用，如果該程序在時間片内結束的話，就切換到下一程序；如果時間片用完該程序仍未結束，把處理器給下一程序，該程序排到就緒隊列隊尾等待下一次被配置設定處理器；
當時間片被配置設定的特别長的話，RR會變為的FCFS算法，當時間片非常短的話，就會成為一種均等配置設定的算法，适用于IO繁忙型排程。
我們可以看一下示意圖
題目是：
下面是我畫的各個時間段的各種算法的執行情況，今天我們主要講述FCFS和RR兩種，其餘兩種類比也可以實作
二、 資料結構及符号說明
因為這兩種算法中都有一個優先的順序，FCFS中優先級是到達的時刻，RR中優先級也是到達的時間，是以我在算法中用的是優先隊列priority_queue<proc,vector,cmp> q;
隊列中元素是一個結構體，容器為vector，優先定義方式為自己定義的cmp(見下)
struct cmp
{
bool operator()(proc a,proc b)
{
return a.arrive_time>b.arrive_time; //到達時間小的，優先級高
}
};
每次添加結點的時候都會自動排序将到達時間最小的程序調到隊首
三、 源代碼
FCFS：
#include <iostream>
#include <iomanip>
#include <queue>
using namespace std;
//程序結構體，包含時間長度，程序ID，到達時間，結束時間和開始時間等幾個屬性
struct proc
{
int time,arrive_time,end_time,start_time;
char name;
};
//重新定義優先隊列的規則
struct cmp
{
bool operator()(proc a,proc b)
{
return a.arrive_time>b.arrive_time; //到達時間小的，優先級高
}
};
//程序個數
int n;
//目前時間
int current_time;
int main()
{
priority_queue<proc,vector<proc>,cmp> q;//聲明優先隊列對象q
cin>>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;
//當隊列非空的時候，說明尚有程序未處理完畢，進入循環
while(!q.empty())
{
p=q.top(); //取優先級最高的程序進入處理器（即到達時間最早的程序）
q.pop();
//當優先級最高的程序到達時間還高于目前時間，我們就讓目前時間往後加
while(current_time<p.arrive_time)
{
current_time++;
}
//如果目前時間比優先級最高的要大，那麼就可以進行處理
if(current_time>=p.arrive_time)
{
p.start_time=current_time; //設定p程序的開始時間
p.end_time=p.start_time+p.time; //設定程序的結束時間
current_time=p.end_time; //目前時間往後移
}
//設定輸出格式
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; //目前時間
struct proc{
int arr_time; //第一次入隊的時間
int arrive_time; //每一次的到達時間
int time; //剩餘需要的時間
int start_time; //開始的時間
int end_time; //結束的時間
int haoshi; //總共需要的時間
char a; //程序ID
};
//重新定義隊列的優先級
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; //初始化目前時間片
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()) //隻要隊列不為空，就說明還有程序未處理完畢
{
p=q.top(); //擷取隊首元素
q.pop(); //将隊首元素出隊列
//若是目前時間比隊首程序的到達時間還小，那麼我們就讓目前時間自增
while(current_time<p.arrive_time)
{
current_time++;
}
//如果start_time為-1，說明這個變量沒被指派，我們就給他指派，标志該程序開始處理了
if(p.start_time==-1)
p.start_time=current_time;
if(time_slice>=p.time) //如果目前時間片大于程序p所需要的時間p.time，那麼我們可以在本次時間片之内結束該程序
{
current_time+=p.time; //目前時間往後加
p.end_time=current_time; //結束時間改變
cout<<setw(5)<<setfill(' ')<<p.a; //輸出相關資訊
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程序所需時間大于時間片，那麼我們本次尚不能完全結束p程序，而把他重新放到就緒隊列中
{
current_time+=time_slice; //目前時間加上時間片的值
p.arrive_time=current_time; //p的到達時間(即此次到達就緒隊列的時間)改為目前時間
p.time-=time_slice; //p程序所需時間減去目前時間片的大小變為新的所需時間
q.push(p); //重新把修改過相關參數的p程序壓入隊列中
}
}
return 0;
}
四、 運作結果
輸入次序依次為程序ID，到達時間和耗費時間
FCFS
RR
五、 實驗思考
本次我們用模拟排程的辦法展現了CPU程序排程的過程，計算了相對周轉時間和帶權周轉時間，但是這并不能代表真正的CPU排程，因為在實際過程中，這個時間是非常快速的，而且我們要考慮阻塞的情況，應該有一個阻塞隊列；并且還應該有接收外部信号（比如IO或者時間）喚醒程序的過程。實際的程序排程中還包含搶占式的排程，即後來的程序會根據優先級強弱決定是否直接打斷目前程序。程序排程算法使我進一步對程序排程有了深刻的思考。
思考題：FCFS算法是非搶占式的算法，易于實作，有利于CPU繁忙型作業不利于I/O繁忙型作業；RR算法如果是非搶占式的話，其優劣程度取決于時間片的大小，如果時間片過大，那麼所有程序基本能在一個時間片内完成則退化成了FCFS算法，如果時間片過小，需要頻繁的進行上下文切換，會産生額外的開銷。RR算法比較适合分時系統。其他的：短程序優先算法總是讓時間耗費短的程序優先處理，這樣子周轉時間少，但是可能會導緻饑餓；優先級排程也會導緻饑餓的情況發生。動态優先級排程算法的優先級會根據等待時間的延長而增加，這樣子兼顧了程序的優先級又不會出現饑餓的情況。
-----------------------------------今天也要加油鴨--------------------------------------