作業系統中涉及的各種排程算法

在每本介紹作業系統的書中，各類排程算法都占據了很大的篇幅，僅從此處我們可以看出

各類排程算法的重要性。而這些排程算法除了在作業系統的各部分使用外，我們也可以将

它們背後蘊含的邏輯用在其他地方，下面是對作業系統中設計的各類排程算法的一個系統

性的總結：

适用于作業與程序的排程算法：

1.先來先服務(FCFS)算法

(1)對于作業，FCFS算法總是從後備作業隊列中選擇最先進入該隊列的一個或多個作業，将

它們調入記憶體，配置設定資源，建立程序并放入就緒隊列

對于程序，FCFS算法總是選擇最先進入就緒隊列的程序，将處理器配置設定給它

(2)FCFS算法屬于不可剝奪算法，對所用程序都是公平的

(3)FCFS算法簡單，但效率低，有利于CPU忙型作業而不利于I/O忙型作業

2.短作業優先(SJF)排程算法

(1)對于作業，SJF算法選擇一個或多個估計運作時間最短的作業調入記憶體

對于程序，SJF算法從就緒隊列中選擇一個估計運作時間最短的程序将處理器配置設定給它

(2)對長作業不利，可能造成 饑餓 現象

(3)SJF排程算法的平均等待時間、平均周轉時間最短

(4)SJF排程算法使用的是對未來的估計，難以實作或者不能保證準确

3.優先級排程算法

(1)使用優先級表示作業或程序的緊迫程度，選擇優先級最高的作用或程序調入記憶體或配置設定

處理器(注意：優先級常用數字表示，但并不一定數字越大優先級越高，需要看具體定義)

(2)根據高優先級程序能否搶占低優先級程序可将該排程算法分為：

非剝奪式優先級排程算法：當一個程序在處理器運作時，即使有一個更高優先級的程序進

入就緒隊列，該高優先級的程序也必須等待低優先級程序退出處理器才能擷取處理器

剝奪式優先級排程算法：當一個程序在處理器運作時，當有一個更高優先級的程序進入

就緒隊列後，暫停正在運作的程序而将處理器配置設定給高優先級的程序

(3)根據程序優先級能否改變分為：

靜态優先級：優先級在程序建立時确定，在程序整個運作期中保持不變

動态優先級：根據程序運作狀況動态調整程序優先級

(4)優先級排程算法可能會導緻 饑餓

(5)一般系統程序優先級大于使用者程序，互動型程序大于非互動型程序，I/O程序大于計算型程序

4.高響應比優先排程算法

(1)主要用于作業排程，是FCFS與SJF的綜合平衡，同時考慮了每個程序的等待時間與估計運作

時間，在每次作業排程時，先計算各作業響應比，選擇響應比最高的作業調入記憶體

(2)響應比 = (等待時間 + 要求服務時間) / 要求服務時間

(3)高響應比優先算法克服了饑餓狀态，兼顧了長作業

5.時間片輪轉排程算法

(1)時間片輪轉排程算法主要适用于分時系統

(2)類似于FCFS算法，但每個程序僅能運作一個時間片，當程序時間片用完後，無論該程序是否

完成，必須釋放處理器給就緒隊列中的下一個程序，而自身進入就緒隊列末尾排隊，屬于剝

奪式排程算法

(3)時間片的大小對算法性能影響很大，過大的時間片使得每個程序在一個時間片中運作完成，

也就使該算法退化為FCFS，過小的時間片，會使得花費在排程上的時間過多

(4)時間片的選擇通常由系統響應時間、就緒隊列中程序數目、系統的處理能力共同決定

6.多級回報隊列排程算法

(1)多級回報隊列排程算法是時間片輪轉排程算法與優先級排程算法的綜合，通過動态調整優先

級與時間片的大小，該算法可兼顧多個方面，且不必估計程序運作時間

(2)多級回報隊列排程算法的實作通過設定多個就緒隊列，每個隊列的優先級不同，高優先級隊

列中每個程序配置設定的時間片越小，每個程序最先進入優先級最高的就緒隊列末尾，當該就緒

隊列中程序在屬于該就緒隊列的時間片中未運作完後，進入下一個優先級低一級的就緒隊列

中等待執行。系統總是愛高優先級隊列為空時才執行下一優先級就緒隊列中的程序

(3)多級回報隊列排程算法對于終端型作業使用者，短作業優先；對于短批處理作業使用者，周轉時

間較短；對于長批處理作業使用者，不會産生饑餓現象

頁面置換算法

1.最佳(OPT)置換算法

(1)選擇以後不會被使用或最長時間内不再被通路的頁面換出，以保證最低的缺頁率

(2)由于是對未來的預測，該算法無法實作，但OPT常被用于評價其他算法

2.先進先出(FIFO)頁面置換算法

(1)選擇最先進入記憶體的頁面(在記憶體中滞留時間最長度的頁面)換出

(2)FIFO實作簡單，但該算法可能出現當所配置設定的實體塊越多頁面故障數不增反減的現象，稱為

Belady異常

3.最近最久未使用(LRU)置換算法

(1)選擇最近最長時間未被通路的頁面換出，該算法認為過去一段時間未被通路的頁面在将來也

不會被通路，采用過去預測将來

(2)LRU算法性能較好，但需要寄存器和棧的硬體支援，屬于堆棧類算法，不會出現 Belady異常

(3)LRU性能接近OPT，但實作困難，且開銷大

4.時鐘(CLOCK)置換算法

(1)簡單的CLOCk算法為每幀關聯一個附加位，稱為使用位。當頁面首次裝入記憶體時，該位為 1，

當該頁面随後又被通路時，也将使用位置為 1，将被換出的幀根據進入記憶體時間先後形成一

個循環緩沖區，有一個指針與該緩沖區相關聯，最初該指針指向第一個進入記憶體的幀，當要

選擇某一幀換出時，該指針循環掃描該緩沖區，将其遇到的第一個使用位為0的幀換出，該指

針指向被換出幀的下一個幀，被該指針掃過的幀，使用位從1變為0

(2)CLOCK算法性能比較接近LRU算法

(3)為每個幀繼續添加附加位，用于辨別各個狀态，形成各個改進的CLOCK算法

磁盤排程算法：

1.先來先服務(FCFS)

(1)最簡單的磁盤排程算法，根據程序通路磁盤的先後順序進行排程

(2)FCFS具有公平性，在少量程序通路簇聚的檔案扇區時有較好性能，但若大量程序競争使用磁盤

則性能接近随機排程

2.最短尋找時間優先(SSTF)

(1)SSTF選擇與目前磁頭距離最近的磁道，以便每次尋找時間最短

(2)SSTF可能産生饑餓現象

3.掃描算法(SCAN)

(1)SCAN算法在目前磁頭移動方向上選擇與目前磁頭距離最近的請求作為下一次服務對象

(2)SCAN算法對最近掃描過的區域不公平，在通路的局部性方面不如FCFS、SSTF

4.循環掃描算法(C-SCAN)

(1)C-SCAN在SCAN算法的基礎上規定磁頭單向移動提供服務，回返時直接快速移動到起始端

(2)SCAN與C-SCAN的改進：磁頭移動隻需要達到最遠端的一個請求即可傳回，不需要達到磁盤端點，稱

為LOOK排程和C-LOOK排程

(3)SCAN與C-SCAN在磁盤負載較大時比較占優勢