處理機(jī)調(diào)度和死鎖

處理機(jī)調(diào)度和死鎖處理機(jī)調(diào)度與死鎖(SchedulingandDeadlock)教學(xué)目的：在多道程序系統(tǒng)中，一個(gè)作業(yè)從提交到執(zhí)行完成，要經(jīng)歷多級(jí)調(diào)度，調(diào)度的好壞要影響系統(tǒng)的運(yùn)行性能，因此調(diào)度是多道系統(tǒng)的關(guān)鍵。為了改善系統(tǒng)資源的利用率和提高系統(tǒng)處理能力，多道程序系統(tǒng)中采用多個(gè)進(jìn)程的并發(fā)執(zhí)行，但它也可能發(fā)生死鎖的危險(xiǎn)，研究死鎖的原因和產(chǎn)生條件，采用預(yù)防死鎖、避免死鎖、檢測死鎖和解除死鎖等多種方法防止死鎖是多道程序系統(tǒng)重要的研究課題。教學(xué)要求：熟悉處理機(jī)三級(jí)調(diào)度概念和處理機(jī)調(diào)度模型，掌握作業(yè)的狀態(tài)和作業(yè)調(diào)度的功能。掌握進(jìn)程調(diào)度的方式和功能，熟悉調(diào)度方式和算法的選擇準(zhǔn)則，掌握各種調(diào)度算法及適合范圍。掌握死鎖的定義和產(chǎn)生死鎖的原因，掌握死鎖的四個(gè)必要條件；熟悉預(yù)防死鎖的方法，熟練掌握銀行家算法及其在死鎖避免中的應(yīng)用；掌握資源分配圖的簡化及其死鎖定理，熟悉解除死鎖的方法。3.1處理機(jī)調(diào)度的層次

高級(jí)調(diào)度

1．作業(yè)和作業(yè)步

(1)作業(yè)(Job)。作業(yè)是一個(gè)比程序更為廣泛的概念，它不僅包含了通常的程序和數(shù)據(jù)，而且還應(yīng)配有一份作業(yè)說明書，系統(tǒng)根據(jù)該說明書來對(duì)程序的運(yùn)行進(jìn)行控制。在批處理系統(tǒng)中，是以作業(yè)為基本單位從外存調(diào)入內(nèi)存的。

(2)作業(yè)步(JobStep)。通常，在作業(yè)運(yùn)行期間，每個(gè)作業(yè)都必須經(jīng)過若干個(gè)相對(duì)獨(dú)立，又相互關(guān)聯(lián)的順序加工步驟才能得到結(jié)果，我們把其中的每一個(gè)加工步驟稱為一個(gè)作業(yè)步，各作業(yè)步之間存在著相互聯(lián)系，往往是把上一個(gè)作業(yè)步的輸出作為下一個(gè)作業(yè)步的輸入。例如，一個(gè)典型的作業(yè)可分成三個(gè)作業(yè)步：①“編譯”作業(yè)步，通過執(zhí)行編譯程序?qū)υ闯绦蜻M(jìn)行編譯，產(chǎn)生若干個(gè)目標(biāo)程序段；②“連結(jié)裝配”作業(yè)步，將“編譯”作業(yè)步所產(chǎn)生的若干個(gè)目標(biāo)程序段裝配成可執(zhí)行的目標(biāo)程序；③“運(yùn)行”作業(yè)步，將可執(zhí)行的目標(biāo)程序讀入內(nèi)存并控制其運(yùn)行。

(3)作業(yè)流。若干個(gè)作業(yè)進(jìn)入系統(tǒng)后，被依次存放在外存上，這便形成了輸入的作業(yè)流；在操作系統(tǒng)的控制下，逐個(gè)作業(yè)進(jìn)行處理，于是便形成了處理作業(yè)流。

作業(yè)調(diào)度作業(yè)運(yùn)行狀態(tài)外存

外存(盤)交換區(qū)作業(yè)后備狀態(tài)作業(yè)提交狀態(tài)作業(yè)完成狀態(tài)終止作業(yè)就緒態(tài)阻塞態(tài)主存

進(jìn)程調(diào)度運(yùn)行態(tài)就緒態(tài)阻塞態(tài)調(diào)出調(diào)進(jìn)作業(yè)的狀態(tài):

作業(yè)從進(jìn)入到運(yùn)行結(jié)束，一般需要經(jīng)歷“提交”、“后備”、“運(yùn)行”和“完成”四個(gè)階段。提交狀態(tài)一個(gè)作業(yè)被提交給機(jī)房后正在通過SPOOLing系統(tǒng)進(jìn)行輸入或用戶通過終端向計(jì)算機(jī)中鍵入其作業(yè)時(shí)所處于的狀態(tài)為提交狀態(tài)。后備狀態(tài)作業(yè)已經(jīng)過SPOOLing系統(tǒng)輸入到磁盤輸入井，等待調(diào)入內(nèi)存運(yùn)行，此時(shí)作業(yè)處于后備狀態(tài)。為了管理和調(diào)度作業(yè)，為每個(gè)作業(yè)設(shè)置一個(gè)作業(yè)控制塊（JCB）。作業(yè)控制塊記錄了作業(yè)類型和資源要求等有關(guān)信息。作業(yè)控制塊按作業(yè)類型組成一個(gè)或多個(gè)后備作業(yè)隊(duì)列。運(yùn)行狀態(tài)一個(gè)在后備作業(yè)隊(duì)列的作業(yè)被作業(yè)調(diào)度程序選中后，分配必要的資源，建立一組相應(yīng)的進(jìn)程后，調(diào)入內(nèi)存，該作業(yè)就進(jìn)入運(yùn)行狀態(tài)。進(jìn)程各狀態(tài)（進(jìn)程運(yùn)行態(tài)、內(nèi)存進(jìn)程就緒態(tài)、內(nèi)存阻塞態(tài)、外存進(jìn)程就緒態(tài)、外存進(jìn)程阻塞態(tài)等）都對(duì)應(yīng)作業(yè)運(yùn)行狀態(tài)。完成狀態(tài)當(dāng)進(jìn)程正常運(yùn)行結(jié)束或因發(fā)生錯(cuò)誤而終止時(shí)，作業(yè)進(jìn)入完成狀態(tài)。終止作業(yè)程序?qū)⒇?fù)責(zé)善后處理。作業(yè)狀態(tài)的轉(zhuǎn)換:作業(yè)調(diào)度作業(yè)調(diào)度程序按一定算法從后備作業(yè)隊(duì)列中選一個(gè)滿足資源要求的作業(yè)，分配它所要求的資源，建立一組相應(yīng)的進(jìn)程，設(shè)置該進(jìn)程狀態(tài)為就緒態(tài)，并將該進(jìn)程插入內(nèi)存就緒隊(duì)列，參加CPU爭奪。終止作業(yè)當(dāng)進(jìn)程正常運(yùn)行結(jié)束或因發(fā)生錯(cuò)誤終止時(shí)，調(diào)用終止作業(yè)程序，它負(fù)責(zé)將輸出文件緩沖輸出到輸出井，并調(diào)用SPOOLing系統(tǒng)輸出進(jìn)程將作業(yè)輸出文件在打印機(jī)輸出。同時(shí)回收作業(yè)所使用內(nèi)、外存、I/O設(shè)備等各種資源，最后調(diào)用記帳程序結(jié)清作業(yè)費(fèi)用。

2．作業(yè)控制塊JCB(JobControlBlock)為了管理和調(diào)度作業(yè)，在多道批處理系統(tǒng)中為每個(gè)作業(yè)設(shè)置了一個(gè)作業(yè)控制塊，如同進(jìn)程控制塊是進(jìn)程在系統(tǒng)中存在的標(biāo)志一樣，它是作業(yè)在系統(tǒng)中存在的標(biāo)志，其中保存了系統(tǒng)對(duì)作業(yè)進(jìn)行管理和調(diào)度所需的全部信息。在JCB中所包含的內(nèi)容因系統(tǒng)而異，通常應(yīng)包含的內(nèi)容有：作業(yè)標(biāo)識(shí)、用戶名稱、用戶帳戶、作業(yè)類型(CPU繁忙型、I/O繁忙型、批量型、終端型)、作業(yè)狀態(tài)、調(diào)度信息(優(yōu)先級(jí)、作業(yè)已運(yùn)行時(shí)間)、資源需求(預(yù)計(jì)運(yùn)行時(shí)間、要求內(nèi)存大小、要求I/O設(shè)備的類型和數(shù)量等)、進(jìn)入系統(tǒng)時(shí)間、開始處理時(shí)間、作業(yè)完成時(shí)間、作業(yè)退出時(shí)間、資源使用情況等。

每當(dāng)作業(yè)進(jìn)入系統(tǒng)時(shí)，系統(tǒng)便為每個(gè)作業(yè)建立一個(gè)JCB，根據(jù)作業(yè)類型將它插入相應(yīng)的后備隊(duì)列中。作業(yè)調(diào)度程序依據(jù)一定的調(diào)度算法來調(diào)度它們，被調(diào)度到的作業(yè)將會(huì)裝入內(nèi)存。在作業(yè)運(yùn)行期間，系統(tǒng)就按照J(rèn)CB中的信息對(duì)作業(yè)進(jìn)行控制。當(dāng)一個(gè)作業(yè)執(zhí)行結(jié)束進(jìn)入完成狀態(tài)時(shí)，系統(tǒng)負(fù)責(zé)回收分配給它的資源，撤消它的作業(yè)控制塊。

3．作業(yè)調(diào)度作業(yè)調(diào)度的主要功能是根據(jù)作業(yè)控制塊中的信息，審查系統(tǒng)能否滿足用戶作業(yè)的資源需求，以及按照一定的算法，從外存的后備隊(duì)列中選取某些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進(jìn)程、分配必要的資源。然后再將新創(chuàng)建的進(jìn)程插入就緒隊(duì)列，準(zhǔn)備執(zhí)行。因此，有時(shí)也把作業(yè)調(diào)度稱為接納調(diào)度(AdmissionScheduling)。

對(duì)用戶而言，總希望自己作業(yè)的周轉(zhuǎn)時(shí)間盡可能的少，最好周轉(zhuǎn)時(shí)間就等于作業(yè)的執(zhí)行時(shí)間。然而對(duì)系統(tǒng)來說，則希望作業(yè)的平均周轉(zhuǎn)時(shí)間盡可能少，有利于提高CPU的利用率和系統(tǒng)的吞吐量。為此，每個(gè)系統(tǒng)在選擇作業(yè)調(diào)度算法時(shí)，既應(yīng)考慮用戶的要求，又能確保系統(tǒng)具有較高的效率。在每次執(zhí)行作業(yè)調(diào)度時(shí)，都須做出以下兩個(gè)決定。

