計算機操作系統(tǒng)_03處理機調(diào)度與死鎖

1、第三章處理機調(diào)度與死鎖 第三章處理機調(diào)度與死鎖 3.1 處理機調(diào)度的層次處理機調(diào)度的層次3.2 調(diào)度隊列模型和調(diào)度準則調(diào)度隊列模型和調(diào)度準則3.3 調(diào)度算法調(diào)度算法3.4 實時調(diào)度實時調(diào)度 3.5 產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件3.6 預防死鎖的方法預防死鎖的方法3.7 死鎖的檢測與解除死鎖的檢測與解除 第三章處理機調(diào)度與死鎖 3.1處理機調(diào)度的層次處理機調(diào)度的層次 3.1.13.1.1高級調(diào)度高級調(diào)度1 1作業(yè)和作業(yè)步作業(yè)和作業(yè)步(1) 作業(yè)(Job)。作業(yè)是一個比程序更為廣泛的概念，它不僅包含了通常的程序和數(shù)據(jù)，而且還應(yīng)配有一份作業(yè)說明書，系統(tǒng)根據(jù)該說明書來對程序的運行進

2、行控制。在批處理系統(tǒng)中，是以作業(yè)為基本單位從外存調(diào)入內(nèi)存的。 第三章處理機調(diào)度與死鎖 (2) 作業(yè)步(Job Step)。通常，在作業(yè)運行期間，每個作業(yè)都必須經(jīng)過若干個相對獨立，又相互關(guān)聯(lián)的順序加工步驟才能得到結(jié)果，我們把其中的每一個加工步驟稱為一個作業(yè)步，各作業(yè)步之間存在著相互聯(lián)系，往往是把上一個作業(yè)步的輸出作為下一個作業(yè)步的輸入。例如，一個典型的作業(yè)可分成三個作業(yè)步： “編譯”作業(yè)步，通過執(zhí)行編譯程序?qū)υ闯绦蜻M行編譯，產(chǎn)生若干個目標程序段； “連結(jié)裝配”作業(yè)步，將“編譯”作業(yè)步所產(chǎn)生的若干個目標程序段裝配成可執(zhí)行的目標程序； “運行”作業(yè)步，將可執(zhí)行的目標程序讀入內(nèi)存并控制其運行。(3)

3、作業(yè)流。若干個作業(yè)進入系統(tǒng)后，被依次存放在外存上，這便形成了輸入的作業(yè)流；在操作系統(tǒng)的控制下，逐個作業(yè)進行處理，于是便形成了處理作業(yè)流。 第三章處理機調(diào)度與死鎖 2 2作業(yè)控制塊作業(yè)控制塊JCB(Job Control Block)JCB(Job Control Block)為了管理和調(diào)度作業(yè)，在多道批處理系統(tǒng)中為每個作業(yè)設(shè)置了一個作業(yè)控制塊，如同進程控制塊是進程在系統(tǒng)中存在的標志一樣，它是作業(yè)在系統(tǒng)中存在的標志，其中保存了系統(tǒng)對作業(yè)進行管理和調(diào)度所需的全部信息。在JCB中所包含的內(nèi)容因系統(tǒng)而異，通常應(yīng)包含的內(nèi)容有：作業(yè)標識、用戶名稱、用戶帳戶、作業(yè)類型(CPU 繁忙型、I/O 繁忙型、批量型

4、、終端型)、作業(yè)狀態(tài)、調(diào)度信息(優(yōu)先級、作業(yè)已運行時間)、資源需求(預計運行時間、要求內(nèi)存大小、要求I/O設(shè)備的類型和數(shù)量等)、進入系統(tǒng)時間、開始處理時間、作業(yè)完成時間、作業(yè)退出時間、資源使用情況等。 第三章處理機調(diào)度與死鎖 每當作業(yè)進入系統(tǒng)時，系統(tǒng)便為每個作業(yè)建立一個JCB，根據(jù)作業(yè)類型將它插入相應(yīng)的后備隊列中。作業(yè)調(diào)度程序依據(jù)一定的調(diào)度算法來調(diào)度它們，被調(diào)度到的作業(yè)將會裝入內(nèi)存。在作業(yè)運行期間，系統(tǒng)就按照JCB中的信息對作業(yè)進行控制。當一個作業(yè)執(zhí)行結(jié)束進入完成狀態(tài)時，系統(tǒng)負責回收分配給它的資源，撤消它的作業(yè)控制塊。 第三章處理機調(diào)度與死鎖 3 3作業(yè)調(diào)度作業(yè)調(diào)度作業(yè)調(diào)度的主要功能是根據(jù)作業(yè)

5、控制塊中的信息，審查系統(tǒng)能否滿足用戶作業(yè)的資源需求，以及按照一定的算法，從外存的后備隊列中選取某些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進程、分配必要的資源。然后再將新創(chuàng)建的進程插入就緒隊列，準備執(zhí)行。因此，有時也把作業(yè)調(diào)度稱為接納調(diào)度(Admission Scheduling)。 第三章處理機調(diào)度與死鎖 對用戶而言，總希望自己作業(yè)的周轉(zhuǎn)時間盡可能的少，最好周轉(zhuǎn)時間就等于作業(yè)的執(zhí)行時間。然而對系統(tǒng)來說，則希望作業(yè)的平均周轉(zhuǎn)時間盡可能少，有利于提高CPU 的利用率和系統(tǒng)的吞吐量。為此，每個系統(tǒng)在選擇作業(yè)調(diào)度算法時，既應(yīng)考慮用戶的要求，又能確保系統(tǒng)具有較高的效率。在每次執(zhí)行作業(yè)調(diào)度時，都須做出以下兩個決定。

6、第三章處理機調(diào)度與死鎖 1) 決定接納多少個作業(yè)作業(yè)調(diào)度每次要接納多少個作業(yè)進入內(nèi)存，取決于多道程序度(Degree of Multiprogramming)，即允許多少個作業(yè)同時在內(nèi)存中運行。當內(nèi)存中同時運行的作業(yè)數(shù)目太多時，可能會影響到系統(tǒng)的服務(wù)質(zhì)量，比如，使周轉(zhuǎn)時間太長。但如果在內(nèi)存中同時運行作業(yè)的數(shù)量太少時，又會導致系統(tǒng)的資源利用率和系統(tǒng)吞吐量太低，因此，多道程序度的確定應(yīng)根據(jù)系統(tǒng)的規(guī)模和運行速度等情況做適當?shù)恼壑浴?第三章處理機調(diào)度與死鎖 2) 決定接納哪些作業(yè)應(yīng)將哪些作業(yè)從外存調(diào)入內(nèi)存，這將取決于所采用的調(diào)度算法。最簡單的是先來先服務(wù)調(diào)度算法，這是指將最早進入外存的作業(yè)最先調(diào)入內(nèi)存

7、；較常用的一種算法是短作業(yè)優(yōu)先調(diào)度算法，是將外存上最短的作業(yè)最先調(diào)入內(nèi)存；另一種較常用的是基于作業(yè)優(yōu)先級的調(diào)度算法，該算法是將外存上優(yōu)先級最高的作業(yè)優(yōu)先調(diào)入內(nèi)存；比較好的一種算法是“響應(yīng)比高者優(yōu)先”的調(diào)度算法。我們將在后面對上述幾種算法作較為詳細的介紹。 第三章處理機調(diào)度與死鎖 在批處理系統(tǒng)中，作業(yè)進入系統(tǒng)后，總是先駐留在外存的后備隊列上，因此需要有作業(yè)調(diào)度的過程，以便將它們分批地裝入內(nèi)存。然而在分時系統(tǒng)中，為了做到及時響應(yīng)，用戶通過鍵盤輸入的命令或數(shù)據(jù)等都是被直接送入內(nèi)存的，因而無需再配置上述的作業(yè)調(diào)度機制，但也需要有某些限制性措施來限制進入系統(tǒng)的用戶數(shù)。即，如果系統(tǒng)尚未飽和，將接納所有授權(quán)

