第三章處理機調度與死鎖3.1處理機調度的基本概念3.2調度算法3.3實時調度3.4多處理機系統中的調度3.5產生死鎖的原因和必要條件3.6預防死鎖的方法3.7死鎖的檢測與解除作業的狀態及其轉換批處理系統才有作業的概念，分時系統沒有作業的概念；作業的狀態分為：提交、后備、運行和完成；提交狀態：作業再輸入設備上并準備進入外存輸入井前的狀態。用戶作業通常包括：程序、數據和作業說明書后備狀態：由SPOOLing輸入程序輸入到外存輸入井中，為其建立作業控制塊（JCB），并將JCB插入到后備作業隊列中的狀態運行狀態：作業被作業調度程序選中，由外存輸入井調入到內存，為其分配了所需的資源并建立了進程，此時作業就進入到運行狀態。完成狀態：當作業正常結束或異常終止時，就進入完成狀態。由作業調度程序做收尾工作：撤銷JCB、回收分給該作業的系統資源等。3.1處理機調度的基本概念作業的狀態及其轉換提交后備運行就緒阻塞就緒阻塞完成SPOOLing程序作業調度程序進程調度程序中級調度外存外存輸入井輸入設備內存在多道批處理系統中，一個作業從提交到后備作業隊列，再調入內從經運行到完成，可能需要經歷三級調度：1.高級調度（HighScheduling)

高級調度又稱為作業調度或宏觀調度或長程調度，其主要功能是根據一定的算法，從后備作業隊列（一批作業）中選出若干個作業調入內存，并為它們創建進程和分配必要的資源，然后將創建的新進程放入進程就緒隊列中，使其處于就緒狀態。當作業運行結束時，還要做一些善后工作（資源回收）3.1.1處理機調度的層次高級調度特點：1）多道批處理系統需要作業調度；分時系統和實時系統一般不需要高級調度。2）每次調度多少作業（程序）？需由系統規定的多道程序度而定；3）調度那些作業？由調度算法（策略）而定，如先來先服務，短作業優先調度，優先權調度算法等。2.中級調度(Intermediate-LevelScheduling)中級調度又稱之為中程調度(Medium-TermScheduling)，中級調度主要任務是實施進程在內、外存間的交換；中級調度的主要功能是在內存使用緊張時，將一些暫時不能運行的進程從內存對換到外存上等待（此時的進程狀態稱為掛起狀態或駐留外存狀態）。以后，當外存有足夠的空閑空間時，再將合適的進程重新換入內存，等待進程調度。引入中級調度的主要目的是為了提高內存的利用率和系統吞吐量。

3.低級調度(LowLevelScheduling)低級調度又稱進程調度或微觀調度或短程調度，其主要功能是根據一定的算法，將CPU分派給就緒進程隊列中的某一進程。執行低級調度功能的程序稱為進程調度程序，由它實現CPU在進程間的切換。進程調度是操作系統中最基本的一種調度，在一般操作系統（包括：多道批處理系統、分時系統和實時系統）中都必須有進程調度，而且它的策略的優劣直接影響整個系統的性能。4、進程調度方式

非搶占方式（Nonpreemptive）：在這種調度方式下，一旦一個進程被選中運行，它就一直運行下去，直到它運行結束并自愿放棄CPU，或者因等待某一事件而被阻塞或終止時為止，才把CPU出讓給其他進程，即得到CPU的進程不管運行多長時間，都一直運行下去，不會因為當前進程以外的原因而被迫讓出CPU。引起調度的原因：1）當前進程運行結束或發生某事件而終止；2）當前進程因提出I/O請求而阻塞；3）進程之間通信或同步而由于執行原語而等待。搶占方式（Preemptive）：搶占方式允許調度程序根據某種策略中止當前進程的執行，將其移入就緒隊列，并將處理機分派給另一個進程使之投入運行。

搶占原則：1）優先權原則：允許高優先權進程搶占低優先權的CPU；2）短作業原則：允許短進程搶占長進程的處理機；3）時間片原則：分時系統中的當前進程，若時間片規定的時間用完，不管是否運行結束，都要立即中止放到就緒隊列中，再將CPU分派給其它進程。3.1.2調度隊列模型 不同OS對高級、中級和低級調度的選取形成了不同的調度隊列模型，共有3種類型。1、僅有進程調度的調度隊列模型

