進程與進程管理 | 進程調度

05-23

進程與進程管理 | 進程調度

來自專欄操作系統筆記

調度 ∕ 分派

1、調度

含義：對所有處於就緒狀態的進程，按一定的原則選擇一個進程準備參與運行；

功能：負責將一個進程插入到就緒隊列並按一定原則排序。

2、分派

含義：當調度時機來到時，從就緒隊列中移出隊首進程並賦予其處理機的使用權。

功能：將指定進程從就緒隊列中移出並建立該進程執行的機器狀態。

可能的進程調度時機

（1）分時系統中時間片用完；

（2）當前進程本身狀態發生轉換：進程終止；進程等待

（3）進程從系統調用中返回用戶態；

（4）系統從中斷處理中返回用戶態；

（5）就緒隊列中出現比當前進程優先順序更高的進程；

（6）在一次出錯陷入之後，該陷入使當前進程在出錯處理時被掛起時；

進程調度方式

按分配處理器的方式，進程調度有兩種方式：

1、非搶佔方式：一旦進程佔用CPU就一直運行，直到終止或等待。

2、搶佔方式：系統強行剝奪已分配給現運行進程的CPU，而重新分配給其他進程運行。

搶佔原則：

時間片原則；
優先權原則；
短作業（進程）優先原則。

搶佔方式的實現機制：

內核完全不可搶先；如winNT，傳統unix
內核部分可搶先：如unix SVR4,linux；
內核完全可搶先：如solaris、win2000。（內核完全可搶先，只是指的不可搶先的內核代碼的數目非常的少，並不是全部都可以搶先。）

各類操作系統對調度方式的選擇：

批處理系統：無須及時的用戶響應，採用不可搶佔的調度方式，或時間間隔很長的可搶佔調度方式，從而允許進程能長時間運行，減少進程的切換次數，提高系統的性能；
互動式系統：及時的用戶響應非常重要，必須採用可搶佔的調度方式。以防單個進程佔用太多CPU時間，影響到其他進程的運行。（基於時間片的搶佔方式）
實時系統：對響應時間要求苛刻，每個進程運行時間很短，可採用可搶佔的調度方式。（基於優先權的可搶佔方式）

進程調度演算法

周轉時間/帶權周轉時間

（1）周轉時間：

從作業進入系統起，直到作業全部運行完成出系統為止，中間所經歷的時間。

平均周轉時間： $T=frac{1}{n}[sum_{i=1}^{i}T_i]$

（2）帶權周轉時間

作業的周轉時間T與系統為它提供服務的時間TS之比，即W=T/TS，稱為帶權周轉時間。

平均帶權周轉時間: $W=frac{1}{n}[sum_{i=1}^{n}frac{T_i}{T_{S_i}}]$

舉個例子，對於如下的作業 J1 和 J2，它們的周轉時間和帶權周轉時間如下：

先來先服務調度演算法（FCFS）

優點：實現簡單；
缺點：對長作業有利，對短作業不利；平均周轉時間可能較長

短作業（進程）優先調度演算法

演算法分類：

非搶佔式調度：
搶佔式調度演算法：

按估計運行時間搶佔
按剩餘運行時間搶佔

（1）非搶佔式調度：

（2）搶佔式調度：按剩餘時間搶佔

優點：使作業的平均周轉時間最短；
缺點：對長作業不利（飢餓狀態）；對緊迫作業不利；估計運行時間不準，難以真正做到短作業（進程）優先。

高優先權優先調度演算法

優先權進程調度演算法的類型：

非強佔式優先權調度演算法
強佔式優先權調度演算法

優先權的設計方法：

靜態優先權：進程創建時確定其優先權，整個生命周期中不改變。這種方式創建簡單，但是不能動態的反映進程特性的變化。

確定依據：

進程類型；
進程對資源的需求；
進程的估計運行時間

動態優先權：進程創建時賦一個優先權初值，運行期間動態調整其權值。具有可防止一個進程長期壟斷或長期等待 CPU 的優點。

動態優先權改變原則：

進程使用CPU超過一定數值時，降低優先順序
進程I/O操作後，增加優先順序
進程等待時間超過一定數值時，提高優先順序

早期linux進程調度演算法：

Linux常採用不設就緒隊列的基於動態優先順序的時間片輪轉調度演算法。每次調度時選擇動態優先順序最高的進程運行。

linux優先順序類型：

靜態優先順序：可以使用 nice() 和 setpriority() 來修改靜態優先順序
動態優先順序：是調度的依據也表示了該進程的時間片長度。

linux動態優先順序改變原則：

每當時鐘中斷髮生時，當前進程的動態優先順序減1，當動態優先順序變為0時，當前進程轉變為就緒態，系統重新進行調度；
當所有就緒進程的動態優先順序都為0時，重新計算所有進程的動態優先順序：
動態優先順序=（當前的動態優先順序/2）取整 + 靜態優先順序

循環輪轉調度演算法：時間片輪轉調度演算法

簡單輪轉法：

時間片大小的確定：

N為就緒隊列中進程數，T為系統響應時間， q為時間片： T=Nq

當時間片很大時，大到一個進程足以完成其全部運行工作所需的時間，此時輪轉調度模式退化為FCFS模式。
當時間片非常小時，調度程序剝奪處理機的次數增多，這將加重了系統開銷，系統性能降低，大多數時間都消耗在處理機的轉換上。

循環輪轉調度演算法的發展

將固定時間片改為可變時間片：每當一輪開始時，系統根據響應時間及當前就緒進程數目重新計算時間片： q=t/n 。這樣不同的進程就會有不同的時間片長度。
將單就緒隊列改為多就緒隊列：如按優先順序組建多個就緒隊列。在調度的時候只需要從高優先順序調度隊列中進行執行即可，可以縮短時間。

多級反饋隊列調度演算法

按調度級別（優先順序）設置多個就緒進程隊列
按優先順序（或就緒隊列）設置不同時間片（同一個就緒隊列中的時間片是相同的，通常優先順序越高的就緒隊列其時間片長度越短。對新進入的進程總是首先插入到最高優先順序的隊列中。）
各級就緒隊列按FIFO組織，FCFS調度，每個進程被調度後運行一個當前隊列的時間片長度。（如果沒有完成就降低它的優先順序，到下一個就緒隊列中等待服務。當低優先順序隊列中的一個進程正在佔用 CPU 進行運行，但是此時高優先順序隊列中有一個新的進程進入，低優先順序進程就需要退回到隊列中，讓新高優先順序進程運行完成再繼續運行。）
最後一級按循環輪轉方式組織調度。

調度演算法設計舉例

（1）進程狀態

運行狀態
低優先就緒狀態
高優先就緒狀態
因I/O而等待狀態

（2）隊列結構

低優先就緒隊列
高優先就緒隊列
因I/O而等待隊列

（3）進程調度演算法：優先調度與時間片調度相結合的調度演算法

當CPU空閑時，若高優先就緒隊列非空，則從高優先就緒隊列中選擇一個進程運行，分配時間片為100ms。
當CPU空閑時，若高優先就緒隊列為空，則從低優先就緒隊列中選擇一個進程運行，分配時間片為500ms。

（4）調度效果：優先照顧 I/O 量大的進程；適當照顧計算量大的進程。