1)決定接納多少個(gè)作業(yè)作業(yè)調(diào)度每次要接納多少個(gè)作業(yè)進(jìn)入內(nèi)存，取決于多道程序度(DegreeofMultiprogramming)，即允許多少個(gè)作業(yè)同時(shí)在內(nèi)存中運(yùn)行。當(dāng)內(nèi)存中同時(shí)運(yùn)行的作業(yè)數(shù)目太多時(shí)，可能會(huì)影響到系統(tǒng)的服務(wù)質(zhì)量，比如，使周轉(zhuǎn)時(shí)間太長。但如果在內(nèi)存中同時(shí)運(yùn)行作業(yè)的數(shù)量太少時(shí)，又會(huì)導(dǎo)致系統(tǒng)的資源利用率和系統(tǒng)吞吐量太低，因此，多道程序度的確定應(yīng)根據(jù)系統(tǒng)的規(guī)模和運(yùn)行速度等情況做適當(dāng)?shù)恼壑浴?/p>

2)決定接納哪些作業(yè)應(yīng)將哪些作業(yè)從外存調(diào)入內(nèi)存，這將取決于所采用的調(diào)度算法。最簡單的是先來先服務(wù)調(diào)度算法，這是指將最早進(jìn)入外存的作業(yè)最先調(diào)入內(nèi)存；較常用的一種算法是短作業(yè)優(yōu)先調(diào)度算法，是將外存上最短的作業(yè)最先調(diào)入內(nèi)存；另一種較常用的是基于作業(yè)優(yōu)先級(jí)的調(diào)度算法，該算法是將外存上優(yōu)先級(jí)最高的作業(yè)優(yōu)先調(diào)入內(nèi)存；比較好的一種算法是“響應(yīng)比高者優(yōu)先”的調(diào)度算法。我們將在后面對(duì)上述幾種算法作較為詳細(xì)的介紹。

在批處理系統(tǒng)中，作業(yè)進(jìn)入系統(tǒng)后，總是先駐留在外存的后備隊(duì)列上，因此需要有作業(yè)調(diào)度的過程，以便將它們分批地裝入內(nèi)存。然而在分時(shí)系統(tǒng)中，為了做到及時(shí)響應(yīng)，用戶通過鍵盤輸入的命令或數(shù)據(jù)等都是被直接送入內(nèi)存的，因而無需再配置上述的作業(yè)調(diào)度機(jī)制，但也需要有某些限制性措施來限制進(jìn)入系統(tǒng)的用戶數(shù)。即，如果系統(tǒng)尚未飽和，將接納所有授權(quán)用戶，否則，將拒絕接納。類似地，在實(shí)時(shí)系統(tǒng)中通常也不需要作業(yè)調(diào)度。

3.1.2低級(jí)調(diào)度通常也把低級(jí)調(diào)度(LowLevelScheduling)稱為進(jìn)程調(diào)度或短程調(diào)度(ShortTermScheduling)，它所調(diào)度的對(duì)象是進(jìn)程(或內(nèi)核級(jí)線程)。進(jìn)程調(diào)度是最基本的一種調(diào)度，在多道批處理、分時(shí)和實(shí)時(shí)三種類型的OS中，都必須配置這級(jí)調(diào)度。

1．低級(jí)調(diào)度的功能低級(jí)調(diào)度用于決定就緒隊(duì)列中的哪個(gè)進(jìn)程(或內(nèi)核級(jí)線程，為敘述方便，以后只寫進(jìn)程)應(yīng)獲得處理機(jī)，然后再由分派程序執(zhí)行把處理機(jī)分配給該進(jìn)程的具體操作。

低級(jí)調(diào)度的主要功能如下：

(1)保存處理機(jī)的現(xiàn)場信息。在進(jìn)程調(diào)度進(jìn)行調(diào)度時(shí)，首先需要保存當(dāng)前進(jìn)程的處理機(jī)的現(xiàn)場信息，如程序計(jì)數(shù)器、多個(gè)通用寄存器中的內(nèi)容等，將它們送入該進(jìn)程的進(jìn)程控制塊(PCB)中的相應(yīng)單元。

(2)按某種算法選取進(jìn)程。低級(jí)調(diào)度程序按某種算法如優(yōu)先數(shù)算法、輪轉(zhuǎn)法等，從就緒隊(duì)列中選取一個(gè)進(jìn)程，把它的狀態(tài)改為運(yùn)行狀態(tài)，并準(zhǔn)備把處理機(jī)分配給它。

(3)把處理器分配給進(jìn)程。由分派程序(Dispatcher)把處理器分配給進(jìn)程。此時(shí)需為選中的進(jìn)程恢復(fù)處理機(jī)現(xiàn)場，即把選中進(jìn)程的進(jìn)程控制塊內(nèi)有關(guān)處理機(jī)現(xiàn)場的信息裝入處理器相應(yīng)的各個(gè)寄存器中，把處理器的控制權(quán)交給該進(jìn)程，讓它從取出的斷點(diǎn)處開始繼續(xù)運(yùn)行。

2．進(jìn)程調(diào)度中的三個(gè)基本機(jī)制為了實(shí)現(xiàn)進(jìn)程調(diào)度，應(yīng)具有如下三個(gè)基本機(jī)制：

(1)排隊(duì)器。為了提高進(jìn)程調(diào)度的效率，應(yīng)事先將系統(tǒng)中所有的就緒進(jìn)程按照一定的方式排成一個(gè)或多個(gè)隊(duì)列，以便調(diào)度程序能最快地找到它。

(2)分派器(分派程序)。分派器把由進(jìn)程調(diào)度程序所選定的進(jìn)程，從就緒隊(duì)列中取出該進(jìn)程，然后進(jìn)行上下文切換，將處理機(jī)分配給它。

(3)上下文切換機(jī)制。當(dāng)對(duì)處理機(jī)進(jìn)行切換時(shí)，會(huì)發(fā)生兩對(duì)上下文切換操作。在第一對(duì)上下文切換時(shí)，操作系統(tǒng)將保存當(dāng)前進(jìn)程的上下文，而裝入分派程序的上下文，以便分派程序運(yùn)行；在第二對(duì)上下文切換時(shí)，將移出分派程序，而把新選進(jìn)程的CPU現(xiàn)場信息裝入到處理機(jī)的各個(gè)相應(yīng)寄存器中。

應(yīng)當(dāng)指出，上下文切換將花去不少的處理機(jī)時(shí)間，即使是現(xiàn)代計(jì)算機(jī)，每一次上下文切換大約需要花費(fèi)幾毫秒的時(shí)間，該時(shí)間大約可執(zhí)行上千條指令。為此，現(xiàn)在已有通過硬件(采用兩組或多組寄存器)的方法來減少上下文切換的時(shí)間。一組寄存器供處理機(jī)在系統(tǒng)態(tài)時(shí)使用，另一組寄存器供應(yīng)用程序使用。在這種條件下的上下文切換只需改變指針，使其指向當(dāng)前寄存器組即可。

3．進(jìn)程調(diào)度方式進(jìn)程調(diào)度可采用下述兩種調(diào)度方式。

1)非搶占方式(NonpreemptiveMode)在采用這種調(diào)度方式時(shí)，一旦把處理機(jī)分配給某進(jìn)程后，不管它要運(yùn)行多長時(shí)間，都一直讓它運(yùn)行下去，決不會(huì)因?yàn)闀r(shí)鐘中斷等原因而搶占正在運(yùn)行進(jìn)程的處理機(jī)，也不允許其它進(jìn)程搶占已經(jīng)分配給它的處理機(jī)。直至該進(jìn)程完成，自愿釋放處理機(jī)，或發(fā)生某事件而被阻塞時(shí)，才再把處理機(jī)分配給其他進(jìn)程。

在采用非搶占調(diào)度方式時(shí)，可能引起進(jìn)程調(diào)度的因素可歸結(jié)為如下幾個(gè)：

(1)正在執(zhí)行的進(jìn)程執(zhí)行完畢，或因發(fā)生某事件而不能再繼續(xù)執(zhí)行；

(2)執(zhí)行中的進(jìn)程因提出I/O請(qǐng)求而暫停執(zhí)行；

(3)在進(jìn)程通信或同步過程中執(zhí)行了某種原語操作，如P操作(wait操作)、Block原語、Wakeup原語等。這種調(diào)度方式的優(yōu)點(diǎn)是實(shí)現(xiàn)簡單，系統(tǒng)開銷小，適用于大多數(shù)的批處理系統(tǒng)環(huán)境。但它難以滿足緊急任務(wù)的要求——立即執(zhí)行，因而可能造成難以預(yù)料的后果。顯然，在要求比較嚴(yán)格的實(shí)時(shí)系統(tǒng)中，不宜采用這種調(diào)度方式。

2)搶占方式(PreemptiveMode)這種調(diào)度方式允許調(diào)度程序根據(jù)某種原則去暫停某個(gè)正在執(zhí)行的進(jìn)程，將已分配給該進(jìn)程的處理機(jī)重新分配給另一進(jìn)程。搶占方式的優(yōu)點(diǎn)是，可以防止一個(gè)長進(jìn)程長時(shí)間占用處理機(jī)，能為大多數(shù)進(jìn)程提供更公平的服務(wù)，特別是能滿足對(duì)響應(yīng)時(shí)間有著較嚴(yán)格要求的實(shí)時(shí)任務(wù)的需求。但搶占方式比非搶占方式調(diào)度所需付出的開銷較大。搶占調(diào)度方式是基于一定原則的，主要有如下幾條：

(1)優(yōu)先權(quán)原則。通常是對(duì)一些重要的和緊急的作業(yè)賦予較高的優(yōu)先權(quán)。當(dāng)這種作業(yè)到達(dá)時(shí)，如果其優(yōu)先權(quán)比正在執(zhí)行進(jìn)程的優(yōu)先權(quán)高，便停止正在執(zhí)行(當(dāng)前)的進(jìn)程，將處理機(jī)分配給優(yōu)先權(quán)高的新到的進(jìn)程，使之執(zhí)行；或者說，允許優(yōu)先權(quán)高的新到進(jìn)程搶占當(dāng)前進(jìn)程的處理機(jī)。