常在分時系統中設置僅有進程調度的調度隊列模型。終端用戶的登錄注冊以及交互命令的輸入執行，系統都將為其建立進程，并放在FIFO就緒隊列中，按照時間片輪轉調度執行。進程的調度和變化過程如下圖所示。圖3-1僅具有進程調度的調度隊列模型P1P2P42.具有高級和低級調度的調度隊列模型在批處理系統中，不僅需要進程調度，而且還需要作業調度。若OS中僅包含高級調度和低級調度就形成了具有高級和低級調度的隊列模型。進程調度常以最高優先權優先調度算法，就緒隊列形式為優先權隊列。阻塞隊列按照不同事件排隊就緒隊列進程調度CPU進程完成等待事件1作業調度事件1出現時間片完等待事件2事件2出現……等待事件n事件n出現后備隊列……3.同時具有三級調度的調度隊列模型作業CPU就緒掛起隊列阻塞掛起隊列阻塞隊列就緒隊列時間片到進程調度作業調度調入中級調度事件出現交互式用戶等待事件進程完成掛起調出掛起調出事件出現

具有三級調度時的調度隊列模型3.1.3選擇調度方式和調度算法的若干準則1.面向用戶的準則周轉時間短：周轉周期是指作業從提交給系統開始，到作業完成為止所消耗的時間。常用于衡量系統性能、作業調度算法的優劣的重要指標。可把平均周轉時間描述為：作業的周轉時間T與系統為它提供服務的時間TS之比，即W=T/TS，稱為帶權周轉時間，而平均帶權周轉時間則可表示為:響應時間快：分時系統性能的主要評價指標。響應時間指用戶從鍵盤鍵入一個命令開始，到系統首次給出響應信息為止這段時間。截止時間的保證：評價實時系統性能的重要指標。截止時間是指系統為處理某事件/任務必須開始執行的最遲時間，或必須完成的最遲時間。優先權準則：批處理、分時和實時系統中的調度算法都應該遵循的原則。這種調度思想就是“急事急辦”，優先權高者為急。2.面向系統的準則系統吞吐量高：評價批處理系統整體性能的重要指標。吞吐量是指單位時間內系統所完成的作業數。作業調度算法對系統吞吐量有直接影響，選擇確定時應考慮這一準則。處理機利用率好：CPU的利用率是衡量大中型系統性能的重要指標。各類資源的平衡利用：選擇適當調度算法，保證各種資源的利用都處于忙碌狀態。3.2調度算法1、先來先服務（FCFS）調度算法適應范圍：適應作業調度和進程調度；調度過程：FCFS用于作業（進程）調度時，從后備（就緒）隊列中選擇若干或一個先到來的作業（進程）投入運行。進程在分派到CPU進入運行過程中，只有當進程運行結束或因某事件發生而被阻塞才放棄CPU。算法特點：算法容易實現，但效率不高；只顧及作業等候時間，沒考慮作業要求服務時間的長短，不利于短作業而優待了長作業；作業調度不分輕重緩急，人人平等；FCFS為非搶占式調度。先來先服務（FCFS）調度算法效率舉例表注：周轉時間=完成時間-到達時間；帶權周轉時間=周轉時間/服務時間2、短作業/進程（SJF/SPF）優先調度算法適應范圍：適應作業調度和進程調度。SJF/SPF算法以進入系統的作業/進程所要求的CPU時間為標準，總選取估計計算時間最短的作業/進程投入運行。算法特點：算法易于實現，效率不高；忽視長作業等待時間，會出現饑餓現象；不考慮緊迫作業/進程的需求；長短時間人為估計，不可靠，會出現以長亂短。SPF算法類型：搶占或非搶占式。搶占式SPF調度算法在新進程進入就緒隊列時，將其運行時間與當前進程的剩余運行時間相比，若更短時，可搶占CPU；非搶占式SPF算法允許當前運行進程先執行直到釋放CPU為止。可搶占SPF調度有時稱為最短剩余時間優先（shortest-remaining-time-first）調度。

FCFS和SJF調度算法的性能分析

