系統中處於就緒狀態的進程對處理機的競爭是由進程調度程式來協調的。調度是依照確定的策略將一批進程排序，從就緒佇列中移出一個進程並給它提供處理機的使用權。
基本介紹
- 中文名：進程調度套用
- 基本狀態：等待、運行、就緒
屬性狀態,處理機,調度方式,算法,進程調度,性能評價,實時調度,
屬性狀態
基本屬性
1、多態性
2、多個不同的進程可以包括相同的程式
3、三種基本狀態 它們之間可進行轉換
基本狀態
1、等待態：等待某個事件的完成；
2、就緒態：等待系統分配處理器以便運行；
3、運行態：占有處理器正在運行。
運行態→等待態 往往是由於等待外設，等待主存等資源分配或等待人工干預而引起的。
等待態→就緒態 則是等待的條件已滿足，只需分配到處理器後就能運行。
運行態→就緒態 不是由於自身原因，而是由外界原因使運行狀態的進程讓出處理器，這時候就變成就緒態。例如時間片用完，或有更高優先權的進程來搶占處理器等。
就緒態→運行態 系統按某種策略選中就緒佇列中的一個進程占用處理器，此時就變成了運行態
處理機
高級、中級和低級調度作業從提交開始直到完成，往往要經歷下述三級調度：
調度方式
非剝奪方式
當有優先權更高的進程轉變為就緒狀態時，仍然讓正在執行的進程繼續執行，直到該進程完成或發生某事
件（如提出I/O請求）而進入“完成”或“阻塞”狀態時，才把處理機分配給“重要而緊迫”的進程，使之執行。
剝奪方式
當有優先權更高的進程轉變為就緒狀態時，便暫停正在執行的進程，立即把處理機分配給高優先權的進程。
採用可剝奪調度方式時，系統中正在運行的進程的優先權一定是最高的。可剝奪調度方式的缺點是系統的開銷比採用非剝奪方式要大，因為，可能增加處理機切換的次數。
算法
先進先出算法
算法總是把處理機分配給最先進入就緒佇列的進程，一個進程一旦分得處理機，便一直執行下去，直到該進程完成或阻塞時，才釋放處理機。
例如，有三個進程P1、P2和P3先後進入就緒佇列，它們的執行期分別是21、6和3個單位時間，
執行情況如下圖：
對於P1、P2、P3的周轉時間為21、27、30，平均周轉時間為26。
可見，FIFO算法服務質量不佳，容易引起作業用戶不滿，常作為一種輔助調度算法。
短進程優先
最短CPU運行期優先調度算法(SCBF--Shortest CPU Burst First)
例如，在就緒佇列中有四個進程P1、P2、P3和P4，它們的下一個執行
進程調度
期分別是16、12、4和3個單位時間，執行情況如下圖：
P1、P2、P3和P4的周轉時間分別為35、19、7、3，平均周轉時間為16。
該算法雖可獲得較好的調度性能，但難以準確地知道下一個CPU執行期，而只能根據每一個進程的執行歷史來預測。
循環輪轉法
簡單輪轉法的優點雖然比較簡單，但由於採用固定時間片和僅有一個就緒佇列，故服務質量是不夠理想的。進一步改善輪轉法的調度性能是沿著一下兩個方向進行的：
①將固定的時間片改為可變時間片，這樣可從固定時間片輪轉法演變為時間片輪轉法；
②將單就緒佇列改為多就緒佇列，從而形成多就緒佇列輪轉法。
多級反饋佇列
多級反饋佇列調度算法採用多就緒佇列結構，每個就緒佇列的優先權按序遞減，而時間片的長度則按序遞增。
進程調度
引起原因
正在執行的進程執行完畢或因發生某事件而不能再繼續執行；
執行中的進程因提出I/O請求而暫停執行；
在進程通信或同步過程中執行了某種原語操作如P操作、阻塞、掛起原語等；
在可剝奪式調度中，有比當前進程優先權更高的進程進入就緒佇列；
在時間片輪轉法中，時間片完；
記錄進程的有關情況
進程控制塊記錄了進程的有關請況和狀態特徵，其內容的變化體現了進程的活動以及系統對進程的控制和
管理。系統中的進程控制模組（包括進程創建、進程撤銷、進程通信等功能模組）通過查詢、修改、記錄進程控制塊PCB結構中有關的數據項的內容，或在不同的佇列中移動PCB結構來實施進程控制的功能。
決定分配策略
進程調度策略實際上是由就緒佇列排序原則體現的。若按優先調度原則，進程就緒佇列按優先權高低排序；若按先來先服務原則，則按進程來到的先後次序排序。入鏈子程式實施這一功能。當處理機空閒時，分派程式只要選擇隊首元素就一定滿足確定的調度原則。
上下文切換
—個進程的上下文(context)包括進程的狀態、有關變數和數據結構的值、機器暫存器的值和PCB以及有關程式、數據等。一個進程的執行是在進程的上下文中執行。當正在執行的進程由於某種原因要讓出處理機時，系統要做進程上下文切換，以使另一個進程得以執行。當進行上下文切換時點統要首先檢查是否允許做上下文切換(在有些情況下，上下文切換是不允許的，例如系統正在執行某個不允許中斷的原語時)。然後，系統要保留有關被切換進程的足夠信息，以便以後切換回該進程時，順利恢復該進程的執行。在系統保留了CPU現場之後，調度程式選擇一個新的處於就緒狀態的進程、並裝配該進程的上下文，使CPU的控制權掌握在被選中進程手中。
進程調度時機的出現情況
①進程完成其任務時；
②在一次系統調用之後，該調用使當前進程暫時不能繼續運行時；
③在一次出錯陷入之後，該陷入使現行進程在出錯處理時被掛起時；
④在分時系統中，當進程使用完規定的時間片，時鐘中斷使該進程讓出處理機時；
⑤在採用可剝奪調度方式的系統中，當具有更高優先權的進程要求處理機時。
兩種占用CPU的方式
不可剝奪式 (不可搶占式non_preemptive)：即使在就緒佇列存在有優先權高於當前執行進程時，當前進程仍將占用處理機直到該進程自己因調用原語操作或等待I/O而進入阻塞、睡眠狀態，或時間片用完時才重新發生調度讓出處理機。
上下切換
進程上下文由正文段、數據段、硬體暫存器的內容以及有關數據結構等組成。硬體暫存器主要包括存放CPU將要執行的下條指令虛擬地址的程式計數器PC，指出機器與進程相關聯的硬體狀態的處理機狀態暫存器PS，存放過程調用(或系統調用)時所傳遞參數的通用暫存器R以及堆疊指針暫存器S等。數據結構則包括PCB等在內的所有與執行該進程有關的管理和控制用表格、數組、鏈等。在發生進程調度時系統要做進程上下文切換。
在進程（上下文）中切換的步驟
@保存處理器的上下文，包括程式計數器和其它暫存器
@用新狀態和其它相關信息更新正在運行進程的PCB(進程狀態控制塊)
@把原來的進程移至合適的佇列-就緒、阻塞
@選擇另一個要執行的進程
@更新被選中進程的PCB
@從被選中進程中重裝入cpu上下文
@把原來的進程移至合適的佇列-就緒、阻塞
@選擇另一個要執行的進程
@更新被選中進程的PCB
@從被選中進程中重裝入cpu上下文
性能評價
進程調度雖然是在系統內部的低級調度，但進程調度的優劣直接影響作業調度的性能。那么，怎樣評價進程調度的優劣呢？反映作業調度優劣的周轉時間和平均周轉時間只在某種程度上反映了進程調度的性能，例如，其執行時間部分中實際上包含有進程等待(包括就緒狀態時的等待)時間，而進程等待時間的多少是要依靠進程調度策略和等待事件何時發生等來決定的。因此，進程調度性能的商量是作業系統設計的一個重要指標。我們說進程調度性能的衡量方法可分為定形和定量兩種。在定形衡量方面，首先是調度的可靠住。包括一次進程調度是否可能引起數據結構的破壞等。這要求我們對調度時機的選擇和保存CPU現場十分謹慎。另外，簡潔性也是衡量進程調度的一個重要指標，由於調度程式的執行涉及到多個進程和必須進行上下文切換，如果調度程式過於繁瑣和複雜，將會耗去較大的系統開銷。這在用戶進程調用系統調用較多的情況下，將會造成回響時間大幅度增加。進程調度的定量評價包括CPU的利用率評價、進程在就緒佇列中的等待時間與執行時間之比等。實際上由於進程進入就緒佇列的隨機模型很難確定，而且進程上下文切換等也將影響進程的執行效率，LL而對進程調度進行解析是很困難的。一般情況下，大多利用模擬或測試系統回響時間的方法來評價進程調度的性能。
實時調度
實時系統與其他作業系統不同在於計算機要能及時回響外部事件的請求，在規定的嚴格時間內完成對該事件的處理，並控制所有實時設備和實時任務協調一致地工作，對於對時間要求嚴格性的不同，實時系統又分為硬實時系統和軟實時系統，其中硬實時系統是指這種時限的要求是絕對的，任何一個實時任務都能夠在時限之前完成；而軟實時系統的要求就沒有這么嚴格，允許偶爾有實時任務不滿足時限的要求.實時系統一般用於嵌入式的系統中，分為實時過程控制和實時通信處理，其中實時過程控制主要用於工業控制，軍事控制領域；時事通信用於電信，銀行，飛機訂票等領域，正是由於在這些特殊領域的運用使得實時作業系統設計時主要追求的是：對外部請求在嚴格時間範圍內做出反應，有高可靠性和完備性.為達到時間要求，進程的調度策略就顯得尤為重要.
基於優先權的進程調度
最簡單最直觀的進程調度策略是基於優先權的調度，多數實時系統採用基於優先權的調度，每個進程根據它重要程度的不同被賦予不同的優先權，調度器在每次調度時，總選擇優先權最高的進程開始執行.首先要考慮的問題是如何分配優先權，對於進程優先權的分配可以採用靜態和動態兩種方式，靜態優先權調度算法：這種調度算法給那些系統中得到運行的所有進程都靜態地分配一個優先權.靜態優先權的分配可以根據套用的屬性來進行，比如進程的周期，用戶優先權，或者其它的預先確定的策略.單調率算法(RM)調度算法是一種典型的靜態優先權調度算法，它根據進程的執行周期的長短來決定調度優先權，那些具有小的執行周期的進程具有較高的優先權.動態優先權調度算法：這種調度算法根據進程的資源需求來動態地分配進程的優先權，其目的就是在資源分配和調度時有更大的靈活性.在實時系統中，最早期限優先算法(EDF)算法是使用最多的一種動態優先權調度算法，該算法給就緒佇列中的各個進程根據它們的截止期限(Deadline)來分配優先權，具有最近的截止期限的進程具有最高的優先權.分配好優先權之後下一個要考慮的問題是何時讓高優先權進程掌握CPU的使用權，這取決於作業系統的核心，有不可搶占式和可搶占式兩種.不可搶占式核心要求每個進程自我放棄CPU的所有權，各個進程彼此合作共享一個CPU.異步事件還是由中斷服務來處理.中斷服務可以使一個高優先權的進程由掛起狀態變為就緒狀態.但中斷服務以後控制權還是回到原來被中斷了的那個進程，直到該進程主動放棄CPU的使用權時，那個高優先權的進程才能獲得CPU的使用權.這就出現了回響時間的問題，高優先權的進程已經進入了就緒狀態但不能執行，這樣進程的回響時間變得不再確定這與實時系統的要求不符，因此一般的實時作業系統都要求是可搶占式的核心，當一個運行著的進程使一個比它優先權高的進程進入了就緒態，當前進程的CPU使用權就被剝奪了，或者說被掛起了，那個高優先權的進程立刻得到了CPU的控制權，如果是中斷服務子程式使一個高優先權的進程進入就緒態，中斷完成時，中斷了的進程被掛起，優先權高的那個進程開始運行.在這種核心設定下，多個進程可能處於並發的狀態，這就出現了多個進程共享資源的情況，因此我們需要設定信號量來保證臨界資源的正確使用，任何一個想使用臨界資源的進程在進入臨界區之前必須擁有使用臨界資源的信號量，否則不可以執行臨界區代碼.這樣基於優先權的可搶占式進程調度策略就基本架構完成，但此時仍然有系統崩潰的危險，假設系統中有3個進程，分別為p1，p2和p3. p1的優先權高於p2，而p2的優先權高於p3.恰在此時p1和p2 因某種原因被阻塞，這時候系統調度p3執行.p3執行一段時間後，p1被喚醒.由於採取的是PBP的調度策略，因此p1搶占 p3的CPU， p1執行.p1執行一段時間後要進入臨界區，但此時p3占有此臨界資源的信號量.因此p1被阻塞，處於等待狀態，等待p3 釋放此信號量.經過這么一段時間後，p2此時此刻處於就緒狀態.因此系統調度p2執行.如果p3在p2的執行期間一直沒有能夠被調度執行的話，那p1和p3將一直等到p2執行完後才能執行，p1更要等到p3釋放它所把持的信號量才能執行；而這段時間完全有可能超出p1的Deadline，使得p1崩潰.我們看到在這個過程中，由於臨界資源的使用問題使得優先權低的進程先於優先權高的進程先執行，這就出現了優先權反轉的問題，從而造成了系統崩潰，對於這個問題可以採用優先權繼承的辦法來進行解決.在優先權繼承方案中，當高優先權進程在等待低優先權的進程占有的信號量時，讓低優先權進程繼承高優先權進程的優先權，即把低優先權進程的優先權提高到高優先權進程的優先權；當低優先權進程釋放高優先權進程等待的信號量時，立即把其優先權降低到原來的優先權.採用這種方法可以有效地解決上面所述的優先權反轉的問題.當高優先權進程p1想要進入臨界區時，由於低優先權進程p3占有這個臨界資源的信號量，導致p1被阻塞.這時候，系統把p3的優先權升到p1的優先權，此時優先權處於p1和p3之間的進程p2，即使處於就緒狀態也不可以被調度執行，因為此時p3的優先權已經高於p2，所以p3此時被調度執行.當p3釋放p1需要的信號量時，系統立即把p3的優先權降到原來的高度，來保證p1和p2正常有序執行.目前，有許多實時系統是採用這種方法來防止優先權反轉的，如VXWORKS.
基於比例共享的進程調度
雖然基於優先權的調度簡單而且易於實現，是目前使用最廣泛的實時系統的進程調度策略，但對於一些軟實時系統而言這種方法不再適用，比如實時多媒體會議，在這種情況下我們可以選擇基於共享的進程調度算法，其基本思想就是按照一定的權重(比例)對一組需要調度的進程進行調度，讓它們的執行時間與它們的權重完全成正比.我們可以通過兩種方法來實現比例共享調度算法：第一種方法是調節各個就緒進程出現在調度佇列隊首的頻率，並調度隊首的進程執行；第二種做法就是逐次調度就緒佇列中的各個進程投入運行，但根據分配的權重調節分配個每個進程的運行時間片。比例共享調度算法的一個問題就是它沒有定義任何優先權的概念；所有的進程都根據它們申請的比例共享CPU資源，當系統處於過載狀態時，所有的進程的執行都會按比例地變慢.所以為了保證系統中實時進程能夠獲得一定的CPU處理時間，一般採用一種動態調節進程權重的方法。
基於時間的進程調度
對於那些具有穩定，已知輸入的簡單系統，可以使用時間驅動的調度算法，它能夠為數據處理提供很好的預測性.這種調度算法本質上是一種設計時就確定下來的離線的靜態調度方法.在系統的設計階段，在明確係統中所有的處理情況下，對於各個進程的開始，切換，以及結束時間等就事先做出明確的安排和設計.這種調度算法適合於那些很小的嵌入式系統，自控系統，感測器等套用環境.這種調度算法的優點是進程的執行有很好的可預測性，但最大的缺點是缺乏靈活性，並且會出現有進程需要被執行而 CPU 卻保持空閒的情況。對於不同要求下的實時系統可以採用不同的進程調度策略來進行設計，也可以將這些方法進行綜合之後得到更適合的調度策略。