(2)短作業(yè)(進(jìn)程)優(yōu)先原則。當(dāng)新到達(dá)的作業(yè)(進(jìn)程)比正在執(zhí)行的作業(yè)(進(jìn)程)明顯的短時(shí)，將暫停當(dāng)前長作業(yè)(進(jìn)程)的執(zhí)行，將處理機(jī)分配給新到的短作業(yè)(進(jìn)程)，使之優(yōu)先執(zhí)行；

或者說，短作業(yè)(進(jìn)程)可以搶占當(dāng)前較長作業(yè)(進(jìn)程)的處理機(jī)。

(3)時(shí)間片原則。各進(jìn)程按時(shí)間片輪流運(yùn)行，當(dāng)一個(gè)時(shí)間片用完后，便停止該進(jìn)程的執(zhí)行而重新進(jìn)行調(diào)度。這種原則適用于分時(shí)系統(tǒng)、大多數(shù)的實(shí)時(shí)系統(tǒng)，以及要求較高的批處理系統(tǒng)。

3.1.3中級(jí)調(diào)度中級(jí)調(diào)度(IntermediateLevelScheduling)又稱中程調(diào)度(Medium-TermScheduling)。引入中級(jí)調(diào)度的主要目的是為了提高內(nèi)存利用率和系統(tǒng)吞吐量。為此，應(yīng)使那些暫時(shí)不能運(yùn)行的進(jìn)程不再占用寶貴的內(nèi)存資源，而將它們調(diào)至外存上去等待，把此時(shí)的進(jìn)程狀態(tài)稱為就緒駐外存狀態(tài)或掛起狀態(tài)。當(dāng)這些進(jìn)程重又具備運(yùn)行條件且內(nèi)存又稍有空閑時(shí)，由中級(jí)調(diào)度來決定把外存上的那些又具備運(yùn)行條件的就緒進(jìn)程重新調(diào)入內(nèi)存，并修改其狀態(tài)為就緒狀態(tài)，掛在就緒隊(duì)列上等待進(jìn)程調(diào)度。中級(jí)調(diào)度實(shí)際上就是存儲(chǔ)器管理中的對(duì)換功能，我們將在第四章中做詳細(xì)闡述。

在上述三種調(diào)度中，進(jìn)程調(diào)度的運(yùn)行頻率最高，在分時(shí)系統(tǒng)中通常是10～100ms便進(jìn)行一次進(jìn)程調(diào)度，因此把它稱為短程調(diào)度。為避免進(jìn)程調(diào)度占用太多的CPU時(shí)間，進(jìn)程調(diào)度算法不宜太復(fù)雜。作業(yè)調(diào)度往往是發(fā)生在一個(gè)(批)作業(yè)運(yùn)行完畢，退出系統(tǒng)，而需要重新調(diào)入一個(gè)(批)作業(yè)進(jìn)入內(nèi)存時(shí)，故作業(yè)調(diào)度的周期較長，大約幾分鐘一次，因此把它稱為長程調(diào)度。由于其運(yùn)行頻率較低，故允許作業(yè)調(diào)度算法花費(fèi)較多的時(shí)間。中級(jí)調(diào)度的運(yùn)行頻率基本上介于上述兩種調(diào)度之間，因此把它稱為中程調(diào)度。

3.2調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則

調(diào)度隊(duì)列模型

1．僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型在分時(shí)系統(tǒng)中，通常僅設(shè)置了進(jìn)程調(diào)度，用戶鍵入的命令和數(shù)據(jù)都直接送入內(nèi)存。對(duì)于命令，是由OS為之建立一個(gè)進(jìn)程。系統(tǒng)可以把處于就緒狀態(tài)的進(jìn)程組織成棧、樹或一個(gè)無序鏈表，至于到底采用其中哪種形式，則與OS類型和所采用的調(diào)度算法有關(guān)。例如，在分時(shí)系統(tǒng)中，常把就緒進(jìn)程組織成FIFO隊(duì)列形式。每當(dāng)OS創(chuàng)建一個(gè)新進(jìn)程時(shí)，便將它掛在就緒隊(duì)列的末尾，然后按時(shí)間片輪轉(zhuǎn)方式運(yùn)行。

每個(gè)進(jìn)程在執(zhí)行時(shí)都可能出現(xiàn)以下三種情況：

(1)任務(wù)在給定的時(shí)間片內(nèi)已經(jīng)完成，該進(jìn)程便在釋放處理機(jī)后進(jìn)入完成狀態(tài)；

(2)任務(wù)在本次分得的時(shí)間片內(nèi)尚未完成，OS便將該任務(wù)再放入就緒隊(duì)列的末尾；

(3)在執(zhí)行期間，進(jìn)程因?yàn)槟呈录蛔枞?，被OS放入阻塞隊(duì)列。圖3-1示出了僅具有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型。

圖

3-1僅具有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型

2．具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型在批處理系統(tǒng)中，不僅需要進(jìn)程調(diào)度，而且還需有作業(yè)調(diào)度，由后者按一定的作業(yè)調(diào)度算法，從外存的后備隊(duì)列中選擇一批作業(yè)調(diào)入內(nèi)存，并為它們建立進(jìn)程，送入就緒隊(duì)列，然后才由進(jìn)程調(diào)度按照一定的進(jìn)程調(diào)度算法選擇一個(gè)進(jìn)程，把處理機(jī)分配給該進(jìn)程。圖3-2示出了具有高、低兩級(jí)調(diào)度的調(diào)度隊(duì)列模型。該模型與上一模型的主要區(qū)別在于如下兩個(gè)方面。

(1)就緒隊(duì)列的形式。在批處理系統(tǒng)中，最常用的是最高優(yōu)先權(quán)優(yōu)先調(diào)度算法，相應(yīng)地，最常用的就緒隊(duì)列形式是優(yōu)先權(quán)隊(duì)列。進(jìn)程在進(jìn)入優(yōu)先級(jí)隊(duì)列時(shí)，根據(jù)其優(yōu)先權(quán)的高低，被插入具有相應(yīng)優(yōu)先權(quán)的位置上，這樣，調(diào)度程序總是把處理機(jī)分配給就緒隊(duì)列中的隊(duì)首進(jìn)程。在最高優(yōu)先權(quán)優(yōu)先的調(diào)度算法中，也可采用無序鏈表方式，即每次把新到的進(jìn)程掛在鏈尾，而調(diào)度程序每次調(diào)度時(shí)，是依次比較該鏈中各進(jìn)程的優(yōu)先權(quán)，從中找出優(yōu)先權(quán)最高的進(jìn)程，將之從鏈中摘下，并把處理機(jī)分配給它。顯然，無序鏈表方式與優(yōu)先權(quán)隊(duì)列相比，這種方式的調(diào)度效率較低。

圖

3-2具有高、低兩級(jí)調(diào)度的調(diào)度隊(duì)列模型

(2)設(shè)置多個(gè)阻塞隊(duì)列。對(duì)于小型系統(tǒng)，可以只設(shè)置一個(gè)阻塞隊(duì)列；但當(dāng)系統(tǒng)較大時(shí)，若仍只有一個(gè)阻塞隊(duì)列，其長度必然會(huì)很長，隊(duì)列中的進(jìn)程數(shù)可以達(dá)到數(shù)百個(gè)，這將嚴(yán)重影響對(duì)阻塞隊(duì)列操作的效率。故在大、中型系統(tǒng)中通常都設(shè)置了若干個(gè)阻塞隊(duì)列，每個(gè)隊(duì)列對(duì)應(yīng)于某一種進(jìn)程阻塞事件。

3．同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型當(dāng)在OS中引入中級(jí)調(diào)度后，人們可把進(jìn)程的就緒狀態(tài)分為內(nèi)存就緒(表示進(jìn)程在內(nèi)存中就緒)和外存就緒(進(jìn)程在外存中就緒)。類似地，也可把阻塞狀態(tài)進(jìn)一步分成內(nèi)存阻塞和外存阻塞兩種狀態(tài)。在調(diào)出操作的作用下，可使進(jìn)程狀態(tài)由內(nèi)存就緒轉(zhuǎn)為外存就緒，由內(nèi)存阻塞轉(zhuǎn)為外存阻塞；在中級(jí)調(diào)度的作用下，又可使外存就緒轉(zhuǎn)為內(nèi)存就緒。圖3-3示出了具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型。

圖

3-3具有三級(jí)調(diào)度時(shí)的調(diào)度隊(duì)列模型

選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則

1．面向用戶的準(zhǔn)則

(1)周轉(zhuǎn)時(shí)間短。通常把周轉(zhuǎn)時(shí)間的長短作為評(píng)價(jià)批處理系統(tǒng)的性能、選擇作業(yè)調(diào)度方式與算法的重要準(zhǔn)則之一。所謂周轉(zhuǎn)時(shí)間，是指從作業(yè)被提交給系統(tǒng)開始，到作業(yè)完成為止的這段時(shí)間間隔(稱為作業(yè)周轉(zhuǎn)時(shí)間)。它包括四部分時(shí)間：作業(yè)在外存后備隊(duì)列上等待(作業(yè))調(diào)度的時(shí)間，進(jìn)程在就緒隊(duì)列上等待進(jìn)程調(diào)度的時(shí)間，進(jìn)程在CPU上執(zhí)行的時(shí)間，以及進(jìn)程等待I/O操作完成的時(shí)間。其中的后三項(xiàng)在一個(gè)作業(yè)的整個(gè)處理過程中可能會(huì)發(fā)生多次。

對(duì)每個(gè)用戶而言，都希望自己作業(yè)的周轉(zhuǎn)時(shí)間最短。但作為計(jì)算機(jī)系統(tǒng)的管理者，則總是希望能使平均周轉(zhuǎn)時(shí)間最短，這不僅會(huì)有效地提高系統(tǒng)資源的利用率，而且還可使大多數(shù)用戶都感到滿意?？砂哑骄苻D(zhuǎn)時(shí)間描述為：

作業(yè)的周轉(zhuǎn)時(shí)間T與系統(tǒng)為它提供服務(wù)的時(shí)間Ts之比，即W=T/Ts，稱為帶權(quán)周轉(zhuǎn)時(shí)間，而平均帶權(quán)周轉(zhuǎn)時(shí)間則可表示為：

(2)響應(yīng)時(shí)間快。常把響應(yīng)時(shí)間的長短用來評(píng)價(jià)分時(shí)系統(tǒng)的性能，這是選擇分時(shí)系統(tǒng)中進(jìn)程調(diào)度算法的重要準(zhǔn)則之一。所謂響應(yīng)時(shí)間，是從用戶通過鍵盤提交一個(gè)請(qǐng)求開始，直至系統(tǒng)首次產(chǎn)生響應(yīng)為止的時(shí)間，或者說，直到屏幕上顯示出結(jié)果為止的一段時(shí)間間隔。它包括三部分時(shí)間：從鍵盤輸入的請(qǐng)求信息傳送到處理機(jī)的時(shí)間，處理機(jī)對(duì)請(qǐng)求信息進(jìn)行處理的時(shí)間，以及將所形成的響應(yīng)信息回送到終端顯示器的時(shí)間。