例題：假如5個就緒進程其到達系統和所需CPU時間如下表所示（單位：毫秒），如果忽略I/O以及其他開銷，分別計算采用FCFS、非搶占式SPF和搶占式SPF調度算法進行CPU調度的平均周轉時間和平均帶權周轉時間。進程到達和運行時間進程到達時間運行時間A03B26C44D65E82解答如下：（1）采用FCFS的調度順序為：ABCDE039131820平均周轉時間為：

T=((3-0)+(9-2)+(13-4)+(18-6)+(20-8))/5=8.6帶權平均周轉時間為：W=2.56（2）采用非搶占SJF的調度順序為：ABECD039111520平均周轉時間為：T=7.6帶權平均周轉時間為：W=1.84（3）采用搶占SJF的調度順序為：平均周轉時間為：T=7.2帶權平均周轉時間為：W=1.59AB1ECB2038101520D43、高優先權優先調度算法（priority-schedulingalgorithm）

1）優先權調度算法的類型非搶占式優先權算法：在此方式下，系統一旦把CPU分配給就緒隊列中優先權最高的進程后，該進程便一直執行下去，直至完成或因發生某事件使該進程放棄處理機時，系統方可再將處理機重新分配給就緒隊列中另一優先權最高的進程。這種調度算法主要用于批處理系統中；也可用于某些對實時性要求不嚴的實時系統中。搶占式優先權算法：在此方式下，系統把處理機分配給優先權最高的進程使之執行。但在其執行期間，只要又有更高優先權新進程進入就緒隊列，進程調度程序就立即停止當前進程的執行，重新將處理機分配給新到的優先權最高的進程。適應較嚴格的實時系統、性能要求較高的批處理和分時系統。2）優先權的類型靜態優先權靜態優先權是在創建進程時確定的，且在進程的整個運行期間保持不變。一般地，優先權是利用某一范圍內的一個整數來表示的，例如，0~9中的某一整數，又把該整數稱為優先數。

優先權的確定準則：系統進程者優先；資源需求少者優先；用戶需求緊迫者優先。動態優先權：動態優先權是指在創建進程時所賦予的優先權，可以隨進程的推進而改變的，以便獲得更好的調度性能。（如等待時間與優先權成正比）4、高響應比優先調度算法動態優先權的變化規律可描述為：系統對作業的響應時間=等待時間+服務時間，故該優先權又相當于響應比RP。據此，優先權變化規律又可表示為：高響應比優先調度算法特點：如果作業的等待時間相同，則要求服務的時間愈短，其優先權愈高，因而該算法有利于短作業；當要求服務的時間相同時，作業的優先權決定于其等待時間，等待時間愈長，其優先權愈高，因而它實現的是先來先服務；對于長作業，作業的優先級可以隨等待時間的增加而提高，當其等待時間足夠長時，其優先級便可升到很高，從而也可獲得處理機，避免了長作業饑餓現象。5、基于時間片的輪轉調度算法

時間片調度算法適用于分時系統。劃分為時間片輪轉和多級反饋隊列調度算法1）時間片輪轉法輪轉法調度做法是：系統將所有的就緒進程按FIFO原則排隊，每次調度時，把CPU分配給隊首進程，并令其執行一個時間片（如20ms）。當執行的時間片用完時，停止該進程的執行，并將它送往就緒隊尾；然后，再把處理機分配給就緒隊列中新的隊首進程，同時也讓它執行一個時間片。如此反復和輪轉，就可以保證就緒隊列中的所有進程，在一給定的時間內，均能獲得一時間片的處理機執行時間。FCBA

….CPUA

