處理機的調度

標簽（空格分隔）： 進程調度 調度演算法 操作系統

基本概念

定義
: 操作系統管理了系統的有限資源，當有多個進程（或多個進程發出的請求）要使用這些資源時，因為資源的有限性，必須按照一定的原則選擇進程（請求）來占用資源, 我們稱之為調度。

其目的是控制資源使用者的數量,選取資源使用者許可占用資源或占用資源。處理機調度的三個層次:

• 高級調度:作業調度, 調度對象為作業.
• 中級調度:記憶體調度(實質是存儲器的對換功能)
• 低級調度:進程調度, 調度對象為進程或內核級線程

作業調度的演算法也適用於進程調度

服務時間\(T_s\): 系統為作業或進程提供服務的時間
周轉時間\(T_i\): 作業或進程被提交給系統到作業或進程完成為止的時間間隔.
通常包括:

作業在外存後備隊列上等待調度的時間.
進程在就緒隊列上等待進程調度的時間.
進程在cpu上執行的時間.
進程等待I/O操作完成的時間.

平均周轉時間:
\[T = \frac{\sum_{i=1}^n T_i}{n}\]
帶權周轉時間: 作業的周轉時間與為它提供服務的時間之比
\[W_i = \frac{T_i}{T_s}\]
平均帶權周轉時間:
\[W = \frac{\sum_{i=1}^n \frac{T_i}{T_s}}{n}\]

調度時機、切換與過程

進程調度和切換程式是操作系統內核程式。當請求調度的事件發生後，才可能會運行進程調度程式，當調度了新的就緒進程後，才會去進行進程間的切換。理論上這三件事情應該順序執行，但在實際設計中，在操作系統內核程式運行時，如果某時發生了引起進程調度的因素，並不一定能夠馬上進行調度與切換。

現代操作系統中，不能進行進程的調度與切換的情況有以下幾種情況:

1. 在處理中斷的過程中：中斷處理過程複雜，在實現上很難做到進程切換，而且中斷處理是系統工作的一部分，邏輯上不屬於某一進程，不應被剝奪處理機資源。

2. 進程在操作系統內核程式臨界區中：進入臨界區後，需要獨占式地訪問共用數據，理論上必須加鎖，以防止其他並行程式進入，在解鎖前不應切換到其他進程運行，以加快該共用數據的釋放。

3. 其他需要完全屏蔽中斷的原子操作過程中：如加鎖、解鎖、中斷現場保護、恢復等原子操作。在原子過程中，連中斷都要屏蔽，更不應該進行進程調度與切換。

如果在上述過程中發生了引起調度的條件，並不能馬上進行調度和切換，應置系統的請求調度標誌，直到上述過程結束後才進行相應的調度與切換。

應該進行進程調度與切換的情況有：

1. 當發生引起調度條件，且當前進程無法繼續運行下去時，可以馬上進行調度與切換。如果操作系統只在這種情況下進行進程調度，就是非剝奪調度。

2. 當中斷處理結束或自陷處理結束後，返回被中斷進程的用戶態程式執行現場前，若置上請求調度標誌，即可馬上進行進程調度與切換。如果操作系統支持這種情況下的運行調度程式，就實現了剝奪方式的調度。

進程切換往往在調度完成後立刻發生，它要求保存原進程當前切換點的現場信息，恢復被調度進程的現場信息。現場切換時，操作系統內核將原進程的現場信息推入到當前進程的內核堆棧來保存它們，並更新堆棧指針。內核完成從新進程的內核棧中裝入新進程的現場信息、更新當前運行進程空間指針、重設PC寄存器等相關工作之後，開始運行新的進程。

調度的方式

• 非搶占方式
  一旦處理機分配給某進程後, 就一直讓它運行下去, 決不會因為時鐘中斷或任何其他原因取搶占當前正在運行進程的處理機, 直至該進程完成, 或發生某事件而被阻塞時, 才把處理機分配給其他進程.
• 搶占方式
  系統允許調度程式根據某種原則, 取暫停某個正在執行的進程, 將已分配個該進程的處理機重新分配給另一進程.
  "搶占"時應遵循一定的原則:
  • 優先權原則
  • 短進程優先原則
  • 時間片原則

典型的調度演算法

先來先服務調度演算法(first-come first-served):

即FCFS調度演算法, 既可用於作業調度, 也可用於進程調度. 系統按照作業到達的先後次序(優先考慮在就緒隊列中等待時間最長的作業)進行調度.
缺點:未考慮作業的緊迫程度, 只能順序運行

短作業(進程)優先的調度演算法(short job first):

為短作業而設立, 因為操作系統中大多為短作業.系統在作業運行時, 選出運行時間最短的作業將其調入記憶體.