8、用戶，否則，將拒絕接納。類似地，在實時系統(tǒng)中通常也不需要作業(yè)調(diào)度。 第三章處理機調(diào)度與死鎖 3.1.2 3.1.2 低級調(diào)度低級調(diào)度通常也把低級調(diào)度(Low Level Scheduling)稱為進程調(diào)度或短程調(diào)度(ShortTerm Scheduling)，它所調(diào)度的對象是進程(或內(nèi)核級線程)。進程調(diào)度是最基本的一種調(diào)度，在多道批處理、分時和實時三種類型的OS中，都必須配置這級調(diào)度。1 1低級調(diào)度的功能低級調(diào)度的功能低級調(diào)度用于決定就緒隊列中的哪個進程(或內(nèi)核級線程，為敘述方便，以后只寫進程)應(yīng)獲得處理機，然后再由分派程序執(zhí)行把處理機分配給該進程的具體操作。第三章處理機調(diào)度與死鎖 低級調(diào)度的

9、主要功能如下： (1) 保存處理機的現(xiàn)場信息。在進程調(diào)度進行調(diào)度時，首先需要保存當前進程的處理機的現(xiàn)場信息，如程序計數(shù)器、多個通用寄存器中的內(nèi)容等，將它們送入該進程的進程控制塊(PCB)中的相應(yīng)單元。(2) 按某種算法選取進程。低級調(diào)度程序按某種算法如優(yōu)先數(shù)算法、輪轉(zhuǎn)法等，從就緒隊列中選取一個進程，把它的狀態(tài)改為運行狀態(tài)，并準備把處理機分配給它。 (3) 把處理器分配給進程。由分派程序(Dispatcher)把處理器分配給進程。此時需為選中的進程恢復處理機現(xiàn)場，即把選中進程的進程控制塊內(nèi)有關(guān)處理機現(xiàn)場的信息裝入處理器相應(yīng)的各個寄存器中，把處理器的控制權(quán)交給該進程，讓它從取出的斷點處開始繼續(xù)運行

10、。 第三章處理機調(diào)度與死鎖 2 2進程調(diào)度中的三個基本機制進程調(diào)度中的三個基本機制為了實現(xiàn)進程調(diào)度，應(yīng)具有如下三個基本機制：(1) 排隊器。為了提高進程調(diào)度的效率，應(yīng)事先將系統(tǒng)中所有的就緒進程按照一定的方式排成一個或多個隊列，以便調(diào)度程序能最快地找到它。(2) 分派器(分派程序)。分派器把由進程調(diào)度程序所選定的進程，從就緒隊列中取出該進程，然后進行上下文切換，將處理機分配給它 第三章處理機調(diào)度與死鎖 (3) 上下文切換機制。當對處理機進行切換時，會發(fā)生兩對上下文切換操作。在第一對上下文切換時，操作系統(tǒng)將保存當前進程的上下文，而裝入分派程序的上下文，以便分派程序運行；在第二對上下文切換時，將移出

11、分派程序，而把新選進程的CPU現(xiàn)場信息裝入到處理機的各個相應(yīng)寄存器中。 第三章處理機調(diào)度與死鎖 應(yīng)當指出，上下文切換將花去不少的處理機時間，即使是現(xiàn)代計算機，每一次上下文切換大約需要花費幾毫秒的時間，該時間大約可執(zhí)行上千條指令。為此，現(xiàn)在已有通過硬件(采用兩組或多組寄存器)的方法來減少上下文切換的時間。一組寄存器供處理機在系統(tǒng)態(tài)時使用，另一組寄存器供應(yīng)用程序使用。在這種條件下的上下文切換只需改變指針，使其指向當前寄存器組即可。 第三章處理機調(diào)度與死鎖 3 3進程調(diào)度方式進程調(diào)度方式進程調(diào)度可采用下述兩種調(diào)度方式。1) 非搶占方式(Nonpreemptive Mode)在采用這種調(diào)度方式時，一旦

12、把處理機分配給某進程后，不管它要運行多長時間，都一直讓它運行下去，決不會因為時鐘中斷等原因而搶占正在運行進程的處理機，也不允許其它進程搶占已經(jīng)分配給它的處理機。直至該進程完成，自愿釋放處理機，或發(fā)生某事件而被阻塞時，才再把處理機分配給其他進程。 第三章處理機調(diào)度與死鎖 在采用非搶占調(diào)度方式時，可能引起進程調(diào)度的因素可歸結(jié)為如下幾個：(1) 正在執(zhí)行的進程執(zhí)行完畢，或因發(fā)生某事件而不能再繼續(xù)執(zhí)行；(2) 執(zhí)行中的進程因提出I/O請求而暫停執(zhí)行；(3) 在進程通信或同步過程中執(zhí)行了某種原語操作，如P操作(wait操作)、Block原語、Wakeup原語等。這種調(diào)度方式的優(yōu)點是實現(xiàn)簡單，系統(tǒng)開銷小，

13、適用于大多數(shù)的批處理系統(tǒng)環(huán)境。但它難以滿足緊急任務(wù)的要求立即執(zhí)行，因而可能造成難以預料的后果。顯然，在要求比較嚴格的實時系統(tǒng)中，不宜采用這種調(diào)度方式。 第三章處理機調(diào)度與死鎖 2) 搶占方式(Preemptive Mode)這種調(diào)度方式允許調(diào)度程序根據(jù)某種原則去暫停某個正在執(zhí)行的進程，將已分配給該進程的處理機重新分配給另一進程。搶占方式的優(yōu)點是，可以防止一個長進程長時間占用處理機，能為大多數(shù)進程提供更公平的服務(wù)，特別是能滿足對響應(yīng)時間有著較嚴格要求的實時任務(wù)的需求。但搶占方式比非搶占方式調(diào)度所需付出的開銷較大。搶占調(diào)度方式是基于一定原則的，主要有如下幾條： 第三章處理機調(diào)度與死鎖 (1) 優(yōu)先

14、權(quán)原則。通常是對一些重要的和緊急的作業(yè)賦予較高的優(yōu)先權(quán)。當這種作業(yè)到達時，如果其優(yōu)先權(quán)比正在執(zhí)行進程的優(yōu)先權(quán)高，便停止正在執(zhí)行(當前)的進程，將處理機分配給優(yōu)先權(quán)高的新到的進程，使之執(zhí)行；或者說，允許優(yōu)先權(quán)高的新到進程搶占當前進程的處理機。(2) 短作業(yè)(進程)優(yōu)先原則。當新到達的作業(yè)(進程)比正在執(zhí)行的作業(yè)(進程)明顯的短時，將暫停當前長作業(yè)(進程)的執(zhí)行，將處理機分配給新到的短作業(yè)(進程)，使之優(yōu)先執(zhí)行； 或者說，短作業(yè)(進程)可以搶占當前較長作業(yè)(進程)的處理機。(3) 時間片原則。各進程按時間片輪流運行，當一個時間片用完后，便停止該進程的執(zhí)行而重新進行調(diào)度。這種原則適用于分時系統(tǒng)、大多

15、數(shù)的實時系統(tǒng)，以及要求較高的批處理系統(tǒng)。 第三章處理機調(diào)度與死鎖 3.1.3 3.1.3 中級調(diào)度中級調(diào)度中級調(diào)度(Intermediate Level Scheduling)又稱中程調(diào)度(Medium-Term Scheduling)。引入中級調(diào)度的主要目的是為了提高內(nèi)存利用率和系統(tǒng)吞吐量。為此，應(yīng)使那些暫時不能運行的進程不再占用寶貴的內(nèi)存資源，而將它們調(diào)至外存上去等待，把此時的進程狀態(tài)稱為就緒駐外存狀態(tài)或掛起狀態(tài)。當這些進程重又具備運行條件且內(nèi)存又稍有空閑時，由中級調(diào)度來決定把外存上的那些又具備運行條件的就緒進程重新調(diào)入內(nèi)存，并修改其狀態(tài)為就緒狀態(tài)，掛在就緒隊列上等待進程調(diào)度。中級調(diào)度實際