(3)截止時(shí)間的保證。這是評(píng)價(jià)實(shí)時(shí)系統(tǒng)性能的重要指標(biāo)，因而是選擇實(shí)時(shí)調(diào)度算法的重要準(zhǔn)則。所謂截止時(shí)間，是指某任務(wù)必須開始執(zhí)行的最遲時(shí)間，或必須完成的最遲時(shí)間。對(duì)于嚴(yán)格的實(shí)時(shí)系統(tǒng)，其調(diào)度方式和調(diào)度算法必須能保證這一點(diǎn)，否則將可能造成難以預(yù)料的后果。

(4)優(yōu)先權(quán)準(zhǔn)則。在批處理、分時(shí)和實(shí)時(shí)系統(tǒng)中選擇調(diào)度算法時(shí)，都可遵循優(yōu)先權(quán)準(zhǔn)則，以便讓某些緊急的作業(yè)能得到及時(shí)處理。在要求較嚴(yán)格的場合，往往還須選擇搶占式調(diào)度方式，才能保證緊急作業(yè)得到及時(shí)處理。

2．面向系統(tǒng)的準(zhǔn)則這是為了滿足系統(tǒng)要求而應(yīng)遵循的一些準(zhǔn)則。其中，較重要的有以下幾點(diǎn)：

(1)系統(tǒng)吞吐量高。這是用于評(píng)價(jià)批處理系統(tǒng)性能的另一個(gè)重要指標(biāo)，因而是選擇批處理作業(yè)調(diào)度的重要準(zhǔn)則。由于吞吐量是指在單位時(shí)間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)，因而它與批處理作業(yè)的平均長度具有密切關(guān)系。對(duì)于大型作業(yè)，一般吞吐量約為每小時(shí)一道作業(yè)；對(duì)于中、小型作業(yè)，其吞吐量則可能達(dá)到數(shù)十道作業(yè)之多。作業(yè)調(diào)度的方式和算法對(duì)吞吐量的大小也將產(chǎn)生較大影響。事實(shí)上，對(duì)于同一批作業(yè)，若采用了較好的調(diào)度方式和算法，則可顯著地提高系統(tǒng)的吞吐量。

(2)處理機(jī)利用率好。對(duì)于大、中型多用戶系統(tǒng)，由于CPU價(jià)格十分昂貴，致使處理機(jī)的利用率成為衡量系統(tǒng)性能的十分重要的指標(biāo)；而調(diào)度方式和算法對(duì)處理機(jī)的利用率起著十分重要的作用。在實(shí)際系統(tǒng)中，CPU的利用率一般在40%(系統(tǒng)負(fù)荷較輕)到90%之間。在大、中型系統(tǒng)中，在選擇調(diào)度方式和算法時(shí)，應(yīng)考慮到這一準(zhǔn)則。但對(duì)于單用戶微機(jī)或某些實(shí)時(shí)系統(tǒng)，則此準(zhǔn)則就不那么重要了。

(3)各類資源的平衡利用。在大、中型系統(tǒng)中，不僅要使處理機(jī)的利用率高，而且還應(yīng)能有效地利用其它各類資源，如內(nèi)存、外存和I/O設(shè)備等。選擇適當(dāng)?shù)恼{(diào)度方式和算法可以保持系統(tǒng)中各類資源都處于忙碌狀態(tài)。但對(duì)于微型機(jī)和某些實(shí)時(shí)系統(tǒng)而言，該準(zhǔn)則并不重要。

3.3調(diào)

度

算

法

先來先服務(wù)和短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法

1．先來先服務(wù)調(diào)度算法先來先服務(wù)(FCFS)調(diào)度算法是一種最簡單的調(diào)度算法，該算法既可用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度。當(dāng)在作業(yè)調(diào)度中采用該算法時(shí)，每次調(diào)度都是從后備作業(yè)隊(duì)列中選擇一個(gè)或多個(gè)最先進(jìn)入該隊(duì)列的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進(jìn)程，然后放入就緒隊(duì)列。在進(jìn)程調(diào)度中采用FCFS算法時(shí)，則每次調(diào)度是從就緒隊(duì)列中選擇一個(gè)最先進(jìn)入該隊(duì)列的進(jìn)程，為之分配處理機(jī)，使之投入運(yùn)行。該進(jìn)程一直運(yùn)行到完成或發(fā)生某事件而阻塞后才放棄處理機(jī)。

FCFS算法比較有利于長作業(yè)(進(jìn)程)，而不利于短作業(yè)(進(jìn)程)。下表列出了A、B、C、D四個(gè)作業(yè)分別到達(dá)系統(tǒng)的時(shí)間、要求服務(wù)的時(shí)間、開始執(zhí)行的時(shí)間及各自的完成時(shí)間，并計(jì)算出各自的周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間。

從表上可以看出，其中短作業(yè)C的帶權(quán)周轉(zhuǎn)時(shí)間競高達(dá)100，這是不能容忍的；而長作業(yè)D的帶權(quán)周轉(zhuǎn)時(shí)間僅為1.99。據(jù)此可知，F(xiàn)CFS調(diào)度算法有利于CPU繁忙型的作業(yè)，而不利于I/O繁忙型的作業(yè)(進(jìn)程)。CPU繁忙型作業(yè)是指該類作業(yè)需要大量的CPU時(shí)間進(jìn)行計(jì)算，而很少請(qǐng)求I/O。通常的科學(xué)計(jì)算便屬于CPU繁忙型作業(yè)。I/O繁忙型作業(yè)是指CPU進(jìn)行處理時(shí)需頻繁地請(qǐng)求I/O。目前的大多數(shù)事務(wù)處理都屬于I/O繁忙型作業(yè)。作業(yè)調(diào)度算法舉例1-FCFS作業(yè)提交時(shí)刻

ts運(yùn)行時(shí)間

tr開始時(shí)刻

tb完成時(shí)刻

tc周轉(zhuǎn)時(shí)間Ti帶權(quán)周轉(zhuǎn)時(shí)間Wi18.002.008.0010.002.001.0028.500.5010.0010.502.004.0039.000.1010.5010.601.6016.0049.500.2010.6010.801.306.50平均周轉(zhuǎn)時(shí)間T=1.725(小時(shí))平均帶權(quán)周轉(zhuǎn)時(shí)間W=6.8756.9027.50

在此，我們通過一個(gè)例子來說明采用FCFS調(diào)度算法時(shí)的調(diào)度性能。圖3-4(a)示出有五個(gè)進(jìn)程A、B、C、D、E，它們到達(dá)的時(shí)間分別是0、1、2、3和4，所要求的服務(wù)時(shí)間分別是4、3、5、2和4，其完成時(shí)間分別是4、7、12、14和18。從每個(gè)進(jìn)程的完成時(shí)間中減去其到達(dá)時(shí)間，即得到其周轉(zhuǎn)時(shí)間，進(jìn)而可以算出每個(gè)進(jìn)程的帶權(quán)周轉(zhuǎn)時(shí)間。

圖3-4

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

2．短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法SJ(P)F，是指對(duì)短作業(yè)或短進(jìn)程優(yōu)先調(diào)度的算法。它們可以分別用于作業(yè)調(diào)度和進(jìn)程調(diào)度。短作業(yè)優(yōu)先(SJF)的調(diào)度算法是從后備隊(duì)列中選擇一個(gè)或若干個(gè)估計(jì)運(yùn)行時(shí)間最短的作業(yè)，將它們調(diào)入內(nèi)存運(yùn)行。而短進(jìn)程優(yōu)先(SPF)調(diào)度算法則是從就緒隊(duì)列中選出一個(gè)估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，將處理機(jī)分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機(jī)時(shí)再重新調(diào)度。

為了和FCFS調(diào)度算法進(jìn)行比較，我們?nèi)岳肍CFS算法中所使用的實(shí)例，并改用SJ(P)F算法重新調(diào)度，再進(jìn)行性能分析。由圖3-4中的(a)和(b)可以看出，采用SJ(P)F算法后，不論是平均周轉(zhuǎn)時(shí)間還是平均帶權(quán)周轉(zhuǎn)時(shí)間，都有較明顯的改善，尤其是對(duì)短作業(yè)D，其周轉(zhuǎn)時(shí)間由原來的(用FCFS算法時(shí))11降為3；而平均帶權(quán)周轉(zhuǎn)時(shí)間是從5.5降到1.5。這說明SJF調(diào)度算法能有效地降低作業(yè)的平均等待時(shí)間，提高系統(tǒng)吞吐量。

作業(yè)調(diào)度算法舉例1-SJT作業(yè)提交時(shí)刻ts運(yùn)行時(shí)間tr開始時(shí)刻tb完成時(shí)刻tc周轉(zhuǎn)時(shí)間Ti帶權(quán)周轉(zhuǎn)時(shí)間Wi18.002.008.0010.002.001.0028.500.5010.3010.802.304.6039.000.1010.0010.101.1011.0049.500.2010.1010.300.804.00平均周轉(zhuǎn)時(shí)間T=1.55(小時(shí))平均帶權(quán)周轉(zhuǎn)時(shí)間W=5.156.2020.60

SJ(P)F調(diào)度算法也存在不容忽視的缺點(diǎn)：

(1)該算法對(duì)長作業(yè)不利，如作業(yè)C的周轉(zhuǎn)時(shí)間由10增至16，其帶權(quán)周轉(zhuǎn)時(shí)間由2增至3.1。更嚴(yán)重的是，如果有一長作業(yè)(進(jìn)程)進(jìn)入系統(tǒng)的后備隊(duì)列(就緒隊(duì)列)，由于調(diào)度程序總是優(yōu)先調(diào)度那些(即使是后進(jìn)來的)短作業(yè)(進(jìn)程)，將導(dǎo)致長作業(yè)(進(jìn)程)長期不被調(diào)度。

(2)該算法完全未考慮作業(yè)的緊迫程度，因而不能保證緊迫性作業(yè)(進(jìn)程)會(huì)被及時(shí)處理。

(3)由于作業(yè)(進(jìn)程)的長短只是根據(jù)用戶所提供的估計(jì)執(zhí)行時(shí)間而定的，而用戶又可能會(huì)有意或無意地縮短其作業(yè)的估計(jì)運(yùn)行時(shí)間，致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。

