處理機的調(diào)度

標簽（空格分隔）：進程調(diào)度調(diào)度算法操作系統(tǒng)

基本概念

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

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

高級調(diào)度:作業(yè)調(diào)度, 調(diào)度對象為作業(yè).
中級調(diào)度:內(nèi)存調(diào)度(實質(zhì)是存儲器的對換功能)
低級調(diào)度:進程調(diào)度, 調(diào)度對象為進程或內(nèi)核級線程

作業(yè)調(diào)度的算法也適用于進程調(diào)度

服務時間(T_s): 系統(tǒng)為作業(yè)或進程提供服務的時間
周轉(zhuǎn)時間(T_i): 作業(yè)或進程被提交給系統(tǒng)到作業(yè)或進程完成為止的時間間隔.
通常包括:

作業(yè)在外存后備隊列上等待調(diào)度的時間.
進程在就緒隊列上等待進程調(diào)度的時間.
進程在cpu上執(zhí)行的時間.
進程等待I/O操作完成的時間.

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

調(diào)度時機、切換與過程

進程調(diào)度和切換程序是操作系統(tǒng)內(nèi)核程序。當請求調(diào)度的事件發(fā)生后，才可能會運行進程調(diào)度程序，當調(diào)度了新的就緒進程后，才會去進行進程間的切換。理論上這三件事情應該順序執(zhí)行，但在實際設計中，在操作系統(tǒng)內(nèi)核程序運行時，如果某時發(fā)生了引起進程調(diào)度的因素，并不一定能夠馬上進行調(diào)度與切換。

現(xiàn)代操作系統(tǒng)中，不能進行進程的調(diào)度與切換的情況有以下幾種情況:

在處理中斷的過程中：中斷處理過程復雜，在實現(xiàn)上很難做到進程切換，而且中斷處理是系統(tǒng)工作的一部分，邏輯上不屬于某一進程，不應被剝奪處理機資源。
進程在操作系統(tǒng)內(nèi)核程序臨界區(qū)中：進入臨界區(qū)后，需要獨占式地訪問共享數(shù)據(jù)，理論上必須加鎖，以防止其他并行程序進入，在解鎖前不應切換到其他進程運行，以加快該共享數(shù)據(jù)的釋放。
其他需要完全屏蔽中斷的原子操作過程中：如加鎖、解鎖、中斷現(xiàn)場保護、恢復等原子操作。在原子過程中，連中斷都要屏蔽，更不應該進行進程調(diào)度與切換。

如果在上述過程中發(fā)生了引起調(diào)度的條件，并不能馬上進行調(diào)度和切換，應置系統(tǒng)的請求調(diào)度標志，直到上述過程結(jié)束后才進行相應的調(diào)度與切換。

應該進行進程調(diào)度與切換的情況有：

當發(fā)生引起調(diào)度條件，且當前進程無法繼續(xù)運行下去時，可以馬上進行調(diào)度與切換。如果操作系統(tǒng)只在這種情況下進行進程調(diào)度，就是非剝奪調(diào)度。
當中斷處理結(jié)束或自陷處理結(jié)束后，返回被中斷進程的用戶態(tài)程序執(zhí)行現(xiàn)場前，若置上請求調(diào)度標志，即可馬上進行進程調(diào)度與切換。如果操作系統(tǒng)支持這種情況下的運行調(diào)度程序，就實現(xiàn)了剝奪方式的調(diào)度。

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

調(diào)度的方式

非搶占方式
一旦處理機分配給某進程后, 就一直讓它運行下去, 決不會因為時鐘中斷或任何其他原因取搶占當前正在運行進程的處理機, 直至該進程完成, 或發(fā)生某事件而被阻塞時, 才把處理機分配給其他進程.
搶占方式
系統(tǒng)允許調(diào)度程序根據(jù)某種原則, 取暫停某個正在執(zhí)行的進程, 將已分配個該進程的處理機重新分配給另一進程.
“搶占”時應遵循一定的原則:

優(yōu)先權(quán)原則
短進程優(yōu)先原則
時間片原則

典型的調(diào)度算法

先來先服務調(diào)度算法(first-come first-served):