16、上就是存儲器管理中的對換功能，我們將在第四章中做詳細闡述。 第三章處理機調(diào)度與死鎖 在上述三種調(diào)度中，進程調(diào)度的運行頻率最高，在分時系統(tǒng)中通常是10100 ms便進行一次進程調(diào)度，因此把它稱為短程調(diào)度。為避免進程調(diào)度占用太多的CPU時間，進程調(diào)度算法不宜太復雜。作業(yè)調(diào)度往往是發(fā)生在一個(批)作業(yè)運行完畢，退出系統(tǒng)，而需要重新調(diào)入一個(批)作業(yè)進入內(nèi)存時，故作業(yè)調(diào)度的周期較長，大約幾分鐘一次，因此把它稱為長程調(diào)度。由于其運行頻率較低，故允許作業(yè)調(diào)度算法花費較多的時間。中級調(diào)度的運行頻率基本上介于上述兩種調(diào)度之間，因此把它稱為中程調(diào)度。 第三章處理機調(diào)度與死鎖 3.2 調(diào)度隊列模型和調(diào)度準則調(diào)度隊

17、列模型和調(diào)度準則 3.2.13.2.1調(diào)度隊列模型調(diào)度隊列模型1 1僅有進程調(diào)度的調(diào)度隊列模型僅有進程調(diào)度的調(diào)度隊列模型在分時系統(tǒng)中，通常僅設(shè)置了進程調(diào)度，用戶鍵入的命令和數(shù)據(jù)都直接送入內(nèi)存。對于命令，是由OS為之建立一個進程。系統(tǒng)可以把處于就緒狀態(tài)的進程組織成棧、樹或一個無序鏈表，至于到底采用其中哪種形式，則與OS類型和所采用的調(diào)度算法有關(guān)。例如，在分時系統(tǒng)中，常把就緒進程組織成FIFO隊列形式。每當OS創(chuàng)建一個新進程時，便將它掛在就緒隊列的末尾，然后按時間片輪轉(zhuǎn)方式運行。 第三章處理機調(diào)度與死鎖 每個進程在執(zhí)行時都可能出現(xiàn)以下三種情況：(1) 任務(wù)在給定的時間片內(nèi)已經(jīng)完成，該進程便在釋放處

18、理機后進入完成狀態(tài)；(2) 任務(wù)在本次分得的時間片內(nèi)尚未完成，OS便將該任務(wù)再放入就緒隊列的末尾；(3) 在執(zhí)行期間，進程因為某事件而被阻塞后，被OS放入阻塞隊列。圖3-1示出了僅具有進程調(diào)度的調(diào)度隊列模型。 第三章處理機調(diào)度與死鎖 圖圖 3-1僅具有進程調(diào)度的調(diào)度隊列模型僅具有進程調(diào)度的調(diào)度隊列模型 就 緒 隊 列阻 塞 隊 列進程調(diào)度CPU進程完成等待事件交互用戶事件出現(xiàn)時間片完第三章處理機調(diào)度與死鎖 2 2具有高級和低級調(diào)度的調(diào)度隊列模型具有高級和低級調(diào)度的調(diào)度隊列模型在批處理系統(tǒng)中，不僅需要進程調(diào)度，而且還需有作業(yè)調(diào)度，由后者按一定的作業(yè)調(diào)度算法，從外存的后備隊列中選擇一批作業(yè)調(diào)入內(nèi)存

19、，并為它們建立進程，送入就緒隊列，然后才由進程調(diào)度按照一定的進程調(diào)度算法選擇一個進程，把處理機分配給該進程。圖3-2示出了具有高、低兩級調(diào)度的調(diào)度隊列模型。該模型與上一模型的主要區(qū)別在于如下兩個方面。 第三章處理機調(diào)度與死鎖 (1) 就緒隊列的形式。在批處理系統(tǒng)中，最常用的是最高優(yōu)先權(quán)優(yōu)先調(diào)度算法，相應(yīng)地，最常用的就緒隊列形式是優(yōu)先權(quán)隊列。進程在進入優(yōu)先級隊列時，根據(jù)其優(yōu)先權(quán)的高低，被插入具有相應(yīng)優(yōu)先權(quán)的位置上，這樣，調(diào)度程序總是把處理機分配給就緒隊列中的隊首進程。在最高優(yōu)先權(quán)優(yōu)先的調(diào)度算法中，也可采用無序鏈表方式，即每次把新到的進程掛在鏈尾，而調(diào)度程序每次調(diào)度時，是依次比較該鏈中各進程的優(yōu)先

20、權(quán)，從中找出優(yōu)先權(quán)最高的進程，將之從鏈中摘下，并把處理機分配給它。顯然，無序鏈表方式與優(yōu)先權(quán)隊列相比，這種方式的調(diào)度效率較低。 第三章處理機調(diào)度與死鎖 圖 3-2具有高、低兩級調(diào)度的調(diào)度隊列模型 就 緒 隊 列進程調(diào)度CPU進程完成等待事件1作業(yè)調(diào)度事件1出現(xiàn)時間片完等待事件2事件2出現(xiàn)等待事件n事件n出現(xiàn)后 備 隊 列第三章處理機調(diào)度與死鎖 (2) 設(shè)置多個阻塞隊列。對于小型系統(tǒng)，可以只設(shè)置一個阻塞隊列；但當系統(tǒng)較大時，若仍只有一個阻塞隊列，其長度必然會很長，隊列中的進程數(shù)可以達到數(shù)百個，這將嚴重影響對阻塞隊列操作的效率。故在大、中型系統(tǒng)中通常都設(shè)置了若干個阻塞隊列，每個隊列對應(yīng)于某一種進程

21、阻塞事件。 第三章處理機調(diào)度與死鎖 3 3同時具有三級調(diào)度的調(diào)度隊列模型同時具有三級調(diào)度的調(diào)度隊列模型當在OS中引入中級調(diào)度后，人們可把進程的就緒狀態(tài)分為內(nèi)存就緒(表示進程在內(nèi)存中就緒)和外存就緒(進程在外存中就緒)。類似地，也可把阻塞狀態(tài)進一步分成內(nèi)存阻塞和外存阻塞兩種狀態(tài)。在調(diào)出操作的作用下，可使進程狀態(tài)由內(nèi)存就緒轉(zhuǎn)為外存就緒，由內(nèi)存阻塞轉(zhuǎn)為外存阻塞；在中級調(diào)度的作用下，又可使外存就緒轉(zhuǎn)為內(nèi)存就緒。圖3-3示出了具有三級調(diào)度的調(diào)度隊列模型。 第三章處理機調(diào)度與死鎖 圖 3-3具有三級調(diào)度時的調(diào)度隊列模型 就緒隊列進程調(diào)度CPU就緒，掛起隊列中級調(diào)度阻塞，掛起隊列阻塞隊列等待事件進程完成時間

22、片完作業(yè)調(diào)度交互型作業(yè)后備隊列批量作業(yè)掛起事件出現(xiàn)事件出現(xiàn)第三章處理機調(diào)度與死鎖 3.2.23.2.2選擇調(diào)度方式和調(diào)度算法的若干準則選擇調(diào)度方式和調(diào)度算法的若干準則1 1面向用戶的準則面向用戶的準則 (1) 周轉(zhuǎn)時間短。通常把周轉(zhuǎn)時間的長短作為評價批處理系統(tǒng)的性能、選擇作業(yè)調(diào)度方式與算法的重要準則之一。所謂周轉(zhuǎn)時間，是指從作業(yè)被提交給系統(tǒng)開始，到作業(yè)完成為止的這段時間間隔(稱為作業(yè)周轉(zhuǎn)時間)。它包括四部分時間：作業(yè)在外存后備隊列上等待(作業(yè))調(diào)度的時間，進程在就緒隊列上等待進程調(diào)度的時間，進程在CPU上執(zhí)行的時間，以及進程等待I/O操作完成的時間。其中的后三項在一個作業(yè)的整個處理過程中可能會

