目錄
說明
1，先來先服務排程算法（First-Come First-Served，FCFS）
概述
本質
特點
2，短作業/短程序優先算法（Short Job/Process First，SJF/SPF）
概述
本質
特點
3，高優先權優先排程算法（FPF或Priority-Scheduling Algorithm，PSA）
概述
說明
優先權：算法的核心
程序的優先權
優先權的确定
4，高響應比優先排程算法（Highest Response Ratio Next，HRRN）
概述
說明
特點
5，基于時間片的輪轉（Round Robin，RR）排程算法
概述
時間片選擇
時間片大小選擇
6，多隊列排程算法
7，多級回報隊列排程算法
概述
算法概述
特點
說明
實質是一種資源配置設定方法，因而排程算法是指：根據系統的資源配置設定政策所規定的資源配置設定算法
對于不同的系統和系統目标，通常采用不同的排程算法，例如，在批處理系統中，為了照顧為數衆多的短作業，應采用短作業優先的排程算法．又如在分時系統中，為了保證系統具有合理的響應時間，應采用輪轉法進行排程。
目前存在的多種排程算法中，有的算法适用于作業排程，有的算法适用于程序排程；但也有些排程算法既可用于作業排程，也可用于程序排程。
排程算法很少有絕對的好壞！
1，先來先服務排程算法（First-Come First-Served，FCFS）
概述
- 既可用于作業排程，也可用于程序排程。
- 用于作業排程：每次排程都是從後備作業隊列中，選擇一個或多個最先進入該隊列的作業，将它們調入記憶體，為它們配置設定資源、建立程序，然後放入就緒隊列。
- 用于程序排程：則每次排程是從就緒隊列中，選擇一個最先進入隊列的程序，為之配置設定處理機，使之投入運作。
本質
僅考慮“到達時間”；
特點
- 實作簡單；
- 貌似公平；
- 實際上，對短作業不公平。
2，短作業/短程序優先算法（Short Job/Process First，SJF/SPF）
概述
- 既可用于作業排程(SJF)，也可用于程序排程(SPF)
- 用于作業排程：每次排程都是從後備作業隊列中，選擇一個要求服務時間（執行時間）最短的作業，将它們調入記憶體，為它們配置設定資源、建立程序，然後放入就緒隊列。
- 用于程序排程：則每次排程是從就緒隊列中，選擇一個執行時間最短的程序，為之配置設定處理機，使之投入運作；
- 實際應用表明，SJF的性能要優于FCFS排程算法的；
本質
僅考慮“執行時間”；
特點
- 實作困難：估算執行時間很難；
- 有利于短作業
- 對長作業不公平。
3，高優先權優先排程算法（FPF或Priority-Scheduling Algorithm，PSA）
概述
- 既可用于作業排程，也可用于程序排程。
- 用于作業排程時：系統将從後備隊列中選擇若幹個優先權最高的作業，裝入記憶體。
- 用于程序排程時：該算法是把處理機配置設定給就緒隊列中優先權最高的程序。分為非搶占式優先權算法和搶占式優先權排程算法。
說明
- 對于FCFS算法，作業的等待時間就是作業的優先級，等待時間越長，其優先級越高。
- 對于SJF算法，作業的長短就是作業的優先級，作業所需運作的時間越短，其優先級越高。
- 但上述兩種優先級都不能反映作業的緊迫程度。
- 而在優先級排程算法中，則是基于作業的緊迫程度，由外部賦予作業相應的優先級，排程算法是根據該優先級進行排程的。這樣就可以保證緊迫性作業優先運作。
優先權：算法的核心
- 反映作業/程序執行時的迫切程度，是對排程所考慮的實際因素的算法抽象。
- 通常用1個整型數來表示。
程序的優先權
搶占式優先權（程序排程）：高優先權程序到達時，立刻停止低優先權程序的執行，讓高優先權程序執行。
非搶占式優先權（程序排程）：高優先權作業程序到達時，須等待低優先權程序執行完畢或主動釋放CPU。
優先權的确定
靜态優先權：程序建立時确定（根據程序類型、資源需求和使用者要求等），直到程序執行結束，保持不變。
動态優先權：程序建立時确定（根據程序類型、資源需求和使用者要求等）初始優先權，在程序執行過程中，可以發生變化。
4，高響應比優先排程算法（Highest Response Ratio Next，HRRN）
概述
- 用于作業排程。
- 系統将從後備隊列中選擇若幹個響應比(優先權)最高的作業，裝入記憶體，投入運作。
- 核心：對等待作業以一定速率a提高其優先權。
說明
由于等待時間與服務時間之和就是系統對該作業的響應時間，故該優先級又相當于響應比Rp。據此，優先又可表示為:
特點
- 如果作業的等待時間相同，則要求服務的時間愈短，其優先權愈高，因而該算法有利于短作業。
- 當要求服務的時間相同時，作業的優先權決定于其等待時間，等待時間愈長，其優先權愈高，因而它實作的是先來先服務。
- 對于長作業，作業的優先級可以随等待時間的增加而提高，當其等待時間足夠長時，其優先級便可升到很高，進而獲得處理機。
- 既照顧了短作業，又考慮了作業到達的先後次序，不會使長作業長期得不到服務。是以，該算法實作了一種較好的折衷。
- 須做響應比計算，會增加系統開銷
5，基于時間片的輪轉（Round Robin，RR）排程算法
概述
- 用于作業排程或程序排程。
- 在早期的時間片輪轉法中，系統将所有的就緒程序按先來先服務的原則，排成一個隊列，每次排程時，把CPU配置設定給隊首程序，并令其執行一個時間片。
- 當執行的時間片用完時，由一個計時器發出時鐘中斷請求，排程程式便據此信号來停止該程序的執行，并将它送往就緒隊列的末尾；
- 然後，再把處理機配置設定給就緒隊列中新的隊首程序，同時也讓它執行一個時間片。
- 保證響應時間：就緒隊列中的所有程序，在給定時間内，均能獲得一個時間片的處理機執行時間。換言之，系統能在給定的時間内，響應所有使用者的請求。
- 時間片的大小從幾毫秒 到幾百毫秒。
時間片選擇
- 固定時間片。
- 可變時間片。
時間片大小選擇
- 不可太大：影響最大響應時間（等待時間+要求服務時間）：T=nq；其中，n為程序數量，q為時間片大小。
- 不可太小：排程開銷，增加周轉時間；
6，多隊列排程算法
- 将系統中的程序就緒隊列從一一個拆分為若幹個；
- 将不同類型或性質的程序固定配置設定在不同的就緒隊列，不同的就緒隊列采用不同的排程算法；
- 一個就緒隊列中的程序可以設定不同的優先級，不同的就緒隊列本身也可以設定不同的優先級。
7，多級回報隊列排程算法
概述
- 設定多個就緒隊列，為各隊列賦予不同的優先級。第1個隊列的優先級最高，其餘隊列優先權逐個降低。
- 賦予各個隊列中程序執行時間片的大小各不相同：優先權愈高的隊列中，為每個程序所規定的執行時間片就愈小。
- 僅當第1隊列空閑時，排程程式才排程第2隊列中的程序運作；僅當第1～(i-1)隊列均空時，才會排程第i隊列中的程序運作。
- 如果處理機正在第i隊列中為某程序服務時，又有新程序進入優先權較高的隊列(第1～(i-1)中的任何一個隊列)，則此時新程序将搶占正在運作程序的處理機（正在運作程序被放回原所在隊列末尾）。
算法概述
- 對新建立程序，首先将它放入第1隊列末尾，按FCFS原則排隊等待排程。
- 當輪到該程序執行時，如它能在該時間片内完成，則結束; 如果未完成，排程程式便将該程序轉入第2隊列的末尾，再同樣按FCFS原則等待排程執行；
- 如果它在第2隊列中運作1個時間片後仍未完成，再依次将它放入第3隊列…。如此下去，當1個長作業（程序）從第1隊列依次降到第n隊列後，在第n隊列中便采取按時間片輪轉的方式運作。
特點
- 避免了事先計算各種程序所需的執行時間。
- 具有較好的性能，能較好地滿足各種類型使用者需要：
- 終端型作業使用者：終端型作業大多屬于互動型作業，作業通常較小，系統隻要能使這些作業（程序）在第一隊列所規定的時間片内完成，便可使終端型作業使用者都感到滿意。
- 短批處理作業使用者：對于很短的批處理型作業，開始時像終端型作業一樣，如果僅在第一隊列中執行一個時間片即可完成，便可獲得與終端型作業一樣的響應時間。對于稍長的作業，通常也隻需在第二隊列和第三隊列各執行一個時間片即可完成，其周轉時間仍然較短。
- 長批處理作業使用者： 對于長作業，它将依次在第1, 2, …,n個隊列中運作，然後再按輪轉方式運作，使用者不必擔心其作業長期得不到處理。