高優(yōu)先權(quán)優(yōu)先調(diào)度算法

1．優(yōu)先權(quán)調(diào)度算法的類型為了照顧緊迫型作業(yè)，使之在進(jìn)入系統(tǒng)后便獲得優(yōu)先處理，引入了最高優(yōu)先權(quán)優(yōu)先(FPF)調(diào)度算法。此算法常被用于批處理系統(tǒng)中，作為作業(yè)調(diào)度算法，也作為多種操作系統(tǒng)中的進(jìn)程調(diào)度算法，還可用于實(shí)時(shí)系統(tǒng)中。當(dāng)把該算法用于作業(yè)調(diào)度時(shí)，系統(tǒng)將從后備隊(duì)列中選擇若干個(gè)優(yōu)先權(quán)最高的作業(yè)裝入內(nèi)存。當(dāng)用于進(jìn)程調(diào)度時(shí)，該算法是把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程，這時(shí)，又可進(jìn)一步把該算法分成如下兩種。

1)非搶占式優(yōu)先權(quán)算法在這種方式下，系統(tǒng)一旦把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程后，該進(jìn)程便一直執(zhí)行下去，直至完成；或因發(fā)生某事件使該進(jìn)程放棄處理機(jī)時(shí)，系統(tǒng)方可再將處理機(jī)重新分配給另一優(yōu)先權(quán)最高的進(jìn)程。這種調(diào)度算法主要用于批處理系統(tǒng)中；也可用于某些對(duì)實(shí)時(shí)性要求不嚴(yán)的實(shí)時(shí)系統(tǒng)中。

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

2．優(yōu)先權(quán)的類型對(duì)于最高優(yōu)先權(quán)優(yōu)先調(diào)度算法，其關(guān)鍵在于：它是使用靜態(tài)優(yōu)先權(quán)，還是用動(dòng)態(tài)優(yōu)先權(quán)，以及如何確定進(jìn)程的優(yōu)先權(quán)。

1)靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進(jìn)程時(shí)確定的，且在進(jìn)程的整個(gè)運(yùn)行期間保持不變。一般地，優(yōu)先權(quán)是利用某一范圍內(nèi)的一個(gè)整數(shù)來表示的，例如，0～7或0～255中的某一整數(shù)，又把該整數(shù)稱為優(yōu)先數(shù)，只是具體用法各異：有的系統(tǒng)用“0”表示最高優(yōu)先權(quán)，當(dāng)數(shù)值愈大時(shí)，其優(yōu)先權(quán)愈低；而有的系統(tǒng)恰恰相反。

確定進(jìn)程優(yōu)先權(quán)的依據(jù)有如下三個(gè)方面：

(1)進(jìn)程類型。通常，系統(tǒng)進(jìn)程(如接收進(jìn)程、對(duì)換進(jìn)程、磁盤I/O進(jìn)程)的優(yōu)先權(quán)高于一般用戶進(jìn)程的優(yōu)先權(quán)。

(2)進(jìn)程對(duì)資源的需求。如進(jìn)程的估計(jì)執(zhí)行時(shí)間及內(nèi)存需要量的多少，對(duì)這些要求少的進(jìn)程應(yīng)賦予較高的優(yōu)先權(quán)。

(3)用戶要求。這是由用戶進(jìn)程的緊迫程度及用戶所付費(fèi)用的多少來確定優(yōu)先權(quán)的。靜態(tài)優(yōu)先權(quán)法簡單易行，系統(tǒng)開銷小，但不夠精確，很可能出現(xiàn)優(yōu)先權(quán)低的作業(yè)(進(jìn)程)長期沒有被調(diào)度的情況。因此，僅在要求不高的系統(tǒng)中才使用靜態(tài)優(yōu)先權(quán)。

2)動(dòng)態(tài)優(yōu)先權(quán)動(dòng)態(tài)優(yōu)先權(quán)是指在創(chuàng)建進(jìn)程時(shí)所賦予的優(yōu)先權(quán)，是可以隨進(jìn)程的推進(jìn)或隨其等待時(shí)間的增加而改變的，以便獲得更好的調(diào)度性能。例如，我們可以規(guī)定，在就緒隊(duì)列中的進(jìn)程，隨其等待時(shí)間的增長，其優(yōu)先權(quán)以速率a提高。若所有的進(jìn)程都具有相同的優(yōu)先權(quán)初值，則顯然是最先進(jìn)入就緒隊(duì)列的進(jìn)程將因其動(dòng)態(tài)優(yōu)先權(quán)變得最高而優(yōu)先獲得處理機(jī)，此即FCFS算法。若所有的就緒進(jìn)程具有各不相同的優(yōu)先權(quán)初值，那么，對(duì)于優(yōu)先權(quán)初值低的進(jìn)程，在等待了足夠的時(shí)間后，其優(yōu)先權(quán)便可能升為最高，從而可以獲得處理機(jī)。當(dāng)采用搶占式優(yōu)先權(quán)調(diào)度算法時(shí)，如果再規(guī)定當(dāng)前進(jìn)程的優(yōu)先權(quán)以速率b下降，則可防止一個(gè)長作業(yè)長期地壟斷處理機(jī)。

3．高響應(yīng)比優(yōu)先調(diào)度算法在批處理系統(tǒng)中，短作業(yè)優(yōu)先算法是一種比較好的算法，其主要的不足之處是長作業(yè)的運(yùn)行得不到保證。如果我們能為每個(gè)作業(yè)引入前面所述的動(dòng)態(tài)優(yōu)先權(quán)，并使作業(yè)的優(yōu)先級(jí)隨著等待時(shí)間的增加而以速率a提高，則長作業(yè)在等待一定的時(shí)間后，必然有機(jī)會(huì)分配到處理機(jī)。該優(yōu)先權(quán)的變化規(guī)律可描述為：

由于等待時(shí)間與服務(wù)時(shí)間之和就是系統(tǒng)對(duì)該作業(yè)的響應(yīng)時(shí)間，故該優(yōu)先權(quán)又相當(dāng)于響應(yīng)比RP。據(jù)此，又可表示為：

由上式可以看出：

(1)如果作業(yè)的等待時(shí)間相同，則要求服務(wù)的時(shí)間愈短，其優(yōu)先權(quán)愈高，因而該算法有利于短作業(yè)。

(2)當(dāng)要求服務(wù)的時(shí)間相同時(shí)，作業(yè)的優(yōu)先權(quán)決定于其等待時(shí)間，等待時(shí)間愈長，其優(yōu)先權(quán)愈高，因而它實(shí)現(xiàn)的是先來先服務(wù)。

(3)對(duì)于長作業(yè)，作業(yè)的優(yōu)先級(jí)可以隨等待時(shí)間的增加而提高，當(dāng)其等待時(shí)間足夠長時(shí)，其優(yōu)先級(jí)便可升到很高，從而也可獲得處理機(jī)。簡言之，該算法既照顧了短作業(yè)，又考慮了作業(yè)到達(dá)的先后次序，不會(huì)使長作業(yè)長期得不到服務(wù)。因此，該算法實(shí)現(xiàn)了一種較好的折衷。當(dāng)然，在利用該算法時(shí)，每要進(jìn)行調(diào)度之前，都須先做響應(yīng)比的計(jì)算，這會(huì)增加系統(tǒng)開銷。

作業(yè)調(diào)度算法舉例1-HRN作業(yè)提交時(shí)刻ts運(yùn)行時(shí)間tr開始時(shí)刻tb完成時(shí)刻tc周轉(zhuǎn)時(shí)間Ti帶權(quán)周轉(zhuǎn)時(shí)間Wi18.002.008.0010.002.001.0028.500.5010.1010.602.104.2039.000.1010.0010.101.1011.0049.500.2010.6010.801.306.50平均周轉(zhuǎn)時(shí)間T=1.625(小時(shí))平均帶權(quán)周轉(zhuǎn)時(shí)間W=5.6756.5022.72基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法

1．時(shí)間片輪轉(zhuǎn)法

1)基本原理在早期的時(shí)間片輪轉(zhuǎn)法中，系統(tǒng)將所有的就緒進(jìn)程按先來先服務(wù)的原則排成一個(gè)隊(duì)列，每次調(diào)度時(shí)，把CPU分配給隊(duì)首進(jìn)程，并令其執(zhí)行一個(gè)時(shí)間片。時(shí)間片的大小從幾ms到幾百ms。當(dāng)執(zhí)行的時(shí)間片用完時(shí)，由一個(gè)計(jì)時(shí)器發(fā)出時(shí)鐘中斷請(qǐng)求，調(diào)度程序便據(jù)此信號(hào)來停止該進(jìn)程的執(zhí)行，并將它送往就緒隊(duì)列的末尾；然后，再把處理機(jī)分配給就緒隊(duì)列中新的隊(duì)首進(jìn)程，同時(shí)也讓它執(zhí)行一個(gè)時(shí)間片。這樣就可以保證就緒隊(duì)列中的所有進(jìn)程在一給定的時(shí)間內(nèi)均能獲得一時(shí)間片的處理機(jī)執(zhí)行時(shí)間。換言之，系統(tǒng)能在給定的時(shí)間內(nèi)響應(yīng)所有用戶的請(qǐng)求。

2)時(shí)間片大小的確定在時(shí)間片輪轉(zhuǎn)算法中，時(shí)間片的大小對(duì)系統(tǒng)性能有很大的影響，如選擇很小的時(shí)間片將有利于短作業(yè)，因?yàn)樗茌^快地完成，但會(huì)頻繁地發(fā)生中斷、進(jìn)程上下文的切換，從而增加系統(tǒng)的開銷；反之，如選擇太長的時(shí)間片，使得每個(gè)進(jìn)程都能在一個(gè)時(shí)間片內(nèi)完成，時(shí)間片輪轉(zhuǎn)算法便退化為FCFS算法，無法滿足交互式用戶的需求。一個(gè)較為可取的大小是，時(shí)間片略大于一次典型的交互所需要的時(shí)間。這樣可使大多數(shù)進(jìn)程在一個(gè)時(shí)間片內(nèi)完成。圖3-5示出了時(shí)間片分別為q=1和q=4時(shí)，A、B、C、D、E五個(gè)進(jìn)程的運(yùn)行情況，而圖3-6為q=1和q=4時(shí)各進(jìn)程的平均周轉(zhuǎn)時(shí)間和帶權(quán)平均周轉(zhuǎn)時(shí)間。圖中的RR(RoundRobin)表示輪轉(zhuǎn)調(diào)度算法。

