處理機調度的詳細介紹

處理機的調度

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

---

基本概念

## 定義

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

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

• 進階調度:作業調度, 調度物件為作業.

• 中階調度:記憶體調度(實質是記憶體的對換功能)

• 低階調度:進程調度, 調度物件為行程或核心級執行緒

##作業調度的演算法也適用於行程排程

服務時間

\(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}\]
#調度時機、切換與過程

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

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

在處理中斷的過程中：中斷處理過程複雜，在實作上很難做到進程切換，中斷處理是系統工作的一部分，邏輯上不屬於某一進程，不應被剝奪處理機資源。
進程在作業系統核心程式臨界區中：進入臨界區後，需要獨佔式地存取共享數據，理論上必須加鎖，以防止其他並行程式進入，在解鎖前不應切換到其他進程運行，以加快該共享資料的釋放。
其他需要完全屏蔽中斷的原子操作過程中：如加鎖、解鎖、中斷現場保護、恢復等原子操作。在原子過程中，連中斷都要屏蔽，更不應該進行進程調度與切換。
如果在上述過程中發生了引起調度的條件，並不能馬上進行調度和切換，應置系統的請求調度標誌，直到上述過程結束後才進行相應的調度與切換。

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

當發生引起調度條件，且當前進程無法繼續運行時，可以馬上進行調度與切換。如果作業系統只在這種情況下進行進程調度，就是非剝奪調度。
當中斷處理結束或自陷處理結束後，返回被中斷程序的用戶態程序執行現場前，若置上請求調度標誌，即可馬上進行進程調度與切換。如果作業系統支援這種情況下的運行調度程序，就實現了剝奪方式的調度。
進程切換往往在調度完成後立刻發生，它要求保存原進程當前切換點的現場訊息，恢復被調度進程的現場資訊。現場切換時，作業系統核心會將原始進程的現場資訊推入到當前進程的核心堆疊來保存它們，並更新堆疊指標。核心完成從新進程的核心堆疊中裝入新進程的現場資訊、更新目前運行進程空間指標、重置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):

設置多個就緒佇列, 並為每個佇列賦予不同的優先權, 優先權越高的佇列其時間片越小.優先權最高的佇列最先進入待調度的佇列
佇列之間採用FCFS調度演算法.只有高優先權佇列中的全部行程完成時才調度下一佇列
佇列內的程序依照輪換演算法調度.新行程進入記憶體後首先進入優先權最高的佇列
在低優先權佇列運行時, 若有新行程到達, 那麼在運行完這個時間片後，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)

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

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

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

以上是處理機調度的詳細介紹的詳細內容。更多資訊請關注PHP中文網其他相關文章！