第3章 處理機調(diào)度與死鎖(1-2)

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

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

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

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

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

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

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

FCFS和SJF調(diào)度算法的性能分析

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

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

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

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

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

….CPUA

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

1進程

2實時進程要求調(diào)度進程

n實時進程調(diào)度實時進程運行(b)非搶占優(yōu)先權(quán)調(diào)度當前進程實時進程實時進程請求調(diào)度當前進程運行完成調(diào)度時間搶占實時進程調(diào)度示意圖當前進程實時進程實時進程請求調(diào)度實時進程槍占當前進程，并立即執(zhí)行(d)立即搶占的優(yōu)先權(quán)調(diào)度當前進程