BC時間片輪轉算法圖示完成2）多級反饋隊列調度算法多級反饋隊列調度算法是目前公認的一種性能比較優良的調度算法，兼備了前述各種算法的優點。原理如下：設置多個就緒隊列，并賦予不同的優先級和時間片：第一個隊列的優先級最高，第二個隊列次之，其余各隊列的優先權逐個降低。該算法賦予各個隊列中進程執行時間片的大小也各不相同，在優先權愈高的隊列中，為每個進程所規定的執行時間片就愈小。圖3-5是多級反饋隊列算法的示意。多級反饋隊列調度算法新進程進入（64ms）調度原則：當一個新進程進入內存后，首先將它放入第一隊列的末尾，按FCFS原則等待調度。當輪到該進程執行時，如它能在該時間片內完成，便可準備撤離系統；如果它在一個時間片結束時尚未完成，調度程序便將該進程轉入第二隊列的末尾，再同樣地按FCFS原則等待調度執行；如果它在第二隊列中運行一個時間片后仍未完成，再依次將它放入第三隊列，……，如此下去，當一個長作業(進程)從第一隊列依次降到第n隊列后，在第n隊列中便采取按時間片輪轉的方式運行。搶占原則：僅當第一隊列空閑時，調度程序才調度第二隊列中的進程運行；僅當第1~i隊列均空時，才會調度第i+1隊列中的進程運行。如果處理機正在第i隊列中為某進程服務時，又有新進程進入優先權較高的隊列(第1~(i-1)中的任何一個隊列)，則此時新進程將搶占正在運行進程的處理機，即由調度程序把正在運行的進程放回到第i隊列的末尾，把處理機分配給新到的高優先權進程。多級反饋隊列調度算法的性能與特點終端型作業用戶：短小作業及時完成，用戶滿意。(2)短批處理作業用戶：短作業優先運行結束。(3)長批處理作業用戶：不出現饑餓現象。作業3-1P101：1、4、6、73.3實時調度3.3.1實現實時調度的基本條件為了實現對實時進程進行有效調度，系統必須滿足下述條件：1.提供必要的信息就緒時間：進程進入就緒狀態的開始時間，有周期性和非周期性開始截止時間和完成截止時間：開始處理或完成任務的最遲時間處理時間：指一個進程從開始執行到完成需要的處理時間；資源要求：指處理一個任務時所需要的資源；優先級：用于標識一個任務得到處理的輕重緩急。實時調度：在實時操作系統中，實現實時進程或任務的調度。實時調度強調對實時進程或任務處理（響應）的及時性和緊迫性。2.系統處理能力強在實時系統中，通常都有多個實時任務（進程）等待計算機及時處理。處理機能力必須滿足：假定系統中有m個周期性的硬實時任務，它們的處理時間分別Ci，周期時間分別為Pi，則在單處理機情況下，其處理能力必須滿足條件：處理機滿足此條件時，才是可調度的；否則，調度不過來。多處理機情況下，需要滿足條件為：（N為處理機個數）3、采用搶占式調度機制當一個優先權更高的任務到達時，允許將當前任務暫時停止，而令高優先權任務立即投入運行，這樣便可滿足該硬實時任務對截止時間的要求。但這種調度機制比較復雜。4、具有快速切換機制對外部中斷的快速響應能力：外部任務來到時能快速響應；快速的任務分派能力：在完成任務調度后，便應進行任務切換。3.3.2實時調度算法的分類1.非搶占式調度算法非搶占式輪轉調度算法：控制多個相同對象；每對象一個實時進程；建立一個FIFO進程就緒隊列，按照FCFS輪轉調度。調度性能：實現數秒至數十秒響應時間，適應不嚴格的實時控制。非搶占式優先調度算法：就緒隊列按優先級進隊排序，調度始終先調度隊首進程。調度性能：可能獲得數秒至數百毫秒的響應時間，適應有一定要求的實時控制系統實時調度算法的分類方式較多：如按照任務性質分為硬實時調度和軟實時調度；按照調度方式分為搶占方式和非搶占方式調度等2.搶占式調度算法基于時鐘中斷的搶占式優先權調度算法：如果有比當前進程優先級更高的進程到來，需等到時鐘中斷到來時搶占CPU。調度性能：響應達到幾十毫秒至幾毫秒，適應大多數控制系統。立即搶占(ImmediatePreemption)的優先權調度算法：如果有比當前進程優先級更高的進程到來，若當前進程不處在臨界區，則立即搶占CPU。調度性能：調度延遲為幾毫秒至100微秒。非搶占實時進程調度示意圖(a)非搶占輪轉調度調度時間進程

1進程

2實時進程要求調度進程

n實時進程調度實時進程運行(b)非搶占優先權調度當前進程實時進程實時進程請求調度當前進程運行完成調度時間搶占實時進程調度示意圖當前進程實時進程實時進程請求調度實時進程槍占當前進程，并立即執行(d)立即搶占的優先權調度當前進程