圖3-5q=1和q=4時(shí)的進(jìn)程運(yùn)行情況

圖3-6q=1和q=4時(shí)進(jìn)程的周轉(zhuǎn)時(shí)間

2．多級(jí)反饋隊(duì)列調(diào)度算法

(1)應(yīng)設(shè)置多個(gè)就緒隊(duì)列，并為各個(gè)隊(duì)列賦予不同的優(yōu)先級(jí)。第一個(gè)隊(duì)列的優(yōu)先級(jí)最高，第二個(gè)隊(duì)列次之，其余各隊(duì)列的優(yōu)先權(quán)逐個(gè)降低。該算法賦予各個(gè)隊(duì)列中進(jìn)程執(zhí)行時(shí)間片的大小也各不相同，在優(yōu)先權(quán)愈高的隊(duì)列中，為每個(gè)進(jìn)程所規(guī)定的執(zhí)行時(shí)間片就愈小。例如，第二個(gè)隊(duì)列的時(shí)間片要比第一個(gè)隊(duì)列的時(shí)間片長一倍，……，第i+1個(gè)隊(duì)列的時(shí)間片要比第i個(gè)隊(duì)列的時(shí)間片長一倍。圖3-7是多級(jí)反饋隊(duì)列算法的示意。

圖

3-7多級(jí)反饋隊(duì)列調(diào)度算法

(2)當(dāng)一個(gè)新進(jìn)程進(jìn)入內(nèi)存后，首先將它放入第一隊(duì)列的末尾，按FCFS原則排隊(duì)等待調(diào)度。當(dāng)輪到該進(jìn)程執(zhí)行時(shí)，如它能在該時(shí)間片內(nèi)完成，便可準(zhǔn)備撤離系統(tǒng)；如果它在一個(gè)時(shí)間片結(jié)束時(shí)尚未完成，調(diào)度程序便將該進(jìn)程轉(zhuǎn)入第二隊(duì)列的末尾，再同樣地按FCFS原則等待調(diào)度執(zhí)行；如果它在第二隊(duì)列中運(yùn)行一個(gè)時(shí)間片后仍未完成，再依次將它放入第三隊(duì)列，……，如此下去，當(dāng)一個(gè)長作業(yè)(進(jìn)程)從第一隊(duì)列依次降到第n隊(duì)列后，在第n隊(duì)列中便采取按時(shí)間片輪轉(zhuǎn)的方式運(yùn)行。

(3)僅當(dāng)?shù)谝魂?duì)列空閑時(shí)，調(diào)度程序才調(diào)度第二隊(duì)列中的進(jìn)程運(yùn)行；僅當(dāng)?shù)?～(i-1)隊(duì)列均空時(shí)，才會(huì)調(diào)度第i隊(duì)列中的進(jìn)程運(yùn)行。如果處理機(jī)正在第i隊(duì)列中為某進(jìn)程服務(wù)時(shí)，又有新進(jìn)程進(jìn)入優(yōu)先權(quán)較高的隊(duì)列(第1～(i-1)中的任何一個(gè)隊(duì)列)，則此時(shí)新進(jìn)程將搶占正在運(yùn)行進(jìn)程的處理機(jī)，即由調(diào)度程序把正在運(yùn)行的進(jìn)程放回到第i隊(duì)列的末尾，把處理機(jī)分配給新到的高優(yōu)先權(quán)進(jìn)程。

3．多級(jí)反饋隊(duì)列調(diào)度算法的性能多級(jí)反饋隊(duì)列調(diào)度算法具有較好的性能，能很好地滿足各種類型用戶的需要。

(1)終端型作業(yè)用戶。由于終端型作業(yè)用戶所提交的作業(yè)大多屬于交互型作業(yè)，作業(yè)通常較小，系統(tǒng)只要能使這些作業(yè)(進(jìn)程)在第一隊(duì)列所規(guī)定的時(shí)間片內(nèi)完成，便可使終端型作業(yè)用戶都感到滿意。

(2)短批處理作業(yè)用戶。對(duì)于很短的批處理型作業(yè)，開始時(shí)像終端型作業(yè)一樣，如果僅在第一隊(duì)列中執(zhí)行一個(gè)時(shí)間片即可完成，便可獲得與終端型作業(yè)一樣的響應(yīng)時(shí)間。對(duì)于稍長的作業(yè)，通常也只需在第二隊(duì)列和第三隊(duì)列各執(zhí)行一個(gè)時(shí)間片即可完成，其周轉(zhuǎn)時(shí)間仍然較短。

(3)長批處理作業(yè)用戶。對(duì)于長作業(yè)，它將依次在第1，2，…，n個(gè)隊(duì)列中運(yùn)行，然后再按輪轉(zhuǎn)方式運(yùn)行，用戶不必?fù)?dān)心其作業(yè)長期得不到處理。

補(bǔ)充材料:多道程序環(huán)境中的作業(yè)調(diào)度1。多道程序?qū)χ苻D(zhuǎn)時(shí)間的影響等待時(shí)間百分?jǐn)?shù)多道程序道數(shù)125507524.020.052.930.46.334.640.01.520.650.00.311.060.00.15.270.00.02.2

CPU進(jìn)度：在給定的時(shí)間間隔內(nèi)，CPU為一個(gè)作業(yè)做了多少“工作”。例如：在單道程序系統(tǒng)中，設(shè)一個(gè)作業(yè)等待I/O的時(shí)間占運(yùn)行時(shí)間的25%，則在一小時(shí)內(nèi)CPU的進(jìn)度為0.75小時(shí)；現(xiàn)在，有兩個(gè)同時(shí)開始投入運(yùn)行的作業(yè)，其等待I/O時(shí)間都占25%，且都需要1.5小時(shí)的CPU時(shí)間，那么其CPU進(jìn)度怎么計(jì)算呢？兩個(gè)作業(yè)將在什么時(shí)候完成呢？從表中可查得，CPU將空閑4%的時(shí)間。即在一小時(shí)內(nèi)對(duì)兩個(gè)作業(yè)的進(jìn)度為0.96小時(shí)，因而每個(gè)作業(yè)的進(jìn)度僅為0.48小時(shí)。顯然，為完成這兩個(gè)作業(yè)所需的總時(shí)間為1.5/0.48，得3.125小時(shí)。如果這兩個(gè)作業(yè)在單道環(huán)境下，就需要4小時(shí)?？梢?，多道程序設(shè)計(jì)的好處是明顯的。時(shí)間事件并行CPU每個(gè)作業(yè)經(jīng)過作業(yè)每個(gè)作業(yè)需要的作業(yè)數(shù)等待%占CPU%時(shí)間的進(jìn)度CPU時(shí)間8.00作業(yè)1到11.508.50作業(yè)2到125750.510.3751.12520.375

10.240.8859.00作業(yè)3到24480.520.240.13530.075

10.0750.8109.226作業(yè)3結(jié)束30.433.20.22620.0750.0630.0750.09.351作業(yè)2結(jié)束24480.12510.060.7520.060.09.5作業(yè)4到125750.14910.1120.63840.159.8125作業(yè)4結(jié)束24480.312510.150.48840.150.010.4632作業(yè)1結(jié)束125750.650710.4880.0多道程序環(huán)境中的作業(yè)調(diào)度舉例作業(yè)提交時(shí)刻ts

運(yùn)行時(shí)間tr

開始時(shí)刻tb

完成時(shí)刻tc

周轉(zhuǎn)時(shí)間Ti帶權(quán)周轉(zhuǎn)時(shí)間Wi18.002.008.0010.46322.46321.231628.500.508.509.3510.8511.70239.000.109.009.2260.2262.2649.500.209.509.81250.31251.5625平均周轉(zhuǎn)時(shí)間T=0.9632(小時(shí))平均帶權(quán)周轉(zhuǎn)時(shí)間W=1.6893.85276.75612。多道程序系統(tǒng)中的調(diào)度算法基于先來先服務(wù)：按作業(yè)到達(dá)的先后順序建立一個(gè)后備作業(yè)隊(duì)列，當(dāng)需要調(diào)度作業(yè)時(shí)，由調(diào)度程序從頭開始掃描這個(gè)隊(duì)列，直至找到一個(gè)資源能得到滿足的作業(yè)為止?；趦?yōu)先級(jí)：在作業(yè)到達(dá)時(shí)，根據(jù)這個(gè)作業(yè)的優(yōu)先級(jí)插入到相應(yīng)優(yōu)先級(jí)隊(duì)列中，當(dāng)需要調(diào)度作業(yè)時(shí)，由調(diào)度程序從非空隊(duì)列的最高優(yōu)先級(jí)開始逐級(jí)進(jìn)行掃描，直至找到一個(gè)資源能得到滿足的作業(yè)為止。同一優(yōu)先級(jí)中則按“先來先服務(wù)”的原則選擇。分時(shí)和優(yōu)先級(jí)相結(jié)合：該算法主要用于分時(shí)系統(tǒng)中，優(yōu)先級(jí)高的作業(yè)可以“排擠”優(yōu)先級(jí)比它低的正在運(yùn)行的作業(yè)。被排擠下來的作業(yè)放在其原來所處優(yōu)先級(jí)隊(duì)列的首部，以便下次盡快地調(diào)度到它。下次運(yùn)行的時(shí)間配給量等于上次運(yùn)行未用完的時(shí)間量。多道程序環(huán)境中的作業(yè)調(diào)度舉例多道環(huán)境作業(yè)調(diào)度算法舉例1

例題:在某多道程序系統(tǒng)中，供用戶使用的內(nèi)存空間有１００K，磁帶機(jī)２臺(tái)，打印機(jī)１臺(tái)。系統(tǒng)采用可變式分區(qū)管理內(nèi)存，對(duì)磁帶機(jī)和打印機(jī)采用靜態(tài)分配方式，并假設(shè)輸入／輸出操作的時(shí)間忽略不計(jì)?，F(xiàn)有一作業(yè)序列如下表所示。作業(yè)號(hào)到達(dá)時(shí)間計(jì)算時(shí)間要求內(nèi)存申請(qǐng)磁帶機(jī)數(shù)申請(qǐng)打印機(jī)數(shù)

————————————————————————————————

１8:00２５分鐘15K1臺(tái)1臺(tái)２8:20１０分鐘30K1臺(tái)３8:20２０分鐘60K1臺(tái)４8:30２０分鐘20K1臺(tái)５8:35１５分鐘10K1臺(tái)1臺(tái)

————————————————————————————————