1. SJF(不可搶占):演算法以作業的長短(作業需要運行的時間)來計算優先順序, 作業越短, 其優先順序越高.
2. SPF(可搶占):同上, 但是當有作業優先順序較高時, 便可以搶占資源優先執行.

缺點:

• 必須預知作業的運行時間
• 對作業程不利
• 無法實現人機交互
• 沒有考慮到作業的緊迫程度

優先順序調度演算法(priority-scheduling algorithm):

PSA演算法基於作業的緊迫程度, 由外部賦予作業相應的優先順序, 根據作業優先順序進行調度.

高響應閉優先調度演算法(highest request ratio next):

HRRN演算法即考慮了作業的等待時間, 又考慮了作業運行時間. 為沒有作業引入一個動態優先順序:

優先權 = (等待時間+要求服務時間) / 要求服務時間

可縮寫為:

R = 響應時間 / 要求服務時間

特點:

1. 作業等待時間相同, 則要求服務時間越短, 優先權越高越, 類似於SJF演算法, 有利於短作業
2. 作業要求服務時間相同時, 則作業等待時間約長, 優先權越高, 類似於FCFS演算法, 有利於長作業
3. 對於長作業(要求服務時間長), 隨著等待的時間足夠長, 也可獲得較高的優先順序. 不會一直等下去.

時間片輪轉調度演算法(RR)

原理: 系統根據FCFS策略將所有的就緒進程排成一個就緒隊列, 並設置每隔一段時間產生依次中斷, 激活系統中的進程調度程式, 完成依次調度, 將cpu分配給新的隊首進程(或新到達的緊迫進程).

進程切換

1. 若一個時間片尚未用完, 正在運行的進程便已完成, 則立即激活調度程式, 將其從執行隊列中刪除, 在調度就緒隊列的隊首進程運行, 並啟動一個新的時間片.
2. 在一個時間片用完時, 計時中斷處理程式被激活, 如果進程尚未運行完畢, 則調度程式將它送往就緒隊列末尾, 並調度就緒隊列的隊首進程運行, 並啟動新時間片.

註意:時間片選取過小, 則將頻繁的執行進程調度和進程長下文切換, 增加系統開銷; 時間片選取過長, 則RR演算法退化為FCFS演算法, 無法滿足短作業和互動式用戶需求. 時間片應選取略大於依次典型的交互所需要的時間, 是大多數進程在一個時間片內完成.

多級反饋隊列調度演算法(multileved feedback queue):

1. 設置多個就緒隊列, 併為每個隊列賦予不同的優先順序, 優先順序越高的隊列其時間片越小.優先順序最高的隊列最先進入待調度的隊列
2. 隊列之間採用FCFS調度演算法.只有高優先順序隊列中的全部進程完成時才調度下一隊列
3. 隊列內的進程按照輪轉演算法調度.新進程進入記憶體後首先進入優先順序最高的隊列
4. 在低優先順序隊列運行時, 若有新進程到達, 那麼在運行完這個時間片後，CPU馬上分配給新到達的作業（搶占式）。

實時系統中的進程調度演算法

實時系統是指系統能及時響應外部事件的請求並及時處理這些請求.基於這一特性, 實時系統在工業(武器)控制, 多媒體等系統中常見.
實時系統中通分為存在一個截止時間, 硬實時任務(HRT)要求在開始截止時間前必須執行, 在結束截止時間前必須結束. 軟實時任務同上, 但並不嚴格.
在實時系統中有兩類演算法值得註意:最早截止時間優先演算法(Earliest Deadline First)和最低鬆弛度優先演算法(Least Laxity First).兩類演算法都可用搶占式和非搶占式調度, 但後者常用於搶占式調度.
在m個周期性的實時調度中, 每個實時任務的處理時間\(C_i\), 周期時間\(P_i\), 在但處理機的情況下, 需滿足條件:$\sum_{i=1}^m\frac{C_i}{P_i} \(小於1; 多處理機條件下, 須滿足條件\)\sum_{i=1}^m\frac{C_i}{P_i} $小於N, N為處理機數量.

最早截止時間優先演算法(EDF)

該演算法在實時系統中根據任務的截止時間確定其優先順序.

1. 非搶占式

2. 搶占式

最低鬆弛度優先演算法(LLF)

在該法中根據任務的緊急程度(鬆弛程度)賦予其優先順序, 越緊急的任務優先順序越高.

任務的鬆弛程度 = 必須完成時間 - 其本身運行時間 - 當前時間

系統的任務按照鬆弛度排成一個就緒隊列, 鬆弛度低的任務排在隊列前面, 即調度程式優先執行.