計算機進程調度

系統中處於就緒狀態的進程對處理機的競爭是由進程調度程式來協調的。調度是依照確定的策略將一批進程排序，從就緒佇列中移出一個進程並給它提供處理機的使用權。

基本介紹

• 中文名：計算機進程調度
• 基本狀態：等待、運行、就緒

基本屬性

1.多態性

2.多個不同的進程可以包括相同的程式

3.三種基本狀態 它們之間可進行轉換

基本狀態

1.等待態：等待某個事件的完成；

2.就緒態：等待系統分配處理器以便運行；

3.運行態：占有處理器正在運行。

運行態→等待態 往往是由於等待外設，等待主存等資源分配或等待人工干預而引起的。

等待態→就緒態 則是等待的條件已滿足，只需分配到處理器後就能運行。

運行態→就緒態 不是由於自身原因，而是由外界原因使運行狀態的進程讓出處理器，這時候就變成就緒態。例如時間片用完，或有更高優先權的進程來搶占處理器等。

就緒態→運行態 系統按某種策略選中就緒佇列中的一個進程占用處理器，此時就變成了運行態

處理機

高級、中級和低級調度作業從提交開始直到完成，往往要經歷下述三級調度：

高級調度：(High-Level Scheduling)又稱為作業調度，它決定把後備作業調入記憶體運行；

低級調度：(Low-Level Scheduling)又稱為進程調度，它決定把就緒佇列的某進程獲得CPU；

中級調度：(Intermediate-Level Scheduling)又稱為在虛擬存儲器中引入，在內、外存對換區進行進程對換。

調度方式

非剝奪方式

當有優先權更高的進程轉變為就緒狀態時，仍然讓正在執行的進程繼續執行，直到該進程完成或發生某事

件（如提出I/O請求）而進入“完成”或“阻塞”狀態時，才把處理機分配給“重要而緊迫”的進程，使之執行。

剝奪方式

當有優先權更高的進程轉變為就緒狀態時，便暫停正在執行的進程，立即把處理機分配給高優先權的進程。

採用可剝奪調度方式時，系統中正在運行的進程的優先權一定是最高的。可剝奪調度方式的缺點是系統的開銷比採用非剝奪方式要大，因為，可能增加處理機切換的

算法

先進先出算法

算法總是把處理機分配給最先進入就緒佇列的進程，一個進程一旦分得處理機，便一直執行下去，直到該進程完成或阻塞時，才釋放處理機。

例如，有三個進程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規則排隊，按一定的時間間隔把處理機分配給佇列中的進程。這樣，就緒佇列中所有進程均可獲得一個時間片的處理機而運行。

簡單輪轉法的優點雖然比較簡單，但由於採用固定時間片和僅有一個就緒佇列，故服務質量是不夠理想的。進一步改善輪轉法的調度性能是沿著一下兩個方向進行的：

①將固定的時間片改為可變時間片，這樣可從固定時間片輪轉法演變為時間片輪轉法；

②將單就緒佇列改為多就緒佇列，從而形成多就緒佇列輪轉法。

多級反饋佇列

多級反饋佇列調度算法採用多就緒佇列結構，每個就緒佇列的優先權按序遞減，而時間片的長度則按序遞增。

進程調度的實現

引起原因

正在執行的進程執行完畢或因發生某事件而不能再繼續執行；

執行中的進程因提出I/O請求而暫停執行；

在進程通信或同步過程中執行了某種原語操作如P操作、阻塞、掛起原語等；

在可剝奪式調度中，有比當前進程優先權更高的進程進入就緒佇列；

在時間片輪轉法中，時間片完；

△通常系統是按先來先服務或優先權形式來組織調度佇列。

其中，RQ為就緒佇列指針，EP為運行佇列指針。

進程調度功能

記錄進程的有關情況

進程控制塊記錄了進程的有關請況和狀態特徵，其內容的變化體現了進程的活動以及系統對進程的控制和

管理。系統中的進程控制模組（包括進程創建、進程撤銷、進程通信等功能模組）通過查詢、修改、記錄進程控制塊PCB結構中有關的數據項的內容，或在不同的佇列中移動PCB結構來實施進程控制的功能。

決定分配策略

進程調度策略實際上是由就緒佇列排序原則體現的。若按優先調度原則，進程就緒佇列按優先權高低排序；若按先來先服務原則，則按進程來到的先後次序排序。入鏈子程式實施這一功能。當處理機空閒時，分派程式只要選擇隊首元素就一定滿足確定的調度原則。

進行進程上下文切換

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

進程調度時機

進程調度時機可能出現的情況

①進程完成其任務時；

②在一次系統調用之後，該調用使當前進程暫時不能繼續運行時；

③在一次出錯陷入之後，該陷入使現行進程在出錯處理時被掛起時；

④在分時系統中，當進程使用完規定的時間片，時鐘中斷使該進程讓出處理機時；

⑤在採用可剝奪調度方式的系統中，當具有更高優先權的進程要求處理機時。

兩種占用CPU的方式

可剝奪式 (可搶占式preemptive)：就緒佇列中一旦有優先權高於當前執行進程優先權的進程存在時，便立即發生進程調度，轉讓處理機。

不可剝奪式 (不可搶占式non_preemptive)：即使在就緒佇列存在有優先權高於當前執行進程時，當前進程仍將占用處理機直到該進程自己因調用原語操作或等待I/O而進入阻塞、睡眠狀態，或時間片用完時才重新發生調度讓出處理機。

上下切換

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

在進程（上下文）中切換的步驟

@保存處理器的上下文，包括程式計數器和其它暫存器

@用新狀態和其它相關信息更新正在運行進程的PCB(進程狀態控制塊)
@把原來的進程移至合適的佇列-就緒、阻塞
@選擇另一個要執行的進程 　
@更新被選中進程的PCB 　
@從被選中進程中重裝入cpu上下文

性能評價

進程調度雖然是在系統內部的低級調度，但進程調度的優劣直接影響作業調度的性能。那么，怎樣評價進程調度的優劣呢？反映作業調度優劣的周轉時間和平均周轉時間只在某種程度上反映了進程調度的性能，例如，其執行時間部分中實際上包含有進程等待(包括就緒狀態時的等待)時間，而進程等待時間的多少是要依靠進程調度策略和等待事件何時發生等來決定的。因此，進程調度性能的商量是作業系統設計的一個重要指標。我們說進程調度性能的衡量方法可分為定形和定量兩種。在定形衡量方面，首先是調度的可靠住。包括一次進程調度是否可能引起數據結構的破壞等。這要求我們對調度時機的選擇和保存CPU現場十分謹慎。另外，簡潔性也是衡量進程調度的一個重要指標，由於調度程式的執行涉及到多個進程和必須進行上下文切換，如果調度程式過於繁瑣和複雜，將會耗去較大的系統開銷。這在用戶進程調用系統調用較多的情況下，將會造成回響時間大幅度增加。進程調度的定量評價包括CPU的利用率評價、進程在就緒佇列中的等待時間與執行時間之比等。實際上由於進程進入就緒佇列的隨機模型很難確定，而且進程上下文切換等也將影響進程的執行效率，LL而對進程調度進行解析是很困難的。一般情況下，大多利用模擬或測試系統回響時間的方法來評價進程調度的性能。