進程調度

出自 MBA智库百科(https://wiki.mbalib.com/)

進程調度（Process Scheduling）

　　進程調度是指操作系統按某種策略或規則選擇進程占用CPU進行運行的過程。

　　無論是在批處理系統還是分時系統中，用戶進程數一般都多於處理機數、這將導致它們互相爭奪處理機。另外，系統進程也同樣需要使用處理機。這就要求進程調度程式按一定的策略，動態地把處理機分配給處於就緒隊列中的某一個進程，以使之執行。進程調度雖然是在系統內部的低級調度，但進程調度的優劣直接影響作業調度的性能。評價進程調度的優劣如反映作業調度優劣的周轉時間和平均周轉時間只在某種程度上反映了進程調度的性能，例如，其執行時間部分中實際上包含有進程等待(包括就緒狀態時的等待)時間，而進程等待時間的多少是要依靠進程調度策略和等待事件何時發生等來決定的。因此，進程調度性能的商量是操作系統設計的一個重要指標。

　　進程調度性能的衡量方法可分為定形和定量兩種。在定形衡量方面，首先是調度的可靠性。包括一次進程調度是否可能引起數據結構的破壞等。這要求我們對調度時機的選擇和保存CPU現場十分謹慎。另外，簡潔性也是衡量進程調度的一個重要指標，由於調度程式的執行涉及到多個進程和必須進行上下文切換，如果調度程式過於繁瑣和複雜，將會耗去較大的系統開銷。這在用戶進程調用系統調用較多的情況下，將會造成響應時間大幅度增加。

　　進程調度的定量評價包括CPU的利用率評價、進程在就緒隊列中的等待時間與執行時間之比等。實際上由於進程進入就緒隊列的隨機模型很難確定，而且進程上下文切換等也將影響進程的執行效率，LL而對進程調度進行解析是很困難的。一般情況下，大多利用模擬或測試系統響應時間的方法來評價進程調度的性能。

　　其基本屬性有多態性 從誕生、運行，直至消滅；多個不同的進程可以包括相同的程式；三種基本狀態 它們之間可進行轉換；併發性併發執行的進程輪流占用處理器。

　　進程對將系統中各進程的執行情況和狀態特征記錄在各進程的PCB表中。並且，根據各進程的狀態特征和資源需求等、進程管理模塊還將各進程的PCB表排成相應的隊列併進行動態隊列轉接。進程調度模塊通過PCB變化來掌握系統中存在的所有進程的執行情況和狀態特征，併在適當的時機從就緒隊列中選擇出一個進程占據處理機。

• 選擇占有處理機的進程

　　進程調度的主要功能是按照一定的策略選擇—個處於就緒狀態的進程，使其獲得處理機執行。根據不同的系統設計目的，有各種各樣的選擇策略，例如系統開銷較少的靜態優先數調度法，適合於分時系統的輪轉法(Round RoLin)和多級互饋輪轉法(Round Robin with Multip1e feedback)等。這些選擇策略決定了調度演算法的性能。

• 進行進程上下文切換

　　—個進程的上下文(context)包括進程的狀態、有關變數和數據結構的值、機器寄存器的值和PCB以及有關程式、數據等。一個進程的執行是在進程的上下文中執行。當正在執行的進程由於某種原因要讓出處理機時，系統要做進程上下文切換，以使另一個進程得以執行。當進行上下文切換時點統要首先檢查是否允許做上下文切換(在有些情況下，上下文切換是不允許的，例如系統正在執行某個不允許中斷的原語時)。然後，系統要保留有關被切換進程的足夠信息，以便以後切換回該進程時，順利恢復該進程的執行。在系統保留了CPU現場之後，調度程式選擇一個新的處於就緒狀態的進程、並裝配該進程的上下文，使CPU的控制權掌握在被選中進程手中。

　　進程上下文由正文段、數據段、硬體寄存器的內容以及有關數據結構等組成。硬體寄存器主要包括存放CPU將要執行的下條指令虛擬地址的程式計數器PC，指出機器與進程相關聯的硬體狀態的處理機狀態寄存器PS，存放過程調用(或系統調用)時所傳遞參數的通用寄存器R以及堆棧指針寄存器S等。數據結構則包括PCB等在內的所有與執行該進程有關的管理和控制用表格、數組、鏈等。在發生進程調度時系統要做進程上下文切換。

• 先進先出演算法

　　演算法總是把處理機分配給最先進入就緒隊列的進程，一個進程一旦分得處理機，便一直執行下去，直到該進程完成或阻塞時，才釋放處理機。 例如，有三個進程P1、P2和P3先後進入就緒隊列，它們的執行期分別是21、6和3個單位時間，對於P1、P2、P3的周轉時間為21、27、30，平均周轉時間為26。可見，FIFO演算法服務質量不佳，容易引起作業用戶不滿，常作為一種輔助調度演算法。

• 短進程優先

　　最短CPU運行期優先調度演算法(SCBF--Shortest CPU Burst First)，該演算法從就緒隊列中選出下一個“CPU執行期最短”的進程，為之分配處理機。例如，在就緒隊列中有四個進程P1、P2、P3和P4，它們的下一個執行期分別是16、12、4和3個單位時間，執行情況如下：P1、P2、P3和P4的周轉時間分別為35、19、7、3，平均周轉時間為16。該演算法雖可獲得較好的調度性能，但難以準確地知道下一個CPU執行期，而只能根據每一個進程的執行歷史來預測。

• 輪轉法

　　前幾種演算法主要用於批處理系統中，不能作為分時系統中的主調度演算法，在分時系統中，都採用時間片輪轉法。

　　簡單輪轉法：系統將所有就緒進程按FIFO規則排隊，按一定的時間間隔把處理機分配給隊列中的進程。這樣，就緒隊列中所有進程均可獲得一個時間片的處理機而運行。

• 多級隊列方法：將系統中所有進程分成若幹類，每類為一級。
• 多級反饋隊列：多級反饋隊列方式是在系統中設置多個就緒隊列，並賦予各隊列以不同的優先權。

　　進程調度發生的時機與引起進程調度的原因以及進程調度的方式有關。

1. 正在執行的進程執行完畢。這時，如果不選擇新的就緒進程執行，將浪費處理機資源。
2. 執行中進程自己調用阻塞原語將自己阻塞起來進入睡眠等狀態。
3. 執行中進程調用了P原語操作，從而因資源不足而被阻塞；或調用了v原語操作激活了等待資源的進程隊列。
4. 執行中進程提出I/O請求後被阻塞。
5. 在分時系統中時間片已經用完。
6. 在執行完系統調用等系統程式後返回用戶進程時，這時可看作系統進程執行完畢，從而可調度選擇一新的用戶進程執行。
7. 就緒隊列中的某進程的優先順序變得高於當前執行進程的優先順序，從而也將引發進程調度。

　　以上都是在可剝奪方式下的引起進程調度的原因。在CPU執行方式是可剝奪時，還有進程調度的調度方法包括非剝奪式的調度和可剝奪式的調度，在可剝奪式調度中有時間片輪轉方法、優先順序調度方法、彩票調度、多級隊列調度方法。如兩種占用CPU的方式：

1. 非剝奪方式，分派程式一旦把處理機分配給某進程後便讓它一直運行下去，直到進程完成或發生。不可剝奪式即不可搶占式non_preemptive，即使在就緒隊列存在有優先順序高於當前執行進程時，當前進程仍將占用處理機直到該進程自己因調用原語操作或等待I/O而進入阻塞、睡眠狀態，或時間片用完時才重新發生調度讓出處理機。
2. 剝奪方式，當一個進程正在運行時，系統可以基於某種原則，剝奪已分配給它的處理機，將之分配給其它進程。剝奪原則有：優先權原則、短進程優先原則、時間片原則。可剝奪式即可搶占式preemptive，就緒隊列中一旦有優先順序高於當前執行進程優先順序的進程存在時，便立即發生進程調度，轉讓處理機。

　　（1）作業調度是從作業後備隊列選擇一個或多個作業，為其分配必要的資源，併為之創建進程，做好運行前的準備。按照一定的作業調度演算法，從後備作業隊列中選擇一個或幾個作業調入記憶體。

　　（2）進程調度是指從已經進入記憶體的進程的就緒隊列中選擇一個進程真正占有CPU，併為其運行進行上下文轉換，讓其立即運行。按照一定的進程調度演算法，從記憶體的進程中選擇一個進程，將處理機分配給它，使其執行。

　　（3）作業調度是主要解決進程真正在CPU上運行的問題。進程調度是主要解決作業有無資格占有CPU的問題。

• 地址寄存器
• 碼頭調度