23、發(fā)生多次。 第三章處理機調(diào)度與死鎖 對每個用戶而言，都希望自己作業(yè)的周轉(zhuǎn)時間最短。但作為計算機系統(tǒng)的管理者，則總是希望能使平均周轉(zhuǎn)時間最短，這不僅會有效地提高系統(tǒng)資源的利用率，而且還可使大多數(shù)用戶都感到滿意?？砂哑骄苻D(zhuǎn)時間描述為： niiTnT11第三章處理機調(diào)度與死鎖 作業(yè)的周轉(zhuǎn)時間T與系統(tǒng)為它提供服務(wù)的時間Ts之比，即W = T/Ts，稱為帶權(quán)周轉(zhuǎn)時間，而平均帶權(quán)周轉(zhuǎn)時間則可表示為： niiTTnW1s1第三章處理機調(diào)度與死鎖 (2) 響應(yīng)時間快。常把響應(yīng)時間的長短用來評價分時系統(tǒng)的性能，這是選擇分時系統(tǒng)中進程調(diào)度算法的重要準則之一。所謂響應(yīng)時間，是從用戶通過鍵盤提交一個請求開始，直至系

24、統(tǒng)首次產(chǎn)生響應(yīng)為止的時間，或者說，直到屏幕上顯示出結(jié)果為止的一段時間間隔。它包括三部分時間：從鍵盤輸入的請求信息傳送到處理機的時間，處理機對請求信息進行處理的時間，以及將所形成的響應(yīng)信息回送到終端顯示器的時間。 第三章處理機調(diào)度與死鎖 (3) 截止時間的保證。這是評價實時系統(tǒng)性能的重要指標，因而是選擇實時調(diào)度算法的重要準則。所謂截止時間，是指某任務(wù)必須開始執(zhí)行的最遲時間，或必須完成的最遲時間。對于嚴格的實時系統(tǒng)，其調(diào)度方式和調(diào)度算法必須能保證這一點，否則將可能造成難以預料的后果。(4) 優(yōu)先權(quán)準則。在批處理、分時和實時系統(tǒng)中選擇調(diào)度算法時，都可遵循優(yōu)先權(quán)準則，以便讓某些緊急的作業(yè)能得到及時處理

25、。在要求較嚴格的場合，往往還須選擇搶占式調(diào)度方式，才能保證緊急作業(yè)得到及時處理。 第三章處理機調(diào)度與死鎖 2 2面向系統(tǒng)的準則面向系統(tǒng)的準則這是為了滿足系統(tǒng)要求而應(yīng)遵循的一些準則。其中，較重要的有以下幾點：(1) 系統(tǒng)吞吐量高。這是用于評價批處理系統(tǒng)性能的另一個重要指標，因而是選擇批處理作業(yè)調(diào)度的重要準則。由于吞吐量是指在單位時間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)，因而它與批處理作業(yè)的平均長度具有密切關(guān)系。對于大型作業(yè)，一般吞吐量約為每小時一道作業(yè)；對于中、小型作業(yè)，其吞吐量則可能達到數(shù)十道作業(yè)之多。作業(yè)調(diào)度的方式和算法對吞吐量的大小也將產(chǎn)生較大影響。事實上，對于同一批作業(yè)，若采用了較好的調(diào)度方式和算法，則

26、可顯著地提高系統(tǒng)的吞吐量。 第三章處理機調(diào)度與死鎖 (2) 處理機利用率好。對于大、中型多用戶系統(tǒng)，由于CPU價格十分昂貴，致使處理機的利用率成為衡量系統(tǒng)性能的十分重要的指標；而調(diào)度方式和算法對處理機的利用率起著十分重要的作用。在實際系統(tǒng)中，CPU的利用率一般在40%(系統(tǒng)負荷較輕)到90%之間。在大、中型系統(tǒng)中，在選擇調(diào)度方式和算法時，應(yīng)考慮到這一準則。但對于單用戶微機或某些實時系統(tǒng)，則此準則就不那么重要了。 第三章處理機調(diào)度與死鎖 (3) 各類資源的平衡利用。在大、中型系統(tǒng)中，不僅要使處理機的利用率高，而且還應(yīng)能有效地利用其它各類資源，如內(nèi)存、外存和I/O設(shè)備等。選擇適當?shù)恼{(diào)度方式和算法可

27、以保持系統(tǒng)中各類資源都處于忙碌狀態(tài)。但對于微型機和某些實時系統(tǒng)而言，該準則并不重要。 第三章處理機調(diào)度與死鎖 3.3調(diào)調(diào) 度度 算算 法法 3.2.13.2.1先來先服務(wù)和短作業(yè)先來先服務(wù)和短作業(yè)( (進程進程) )優(yōu)先調(diào)度算法優(yōu)先調(diào)度算法1 1先來先服務(wù)調(diào)度算法先來先服務(wù)調(diào)度算法先來先服務(wù)(FCFS)調(diào)度算法是一種最簡單的調(diào)度算法，該算法既可用于作業(yè)調(diào)度，也可用于進程調(diào)度。當在作業(yè)調(diào)度中采用該算法時，每次調(diào)度都是從后備作業(yè)隊列中選擇一個或多個最先進入該隊列的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進程，然后放入就緒隊列。在進程調(diào)度中采用FCFS算法時，則每次調(diào)度是從就緒隊列中選擇一個最先進

28、入該隊列的進程，為之分配處理機，使之投入運行。該進程一直運行到完成或發(fā)生某事件而阻塞后才放棄處理機。 第三章處理機調(diào)度與死鎖 FCFS算法比較有利于長作業(yè)(進程)，而不利于短作業(yè)(進程)。下表列出了A、B、C、D四個作業(yè)分別到達系統(tǒng)的時間、要求服務(wù)的時間、開始執(zhí)行的時間及各自的完成時間，并計算出各自的周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間。 進程名 到達時間 服務(wù)時間 開始執(zhí)行時間 完成時間 周轉(zhuǎn)時間 帶權(quán)周 轉(zhuǎn)時間 A 0 1 0 1 1 1 B 1 100 1 101 100 1 C 2 1 101 102 100 100 D 3 100 102 202 199 1.99 第三章處理機調(diào)度與死鎖 從表上可

29、以看出，其中短作業(yè)C的帶權(quán)周轉(zhuǎn)時間競高達100，這是不能容忍的；而長作業(yè)D的帶權(quán)周轉(zhuǎn)時間僅為1.99。據(jù)此可知，F(xiàn)CFS調(diào)度算法有利于CPU繁忙型的作業(yè)，而不利于I/O繁忙型的作業(yè)(進程)。CPU繁忙型作業(yè)是指該類作業(yè)需要大量的CPU時間進行計算，而很少請求I/O。通常的科學計算便屬于CPU繁忙型作業(yè)。I/O繁忙型作業(yè)是指CPU進行處理時需頻繁地請求I/O。目前的大多數(shù)事務(wù)處理都屬于I/O繁忙型作業(yè)。第三章處理機調(diào)度與死鎖 在此，我們通過一個例子來說明采用FCFS調(diào)度算法時的調(diào)度性能。圖3-4(a)示出有五個進程A、B、C、D、E，它們到達的時間分別是0、1、2、3和4，所要求的服務(wù)時間分別是

30、4、3、5、2和4，其完成時間分別是4、7、12、14和18。從每個進程的完成時間中減去其到達時間，即得到其周轉(zhuǎn)時間，進而可以算出每個進程的帶權(quán)周轉(zhuǎn)時間。 第三章處理機調(diào)度與死鎖 圖3-4FCFS和SJF調(diào)度算法的性能 進程名 A B C D E 平 均 到達時間 0 1 2 3 4 作業(yè) 情況 調(diào)度 算法 服務(wù)時間 4 3 5 2 4 完成時間 4 7 12 14 18 周轉(zhuǎn)時間 4 6 10 11 14 9 FCFS (a) 帶權(quán)周轉(zhuǎn)時間 1 2 2 5.5 3.5 2.8 完成時間 4 9 18 6 13 周轉(zhuǎn)時間 4 8 16 3 9 8 SJF (b) 帶權(quán)周轉(zhuǎn)時間 1 2.67 3

31、.1 1.5 2.25 2.1 第三章處理機調(diào)度與死鎖 2 2短作業(yè)短作業(yè)( (進程進程) )優(yōu)先調(diào)度算法優(yōu)先調(diào)度算法短作業(yè)(進程)優(yōu)先調(diào)度算法SJ(P)F，是指對短作業(yè)或短進程優(yōu)先調(diào)度的算法。它們可以分別用于作業(yè)調(diào)度和進程調(diào)度。短作業(yè)優(yōu)先(SJF)的調(diào)度算法是從后備隊列中選擇一個或若干個估計運行時間最短的作業(yè)，將它們調(diào)入內(nèi)存運行。而短進程優(yōu)先(SPF)調(diào)度算法則是從就緒隊列中選出一個估計運行時間最短的進程，將處理機分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機時再重新調(diào)度。 第三章處理機調(diào)度與死鎖 為了和FCFS調(diào)度算法進行比較，我們?nèi)岳肍CFS算法中所使用的實例，