即FCFS調(diào)度算法, 既可用于作業(yè)調(diào)度, 也可用于進程調(diào)度. 系統(tǒng)按照作業(yè)到達的先后次序(優(yōu)先考慮在就緒隊列中等待時間最長的作業(yè))進行調(diào)度.
缺點:未考慮作業(yè)的緊迫程度, 只能順序運行

短作業(yè)(進程)優(yōu)先的調(diào)度算法(short job first):

為短作業(yè)而設立, 因為操作系統(tǒng)中大多為短作業(yè).系統(tǒng)在作業(yè)運行時, 選出運行時間最短的作業(yè)將其調(diào)入內(nèi)存.

SJF(不可搶占):算法以作業(yè)的長短(作業(yè)需要運行的時間)來計算優(yōu)先級, 作業(yè)越短, 其優(yōu)先級越高.
SPF(可搶占):同上, 但是當有作業(yè)優(yōu)先級較高時, 便可以搶占資源優(yōu)先執(zhí)行.

缺點:

必須預知作業(yè)的運行時間
對作業(yè)程不利
無法實現(xiàn)人機交互
沒有考慮到作業(yè)的緊迫程度

優(yōu)先級調(diào)度算法(priority-scheduling algorithm):

PSA算法基于作業(yè)的緊迫程度, 由外部賦予作業(yè)相應的優(yōu)先級, 根據(jù)作業(yè)優(yōu)先級進行調(diào)度.

高響應閉優(yōu)先調(diào)度算法(highest request ratio next):

HRRN算法即考慮了作業(yè)的等待時間, 又考慮了作業(yè)運行時間. 為沒有作業(yè)引入一個動態(tài)優(yōu)先級:

優(yōu)先權(quán) = (等待時間+要求服務時間) / 要求服務時間

可縮寫為:

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

特點:

作業(yè)等待時間相同, 則要求服務時間越短, 優(yōu)先權(quán)越高越, 類似于SJF算法, 有利于短作業(yè)
作業(yè)要求服務時間相同時, 則作業(yè)等待時間約長, 優(yōu)先權(quán)越高, 類似于FCFS算法, 有利于長作業(yè)
對于長作業(yè)(要求服務時間長), 隨著等待的時間足夠長, 也可獲得較高的優(yōu)先級. 不會一直等下去.

時間片輪轉(zhuǎn)調(diào)度算法(RR)

原理: 系統(tǒng)根據(jù)FCFS策略將所有的就緒進程排成一個就緒隊列, 并設置每隔一段時間產(chǎn)生依次中斷, 激活系統(tǒng)中的進程調(diào)度程序, 完成依次調(diào)度, 將cpu分配給新的隊首進程(或新到達的緊迫進程).

進程切換

若一個時間片尚未用完, 正在運行的進程便已完成, 則立即激活調(diào)度程序, 將其從執(zhí)行隊列中刪除, 在調(diào)度就緒隊列的隊首進程運行, 并啟動一個新的時間片.
在一個時間片用完時, 計時中斷處理程序被激活, 如果進程尚未運行完畢, 則調(diào)度程序?qū)⑺屯途w隊列末尾, 并調(diào)度就緒隊列的隊首進程運行, 并啟動新時間片.

注意:時間片選取過小, 則將頻繁的執(zhí)行進程調(diào)度和進程長下文切換, 增加系統(tǒng)開銷; 時間片選取過長, 則RR算法退化為FCFS算法, 無法滿足短作業(yè)和交互式用戶需求. 時間片應選取略大于依次典型的交互所需要的時間, 是大多數(shù)進程在一個時間片內(nèi)完成.

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

設置多個就緒隊列, 并為每個隊列賦予不同的優(yōu)先級, 優(yōu)先級越高的隊列其時間片越小.優(yōu)先級最高的隊列最先進入待調(diào)度的隊列
隊列之間采用FCFS調(diào)度算法.只有高優(yōu)先級隊列中的全部進程完成時才調(diào)度下一隊列
隊列內(nèi)的進程按照輪轉(zhuǎn)算法調(diào)度.新進程進入內(nèi)存后首先進入優(yōu)先級最高的隊列
在低優(yōu)先級隊列運行時, 若有新進程到達, 那么在運行完這個時間片后，CPU馬上分配給新到達的作業(yè)（搶占式）。

實時系統(tǒng)中的進程調(diào)度算法

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