假設(shè)作業(yè)調(diào)度采用先來先服務(wù)算法，優(yōu)先分配內(nèi)存的低地址區(qū)域且不移動(dòng)已在內(nèi)存中的作業(yè)，在內(nèi)存中的作業(yè)平分CPU時(shí)間，試問：⑴作業(yè)調(diào)度選中作業(yè)的次序是什么？⑵每個(gè)作業(yè)的周轉(zhuǎn)時(shí)間和平均周轉(zhuǎn)時(shí)間分別是多少？⑶作業(yè)全部執(zhí)行結(jié)束的時(shí)間是多少？時(shí)間事件并行內(nèi)存使每個(gè)作業(yè)經(jīng)過作業(yè)每個(gè)作業(yè)需要的作業(yè)數(shù)用情況占CPU%時(shí)間的進(jìn)度CPU時(shí)間8:00作業(yè)1開始1258:20作業(yè)3開始11002012053208:30作業(yè)1結(jié)束250101503515

作業(yè)4開始4209:00作業(yè)3結(jié)束250303150

作業(yè)2開始41552109:10作業(yè)4結(jié)束250104502559:15作業(yè)2結(jié)束11005250

作業(yè)5開始5159:30作業(yè)5結(jié)束1100155150圖示圖示圖示圖示圖示圖示作業(yè)提交時(shí)刻ts運(yùn)行時(shí)間tr開始時(shí)刻tb完成時(shí)刻tc周轉(zhuǎn)時(shí)間Ti帶權(quán)周轉(zhuǎn)時(shí)間Wi18:00258.008:30301.228:20109:009:15555.538:20208:209:0040248:30208:309:1040258:35159:159:30553.67平均周轉(zhuǎn)時(shí)間T=44(分鐘)平均帶權(quán)周轉(zhuǎn)時(shí)間W=2.87422014.37作業(yè)1進(jìn)入內(nèi)存后的資源使用情況015k100k作業(yè)18:00~8:20返回磁帶機(jī)打印機(jī)10作業(yè)1作業(yè)3進(jìn)入內(nèi)存后的資源使用情況015k100k作業(yè)1作業(yè)375k8:20~8:30返回磁帶機(jī)打印機(jī)00作業(yè)1作業(yè)4進(jìn)入內(nèi)存后的資源使用情況015k100k作業(yè)1作業(yè)375k95k作業(yè)48:30~9:00返回磁帶機(jī)打印機(jī)01作業(yè)2進(jìn)入內(nèi)存后的資源使用情況030k100k作業(yè)175k95k作業(yè)4作業(yè)29:00~9:10返回磁帶機(jī)打印機(jī)10作業(yè)4結(jié)束后的資源使用情況030k100k作業(yè)1作業(yè)29:10~9:15返回磁帶機(jī)打印機(jī)20作業(yè)5進(jìn)入內(nèi)存后的資源使用情況010k100k作業(yè)1作業(yè)59:15~9:30返回磁帶機(jī)打印機(jī)103.4實(shí)

時(shí)

調(diào)

度

實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件

1．提供必要的信息為了實(shí)現(xiàn)實(shí)時(shí)調(diào)度，系統(tǒng)應(yīng)向調(diào)度程序提供有關(guān)任務(wù)的下述一些信息：

(1)就緒時(shí)間。這是該任務(wù)成為就緒狀態(tài)的起始時(shí)間，在周期任務(wù)的情況下，它就是事先預(yù)知的一串時(shí)間序列；而在非周期任務(wù)的情況下，它也可能是預(yù)知的。

(2)開始截止時(shí)間和完成截止時(shí)間。對(duì)于典型的實(shí)時(shí)應(yīng)用，只須知道開始截止時(shí)間，或者知道完成截止時(shí)間。

(3)處理時(shí)間。這是指一個(gè)任務(wù)從開始執(zhí)行直至完成所需的時(shí)間。在某些情況下，該時(shí)間也是系統(tǒng)提供的。

(4)資源要求。這是指任務(wù)執(zhí)行時(shí)所需的一組資源。

(5)優(yōu)先級(jí)。如果某任務(wù)的開始截止時(shí)間已經(jīng)錯(cuò)過，就會(huì)引起故障，則應(yīng)為該任務(wù)賦予“絕對(duì)”優(yōu)先級(jí)；如果開始截止時(shí)間的推遲對(duì)任務(wù)的繼續(xù)運(yùn)行無重大影響，則可為該任務(wù)賦予“相對(duì)”優(yōu)先級(jí)，供調(diào)度程序參考。

2．系統(tǒng)處理能力強(qiáng)在實(shí)時(shí)系統(tǒng)中，通常都有著多個(gè)實(shí)時(shí)任務(wù)。若處理機(jī)的處理能力不夠強(qiáng)，則有可能因處理機(jī)忙不過來而使某些實(shí)時(shí)任務(wù)不能得到及時(shí)處理，從而導(dǎo)致發(fā)生難以預(yù)料的后果。

假定系統(tǒng)中有m個(gè)周期性的硬實(shí)時(shí)任務(wù)，它們的處理時(shí)間可表示為Ci，周期時(shí)間表示為Pi，則在單處理機(jī)情況下，必須滿足下面的限制條件：

系統(tǒng)才是可調(diào)度的。假如系統(tǒng)中有6個(gè)硬實(shí)時(shí)任務(wù)，它們的周期時(shí)間都是50ms，而每次的處理時(shí)間為10ms，則不難算出，此時(shí)是不能滿足上式的，因而系統(tǒng)是不可調(diào)度的。

解決的方法是提高系統(tǒng)的處理能力，其途徑有二：其一仍是采用單處理機(jī)系統(tǒng)，但須增強(qiáng)其處理能力，以顯著地減少對(duì)每一個(gè)任務(wù)的處理時(shí)間；其二是采用多處理機(jī)系統(tǒng)。假定系統(tǒng)中的處理機(jī)數(shù)為N，則應(yīng)將上述的限制條件改為：

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

4．具有快速切換機(jī)制為保證要求較高的硬實(shí)時(shí)任務(wù)能及時(shí)運(yùn)行，在實(shí)時(shí)系統(tǒng)中還應(yīng)具有快速切換機(jī)制，以保證能進(jìn)行任務(wù)的快速切換。該機(jī)制應(yīng)具有如下兩方面的能力：

(1)對(duì)外部中斷的快速響應(yīng)能力。為使在緊迫的外部事件請(qǐng)求中斷時(shí)系統(tǒng)能及時(shí)響應(yīng)，要求系統(tǒng)具有快速硬件中斷機(jī)構(gòu)，還應(yīng)使禁止中斷的時(shí)間間隔盡量短，以免耽誤時(shí)機(jī)(其它緊迫任務(wù))。

(2)快速的任務(wù)分派能力。在完成任務(wù)調(diào)度后，便應(yīng)進(jìn)行任務(wù)切換。為了提高分派程序進(jìn)行任務(wù)切換時(shí)的速度，應(yīng)使系統(tǒng)中的每個(gè)運(yùn)行功能單位適當(dāng)?shù)匦?，以減少任務(wù)切換的時(shí)間開銷。

實(shí)時(shí)調(diào)度算法的分類

1．非搶占式調(diào)度算法

1)非搶占式輪轉(zhuǎn)調(diào)度算法該算法常用于工業(yè)生產(chǎn)的群控系統(tǒng)中，由一臺(tái)計(jì)算機(jī)控制若干個(gè)相同的(或類似的)對(duì)象，為每一個(gè)被控對(duì)象建立一個(gè)實(shí)時(shí)任務(wù)，并將它們排成一個(gè)輪轉(zhuǎn)隊(duì)列。調(diào)度程序每次選擇隊(duì)列中的第一個(gè)任務(wù)投入運(yùn)行。當(dāng)該任務(wù)完成后，便把它掛在輪轉(zhuǎn)隊(duì)列的末尾，等待下次調(diào)度運(yùn)行，而調(diào)度程序再選擇下一個(gè)(隊(duì)首)任務(wù)運(yùn)行。這種調(diào)度算法可獲得數(shù)秒至數(shù)十秒的響應(yīng)時(shí)間，可用于要求不太嚴(yán)格的實(shí)時(shí)控制系統(tǒng)中。

2)非搶占式優(yōu)先調(diào)度算法如果在實(shí)時(shí)系統(tǒng)中存在著要求較為嚴(yán)格(響應(yīng)時(shí)間為數(shù)百毫秒)的任務(wù)，則可采用非搶占式優(yōu)先調(diào)度算法為這些任務(wù)賦予較高的優(yōu)先級(jí)。當(dāng)這些實(shí)時(shí)任務(wù)到達(dá)時(shí)，把它們安排在就緒隊(duì)列的隊(duì)首，等待當(dāng)前任務(wù)自我終止或運(yùn)行完成后才能被調(diào)度執(zhí)行。這種調(diào)度算法在做了精心的處理后，有可能獲得僅為數(shù)秒至數(shù)百毫秒級(jí)的響應(yīng)時(shí)間，因而可用于有一定要求的實(shí)時(shí)控制系統(tǒng)中。

2．搶占式調(diào)度算法在要求較嚴(yán)格的(響應(yīng)時(shí)間為數(shù)十毫秒以下)的實(shí)時(shí)系統(tǒng)中，應(yīng)采用搶占式優(yōu)先權(quán)調(diào)度算法?？筛鶕?jù)搶占發(fā)生時(shí)間的不同而進(jìn)一步分成以下兩種調(diào)度算法。

1)基于時(shí)鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法在某實(shí)時(shí)任務(wù)到達(dá)后，如果該任務(wù)的優(yōu)先級(jí)高于當(dāng)前任務(wù)的優(yōu)先級(jí)，這時(shí)并不立即搶占當(dāng)前任務(wù)的處理機(jī)，而是等到時(shí)鐘中斷到來時(shí)，調(diào)度程序才剝奪當(dāng)前任務(wù)的執(zhí)行，將處理機(jī)分配給新到的高優(yōu)先權(quán)任務(wù)。這種調(diào)度算法能獲得較好的響應(yīng)效果，其調(diào)度延遲可降為幾十毫秒至幾毫秒。因此，此算法可用于大多數(shù)的實(shí)時(shí)系統(tǒng)中。

