【Linux】程序的排程算法

       排程算法指的是根據系統的資源配置設定政策所規定的資源配置設定算法。對于不同的系統和系統目标，通常采用不同的排程算法。

1.先來先服務算法

• 先來先服務算法(FCFS: First Come, First Served)，是一種依據程序進入就緒狀态的先後順序排列的算法，當程序進入等待或者結束狀态時，就緒隊列中的下一個程序占用CPU。
• 優點：易于了解且實作簡單。
• 缺點：

1.平均等待時間波動較大

周轉時間：程序從初始化到結束(包含等待時間)的總時間。

短程序可能排在長程序後面，假如有三個程序，計算時間分别為P1(12),P2(3),P3(3)，任務的到達順序為P1，P2，P3，那麼周轉時間就是(12+15+18)/3=15。

若任務的到達順序為P2，P3，P1，則周轉時間為(3+6+18)/3=9，可見平均等待時間波動較大。

2.I/O資源和CPU資源的使用率較低

CPU密集型程序會導緻I/O裝置閑置時，I/O密集型程序也等待。

2.短程序優先算法

• 短程序優先算法(SPN：Shortest Process First)，是一種選擇就緒隊列中執行時間最短的程序占用CPU進入運作狀态的算法，其中，就緒隊列按照預期的執行時間來排序，該算法具有最優平均周轉時間。
• SPN算法的可搶占改進：短剩餘時間優先算法(SRT)
• 假設一個正在執行的程序的預期執行時間比較長，其剩餘的執行時間大于某個将要執行的程序的預期時間時，允許該預期時間短的程序搶先執行。
• 缺點：

1.可能導緻饑餓(連續的短程序流會使得長程序無法獲得CPU資源)；

2.需要預知未來(如何預估下一個CPU計算的持續時間？簡單的解決方法：詢問使用者  用曆史的執行時間來預估未來的執行時間)。

3.最高響應比優先算法

• 最高響應比優先算法(HRRN：Highest Response Ratio Next)，是一種選擇就緒隊列中響應比R值最高的程序的算法。響應比R定義如下：R=(w+s)/s，其中w表示等待時間，s表示執行時間，等待時間越長，R值越高。這解決了短程序優先算法中連續的短程序流會使得長程序無法獲得CPU資源。

4.時間片輪轉算法

• 時間片輪轉算法(RR：Round-Robin)，是一種讓就緒隊列上的每個程序隻運作一個時間片的算法。當時間片結束時，按照FCFS算法切換到下一個就緒程序。
• 缺點：

1.額外的上下文切換；

2.時間片太大，導緻等待時間過長，極限情況退化成FCFS；

3.時間片太小，導緻反映迅速，産生大量上下文切換，而大量上下文切換開銷會影響到系統吞吐量。

5.多級回報隊列算法

• 多級回報隊列算法(MLFQ：Multilevel Feedback Queue)，是一種程序可以在不同隊列間移動的多級隊列算法，其實質是多種算法的內建。時間片大小随着優先級别增加而增加，若程序在目前的時間片還沒有完成，則降到下一個優先級。CPU密集型程序(時間片大)的優先級下降很快，I/O密集型程序(時間片小)會停留在高優先級。