32、并改用SJ(P)F算法重新調(diào)度，再進行性能分析。由圖3-4 中的(a)和(b)可以看出，采用SJ(P)F算法后，不論是平均周轉(zhuǎn)時間還是平均帶權(quán)周轉(zhuǎn)時間，都有較明顯的改善，尤其是對短作業(yè)D，其周轉(zhuǎn)時間由原來的(用FCFS算法時)11降為3；而平均帶權(quán)周轉(zhuǎn)時間是從5.5降到1.5。這說明SJF調(diào)度算法能有效地降低作業(yè)的平均等待時間，提高系統(tǒng)吞吐量。 第三章處理機調(diào)度與死鎖 SJ(P)F調(diào)度算法也存在不容忽視的缺點：(1) 該算法對長作業(yè)不利，如作業(yè)C的周轉(zhuǎn)時間由10增至16，其帶權(quán)周轉(zhuǎn)時間由2增至3.1。更嚴重的是，如果有一長作業(yè)(進程)進入系統(tǒng)的后備隊列(就緒隊列)，由于調(diào)度程序總是優(yōu)先調(diào)度那些

33、(即使是后進來的)短作業(yè)(進程)，將導致長作業(yè)(進程)長期不被調(diào)度。(2) 該算法完全未考慮作業(yè)的緊迫程度，因而不能保證緊迫性作業(yè)(進程)會被及時處理。(3) 由于作業(yè)(進程)的長短只是根據(jù)用戶所提供的估計執(zhí)行時間而定的，而用戶又可能會有意或無意地縮短其作業(yè)的估計運行時間，致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。 第三章處理機調(diào)度與死鎖 3.3.23.3.2高優(yōu)先權(quán)優(yōu)先調(diào)度算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法1 1優(yōu)先權(quán)調(diào)度算法的類型優(yōu)先權(quán)調(diào)度算法的類型為了照顧緊迫型作業(yè)，使之在進入系統(tǒng)后便獲得優(yōu)先處理，引入了最高優(yōu)先權(quán)優(yōu)先(FPF)調(diào)度算法。此算法常被用于批處理系統(tǒng)中，作為作業(yè)調(diào)度算法，也作為多種操作

34、系統(tǒng)中的進程調(diào)度算法，還可用于實時系統(tǒng)中。當把該算法用于作業(yè)調(diào)度時，系統(tǒng)將從后備隊列中選擇若干個優(yōu)先權(quán)最高的作業(yè)裝入內(nèi)存。當用于進程調(diào)度時，該算法是把處理機分配給就緒隊列中優(yōu)先權(quán)最高的進程，這時，又可進一步把該算法分成如下兩種。 第三章處理機調(diào)度與死鎖 1) 非搶占式優(yōu)先權(quán)算法在這種方式下，系統(tǒng)一旦把處理機分配給就緒隊列中優(yōu)先權(quán)最高的進程后，該進程便一直執(zhí)行下去，直至完成；或因發(fā)生某事件使該進程放棄處理機時，系統(tǒng)方可再將處理機重新分配給另一優(yōu)先權(quán)最高的進程。這種調(diào)度算法主要用于批處理系統(tǒng)中；也可用于某些對實時性要求不嚴的實時系統(tǒng)中。 第三章處理機調(diào)度與死鎖 2) 搶占式優(yōu)先權(quán)調(diào)度算法在這種方式

35、下，系統(tǒng)同樣是把處理機分配給優(yōu)先權(quán)最高的進程，使之執(zhí)行。但在其執(zhí)行期間，只要又出現(xiàn)了另一個其優(yōu)先權(quán)更高的進程，進程調(diào)度程序就立即停止當前進程(原優(yōu)先權(quán)最高的進程)的執(zhí)行，重新將處理機分配給新到的優(yōu)先權(quán)最高的進程。因此，在采用這種調(diào)度算法時，是每當系統(tǒng)中出現(xiàn)一個新的就緒進程i時，就將其優(yōu)先權(quán)Pi與正在執(zhí)行的進程j的優(yōu)先權(quán)Pj進行比較。如果PiPj，原進程Pj便繼續(xù)執(zhí)行；但如果是PiPj，則立即停止Pj的執(zhí)行，做進程切換，使i進程投入執(zhí)行。顯然，這種搶占式的優(yōu)先權(quán)調(diào)度算法能更好地滿足緊迫作業(yè)的要求，故而常用于要求比較嚴格的實時系統(tǒng)中，以及對性能要求較高的批處理和分時系統(tǒng)中。 第三章處理機調(diào)度與死鎖

36、 2 2優(yōu)先權(quán)的類型優(yōu)先權(quán)的類型對于最高優(yōu)先權(quán)優(yōu)先調(diào)度算法，其關(guān)鍵在于：它是使用靜態(tài)優(yōu)先權(quán)，還是用動態(tài)優(yōu)先權(quán)，以及如何確定進程的優(yōu)先權(quán)。1) 靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進程時確定的，且在進程的整個運行期間保持不變。一般地，優(yōu)先權(quán)是利用某一范圍內(nèi)的一個整數(shù)來表示的，例如，07或0255中的某一整數(shù)，又把該整數(shù)稱為優(yōu)先數(shù)，只是具體用法各異：有的系統(tǒng)用“0”表示最高優(yōu)先權(quán)，當數(shù)值愈大時，其優(yōu)先權(quán)愈低；而有的系統(tǒng)恰恰相反。 第三章處理機調(diào)度與死鎖 確定進程優(yōu)先權(quán)的依據(jù)有如下三個方面：(1) 進程類型。通常，系統(tǒng)進程(如接收進程、對換進程、磁盤I/O進程)的優(yōu)先權(quán)高于一般用戶進程的優(yōu)先權(quán)。(2) 進程

37、對資源的需求。如進程的估計執(zhí)行時間及內(nèi)存需要量的多少，對這些要求少的進程應(yīng)賦予較高的優(yōu)先權(quán)。(3) 用戶要求。這是由用戶進程的緊迫程度及用戶所付費用的多少來確定優(yōu)先權(quán)的。靜態(tài)優(yōu)先權(quán)法簡單易行，系統(tǒng)開銷小，但不夠精確，很可能出現(xiàn)優(yōu)先權(quán)低的作業(yè)(進程)長期沒有被調(diào)度的情況。因此，僅在要求不高的系統(tǒng)中才使用靜態(tài)優(yōu)先權(quán)。 第三章處理機調(diào)度與死鎖 2) 動態(tài)優(yōu)先權(quán)動態(tài)優(yōu)先權(quán)是指在創(chuàng)建進程時所賦予的優(yōu)先權(quán)，是可以隨進程的推進或隨其等待時間的增加而改變的，以便獲得更好的調(diào)度性能。例如，我們可以規(guī)定，在就緒隊列中的進程，隨其等待時間的增長，其優(yōu)先權(quán)以速率a提高。若所有的進程都具有相同的優(yōu)先權(quán)初值，則顯然是最先