2)立即搶占(ImmediatePreemption)的優(yōu)先權(quán)調(diào)度算法在這種調(diào)度策略中，要求操作系統(tǒng)具有快速響應(yīng)外部事件中斷的能力。一旦出現(xiàn)外部中斷，只要當(dāng)前任務(wù)未處于臨界區(qū)，便立即剝奪當(dāng)前任務(wù)的執(zhí)行，把處理機(jī)分配給請(qǐng)求中斷的緊迫任務(wù)。這種算法能獲得非?？斓捻憫?yīng)，可把調(diào)度延遲降低到幾毫秒至100微秒，甚至更低。圖3-8中的(a)、(b)、(c)、(d)分別示出了采用非搶占式輪轉(zhuǎn)調(diào)度算法、非搶占式優(yōu)先權(quán)調(diào)度算法、基于時(shí)鐘中斷搶占的優(yōu)先權(quán)調(diào)度算法和立即搶占的優(yōu)先權(quán)調(diào)度算法四種情況的調(diào)度時(shí)間。

圖3-8實(shí)時(shí)進(jìn)程調(diào)度

常用的幾種實(shí)時(shí)調(diào)度算法

1．最早截止時(shí)間優(yōu)先即EDF(EarliestDeadlineFirst)算法該算法是根據(jù)任務(wù)的開始截止時(shí)間來確定任務(wù)的優(yōu)先級(jí)。截止時(shí)間愈早，其優(yōu)先級(jí)愈高。該算法要求在系統(tǒng)中保持一個(gè)實(shí)時(shí)任務(wù)就緒隊(duì)列，該隊(duì)列按各任務(wù)截止時(shí)間的早晚排序；當(dāng)然，具有最早截止時(shí)間的任務(wù)排在隊(duì)列的最前面。調(diào)度程序在選擇任務(wù)時(shí)，總是選擇就緒隊(duì)列中的第一個(gè)任務(wù)，為之分配處理機(jī)，使之投入運(yùn)行。最早截止時(shí)間優(yōu)先算法既可用于搶占式調(diào)度，也可用于非搶占式調(diào)度方式中。

1)非搶占式調(diào)度方式用于非周期實(shí)時(shí)任務(wù)圖3-9示出了將該算法用于非搶占調(diào)度方式之例。該例中具有四個(gè)非周期任務(wù)，它們先后到達(dá)。系統(tǒng)首先調(diào)度任務(wù)1執(zhí)行，在任務(wù)1執(zhí)行期間，任務(wù)2、3又先后到達(dá)。由于任務(wù)3的開始截止時(shí)間早于任務(wù)2，故系統(tǒng)在任務(wù)1后將調(diào)度任務(wù)3執(zhí)行。在此期間又到達(dá)作業(yè)4，其開始截止時(shí)間仍是早于任務(wù)2的，故在任務(wù)3執(zhí)行完后，系統(tǒng)又調(diào)度任務(wù)4執(zhí)行，最后才調(diào)度任務(wù)2執(zhí)行。

圖3-9

EDF算法用于非搶占調(diào)度的調(diào)度方式

2)搶占式調(diào)度方式用于周期實(shí)時(shí)任務(wù)圖3-10示出了將最早截止時(shí)間優(yōu)先算法用于搶占調(diào)度方式之例。在該例中有兩個(gè)周期性任務(wù)，任務(wù)A的周期時(shí)間為20ms，每個(gè)周期的處理時(shí)間為10ms；任務(wù)B的周期時(shí)間為50ms，每個(gè)周期的處理時(shí)間為25ms。圖中的第一行示出了兩個(gè)任務(wù)的到達(dá)時(shí)間、最后期限和執(zhí)行時(shí)間圖。其中任務(wù)A的到達(dá)時(shí)間為0、20、40、…；任務(wù)A的最后期限為20、40、60、…；任務(wù)B的到達(dá)時(shí)間為0、50、100、…；任務(wù)B的最后期限為50、100、150、…(注：單位皆為ms)。

圖3-10最早截止時(shí)間優(yōu)先算法用于搶占調(diào)度方式之例

為了說明通常的優(yōu)先級(jí)調(diào)度不能適用于實(shí)時(shí)系統(tǒng)，該圖特增加了第二和第三行。在第二行中假定任務(wù)A具有較高的優(yōu)先級(jí)，所以在t=0ms時(shí)，先調(diào)度A1執(zhí)行，在A1完成后(t=10ms)才調(diào)度B1執(zhí)行；在t=20ms時(shí)，調(diào)度A2執(zhí)行；在t=30ms時(shí)，A2完成，又調(diào)度B1執(zhí)行；在t=40ms時(shí)，調(diào)度A3執(zhí)行；在t=50ms時(shí)，雖然A3已完成，但B1已錯(cuò)過了它的最后期限，這說明了利用通常的優(yōu)先級(jí)調(diào)度已經(jīng)失敗。第三行與第二行類似，只是假定任務(wù)B具有較高的優(yōu)先級(jí)。

第四行是采用最早截止時(shí)間優(yōu)先算法的時(shí)間圖。在t=0時(shí)，A1和B1同時(shí)到達(dá)，由于A1的截止時(shí)間比B1早，故調(diào)度A1執(zhí)行；在t=10時(shí)，A1完成，又調(diào)度B1執(zhí)行；在t=20時(shí)，A2到達(dá)，由于A2的截止時(shí)間比B2早，B1被中斷而調(diào)度A2執(zhí)行；在t=30時(shí)，A2完成，又重新調(diào)度B1執(zhí)行；在t=40時(shí)，A3又到達(dá)，但B1的截止時(shí)間要比A3早，仍應(yīng)讓B1繼續(xù)執(zhí)行直到完成(t=45)，然后再調(diào)度A3執(zhí)行；在t=55時(shí)，A3完成，又調(diào)度B2執(zhí)行。在該例中利用最早截止時(shí)間優(yōu)先算法可以滿足系統(tǒng)的要求。

2．最低松弛度優(yōu)先即LLF(LeastLaxityFirst)算法該算法是根據(jù)任務(wù)緊急(或松弛)的程度，來確定任務(wù)的優(yōu)先級(jí)。任務(wù)的緊急程度愈高，為該任務(wù)所賦予的優(yōu)先級(jí)就愈高，以使之優(yōu)先執(zhí)行。例如，一個(gè)任務(wù)在200ms時(shí)必須完成，而它本身所需的運(yùn)行時(shí)間就有100ms，因此，調(diào)度程序必須在100ms之前調(diào)度執(zhí)行，該任務(wù)的緊急程度(松弛程度)為100ms。又如，另一任務(wù)在400ms時(shí)必須完成，它本身需要運(yùn)行

150ms，則其松弛程度為

250ms。在實(shí)現(xiàn)該算法時(shí)要求系統(tǒng)中有一個(gè)按松弛度排序的實(shí)時(shí)任務(wù)就緒隊(duì)列，松弛度最低的任務(wù)排在隊(duì)列最前面，調(diào)度程序總是選擇就緒隊(duì)列中的隊(duì)首任務(wù)執(zhí)行。

該算法主要用于可搶占調(diào)度方式中。假如在一個(gè)實(shí)時(shí)系統(tǒng)中，有兩個(gè)周期性實(shí)時(shí)任務(wù)A和B，任務(wù)A要求每

20ms執(zhí)行一次，執(zhí)行時(shí)間為

10ms；任務(wù)B只要求每50ms執(zhí)行一次，執(zhí)行時(shí)間為

25ms。由此可得知任務(wù)A和B每次必須完成的時(shí)間分別為：A1、A2、A3、…和B1、B2、B3、…，見圖3-11。為保證不遺漏任何一次截止時(shí)間，應(yīng)采用最低松弛度優(yōu)先的搶占調(diào)度策略。

圖

3-11

A和B任務(wù)每次必須完成的時(shí)間

在剛開始時(shí)(t1?=?0)，A1必須在20ms時(shí)完成，而它本身運(yùn)行又需

10ms，可算出A1的松弛度為10ms；B1必須在50ms時(shí)完成，而它本身運(yùn)行就需25ms，可算出B1的松弛度為25ms，故調(diào)度程序應(yīng)先調(diào)度A1執(zhí)行。在t2?=?10ms時(shí)，A2的松弛度可按下式算出：

A2的松弛度?=?必須完成時(shí)間?-?其本身的運(yùn)行時(shí)間?-?當(dāng)前時(shí)間

=?40ms-10ms-10ms?=?20ms

類似地，可算出B1的松弛度為15ms，故調(diào)度程序應(yīng)選擇B2運(yùn)行。在t3?=?30ms時(shí)，A2的松弛度已減為0(即40?-?10?-?30)，而B1的松弛度為15ms(即50?-?5?-?30)，于是調(diào)度程序應(yīng)搶占B1的處理機(jī)而調(diào)度A2運(yùn)行。在t4?=?40ms時(shí)，A3的松弛度為10ms(即60?-?10?-?40)，而B1的松弛度僅為5ms(即50?-?5?-?40)，故又應(yīng)重新調(diào)度B1執(zhí)行。在t5?=?45ms時(shí)，B1執(zhí)行完成，而此時(shí)A3的松弛度已減為5ms(即60?-?10?-?45)，而B2的松弛度為30ms(即100?-?25?-?45)，于是又應(yīng)調(diào)度A3執(zhí)行。在t6?=?55ms時(shí)，任務(wù)A尚未進(jìn)入第4周期，而任務(wù)B已進(jìn)入第2周期，故再調(diào)度B2執(zhí)行。在t7?=?70ms時(shí)，A4的松弛度已減至0ms(即80?-?10?-?70)，而B2的松弛度為20ms(即100?-?10?-?70)，故此時(shí)調(diào)度又應(yīng)搶占B2的處理機(jī)而調(diào)度A4執(zhí)行。圖3-12示出了具有兩個(gè)周期性實(shí)時(shí)任務(wù)的調(diào)度情況。

圖

3-12利用LLF算法進(jìn)行調(diào)度的情況

3.5產(chǎn)生死鎖的原因和必要條件

產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因可歸結(jié)為如下兩點(diǎn)：

(1)競爭資源。當(dāng)系統(tǒng)中供多個(gè)進(jìn)程共享的資源如打印機(jī)、公用隊(duì)列等，其數(shù)目不足以滿足諸進(jìn)程的需要時(shí)，會(huì)引起諸進(jìn)程對(duì)資源的競爭而產(chǎn)生死鎖。

(2)進(jìn)程間推進(jìn)順序非法。進(jìn)程在運(yùn)行過程中，請(qǐng)求和釋放資源的順序不當(dāng)，也同樣會(huì)導(dǎo)致產(chǎn)生進(jìn)程死鎖。

1．競爭資源引起進(jìn)程死鎖

1)可剝奪和非剝奪性資源可把系統(tǒng)中的資源分成兩類，一類是可剝奪性資源，是指某進(jìn)程在獲得這類資源后，該資源可以再被