作業系統中常用到的程序排程算法

一、先來先服務

最簡單的排程算法是先來先服務（FCFS），也稱為先進先出（First-In-First-Out,FIFO）或嚴格排隊方案。當每個程序就緒後，它加入就緒隊列。目前正在運作的程序停止執行時，選擇在就緒隊列中存在時間最長的程序運作。

二、輪轉法

這是一種基于時鐘的搶占政策，以一個周期性間隔産生時鐘中斷，當中斷發生時，目前正在運作的程序被置于就緒隊列中，然後基于FCFS政策選擇下一個就緒作業的運作。這種技術也稱時間片，因為每個程序在被搶占前都給定一片時間。

三、最短程序優先

最短程序優先（Short Process Next,SPN）政策,這是一個非搶占的政策，其原則是下一次選擇預計處理時間最短的程序，是以短程序将會越過長作業，跳到隊列頭。

四、最短剩餘時間

最短剩餘時間（Shortest Remaining Time,SRT）是針對SPN增加了搶占機制的版本。在這種情況下，排程程式總是選擇預期剩餘時間最短的程序。當一個程序加入就緒隊列時，它可能比目前運作的程序具有更短的剩餘時間，是以隻要新程序就緒，排程程式就可能搶占目前正在運作的程序。像SPN一樣，排程程式在執行選擇函數時必須有關于處理時間的估計，并且存在長程序饑餓的危險。

五、最高響應比優先

根據比率：R=(w+s)/s （R為響應比，w為等待處理的時間，s為預計的服務時間）

如果該程序被立即調用，則R值等于歸一化周轉時間（周轉時間和服務時間的比率）。R最小值為1.0，隻有第一個進入系統的程序才能達到該值。

  排程規則為：在目前程序完成或被阻塞時，選擇R值最大的就緒程序，它說明了程序的年齡。當偏向短作業時，長程序由于得不到服務，等待時間不斷增加，進而增加比值，最終在競争中勝了短程序。

 和STR,SPN一樣，使用最高響應比（HRRN）政策需要估計預計服務時間。

六、回報法

如果沒有關于各程序相對長度的任何資訊，則SPN，SRT和HRRN都不能使用。另一種導緻偏向短作業的方法是處罰運作時間較長的作業，換句話說，如果不能獲得剩餘的執行時間，那就關注已經執行了的時間。

  方法為：排程基于搶占原則（按時間片）并且使用動态優先級機制。當一個程序第一次進入系統中時，它被放置在一個優先級隊列中，當第一次被搶占後并傳回就緒狀态時，它被放置在下一個低優先級隊列中，在随後的時間裡，每當被搶占時，它被降級到下一個低優先級隊列中。一個短程序很快會執行完，不會在就緒隊列中降很多級，一個長程序會逐漸降級。是以新到的程序和短程序優先于老程序和長程序。在每個隊列中，除了在優先級最低的隊列中之外，都是用簡單的FCFS機制，一旦一個程序處于優先級最低的隊列中，它就不可能再降級，但會重複的傳回該隊列，知道運作結束。是以，該隊列可按照輪轉方式排程。

各種排程算法的特點

參照操作作業系統精髓與設計原理（第七版）