38、進入就緒隊列的進程將因其動態(tài)優(yōu)先權(quán)變得最高而優(yōu)先獲得處理機，此即FCFS算法。若所有的就緒進程具有各不相同的優(yōu)先權(quán)初值，那么，對于優(yōu)先權(quán)初值低的進程，在等待了足夠的時間后，其優(yōu)先權(quán)便可能升為最高，從而可以獲得處理機。當采用搶占式優(yōu)先權(quán)調(diào)度算法時，如果再規(guī)定當前進程的優(yōu)先權(quán)以速率b下降，則可防止一個長作業(yè)長期地壟斷處理機。 第三章處理機調(diào)度與死鎖 3 3高響應(yīng)比優(yōu)先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法在批處理系統(tǒng)中，短作業(yè)優(yōu)先算法是一種比較好的算法，其主要的不足之處是長作業(yè)的運行得不到保證。如果我們能為每個作業(yè)引入前面所述的動態(tài)優(yōu)先權(quán)，并使作業(yè)的優(yōu)先級隨著等待時間的增加而以速率a提高，則長作業(yè)在等待一定

39、的時間后，必然有機會分配到處理機。該優(yōu)先權(quán)的變化規(guī)律可描述為： 要求服務(wù)時間要求服務(wù)時間等待時間優(yōu)先權(quán)第三章處理機調(diào)度與死鎖 由于等待時間與服務(wù)時間之和就是系統(tǒng)對該作業(yè)的響應(yīng)時間，故該優(yōu)先權(quán)又相當于響應(yīng)比RP。據(jù)此，又可表示為： 要求服務(wù)時間響應(yīng)時間要求服務(wù)時間要求服務(wù)時間等待時間PR第三章處理機調(diào)度與死鎖 由上式可以看出：(1) 如果作業(yè)的等待時間相同，則要求服務(wù)的時間愈短，其優(yōu)先權(quán)愈高，因而該算法有利于短作業(yè)。(2) 當要求服務(wù)的時間相同時，作業(yè)的優(yōu)先權(quán)決定于其等待時間，等待時間愈長，其優(yōu)先權(quán)愈高，因而它實現(xiàn)的是先來先服務(wù)。 第三章處理機調(diào)度與死鎖 (3) 對于長作業(yè)，作業(yè)的優(yōu)先級可以隨等

40、待時間的增加而提高，當其等待時間足夠長時，其優(yōu)先級便可升到很高，從而也可獲得處理機。簡言之，該算法既照顧了短作業(yè)，又考慮了作業(yè)到達的先后次序，不會使長作業(yè)長期得不到服務(wù)。因此，該算法實現(xiàn)了一種較好的折衷。當然，在利用該算法時，每要進行調(diào)度之前，都須先做響應(yīng)比的計算，這會增加系統(tǒng)開銷。 第三章處理機調(diào)度與死鎖 3.3.33.3.3基于時間片的輪轉(zhuǎn)調(diào)度算法基于時間片的輪轉(zhuǎn)調(diào)度算法1 1時間片輪轉(zhuǎn)法時間片輪轉(zhuǎn)法1) 基本原理在早期的時間片輪轉(zhuǎn)法中，系統(tǒng)將所有的就緒進程按先來先服務(wù)的原則排成一個隊列，每次調(diào)度時，把CPU分配給隊首進程，并令其執(zhí)行一個時間片。時間片的大小從幾ms到幾百ms。當執(zhí)行的時間

41、片用完時，由一個計時器發(fā)出時鐘中斷請求，調(diào)度程序便據(jù)此信號來停止該進程的執(zhí)行，并將它送往就緒隊列的末尾；然后，再把處理機分配給就緒隊列中新的隊首進程，同時也讓它執(zhí)行一個時間片。這樣就可以保證就緒隊列中的所有進程在一給定的時間內(nèi)均能獲得一時間片的處理機執(zhí)行時間。換言之，系統(tǒng)能在給定的時間內(nèi)響應(yīng)所有用戶的請求。 第三章處理機調(diào)度與死鎖 2) 時間片大小的確定在時間片輪轉(zhuǎn)算法中，時間片的大小對系統(tǒng)性能有很大的影響，如選擇很小的時間片將有利于短作業(yè)，因為它能較快地完成，但會頻繁地發(fā)生中斷、進程上下文的切換，從而增加系統(tǒng)的開銷；反之，如選擇太長的時間片，使得每個進程都能在一個時間片內(nèi)完成，時間片輪轉(zhuǎn)算法

42、便退化為FCFS算法，無法滿足交互式用戶的需求。一個較為可取的大小是，時間片略大于一次典型的交互所需要的時間。這樣可使大多數(shù)進程在一個時間片內(nèi)完成。圖3-5示出了時間片分別為q=1和q=4時，A、B、C、D、E五個進程的運行情況，而圖3-6為q=1和q=4時各進程的平均周轉(zhuǎn)時間和帶權(quán)平均周轉(zhuǎn)時間。圖中的RR(Round Robin)表示輪轉(zhuǎn)調(diào)度算法。 第三章處理機調(diào)度與死鎖 圖3-5 q=1和q=4時的進程運行情況 ABCDEABCDEABCEACE(a) q1(b) q412345678910 11 12 13 14 15 16 17t第三章處理機調(diào)度與死鎖 圖3-6 q=1和q=4時進程的

43、周轉(zhuǎn)時間 進程名 A B C D E 平均 到達時間 0 1 2 3 4 作業(yè) 情況 時 間 片 服務(wù)時間 4 3 4 2 4 完成時間 15 12 16 9 17 周轉(zhuǎn)時間 15 11 14 6 13 11.8 RR q=1 帶權(quán)周轉(zhuǎn)時間 3.75 3.67 3.5 3 3.33 3.46 完成時間 4 7 11 13 17 周轉(zhuǎn)時間 4 6 9 10 13 8.4 RR q=4 帶權(quán)周轉(zhuǎn)時間 1 2 2.25 5 3.33 2.5 第三章處理機調(diào)度與死鎖 2 2多級反饋隊列調(diào)度算法多級反饋隊列調(diào)度算法(1) 應(yīng)設(shè)置多個就緒隊列，并為各個隊列賦予不同的優(yōu)先級。第一個隊列的優(yōu)先級最高，第二個隊

44、列次之，其余各隊列的優(yōu)先權(quán)逐個降低。該算法賦予各個隊列中進程執(zhí)行時間片的大小也各不相同，在優(yōu)先權(quán)愈高的隊列中，為每個進程所規(guī)定的執(zhí)行時間片就愈小。例如，第二個隊列的時間片要比第一個隊列的時間片長一倍，第i+1個隊列的時間片要比第i個隊列的時間片長一倍。圖3-7是多級反饋隊列算法的示意。 第三章處理機調(diào)度與死鎖 圖 3-7多級反饋隊列調(diào)度算法 就緒隊列 1就緒隊列 2就緒隊列 3就緒隊列 nS1S2S3至CPU至CPU至CPU至CPU(時間片： S1 S2 S3)第三章處理機調(diào)度與死鎖 (2) 當一個新進程進入內(nèi)存后，首先將它放入第一隊列的末尾，按FCFS原則排隊等待調(diào)度。當輪到該進程執(zhí)行時，如

45、它能在該時間片內(nèi)完成，便可準備撤離系統(tǒng)；如果它在一個時間片結(jié)束時尚未完成，調(diào)度程序便將該進程轉(zhuǎn)入第二隊列的末尾，再同樣地按FCFS原則等待調(diào)度執(zhí)行；如果它在第二隊列中運行一個時間片后仍未完成，再依次將它放入第三隊列，如此下去，當一個長作業(yè)(進程)從第一隊列依次降到第n隊列后，在第n隊列中便采取按時間片輪轉(zhuǎn)的方式運行。 第三章處理機調(diào)度與死鎖 (3) 僅當?shù)谝魂犃锌臻e時，調(diào)度程序才調(diào)度第二隊列中的進程運行；僅當?shù)?(i-1)隊列均空時，才會調(diào)度第i隊列中的進程運行。如果處理機正在第i隊列中為某進程服務(wù)時，又有新進程進入優(yōu)先權(quán)較高的隊列(第1(i-1)中的任何一個隊列)，則此時新進程將搶占正在運行

