考RR演算法

① LTE上行調度演算法(RR,MAXCI,PF)，要求c++，作個參考，簡單明了即可，[email protected]

演算法導論

② 進程調度演算法

FCFS調度演算法屬於不可剝奪演算法。從表面上看，它對所有作業都是公平的，但若一個長作業先到達系統，就會使後面許多短作業等待很長時間，因此它不能作為分時系統和實時系統的主要調度策略。但它常被結合在其他調度策略中使用。例如，在使用優先順序作為調度策略的系統中，往往對多個具有相同優先順序的進程按FCFS原則處理。

FCFS調度演算法的特點是演算法簡單，但效率低； 對長作業比較有利，但對短作業不利（相對SJF和高響應比）；

FCFS調度演算法有利於CPU繁忙型作業，而不利於I/O繁忙型作業。

​ 短作業優先調度演算法是一個非搶占策略，他的原則是下一次選擇預計處理時間最短的進程，因此短進程將會越過長作業，跳至隊列頭。該演算法即可用於作業調度，也可用於進程調度。 但是他對長作業不利，不能保證緊迫性作業（進程）被及時處理，作業的長短只是被估算出來的。

缺點：

該演算法對長作業不利，SJF調度演算法中長作業的周轉時間會增加。更嚴重的是，如果有一長作業進入系統的後備隊列，由於調度程序總是優先調度那些 (即使是後進來的）短作業，將導致長作業長期不被調度（「飢餓」現象，注意區分「死鎖」。後者是系統環形等待，前者是調度策略問題）。

該演算法完全未考慮作業的緊迫程度，因而不能保證緊迫性作業會被及時處理。

由於作業的長短只是根據用戶所提供的估計執行時間而定的，而用戶又可能會有意或無意地縮短其作業的估計運行時間，致使該演算法不一定能真正做到短作業優先調度。

SJF調度演算法的平均等待時間、平均周轉時間最少。

高響應比優先調度演算法既考慮作業的執行時間也考慮作業的等待時間，綜合了先來先服務和最短作業優先兩種演算法的特點。

該演算法中的響應比是指作業等待時間與運行比值，響應比公式定義如下：

響應比 =（等待時間+要求服務時間）/ 要求服務時間,即RR=（w+s）/s=1+w/s，因此 響應比一定是大於等於1的。

短作業與先後次序的兼顧，且不會使長作業長期得不到服務。

響應比計算系統開銷，增加系統開銷。

高響應比優先調度演算法適合批處理系統，主要用於作業調度。

為了實現 RR 調度，我們將就緒隊列視為進程的 FIFO 隊列。新進程添加到就緒隊列的尾部。CPU 調度程序從就緒隊列中選擇第一個進程，將定時器設置在一個時間片後中斷，最後分派這個進程。

接下來，有兩種情況可能發生。進程可能只需少於時間片的 CPU 執行。對於這種情況，進程本身會自動釋放 CPU。調度程序接著處理就緒隊列的下一個進程。否則，如果當前運行進程的 CPU 執行大於一個時間片，那麼定時器會中斷，進而中斷操作系統。然後，進行上下文切換，再將進程加到就緒隊列的尾部，接著 CPU 調度程序會選擇就緒隊列內的下一個進程。

採用 RR 策略的平均等待時間通常較長。

在 RR 調度演算法中，沒有進程被連續分配超過一個時間片的 CPU（除非它是唯一可運行的進程）。如果進程的 CPU 執行超過一個時間片，那麼該進程會被搶占，並被放回到就緒隊列。因此， RR調度演算法是搶占的。

演算法描述

1、進程在進入待調度的隊列等待時，首先進入優先順序最高的Q1等待。

2、首先調度優先順序高的隊列中的進程。若高優先順序中隊列中已沒有調度的進程，則調度次優先順序隊列中的進程。例如：Q1,Q2,Q3三個隊列，當且僅當在Q1中沒有進程等待時才去調度Q2，同理，只有Q1,Q2都為空時才會去調度Q3。

3、對於同一個隊列中的各個進程，按照FCFS分配時間片調度。比如Q1隊列的時間片為N，那麼Q1中的作業在經歷了N個時間片後若還沒有完成，則進入Q2隊列等待，若Q2的時間片用完後作業還不能完成，一直進入下一級隊列，直至完成。

4、在最後一個隊列QN中的各個進程，按照時間片輪轉分配時間片調度。

5、在低優先順序的隊列中的進程在運行時，又有新到達的作業，此時須立即把正在運行的進程放回當前隊列的隊尾，然後把處理機分給高優先順序進程。換而言之，任何時刻，只有當第1~i-1隊列全部為空時，才會去執行第i隊列的進程（搶占式）。特別說明，當再度運行到當前隊列的該進程時，僅分配上次還未完成的時間片，不再分配該隊列對應的完整時間片。

③ linux 進程調度

Linux的調度策略區分實時進程和普通進程，實時進程的調度策略是SCHED_FIFO和SCHED_RR，普通的，非實時進程的調度策略是SCHED_NORMAL（SCHED_OTHER）。

實時調度策略被實時調度器管理，普通調度策略被完全公平調度器來管理。實時進程的優先順序要高於普通進程（nice越小優先順序越高）。

SCHED_FIFO實現了一種簡單的先入先出的調度演算法，它不使用時間片，但支持搶占，只有優先順序更高的SCHED_FIFO或者SCHED_RR進程才能搶占它，否則它會一直執行下去，低優先順序的進程不能搶占它，直到它受阻塞或自己主動釋放處理器。

SCHED_RR是帶有時間片的一種實時輪流調度演算法，當SCHED_RR進程耗盡它的時間片時，同一優先順序的其它實時進程被輪流調度，時間片只用來重新調用同一優先順序的進程，低優先順序的進程決不能搶佔SCHED_RR任務，即使它的時間片耗盡。SCHED_RR是帶時間片的SCHED_FIFO。

Linux的實時調度演算法提供了一種軟實時工作方式，軟實時的含義是盡力調度進程，盡力使進程在它的限定時間到來前運行，但內核不保證總能滿足這些進程的要求，相反，硬實時系統保證在一定的條件下，可以滿足任何調度的要求。

SCHED_NORMAL使用完全公平調度演算法（CFS），之前的演算法直接將nice值對應時間片的長度，而在CFS中，nice值只作為進程獲取處理器運行比的權重，每個進程都有一個權重，nice優先順序越高，權重越大，表示應該運行更長的時間。Linux的實現中，每個進程都有一個vruntime欄位，vruntime是經過量化的進程運行時間，也就是實際運行時間除以權重，所以每個量化後的vruntime應該相等，這就體現了公平性。

CFS當然也支持搶占，但與實時調度演算法不同，實時調度演算法是根據優先順序進行搶占，CFS是根據vruntime進行搶占，vruntime小就擁有優先被運行的權利。

為了計算時間片，CFS演算法需要為完美多任務中的無限小調度周期設定近似值，這個近似值也稱作目標延遲，指每個可運行進程在目標延遲內都會調度一次，如果進程數量太多，則時間粒度太小，所以約定時間片的默認最小粒度是1ms。

進程可以分為I/O消耗型和處理器消耗型，這兩種進程的調度策略應該不同，I/O消耗型應該更加實時，給對端的感覺是響應很快，同時它一般又不會消耗太多的處理器，因而I/O消耗型需要調度頻繁。相對來說，處理器消耗型不需要特別實時，應該盡量降低它的調度頻度，延長其運行時間。

參考： linux內核分析——CFS（完全公平調度演算法） - 一路向北你好 - 博客園

④ 高響應比優先調度演算法的原理

高響應比優先調度演算法既考慮作業的執行時間也考慮作業的等待時間，綜合了先來先服務和最短作業優先兩種演算法的特點。
該演算法中的響應比是指作業等待時間與運行比值，響應比公式定義如下：
響應比 =（等待時間+要求服務時間）/ 要求服務時間,即RR=（w+s）/s=1+w/s，因此響應比一定是大於1的。
如實例：
某系統有3個作業，系統確定它們在全部到達後，再開始採用響應比高者優先的調度演算法，則它們的調度順序是什麼？各自的周轉時間是什麼？
作業號 提交時間 運行時間
1 8.8 1.5
2 9.0 0.4
3 9.5 1.0
(1)如果都到達再算的話,等待時間=最後一個的提交時間-該作業到達的時刻
1: 9.5-8.8=0.7
2: 9.5-9=0.5
3: 0
所以響應比為（等待時間+要求服務時間）要求服務時間=等待時間/要求服務時間+1
1: 0.7/1.5+1=1.47
2: 0.5/0.4+1=2.25
3: 1
所以2先運行,2從9.5開始運行到9.9結束;
再以9.9時刻算響應比:
1: (9.9-8.8)/1.5+1=1.73
3: (9.9-9.5)/1+1=1.4
所以2執行完後1開始執行,從9.9執行到11.4結束
最後一個是3:從11.4開始執行到12.4結束
(2)如果不是都到達後才運行，那麼在8.8時只有作業1到達，所以先運行作業1
8.8+1.5（運行時間）=10.3
到10.3的時候作業1完成，此時作業2和3都已到達所以計算其響應比
（等待時間+要求服務時間）要求服務時間=等待時間/要求服務時間+1
作業2：（10.3-9.0）/0.4+1=4.325
作業3：（10.3-9.5）/1.0+1=1.8
所以先運行作業2
10.3+0.4=10.7
到10.7運行作業3
10.7+1.0=11.7
到11.7結束

⑤ 考慮一種RR(時間片輪轉)調度演算法的變種,演算法中就緒隊列中存放的是指向各個進程式控制

#include 「stdio.h」
#define running 1 // 用running表示進程處於運行態
#define aready 2 // 用aready表示進程處於就緒態
#define blocking 3 // 用blocking表示進程處於阻塞態
#define sometime 5 // 用sometime表示時間片大小
#define n 10 //假定系統允許進程個數為n
struct
{
int name; //進程標識符
int status; //進程狀態
int ax,bx,cx,dx ; //進程現場信息，通用寄存器內容
int pc ; //進程現場信息，程序計數器內容
int psw; //進程現場信息，程序狀態字內容
int next; //下一個進程式控制制塊的位置
}pcbarea[n]; //模擬進程式控制制塊區域的數組
int PSW, AX,BX,CX,DX , PC ,TIME ; //模擬寄存器
int run; //定義指向正在運行進程的進程式控制制塊的指針
struct
{
int head;
int tail;
}ready; //定義就緒隊列的頭指針head和尾指針tail
int pfree; //定義指向空閑進程式控制制塊隊列的指針

scheling( ) //進程調度函數
{
int i;
if (ready.head==-1) //空閑進程式控制制塊隊列為空，退出
{
printf(「無就緒進程\n」);
return;
}
i=ready.head; //就緒隊列頭指針賦給i
ready.head=pcbarea[ready.head].next; //就緒隊列頭指針後移
if(ready.head==-1) ready.tail=-1; //就緒隊列為空，修正尾指針ready.tail
pcbarea[i].status=running; //修改進程式控制制塊狀態
TIME=sometime; //設置相對時鍾寄存器
//恢復該進程現場信息
AX=pcbarea[run].ax;
BX=pcbarea[run].bx;
CX=pcbarea[run].cx;
DX=pcbarea[run].dx;
PC=pcbarea[run].pc;
PSW=pcbarea[run].psw;
run=i;
}//進程調度函數結束

create(int x) //進程創建函數
{
int i;
if(pfree==-1) //空閑進程式控制制塊隊列為空
{
printf(「無空閑進程式控制制塊，進程創建失敗\n」);
return;
}
i=pfree; //取空閑進程式控制制塊隊列的第一個
pfree=pcbarea[pfree].next; // pfree後移
//填寫該進程式控制制塊的內容
pcbarea[i].name=x;
pcbarea[i].status=aready;
pcbarea[i].ax=x;
pcbarea[i].bx=x;
pcbarea[i].cx=x;
pcbarea[i].dx=x;
pcbarea[i].pc=x;
pcbarea[i].psw=x;
if (ready.head!=-1) //就緒隊列不為空時，掛入就緒隊列的方式
{
pcbarea[ready.tail].next=i;
ready.tail=i;
pcbarea[ready.tail].next=-1;
}
else //就緒隊列為空時，掛入就緒隊列的方式
{
ready.head=i;
ready.tail=i;
pcbarea[ready.tail].next=-1;
}
}//進程創建函數結束

main()
{ //系統初始化
int num,i,j;
run=ready.head=ready.tail =-1;
pfree=0;
for(j=0;j<n-1;j++)
pcbarea[j].next=j+1;
pcbarea[n-1].next=-1;
printf(「輸入進程編號（避免編號沖突，以負數輸入結束，最多可以創建10個進程）：\n」);
scanf(「%d」,num);
while(num>=0)
{
create(num) ;
scanf(「%d」,num) ;
}
scheling(); //進程調度
if(run!=-1)
{
printf(「進程標識符 進程狀態 寄存器內容：ax bx cx dx pc psw:\n」);
printf(「%8d%10d%3d%3d%3d%3d%3d%3d\n」, pcbarea[run].name, pcbarea[run].status, pcbarea[run].ax, pcbarea[run].bx, pcbarea[run].cx, pcbarea[run].dx, pcbarea[run].pc, pcbarea[run].psw);
}
}//main()結束
我用的是vc++6.0的，你可以試試，有不懂得在和我交流吧

⑥ linux進程調度的三種策略是什麼

進程調度策略就是調度系統種哪一個進程來CPU運行。這種調度分2層考慮。 第一層，進程狀態這個是最優先考慮的，也就是說優先順序最高的。在linux中只有就緒態的進程才有可能會被調度選中然後佔有CPU，其它狀態的進程不可能佔有的到CPU。下面是linux中進程的狀態TASK_RUNNING:就緒狀態，得到CPU就可以運行。
TASK_INTERRUPTIBLE:淺度睡眠，資源到位或者受到信號就會變成就緒態。
TASK_UNINTERRUPTIBLE:深度睡眠，資源到位就會進入就緒態，不響應信號。
TASK_ZOMBIE：僵死態，進程exit後。
TASK_STOPPED：暫停態，收到SIG_CONT信號進入就緒態。 第二層，其實真正在操作系統中的實現，就是所有就緒態進程鏈接成一個隊列，進程調度時候只會考慮這個隊列中的進程，對其它的進程不考慮，這就實現了第一層中的要求。接下來就是就緒隊列內部各個進程的競爭了。 Linux採用3種不同的調度政策，SCHED_FIFO（下面簡寫成FIFO，先來先服務），SCHED_RR（簡寫成RR，時間片輪流），SCHED_OTHER（下面簡寫成OTHER）。這里大家就能看出一個問題，採用同等調度政策的進程之間自然有可比性，Linux3種調度政策並存，那麼不同調度政策間的進程如何比較呢？可以說他們之間根本就沒有可比性。其實在調度時候，調度只看一個指標，那就是各個進程所具有的權值，權值最大的且在可執行隊列中排在最前面的就會被調度執行。而權值的計算才會設計到各方面因素，其中調度政策可以說在計算權值中，份量是最重的。 為什麼Linux要這么干呢？這是由於事務的多樣性決定的，進程有實時性進程和非實時性的進程2種，FIFO和RR是用來支持實時性進程的調度，我們看一下這3種政策下權值的計算公式就明白了：FIFO和RR計算公式，權值=1000+進程真正的運行時間OTHER計算公式，當時間片為0時，權值=0.當時間片不為0時候，權值=剩餘時間片+20-nice,同時如果是內核線程有+1的小加分，這是因為內核線程無需用戶空間的切換，所以給它加了一分，獎勵他在進程切換時候開銷小的功勞。時間片好理解，那麼nice這個值，用過linux系統的人都知道，這是一個從unix下繼承過來的概念，表示謙讓度，是一個從20～-19的數，可以通過nice和renice指令來設置。從代碼中也能看到值越小就越不會謙讓他人。 從這里我們看出FIFO和RR至少有1000的基數，所以在有FIFO和RR調度政策進程存在時，OTHER進程是沒有機會被調度的到的。從權值計算公式同時也能看出，FIFO先來先服務的調度政策滿足了，但RR這個時間片輪流的調度如果按照這種權值計算是不能滿足時間片輪流這一概念的。這里只是權值的計算，在調度時候對RR政策的進程特殊處理。 以上都是權值計算，下面看看真正的調度過程，首先是對RR政策進程的特殊處理，如果當前進程採用的RR政策，那麼看他的時間片是否用完，用完了就踢到就緒隊列尾部，同時恢復他的時間片。然後是便利整個就緒隊列，找到第一個權值最大的進程來運行。 整體調度效果就是：如果有FIFO和RR政策的進程，就優先調度他們2個，他們之間看已執行時間長短決定勝負，而2種政策內部則遵守各自調度政策。而OTHER只有在前面2種不存在於就緒隊列時候才有可能執行，他們實際也是輪流執行，但他們之間是靠剩餘時間和NICE值來決定勝負。同時就緒隊列中排在最前面的最優先考慮在同樣權值情況下。