46、進程的處理機，即由調(diào)度程序把正在運行的進程放回到第i隊列的末尾，把處理機分配給新到的高優(yōu)先權(quán)進程。 第三章處理機調(diào)度與死鎖 3 3多級反饋隊列調(diào)度算法的性能多級反饋隊列調(diào)度算法的性能多級反饋隊列調(diào)度算法具有較好的性能，能很好地滿足各種類型用戶的需要。(1) 終端型作業(yè)用戶。由于終端型作業(yè)用戶所提交的作業(yè)大多屬于交互型作業(yè)，作業(yè)通常較小，系統(tǒng)只要能使這些作業(yè)(進程)在第一隊列所規(guī)定的時間片內(nèi)完成，便可使終端型作業(yè)用戶都感到滿意。 第三章處理機調(diào)度與死鎖 (2) 短批處理作業(yè)用戶。對于很短的批處理型作業(yè)，開始時像終端型作業(yè)一樣，如果僅在第一隊列中執(zhí)行一個時間片即可完成，便可獲得與終端型作業(yè)一樣的響

47、應(yīng)時間。對于稍長的作業(yè)，通常也只需在第二隊列和第三隊列各執(zhí)行一個時間片即可完成，其周轉(zhuǎn)時間仍然較短。(3) 長批處理作業(yè)用戶。對于長作業(yè)，它將依次在第1，2，n個隊列中運行，然后再按輪轉(zhuǎn)方式運行，用戶不必擔心其作業(yè)長期得不到處理。 第三章處理機調(diào)度與死鎖 3.4實實 時時 調(diào)調(diào) 度度 3.4.13.4.1實現(xiàn)實時調(diào)度的基本條件實現(xiàn)實時調(diào)度的基本條件1 1提供必要的信息提供必要的信息為了實現(xiàn)實時調(diào)度，系統(tǒng)應(yīng)向調(diào)度程序提供有關(guān)任務(wù)的下述一些信息：(1) 就緒時間。這是該任務(wù)成為就緒狀態(tài)的起始時間，在周期任務(wù)的情況下，它就是事先預知的一串時間序列；而在非周期任務(wù)的情況下，它也可能是預知的。 第三章處

48、理機調(diào)度與死鎖 (2) 開始截止時間和完成截止時間。對于典型的實時應(yīng)用，只須知道開始截止時間，或者知道完成截止時間。(3) 處理時間。這是指一個任務(wù)從開始執(zhí)行直至完成所需的時間。在某些情況下，該時間也是系統(tǒng)提供的。(4) 資源要求。這是指任務(wù)執(zhí)行時所需的一組資源。(5) 優(yōu)先級。如果某任務(wù)的開始截止時間已經(jīng)錯過，就會引起故障，則應(yīng)為該任務(wù)賦予“絕對”優(yōu)先級；如果開始截止時間的推遲對任務(wù)的繼續(xù)運行無重大影響，則可為該任務(wù)賦予“相對”優(yōu)先級，供調(diào)度程序參考。 第三章處理機調(diào)度與死鎖 2 2系統(tǒng)處理能力強系統(tǒng)處理能力強在實時系統(tǒng)中，通常都有著多個實時任務(wù)。若處理機的處理能力不夠強，則有可能因處理機忙

49、不過來而使某些實時任務(wù)不能得到及時處理，從而導致發(fā)生難以預料的后果。假定系統(tǒng)中有m個周期性的硬實時任務(wù)，它們的處理時間可表示為Ci，周期時間表示為Pi，則在單處理機情況下，必須滿足下面的限制條件： 11miiiPC第三章處理機調(diào)度與死鎖 系統(tǒng)才是可調(diào)度的。假如系統(tǒng)中有6個硬實時任務(wù)，它們的周期時間都是 50 ms，而每次的處理時間為 10 ms，則不難算出，此時是不能滿足上式的，因而系統(tǒng)是不可調(diào)度的。解決的方法是提高系統(tǒng)的處理能力，其途徑有二：其一仍是采用單處理機系統(tǒng)，但須增強其處理能力，以顯著地減少對每一個任務(wù)的處理時間；其二是采用多處理機系統(tǒng)。假定系統(tǒng)中的處理機數(shù)為N，則應(yīng)將上述的限制條件

50、改為： NPCmiii1第三章處理機調(diào)度與死鎖 3 3采用搶占式調(diào)度機制采用搶占式調(diào)度機制在含有硬實時任務(wù)的實時系統(tǒng)中，廣泛采用搶占機制。當一個優(yōu)先權(quán)更高的任務(wù)到達時，允許將當前任務(wù)暫時掛起，而令高優(yōu)先權(quán)任務(wù)立即投入運行，這樣便可滿足該硬實時任務(wù)對截止時間的要求。但這種調(diào)度機制比較復雜。對于一些小型實時系統(tǒng)，如果能預知任務(wù)的開始截止時間，則對實時任務(wù)的調(diào)度可采用非搶占調(diào)度機制，以簡化調(diào)度程序和對任務(wù)調(diào)度時所花費的系統(tǒng)開銷。但在設(shè)計這種調(diào)度機制時，應(yīng)使所有的實時任務(wù)都比較小，并在執(zhí)行完關(guān)鍵性程序和臨界區(qū)后，能及時地將自己阻塞起來，以便釋放出處理機，供調(diào)度程序去調(diào)度那種開始截止時間即將到達的任務(wù)。

51、 第三章處理機調(diào)度與死鎖 4 4具有快速切換機制具有快速切換機制為保證要求較高的硬實時任務(wù)能及時運行，在實時系統(tǒng)中還應(yīng)具有快速切換機制，以保證能進行任務(wù)的快速切換。該機制應(yīng)具有如下兩方面的能力：(1) 對外部中斷的快速響應(yīng)能力。為使在緊迫的外部事件請求中斷時系統(tǒng)能及時響應(yīng)，要求系統(tǒng)具有快速硬件中斷機構(gòu)，還應(yīng)使禁止中斷的時間間隔盡量短，以免耽誤時機(其它緊迫任務(wù))。(2) 快速的任務(wù)分派能力。在完成任務(wù)調(diào)度后，便應(yīng)進行任務(wù)切換。為了提高分派程序進行任務(wù)切換時的速度，應(yīng)使系統(tǒng)中的每個運行功能單位適當?shù)匦。詼p少任務(wù)切換的時間開銷。 第三章處理機調(diào)度與死鎖 3.4.23.4.2實時調(diào)度算法的分類實時

52、調(diào)度算法的分類1 1非搶占式調(diào)度算法非搶占式調(diào)度算法1) 非搶占式輪轉(zhuǎn)調(diào)度算法該算法常用于工業(yè)生產(chǎn)的群控系統(tǒng)中，由一臺計算機控制若干個相同的(或類似的)對象，為每一個被控對象建立一個實時任務(wù)，并將它們排成一個輪轉(zhuǎn)隊列。調(diào)度程序每次選擇隊列中的第一個任務(wù)投入運行。當該任務(wù)完成后，便把它掛在輪轉(zhuǎn)隊列的末尾，等待下次調(diào)度運行，而調(diào)度程序再選擇下一個(隊首)任務(wù)運行。這種調(diào)度算法可獲得數(shù)秒至數(shù)十秒的響應(yīng)時間，可用于要求不太嚴格的實時控制系統(tǒng)中。 第三章處理機調(diào)度與死鎖 2) 非搶占式優(yōu)先調(diào)度算法如果在實時系統(tǒng)中存在著要求較為嚴格(響應(yīng)時間為數(shù)百毫秒)的任務(wù)，則可采用非搶占式優(yōu)先調(diào)度算法為這些任務(wù)賦予較

53、高的優(yōu)先級。當這些實時任務(wù)到達時，把它們安排在就緒隊列的隊首，等待當前任務(wù)自我終止或運行完成后才能被調(diào)度執(zhí)行。這種調(diào)度算法在做了精心的處理后，有可能獲得僅為數(shù)秒至數(shù)百毫秒級的響應(yīng)時間，因而可用于有一定要求的實時控制系統(tǒng)中。 第三章處理機調(diào)度與死鎖 2 2搶占式調(diào)度算法搶占式調(diào)度算法在要求較嚴格的(響應(yīng)時間為數(shù)十毫秒以下)的實時系統(tǒng)中，應(yīng)采用搶占式優(yōu)先權(quán)調(diào)度算法?？筛鶕?jù)搶占發(fā)生時間的不同而進一步分成以下兩種調(diào)度算法。1) 基于時鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法在某實時任務(wù)到達后，如果該任務(wù)的優(yōu)先級高于當前任務(wù)的優(yōu)先級，這時并不立即搶占當前任務(wù)的處理機，而是等到時鐘中斷到來時，調(diào)度程序才剝奪當前任務(wù)的

54、執(zhí)行，將處理機分配給新到的高優(yōu)先權(quán)任務(wù)。這種調(diào)度算法能獲得較好的響應(yīng)效果，其調(diào)度延遲可降為幾十毫秒至幾毫秒。因此，此算法可用于大多數(shù)的實時系統(tǒng)中。 第三章處理機調(diào)度與死鎖 2) 立即搶占(Immediate Preemption)的優(yōu)先權(quán)調(diào)度算法在這種調(diào)度策略中，要求操作系統(tǒng)具有快速響應(yīng)外部事件中斷的能力。一旦出現(xiàn)外部中斷，只要當前任務(wù)未處于臨界區(qū)，便立即剝奪當前任務(wù)的執(zhí)行，把處理機分配給請求中斷的緊迫任務(wù)。這種算法能獲得非常快的響應(yīng)，可把調(diào)度延遲降低到幾毫秒至100微秒，甚至更低。圖3-8中的(a)、(b)、(c)、(d)分別示出了采用非搶占式輪轉(zhuǎn)調(diào)度算法、非搶占式優(yōu)先權(quán)調(diào)度算法、基于時鐘中

55、斷搶占的優(yōu)先權(quán)調(diào)度算法和立即搶占的優(yōu)先權(quán)調(diào)度算法四種情況的調(diào)度時間。 第三章處理機調(diào)度與死鎖 圖3-8 實時進程調(diào)度 (a) 非搶占式輪轉(zhuǎn)調(diào)度當前進程實時進程實時進程請求調(diào)度實時進程搶占當前進程并立即執(zhí)行(d) 立即搶占的優(yōu)先權(quá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)度時間(c) 基于時鐘中斷搶占的優(yōu)先權(quán)搶占調(diào)度調(diào)度時間實時進程第三章處理機調(diào)度與死鎖 3.4.33.4.3常用的幾種實時調(diào)度算法常用的幾種實時調(diào)度算法1 1最早截止時間優(yōu)先即

56、最早截止時間優(yōu)先即EDF(Earliest Deadline First)EDF(Earliest Deadline First)算法算法該算法是根據(jù)任務(wù)的開始截止時間來確定任務(wù)的優(yōu)先級。截止時間愈早，其優(yōu)先級愈高。該算法要求在系統(tǒng)中保持一個實時任務(wù)就緒隊列，該隊列按各任務(wù)截止時間的早晚排序；當然，具有最早截止時間的任務(wù)排在隊列的最前面。調(diào)度程序在選擇任務(wù)時，總是選擇就緒隊列中的第一個任務(wù)，為之分配處理機，使之投入運行。最早截止時間優(yōu)先算法既可用于搶占式調(diào)度，也可用于非搶占式調(diào)度方式中。 第三章處理機調(diào)度與死鎖 1) 非搶占式調(diào)度方式用于非周期實時任務(wù)圖3-9示出了將該算法用于非搶占調(diào)度方式之

57、例。該例中具有四個非周期任務(wù)，它們先后到達。系統(tǒng)首先調(diào)度任務(wù)1執(zhí)行，在任務(wù)1執(zhí)行期間，任務(wù)2、3又先后到達。由于任務(wù)3的開始截止時間早于任務(wù)2，故系統(tǒng)在任務(wù)1后將調(diào)度任務(wù)3執(zhí)行。在此期間又到達作業(yè)4，其開始截止時間仍是早于任務(wù)2的，故在任務(wù)3執(zhí)行完后，系統(tǒng)又調(diào)度任務(wù)4執(zhí)行，最后才調(diào)度任務(wù)2執(zhí)行。 第三章處理機調(diào)度與死鎖 圖 3-9EDF算法用于非搶占調(diào)度的調(diào)度方式1342開始截止時間任務(wù)執(zhí)行任務(wù)到達12 341342t第三章處理機調(diào)度與死鎖 2) 搶占式調(diào)度方式用于周期實時任務(wù)圖3-10示出了將最早截止時間優(yōu)先算法用于搶占調(diào)度方式之例。在該例中有兩個周期性任務(wù)，任務(wù)A的周期時間為20 ms，每

58、個周期的處理時間為10 ms；任務(wù)B的周期時間為50 ms，每個周期的處理時間為25 ms。圖中的第一行示出了兩個任務(wù)的到達時間、最后期限和執(zhí)行時間圖。其中任務(wù)A的到達時間為0、20、40、；任務(wù)A的最后期限為20、40、60、；任務(wù)B的到達時間為0、50、100、；任務(wù)B的最后期限為50、100、150、(注：單位皆為ms)。 第三章處理機調(diào)度與死鎖 圖3-10 最早截止時間優(yōu)先算法用于搶占調(diào)度方式之例 A1 B1A2B1A3 B2 A4B2A5B1A2A3B2A5A1B1B1A2B1A3 B2 A4B2A5 B2A1A2B2A3A4A5B1最后期限B2最后期限A1最后期限A2最后期限A3最

59、后期限A4最后期限A5最后期限到達時間、執(zhí)行時間和最后期限A1固定優(yōu)先級調(diào)度固定優(yōu)先級調(diào)度A2B1A3A4A5，B2A5，B2A4A1(錯過)A2B1A3(錯過)A1A2B1(錯過)A3A4A5，B201020304050 60708090100 時間t/ms使用完成最后期限最早和最后期限調(diào)度(A有較高優(yōu)先級)(B有較高優(yōu)先級)第三章處理機調(diào)度與死鎖 為了說明通常的優(yōu)先級調(diào)度不能適用于實時系統(tǒng)，該圖特增加了第二和第三行。在第二行中假定任務(wù)A具有較高的優(yōu)先級，所以在t=0 ms時，先調(diào)度A1執(zhí)行，在A1完成后(t = 10 ms)才調(diào)度B1執(zhí)行；在t = 20 ms時，調(diào)度A2執(zhí)行；在t = 3

60、0 ms時，A2完成，又調(diào)度B1執(zhí)行；在t = 40 ms時，調(diào)度A3執(zhí)行；在t = 50 ms時，雖然A3已完成，但B1已錯過了它的最后期限，這說明了利用通常的優(yōu)先級調(diào)度已經(jīng)失敗。第三行與第二行類似，只是假定任務(wù)B具有較高的優(yōu)先級。 第三章處理機調(diào)度與死鎖 第四行是采用最早截止時間優(yōu)先算法的時間圖。在t = 0時，A1和B1同時到達，由于A1的截止時間比B1早，故調(diào)度A1執(zhí)行；在t = 10時，A1完成，又調(diào)度B1執(zhí)行；在t = 20時，A2到達，由于A2的截止時間比B2早，B1被中斷而調(diào)度A2執(zhí)行；在t = 30時，A2完成，又重新調(diào)度B1執(zhí)行；在t = 40時，A3又到達，但B1的截止時