1、.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 死鎖的檢測與解除死鎖的檢測與解除 .2.3.1 處理機調(diào)度的層次處理機調(diào)度的層次 3.1.1 高級調(diào)度高級調(diào)度(High Level Scheduling) 高級調(diào)度又稱為高級調(diào)度又稱為作業(yè)調(diào)度作業(yè)調(diào)度或或長程調(diào)度長程調(diào)度(LongTerm Scheduling)，其調(diào)度對象是作業(yè)。，其調(diào)度對象是作業(yè)。

2、1. 作業(yè)和作業(yè)步作業(yè)和作業(yè)步(1) 作業(yè)作業(yè)(Job) 作業(yè)是一個比程序更為廣泛的概念，它不僅包含通作業(yè)是一個比程序更為廣泛的概念，它不僅包含通常的程序和數(shù)據(jù)，而且還配有一份常的程序和數(shù)據(jù)，而且還配有一份作業(yè)說明書作業(yè)說明書，系統(tǒng)根，系統(tǒng)根據(jù)作業(yè)說明書來對程序的運行進行控制。據(jù)作業(yè)說明書來對程序的運行進行控制。 在批處理系統(tǒng)中，以作業(yè)為基本單位從外存調(diào)入內(nèi)在批處理系統(tǒng)中，以作業(yè)為基本單位從外存調(diào)入內(nèi)存的。存的。 .3.(2) 作業(yè)步作業(yè)步(Job Step) 在作業(yè)運行期間，每個作業(yè)都必須經(jīng)過若干在作業(yè)運行期間，每個作業(yè)都必須經(jīng)過若干個相對獨立、又相互關(guān)聯(lián)的順序加工步驟才能得個相對獨立、又相

3、互關(guān)聯(lián)的順序加工步驟才能得到結(jié)果，我們把其中的每一個加工步驟稱為一個到結(jié)果，我們把其中的每一個加工步驟稱為一個作業(yè)步作業(yè)步。 各作業(yè)步之間存在著相互聯(lián)系，通常上一個各作業(yè)步之間存在著相互聯(lián)系，通常上一個作業(yè)步的輸出作為下一個作業(yè)步的輸入。作業(yè)步的輸出作為下一個作業(yè)步的輸入。 3.1 處理機調(diào)度的層次處理機調(diào)度的層次 .4.一個典型的作業(yè)可分成三個作業(yè)步：一個典型的作業(yè)可分成三個作業(yè)步： “編譯編譯”作業(yè)步：作業(yè)步：通過執(zhí)行編譯程序?qū)υ闯掏ㄟ^執(zhí)行編譯程序?qū)υ闯绦蜻M行編譯，產(chǎn)生若干個目標程序段；序進行編譯，產(chǎn)生若干個目標程序段； “連結(jié)裝配連結(jié)裝配”作業(yè)步：作業(yè)步：將將“編譯編譯”作業(yè)步所作業(yè)步所

4、產(chǎn)生的若干個目標程序段裝配成可執(zhí)行的目標程產(chǎn)生的若干個目標程序段裝配成可執(zhí)行的目標程序；序； “運行運行”作業(yè)步：作業(yè)步：將可執(zhí)行的目標程序讀入將可執(zhí)行的目標程序讀入內(nèi)存并控制其運行。內(nèi)存并控制其運行。3.1 處理機調(diào)度的層次處理機調(diào)度的層次 .5.(3) 作業(yè)流作業(yè)流 若干個作業(yè)進入系統(tǒng)后，被依次存放在外存若干個作業(yè)進入系統(tǒng)后，被依次存放在外存上，便形成了上，便形成了輸入作業(yè)流輸入作業(yè)流。 在操作系統(tǒng)的控制下，逐個作業(yè)進行處理，在操作系統(tǒng)的控制下，逐個作業(yè)進行處理，于是便形成了于是便形成了處理作業(yè)流處理作業(yè)流。 3.1 處理機調(diào)度的層次處理機調(diào)度的層次 .6.2. 作業(yè)控制塊作業(yè)控制塊JCB

5、(Job Control Block) 為管理和調(diào)度作業(yè)，在多道批處理系統(tǒng)中為每個作業(yè)設置為管理和調(diào)度作業(yè)，在多道批處理系統(tǒng)中為每個作業(yè)設置一個作業(yè)控制塊，作為作業(yè)在系統(tǒng)中存在的標志，其中保存了一個作業(yè)控制塊，作為作業(yè)在系統(tǒng)中存在的標志，其中保存了系統(tǒng)對作業(yè)進行管理和調(diào)度所需的全部信息。系統(tǒng)對作業(yè)進行管理和調(diào)度所需的全部信息。JCB中的內(nèi)容因系統(tǒng)而異，通常包含：中的內(nèi)容因系統(tǒng)而異，通常包含： 作業(yè)標識、用戶名稱、用戶帳戶、作業(yè)類型作業(yè)標識、用戶名稱、用戶帳戶、作業(yè)類型(CPU繁忙型、繁忙型、I/O繁忙型、批量型、終端型繁忙型、批量型、終端型)、作業(yè)狀態(tài)、調(diào)度信息、作業(yè)狀態(tài)、調(diào)度信息(優(yōu)先級、優(yōu)

6、先級、已運行時間已運行時間)、資源需求、資源需求(預計運行時間、要求內(nèi)存大小、要求預計運行時間、要求內(nèi)存大小、要求I/O設備的類型和數(shù)量設備的類型和數(shù)量)、進入系統(tǒng)時間、開始處理時間、作業(yè)、進入系統(tǒng)時間、開始處理時間、作業(yè)完成時間、作業(yè)退出時間、資源使用情況等。完成時間、作業(yè)退出時間、資源使用情況等。 3.1 處理機調(diào)度的層次處理機調(diào)度的層次 .7.每當作業(yè)進入系統(tǒng)時，系統(tǒng)便為每個作業(yè)建立每當作業(yè)進入系統(tǒng)時，系統(tǒng)便為每個作業(yè)建立一個一個JCB，根據(jù)作業(yè)類型將它插入相應的后備隊列，根據(jù)作業(yè)類型將它插入相應的后備隊列中。中。 作業(yè)調(diào)度程序依據(jù)一定的調(diào)度算法來調(diào)度它們，作業(yè)調(diào)度程序依據(jù)一定的調(diào)度算法

7、來調(diào)度它們，被調(diào)度到的作業(yè)將會裝入內(nèi)存。在作業(yè)運行期間，被調(diào)度到的作業(yè)將會裝入內(nèi)存。在作業(yè)運行期間，系統(tǒng)就按照系統(tǒng)就按照JCB中的信息對作業(yè)進行控制。中的信息對作業(yè)進行控制。 當一個作業(yè)執(zhí)行結(jié)束進入完成狀態(tài)時，系統(tǒng)負當一個作業(yè)執(zhí)行結(jié)束進入完成狀態(tài)時，系統(tǒng)負責回收分配給它的資源，撤消它的作業(yè)控制塊。責回收分配給它的資源，撤消它的作業(yè)控制塊。 3.1 處理機調(diào)度的層次處理機調(diào)度的層次 .8.3作業(yè)調(diào)度作業(yè)調(diào)度作業(yè)調(diào)度的主要功能是根據(jù)作業(yè)控制塊中的信息，作業(yè)調(diào)度的主要功能是根據(jù)作業(yè)控制塊中的信息，審查系統(tǒng)能否滿足用戶作業(yè)的資源需求，以及按照一審查系統(tǒng)能否滿足用戶作業(yè)的資源需求，以及按照一定的算法，從

8、外存的后備隊列中選取某些作業(yè)調(diào)入內(nèi)定的算法，從外存的后備隊列中選取某些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進程、分配必要的資源。然后再將存，并為它們創(chuàng)建進程、分配必要的資源。然后再將新創(chuàng)建的進程插入就緒隊列，準備執(zhí)行。新創(chuàng)建的進程插入就緒隊列，準備執(zhí)行。 因此，有時作業(yè)調(diào)度也稱為因此，有時作業(yè)調(diào)度也稱為接納調(diào)度接納調(diào)度(Admission Scheduling)。 3.1 處理機調(diào)度的層次處理機調(diào)度的層次 .9.對用戶而言，總希望自己作業(yè)的周轉(zhuǎn)時間盡可能對用戶而言，總希望自己作業(yè)的周轉(zhuǎn)時間盡可能的短，最好周轉(zhuǎn)時間就等于作業(yè)的執(zhí)行時間。的短，最好周轉(zhuǎn)時間就等于作業(yè)的執(zhí)行時間。 對系統(tǒng)來說，則希望作業(yè)的平均

9、周轉(zhuǎn)時間盡可能對系統(tǒng)來說，則希望作業(yè)的平均周轉(zhuǎn)時間盡可能少，有利于提高少，有利于提高CPU 的利用率和系統(tǒng)的吞吐量。的利用率和系統(tǒng)的吞吐量。 為此，每個系統(tǒng)在選擇作業(yè)調(diào)度算法時，既應考為此，每個系統(tǒng)在選擇作業(yè)調(diào)度算法時，既應考慮用戶的要求，又能確保系統(tǒng)具有較高的效率。慮用戶的要求，又能確保系統(tǒng)具有較高的效率。3.1 處理機調(diào)度的層次處理機調(diào)度的層次 .10.系統(tǒng)每次執(zhí)行作業(yè)調(diào)度時，必須做出兩個決定系統(tǒng)每次執(zhí)行作業(yè)調(diào)度時，必須做出兩個決定:1) 決定接納多少個作業(yè)決定接納多少個作業(yè)作業(yè)調(diào)度每次要接納多少個作業(yè)進入內(nèi)存，取決于作業(yè)調(diào)度每次要接納多少個作業(yè)進入內(nèi)存，取決于多道程序度多道程序度( De

10、gree of Multiprogramming )，即允許多即允許多少個作業(yè)同時在內(nèi)存中運行少個作業(yè)同時在內(nèi)存中運行。當內(nèi)存中同時運行的作業(yè)。當內(nèi)存中同時運行的作業(yè)數(shù)目太多時，可能會影響到系統(tǒng)的服務質(zhì)量，數(shù)目太多時，可能會影響到系統(tǒng)的服務質(zhì)量，比如使周比如使周轉(zhuǎn)時間太長。轉(zhuǎn)時間太長。但如果在內(nèi)存中同時運行作業(yè)的數(shù)量太少但如果在內(nèi)存中同時運行作業(yè)的數(shù)量太少時，又會導致系統(tǒng)的資源利用率和系統(tǒng)吞吐量太低。因時，又會導致系統(tǒng)的資源利用率和系統(tǒng)吞吐量太低。因此，此，多道程序度多道程序度的確定應根據(jù)系統(tǒng)的規(guī)模和運行速度等的確定應根據(jù)系統(tǒng)的規(guī)模和運行速度等情況做適當?shù)恼壑?。情況做適當?shù)恼壑浴?3.1 處理

11、機調(diào)度的層次處理機調(diào)度的層次 .11.2) 決定接納哪些作業(yè)決定接納哪些作業(yè)將哪些作業(yè)從外存調(diào)入內(nèi)存，取決于所采用的將哪些作業(yè)從外存調(diào)入內(nèi)存，取決于所采用的調(diào)度算法。調(diào)度算法。 先來先服務調(diào)度算法先來先服務調(diào)度算法 短作業(yè)優(yōu)先調(diào)度算法短作業(yè)優(yōu)先調(diào)度算法 作業(yè)優(yōu)先級調(diào)度算法作業(yè)優(yōu)先級調(diào)度算法 “響應比高者優(yōu)先響應比高者優(yōu)先”調(diào)度算法調(diào)度算法3.1 處理機調(diào)度的層次處理機調(diào)度的層次 .12.說明：說明： 批處理系統(tǒng)中，批處理系統(tǒng)中，作業(yè)進入系統(tǒng)后，總是先駐留在作業(yè)進入系統(tǒng)后，總是先駐留在外存的后備隊列上，因此需要有作業(yè)調(diào)度的過程，以外存的后備隊列上，因此需要有作業(yè)調(diào)度的過程，以便將它們分批地裝入內(nèi)

12、存。便將它們分批地裝入內(nèi)存。 分時系統(tǒng)中，分時系統(tǒng)中，為了做到及時響應，用戶通過鍵盤為了做到及時響應，用戶通過鍵盤輸入的命令或數(shù)據(jù)都被直接送入內(nèi)存，因而無需再配輸入的命令或數(shù)據(jù)都被直接送入內(nèi)存，因而無需再配置上述的作業(yè)調(diào)度機制，但也需要有某些限制性措施置上述的作業(yè)調(diào)度機制，但也需要有某些限制性措施來限制進入系統(tǒng)的用戶數(shù)。來限制進入系統(tǒng)的用戶數(shù)。 實時系統(tǒng)中，實時系統(tǒng)中，通常也不需要作業(yè)調(diào)度。通常也不需要作業(yè)調(diào)度。 3.1 處理機調(diào)度的層次處理機調(diào)度的層次 .13.3.1.2 低級調(diào)度低級調(diào)度(Low Level Scheduling)通 常通 常 低 級 調(diào) 度低 級 調(diào) 度 稱 為稱 為 進

13、 程 調(diào) 度進 程 調(diào) 度 或或 短 程 調(diào) 度短 程 調(diào) 度(ShortTerm Scheduling)，它所調(diào)度的對象是進程，它所調(diào)度的對象是進程(或或內(nèi)核級線程內(nèi)核級線程)。進程調(diào)度是最基本的一種調(diào)度，在多道。進程調(diào)度是最基本的一種調(diào)度，在多道批處理、分時和實時三種類型的批處理、分時和實時三種類型的OS中，都必須配置這中，都必須配置這級調(diào)度。級調(diào)度。1低級調(diào)度的功能低級調(diào)度的功能低級調(diào)度用于決定就緒隊列中的哪個進程低級調(diào)度用于決定就緒隊列中的哪個進程(或內(nèi)核或內(nèi)核級線程級線程)應獲得處理機，然后再由應獲得處理機，然后再由分派程序分派程序執(zhí)行把處理執(zhí)行把處理機分配給該進程的具體操作。機分配

14、給該進程的具體操作。3.1 處理機調(diào)度的層次處理機調(diào)度的層次 .14.低級調(diào)度的低級調(diào)度的3個主要功能：個主要功能： (1) 保存處理機的現(xiàn)場信息保存處理機的現(xiàn)場信息 在進程調(diào)度進行調(diào)度時，首先需要保存當前進程在進程調(diào)度進行調(diào)度時，首先需要保存當前進程的處理機的現(xiàn)場信息，如程序計數(shù)器、多個通用寄存的處理機的現(xiàn)場信息，如程序計數(shù)器、多個通用寄存器中的內(nèi)容等，將它們送入該進程的進程控制塊器中的內(nèi)容等，將它們送入該進程的進程控制塊(PCB)中的相應單元。中的相應單元。(2) 按某種算法選取進程按某種算法選取進程 低級調(diào)度程序按某種算法如優(yōu)先級算法、輪轉(zhuǎn)法低級調(diào)度程序按某種算法如優(yōu)先級算法、輪轉(zhuǎn)法等，

15、從就緒隊列中選取一個進程，把它的狀態(tài)改為運等，從就緒隊列中選取一個進程，把它的狀態(tài)改為運行狀態(tài)，并準備把處理機分配給它。行狀態(tài)，并準備把處理機分配給它。 3.1 處理機調(diào)度的層次處理機調(diào)度的層次 .15.(3) 把處理器分配給進程把處理器分配給進程 由由分派程序分派程序(Dispatcher)把處理器分配給進程。把處理器分配給進程。此時需為選中的進程恢復處理機現(xiàn)場，即把選中進此時需為選中的進程恢復處理機現(xiàn)場，即把選中進程的進程控制塊內(nèi)有關(guān)處理機現(xiàn)場的信息裝入處理程的進程控制塊內(nèi)有關(guān)處理機現(xiàn)場的信息裝入處理器相應的各個寄存器中，把處理器的控制權(quán)交給該器相應的各個寄存器中，把處理器的控制權(quán)交給該進

16、程，讓它從取出的斷點處開始繼續(xù)運行。進程，讓它從取出的斷點處開始繼續(xù)運行。 3.1 處理機調(diào)度的層次處理機調(diào)度的層次 .16.2進程調(diào)度中的三個基本機制進程調(diào)度中的三個基本機制為實現(xiàn)進程調(diào)度，應具有如下三個基本機制：為實現(xiàn)進程調(diào)度，應具有如下三個基本機制：(1) 排隊器。排隊器。為了提高進程調(diào)度的效率，應事先將為了提高進程調(diào)度的效率，應事先將系統(tǒng)中所有的就緒進程按照一定的方式排成一個或多系統(tǒng)中所有的就緒進程按照一定的方式排成一個或多個隊列，以便調(diào)度程序能最快地找到它。個隊列，以便調(diào)度程序能最快地找到它。(2) 分派器分派器(分派程序分派程序)。分派器把由進程調(diào)度程序分派器把由進程調(diào)度程序所選定

17、的進程，從就緒隊列中取出，然后進行上下文所選定的進程，從就緒隊列中取出，然后進行上下文切換，將處理機分配給它切換，將處理機分配給它 3.1 處理機調(diào)度的層次處理機調(diào)度的層次 .17. (3) 上下文切換機制。上下文切換機制。當對處理機進行切換時，會當對處理機進行切換時，會發(fā)生兩對上下文切換操作。發(fā)生兩對上下文切換操作。 第一對上下文切換：第一對上下文切換：操作系統(tǒng)將保存當前進程的操作系統(tǒng)將保存當前進程的上下文，而裝入分派程序的上下文，以便分派程序運上下文，而裝入分派程序的上下文，以便分派程序運行。行。 第二對上下文切換：第二對上下文切換：將移出分派程序，而把新選將移出分派程序，而把新選進程的進

18、程的CPU現(xiàn)場信息裝入到處理機的各個相應寄存器現(xiàn)場信息裝入到處理機的各個相應寄存器中。中。 3.1 處理機調(diào)度的層次處理機調(diào)度的層次 .18.特別指出：特別指出：上下文切換將花費處理機時間，即上下文切換將花費處理機時間，即使是現(xiàn)代計算機，每一次上下文切換大約需要花費使是現(xiàn)代計算機，每一次上下文切換大約需要花費幾毫秒的時間，該時間大約可執(zhí)行上千條指令。幾毫秒的時間，該時間大約可執(zhí)行上千條指令。 為此，現(xiàn)在已有通過硬件為此，現(xiàn)在已有通過硬件(采用兩組或多組寄存采用兩組或多組寄存器器)的方法來減少上下文切換的時間。一組寄存器供的方法來減少上下文切換的時間。一組寄存器供處理機在系統(tǒng)態(tài)時使用，另一組寄存

19、器供應用程序處理機在系統(tǒng)態(tài)時使用，另一組寄存器供應用程序使用。在這種條件下的上下文切換只需改變指針，使用。在這種條件下的上下文切換只需改變指針，使其指向當前寄存器組即可。使其指向當前寄存器組即可。 3.1 處理機調(diào)度的層次處理機調(diào)度的層次 .19.3進程調(diào)度方式進程調(diào)度方式進程調(diào)度采用兩種調(diào)度方式：進程調(diào)度采用兩種調(diào)度方式：1) 非搶占方式非搶占方式(Nonpreemptive Mode)采用這種調(diào)度方式時，一旦把處理機分配給某進采用這種調(diào)度方式時，一旦把處理機分配給某進程后，不管它要運行多長時間，都一直讓它運行下去，程后，不管它要運行多長時間，都一直讓它運行下去，決不會因為時鐘中斷等原因而搶

20、占正在運行進程的處決不會因為時鐘中斷等原因而搶占正在運行進程的處理機，也不允許其它進程搶占已經(jīng)分配給它的處理機。理機，也不允許其它進程搶占已經(jīng)分配給它的處理機。直至該進程完成，自愿釋放處理機，或發(fā)生某事件而直至該進程完成，自愿釋放處理機，或發(fā)生某事件而被阻塞時，才再把處理機分配給其他進程。被阻塞時，才再把處理機分配給其他進程。 3.1 處理機調(diào)度的層次處理機調(diào)度的層次 .20. 采用非搶占調(diào)度方式時，可能引起進程調(diào)度的因素采用非搶占調(diào)度方式時，可能引起進程調(diào)度的因素可歸結(jié)為如下幾個：可歸結(jié)為如下幾個：(1) 正在執(zhí)行的進程執(zhí)行完畢，或因發(fā)生某事件不能正在執(zhí)行的進程執(zhí)行完畢，或因發(fā)生某事件不能再

21、繼續(xù)執(zhí)行；再繼續(xù)執(zhí)行；(2) 執(zhí)行中的進程因提出執(zhí)行中的進程因提出I/O請求而暫停執(zhí)行；請求而暫停執(zhí)行；(3) 在進程通信或同步過程中執(zhí)行了某種原語操作，在進程通信或同步過程中執(zhí)行了某種原語操作，如如Wait原語原語、Block原語原語等。等。非搶占調(diào)度方式的優(yōu)點是實現(xiàn)簡單，系統(tǒng)開銷小，非搶占調(diào)度方式的優(yōu)點是實現(xiàn)簡單，系統(tǒng)開銷小，適用于大多數(shù)的批處理系統(tǒng)環(huán)境。但難以滿足緊急任務適用于大多數(shù)的批處理系統(tǒng)環(huán)境。但難以滿足緊急任務立即執(zhí)行的要求，在要求比較嚴格的實時系統(tǒng)中，不宜立即執(zhí)行的要求，在要求比較嚴格的實時系統(tǒng)中，不宜采用這種調(diào)度方式。采用這種調(diào)度方式。 3.1 處理機調(diào)度的層次處理機調(diào)度的層

22、次 .21.2) 搶占方式搶占方式(Preemptive Mode)搶占式調(diào)度方式允許調(diào)度程序根據(jù)某種原則去暫搶占式調(diào)度方式允許調(diào)度程序根據(jù)某種原則去暫停某個正在執(zhí)行的進程，將已分配給該進程的處理機停某個正在執(zhí)行的進程，將已分配給該進程的處理機重新分配給另一進程。重新分配給另一進程。 搶占方式的優(yōu)點：搶占方式的優(yōu)點：可以防止一個長進程長時間占可以防止一個長進程長時間占用處理機，能為大多數(shù)進程提供更公平的服務，特別用處理機，能為大多數(shù)進程提供更公平的服務，特別是能滿足對響應時間有著較嚴格要求的實時任務的需是能滿足對響應時間有著較嚴格要求的實時任務的需求。但搶占方式比非搶占方式調(diào)度所需付出的開銷較

23、求。但搶占方式比非搶占方式調(diào)度所需付出的開銷較大。大。3.1 處理機調(diào)度的層次處理機調(diào)度的層次 .22.搶占調(diào)度方式基于的原則：搶占調(diào)度方式基于的原則：(1) 優(yōu)先權(quán)原則優(yōu)先權(quán)原則 通常是對一些重要的和緊急的作業(yè)賦予較高的通常是對一些重要的和緊急的作業(yè)賦予較高的優(yōu)先權(quán)。當這種作業(yè)到達時，如果其優(yōu)先權(quán)比正在優(yōu)先權(quán)。當這種作業(yè)到達時，如果其優(yōu)先權(quán)比正在執(zhí)行進程的優(yōu)先權(quán)高，便停止正在執(zhí)行的當前進程，執(zhí)行進程的優(yōu)先權(quán)高，便停止正在執(zhí)行的當前進程，將處理機分配給優(yōu)先權(quán)高的新到的進程，使之執(zhí)行；將處理機分配給優(yōu)先權(quán)高的新到的進程，使之執(zhí)行；或者說，允許優(yōu)先權(quán)高的新到進程搶占當前進程的或者說，允許優(yōu)先權(quán)高的

24、新到進程搶占當前進程的處理機。處理機。3.1 處理機調(diào)度的層次處理機調(diào)度的層次 .23.(2) 短作業(yè)短作業(yè)(進程進程)優(yōu)先原則優(yōu)先原則 當新到達的作業(yè)當新到達的作業(yè)(進程進程)比正在執(zhí)行的作業(yè)比正在執(zhí)行的作業(yè)(進程進程)明明顯的短時，將暫停當前長作業(yè)顯的短時，將暫停當前長作業(yè)(進程進程)的執(zhí)行，將處理的執(zhí)行，將處理機分配給新到的短作業(yè)機分配給新到的短作業(yè)(進程進程)，使之優(yōu)先執(zhí)行；或者，使之優(yōu)先執(zhí)行；或者說，短作業(yè)說，短作業(yè)(進程進程)可以搶占當前較長作業(yè)可以搶占當前較長作業(yè)(進程進程)的處理的處理機。機。(3) 時間片原則時間片原則 各進程按時間片輪流運行，當一個時間片用完后，各進程按時間

25、片輪流運行，當一個時間片用完后，便停止該進程的執(zhí)行而重新進行調(diào)度。這種原則適用便停止該進程的執(zhí)行而重新進行調(diào)度。這種原則適用于分時系統(tǒng)、大多數(shù)的實時系統(tǒng)以及要求較高的批處于分時系統(tǒng)、大多數(shù)的實時系統(tǒng)以及要求較高的批處理系統(tǒng)。理系統(tǒng)。 3.1 處理機調(diào)度的層次處理機調(diào)度的層次 .24.3.1.3 中級調(diào)度中級調(diào)度(Intermediate Level Scheduling) 中級調(diào)度中級調(diào)度又稱又稱中程調(diào)度中程調(diào)度(Medium-Term Scheduling)。引引入中級調(diào)度的主要目的是為了提高內(nèi)存利用率和系統(tǒng)吞入中級調(diào)度的主要目的是為了提高內(nèi)存利用率和系統(tǒng)吞吐量。吐量。 將暫時不能運行的進程

26、，使之不再占用寶貴的內(nèi)存將暫時不能運行的進程，使之不再占用寶貴的內(nèi)存資源，而將它們資源，而將它們調(diào)至外存調(diào)至外存去等待，把此時的進程狀態(tài)稱去等待，把此時的進程狀態(tài)稱為為就緒駐外存狀態(tài)就緒駐外存狀態(tài)或或掛起狀態(tài)掛起狀態(tài)。當這些進程重又具備運。當這些進程重又具備運行條件且內(nèi)存又有空閑時，由中級調(diào)度來決定把外存上行條件且內(nèi)存又有空閑時，由中級調(diào)度來決定把外存上的那些又具備運行條件的就緒進程重新調(diào)入內(nèi)存，并修的那些又具備運行條件的就緒進程重新調(diào)入內(nèi)存，并修改其狀態(tài)為就緒狀態(tài)，掛在就緒隊列上等待進程調(diào)度。改其狀態(tài)為就緒狀態(tài)，掛在就緒隊列上等待進程調(diào)度。3.1 處理機調(diào)度的層次處理機調(diào)度的層次 .25.作

27、業(yè)調(diào)度、進程調(diào)度和中級調(diào)度說明：作業(yè)調(diào)度、進程調(diào)度和中級調(diào)度說明： 進程調(diào)度進程調(diào)度的運行頻率最高，在分時系統(tǒng)中通常是的運行頻率最高，在分時系統(tǒng)中通常是10100 ms便進行一次進程調(diào)度，因此把它稱為便進行一次進程調(diào)度，因此把它稱為短程短程調(diào)度調(diào)度。為避免進程調(diào)度占用太多的。為避免進程調(diào)度占用太多的CPU時間，進程調(diào)時間，進程調(diào)度算法不宜太復雜。度算法不宜太復雜。 作業(yè)調(diào)度作業(yè)調(diào)度往往是發(fā)生在一個往往是發(fā)生在一個(批批)作業(yè)運行完畢并作業(yè)運行完畢并退出系統(tǒng)，而需要重新調(diào)入一個退出系統(tǒng)，而需要重新調(diào)入一個(批批)作業(yè)進入內(nèi)存時，作業(yè)進入內(nèi)存時，故作業(yè)調(diào)度的周期較長，大約幾分鐘一次，因此把它故作業(yè)

28、調(diào)度的周期較長，大約幾分鐘一次，因此把它稱為稱為長程調(diào)度長程調(diào)度。由于其運行頻率較低，故允許作業(yè)調(diào)。由于其運行頻率較低，故允許作業(yè)調(diào)度算法花費較多的時間。度算法花費較多的時間。 中級調(diào)度中級調(diào)度的運行頻率基本上介于上述兩種調(diào)度之的運行頻率基本上介于上述兩種調(diào)度之間，因此把它稱為間，因此把它稱為中程調(diào)度中程調(diào)度。 3.1 處理機調(diào)度的層次處理機調(diào)度的層次 .26.3.2 調(diào)度隊列模型和調(diào)度準則調(diào)度隊列模型和調(diào)度準則 3.2.1調(diào)度隊列模型調(diào)度隊列模型1僅有進程調(diào)度的調(diào)度隊列模型僅有進程調(diào)度的調(diào)度隊列模型在分時系統(tǒng)中，通常僅設置進程調(diào)度，用戶鍵入在分時系統(tǒng)中，通常僅設置進程調(diào)度，用戶鍵入的命令和數(shù)

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

30、行。 .27.進程在執(zhí)行時可能出現(xiàn)的三種情況：進程在執(zhí)行時可能出現(xiàn)的三種情況：(1) 任務在給定的時間片內(nèi)已經(jīng)完成，該進程便在任務在給定的時間片內(nèi)已經(jīng)完成，該進程便在釋放處理機后進入完成狀態(tài)；釋放處理機后進入完成狀態(tài)；(2) 任務在本次分得的時間片內(nèi)尚未完成，任務在本次分得的時間片內(nèi)尚未完成，OS便將便將該任務再放入就緒隊列的末尾；該任務再放入就緒隊列的末尾；(3) 在執(zhí)行期間，進程因為某事件而被阻塞后，被在執(zhí)行期間，進程因為某事件而被阻塞后，被OS放入阻塞隊列。放入阻塞隊列。圖圖3-1示出了僅具有進程調(diào)度的調(diào)度隊列模型。示出了僅具有進程調(diào)度的調(diào)度隊列模型。 3.2 調(diào)度隊列模型和調(diào)度準則調(diào)度

31、隊列模型和調(diào)度準則 .28.圖圖 3-1 僅具有進程調(diào)度的調(diào)度隊列模型僅具有進程調(diào)度的調(diào)度隊列模型 就就 緒緒 隊隊 列列阻阻 塞塞 隊隊 列列進程調(diào)度進程調(diào)度CPU進程完成進程完成等待事件等待事件交互用戶交互用戶事事件件出出現(xiàn)現(xiàn)時間片完時間片完3.2 調(diào)度隊列模型和調(diào)度準則調(diào)度隊列模型和調(diào)度準則 .29.2具有高級和低級調(diào)度的調(diào)度隊列模型具有高級和低級調(diào)度的調(diào)度隊列模型在批處理系統(tǒng)中，不僅需要進程調(diào)度，而且還在批處理系統(tǒng)中，不僅需要進程調(diào)度，而且還需有作業(yè)調(diào)度，由后者按一定的作業(yè)調(diào)度算法，從需有作業(yè)調(diào)度，由后者按一定的作業(yè)調(diào)度算法，從外存的后備隊列中選擇一批作業(yè)調(diào)入內(nèi)存，并為它外存的后備隊列

32、中選擇一批作業(yè)調(diào)入內(nèi)存，并為它們建立進程，送入就緒隊列，然后才由進程調(diào)度按們建立進程，送入就緒隊列，然后才由進程調(diào)度按照一定的進程調(diào)度算法選擇一個進程，把處理機分照一定的進程調(diào)度算法選擇一個進程，把處理機分配給該進程。配給該進程。 圖圖3-2示出了具有高、低兩級調(diào)度的調(diào)度隊列示出了具有高、低兩級調(diào)度的調(diào)度隊列模型：模型：3.2 調(diào)度隊列模型和調(diào)度準則調(diào)度隊列模型和調(diào)度準則 .30.圖圖3-2 具有高、低兩級調(diào)度的調(diào)度隊列模型具有高、低兩級調(diào)度的調(diào)度隊列模型 就就 緒緒 隊隊 列列進程調(diào)度進程調(diào)度CPU進程完成進程完成等待事件等待事件1作業(yè)作業(yè)調(diào)度調(diào)度事件事件1出現(xiàn)出現(xiàn)時間片完時間片完等待事件等

33、待事件2事件事件2出現(xiàn)出現(xiàn)等待事件等待事件n事件事件n出現(xiàn)出現(xiàn)后后 備備 隊隊 列列3.2 調(diào)度隊列模型和調(diào)度準則調(diào)度隊列模型和調(diào)度準則 .31.上述兩種模型的主要區(qū)別：上述兩種模型的主要區(qū)別：(1) 就緒隊列的形式就緒隊列的形式 在批處理系統(tǒng)中，最常用的是最高優(yōu)先權(quán)優(yōu)先調(diào)在批處理系統(tǒng)中，最常用的是最高優(yōu)先權(quán)優(yōu)先調(diào)度算法。度算法。相應地，最常用的就緒隊列形式是相應地，最常用的就緒隊列形式是優(yōu)先權(quán)隊優(yōu)先權(quán)隊列列，進程在進入優(yōu)先級隊列時，根據(jù)其優(yōu)先權(quán)的高低，進程在進入優(yōu)先級隊列時，根據(jù)其優(yōu)先權(quán)的高低，被插入具有相應優(yōu)先權(quán)的位置上，調(diào)度程序總是把處被插入具有相應優(yōu)先權(quán)的位置上，調(diào)度程序總是把處理機分

34、配給就緒隊列中的隊首進程。理機分配給就緒隊列中的隊首進程。在最高優(yōu)先權(quán)優(yōu)在最高優(yōu)先權(quán)優(yōu)先的調(diào)度算法中，也可采用先的調(diào)度算法中，也可采用無序鏈表方式無序鏈表方式，即每次把，即每次把新到的進程掛在鏈尾，而調(diào)度程序每次調(diào)度時，依次新到的進程掛在鏈尾，而調(diào)度程序每次調(diào)度時，依次比較該鏈中各進程的優(yōu)先權(quán)，從中找出優(yōu)先權(quán)最高的比較該鏈中各進程的優(yōu)先權(quán)，從中找出優(yōu)先權(quán)最高的進程，將之從鏈中摘下，并把處理機分配給它。進程，將之從鏈中摘下，并把處理機分配給它。3.2 調(diào)度隊列模型和調(diào)度準則調(diào)度隊列模型和調(diào)度準則 .32. (2) 設置多個阻塞隊列設置多個阻塞隊列 對于小型系統(tǒng)，可以只設置一個阻塞隊列；但對于小型

35、系統(tǒng)，可以只設置一個阻塞隊列；但當系統(tǒng)較大時，若只有一個阻塞隊列，其長度必然當系統(tǒng)較大時，若只有一個阻塞隊列，其長度必然會很長，隊列中的進程數(shù)可以達到數(shù)百個，這將嚴會很長，隊列中的進程數(shù)可以達到數(shù)百個，這將嚴重影響對阻塞隊列操作的效率。重影響對阻塞隊列操作的效率。 故在大、中型系統(tǒng)中通常都設置了若干個阻塞故在大、中型系統(tǒng)中通常都設置了若干個阻塞隊列，每個隊列對應于某一種進程阻塞事件。隊列，每個隊列對應于某一種進程阻塞事件。 3.2 調(diào)度隊列模型和調(diào)度準則調(diào)度隊列模型和調(diào)度準則 .33.3同時具有三級調(diào)度的調(diào)度隊列模型同時具有三級調(diào)度的調(diào)度隊列模型當在當在OS中引入中級調(diào)度后，人們可把進程的就中

36、引入中級調(diào)度后，人們可把進程的就緒狀態(tài)分為緒狀態(tài)分為內(nèi)存就緒內(nèi)存就緒(表示進程在內(nèi)存中就緒表示進程在內(nèi)存中就緒)和和外存外存就緒就緒(進程在外存中就緒進程在外存中就緒)。類似地，也可把阻塞狀態(tài)。類似地，也可把阻塞狀態(tài)進一步分成內(nèi)存阻塞和外存阻塞兩種狀態(tài)。在調(diào)出操進一步分成內(nèi)存阻塞和外存阻塞兩種狀態(tài)。在調(diào)出操作的作用下，可使進程狀態(tài)由內(nèi)存就緒轉(zhuǎn)為外存就緒，作的作用下，可使進程狀態(tài)由內(nèi)存就緒轉(zhuǎn)為外存就緒，由內(nèi)存阻塞轉(zhuǎn)為外存阻塞；在中級調(diào)度的作用下，又由內(nèi)存阻塞轉(zhuǎn)為外存阻塞；在中級調(diào)度的作用下，又可使外存就緒轉(zhuǎn)為內(nèi)存就緒?？墒雇獯婢途w轉(zhuǎn)為內(nèi)存就緒。圖圖3-3示出了具有三級調(diào)度的調(diào)度隊列模型。示出了具

37、有三級調(diào)度的調(diào)度隊列模型。 3.2 調(diào)度隊列模型和調(diào)度準則調(diào)度隊列模型和調(diào)度準則 .34.圖圖3-3 具有三級調(diào)度時的調(diào)度隊列模型具有三級調(diào)度時的調(diào)度隊列模型 3.2 調(diào)度隊列模型和調(diào)度準則調(diào)度隊列模型和調(diào)度準則 就緒隊列就緒隊列進程調(diào)度進程調(diào)度CPU就緒，掛起隊列就緒，掛起隊列中級調(diào)度中級調(diào)度阻塞，掛起隊列阻塞，掛起隊列阻塞隊列阻塞隊列等待事件等待事件進程完成進程完成時間片完時間片完作業(yè)調(diào)度作業(yè)調(diào)度交互型作業(yè)交互型作業(yè)后備隊列后備隊列批量作業(yè)批量作業(yè)掛起掛起事件出現(xiàn)事件出現(xiàn)事事件件出出現(xiàn)現(xiàn)掛起掛起.35.3.2.2 選擇調(diào)度方式和調(diào)度算法的若干準則選擇調(diào)度方式和調(diào)度算法的若干準則1面向用戶的

38、準則面向用戶的準則(1) 周轉(zhuǎn)時間短周轉(zhuǎn)時間短 通常把周轉(zhuǎn)時間的長短作為通常把周轉(zhuǎn)時間的長短作為評價批處理系統(tǒng)評價批處理系統(tǒng)的性的性能、選擇作業(yè)調(diào)度方式與算法的重要準則之一。能、選擇作業(yè)調(diào)度方式與算法的重要準則之一。 作業(yè)周轉(zhuǎn)時間：作業(yè)周轉(zhuǎn)時間：是指從作業(yè)被提交給系統(tǒng)開始，是指從作業(yè)被提交給系統(tǒng)開始，到作業(yè)完成為止的這段時間間隔。到作業(yè)完成為止的這段時間間隔。它包括四部分時間：它包括四部分時間：作業(yè)在外存后備隊列上等待作業(yè)調(diào)度的時間、進程在作業(yè)在外存后備隊列上等待作業(yè)調(diào)度的時間、進程在就緒隊列上等待進程調(diào)度的時間、進程在就緒隊列上等待進程調(diào)度的時間、進程在CPU上執(zhí)行上執(zhí)行的時間及進程等待的時

39、間及進程等待I/O操作完成的時間。操作完成的時間。3.2 調(diào)度隊列模型和調(diào)度準則調(diào)度隊列模型和調(diào)度準則 .36.對每個用戶而言，都希望自己作業(yè)的周轉(zhuǎn)時間對每個用戶而言，都希望自己作業(yè)的周轉(zhuǎn)時間最短。但作為計算機系統(tǒng)的管理者，則總是希望能最短。但作為計算機系統(tǒng)的管理者，則總是希望能使使平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間最短，這不僅會有效地提高系統(tǒng)資最短，這不僅會有效地提高系統(tǒng)資源的利用率，而且還可使大多數(shù)用戶都感到滿意。源的利用率，而且還可使大多數(shù)用戶都感到滿意。 平均周轉(zhuǎn)時間：平均周轉(zhuǎn)時間： niiTnT113.2 調(diào)度隊列模型和調(diào)度準則調(diào)度隊列模型和調(diào)度準則 .37.作業(yè)的周轉(zhuǎn)時間作業(yè)的周轉(zhuǎn)時間T與系

40、統(tǒng)為它提供服務的時間與系統(tǒng)為它提供服務的時間Ts之比，即之比，即W = T / Ts，稱為，稱為帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間。 平均帶權(quán)周轉(zhuǎn)時間平均帶權(quán)周轉(zhuǎn)時間則可表示為：則可表示為： niiTTnW1s13.2 調(diào)度隊列模型和調(diào)度準則調(diào)度隊列模型和調(diào)度準則 .38.(2) 響應時間快響應時間快 響應時間的長短常用來響應時間的長短常用來評價分時系統(tǒng)的性能評價分時系統(tǒng)的性能，這，這是選擇分時系統(tǒng)中進程調(diào)度算法的重要準則之一。是選擇分時系統(tǒng)中進程調(diào)度算法的重要準則之一。 響應時間：響應時間：是從用戶通過鍵盤提交一個請求開始，是從用戶通過鍵盤提交一個請求開始，直至系統(tǒng)首次產(chǎn)生響應為止的時間，或者說，直到

41、屏直至系統(tǒng)首次產(chǎn)生響應為止的時間，或者說，直到屏幕上顯示出結(jié)果為止的一段時間間隔。幕上顯示出結(jié)果為止的一段時間間隔。它包括三部分它包括三部分時間：時間：從鍵盤輸入的請求信息傳送到處理機的時間，從鍵盤輸入的請求信息傳送到處理機的時間，處理機對請求信息進行處理的時間，以及將所形成的處理機對請求信息進行處理的時間，以及將所形成的響應信息回送到終端顯示器的時間。響應信息回送到終端顯示器的時間。 3.2 調(diào)度隊列模型和調(diào)度準則調(diào)度隊列模型和調(diào)度準則 .39.3.2 調(diào)度隊列模型和調(diào)度準則調(diào)度隊列模型和調(diào)度準則 (3) 截止時間的保證截止時間的保證 截止時間的保證是截止時間的保證是評價實時系統(tǒng)性能評價實時

42、系統(tǒng)性能的重要指的重要指標，因而是選擇實時調(diào)度算法的重要準則。標，因而是選擇實時調(diào)度算法的重要準則。 截止時間：截止時間：是指某任務必須開始執(zhí)行的最遲時是指某任務必須開始執(zhí)行的最遲時間，或必須完成的最遲時間。間，或必須完成的最遲時間。 對于嚴格的實時系統(tǒng)，其調(diào)度方式和調(diào)度算法對于嚴格的實時系統(tǒng)，其調(diào)度方式和調(diào)度算法必須能保證這一點，否則將可能造成難以預料的后必須能保證這一點，否則將可能造成難以預料的后果。果。.40.(4) 優(yōu)先權(quán)準則優(yōu)先權(quán)準則 在批處理、分時和實時系統(tǒng)中選擇調(diào)度算法在批處理、分時和實時系統(tǒng)中選擇調(diào)度算法時，都可遵循優(yōu)先權(quán)準則，以便讓某些緊急的作時，都可遵循優(yōu)先權(quán)準則，以便讓某

43、些緊急的作業(yè)能得到及時處理。業(yè)能得到及時處理。 在要求較嚴格的場合，往往還須選擇搶占式在要求較嚴格的場合，往往還須選擇搶占式調(diào)度方式，才能保證緊急作業(yè)得到及時處理。調(diào)度方式，才能保證緊急作業(yè)得到及時處理。 3.2 調(diào)度隊列模型和調(diào)度準則調(diào)度隊列模型和調(diào)度準則 .41.2. 面向系統(tǒng)的準則面向系統(tǒng)的準則(1) 系統(tǒng)吞吐量高系統(tǒng)吞吐量高 系統(tǒng)吞吐量系統(tǒng)吞吐量是用于是用于評價批處理系統(tǒng)性能評價批處理系統(tǒng)性能的另一個重的另一個重要指標，因而是選擇批處理作業(yè)調(diào)度的重要準則。要指標，因而是選擇批處理作業(yè)調(diào)度的重要準則。 吞吐量吞吐量是指在單位時間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)，因是指在單位時間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)，

44、因而它與批處理作業(yè)的平均長度具有密切關(guān)系。而它與批處理作業(yè)的平均長度具有密切關(guān)系。 作業(yè)調(diào)度的方式和算法對吞吐量的大小將產(chǎn)生較大作業(yè)調(diào)度的方式和算法對吞吐量的大小將產(chǎn)生較大影響。事實上，對于同一批作業(yè)，若采用了較好的調(diào)度影響。事實上，對于同一批作業(yè)，若采用了較好的調(diào)度方式和算法，則可顯著地提高系統(tǒng)的吞吐量。方式和算法，則可顯著地提高系統(tǒng)的吞吐量。 3.2 調(diào)度隊列模型和調(diào)度準則調(diào)度隊列模型和調(diào)度準則 .42.(2) 處理機利用率高處理機利用率高 對于大、中型多用戶系統(tǒng)，由于對于大、中型多用戶系統(tǒng)，由于CPU價格十分昂價格十分昂貴，處理機的利用率成為衡量系統(tǒng)性能的十分重要的貴，處理機的利用率成為

45、衡量系統(tǒng)性能的十分重要的指標；而調(diào)度方式和算法對處理機的利用率起著十分指標；而調(diào)度方式和算法對處理機的利用率起著十分重要的作用。重要的作用。 在實際系統(tǒng)中，在實際系統(tǒng)中，CPU的利用率一般在的利用率一般在40%(系統(tǒng)負系統(tǒng)負荷較輕荷較輕)到到90%之間。在大、中型系統(tǒng)中，在選擇調(diào)度之間。在大、中型系統(tǒng)中，在選擇調(diào)度方式和算法時，應考慮到這一準則。方式和算法時，應考慮到這一準則。 對于單用戶微機或某些實時系統(tǒng)，該準則并不重對于單用戶微機或某些實時系統(tǒng)，該準則并不重要。要。 3.2 調(diào)度隊列模型和調(diào)度準則調(diào)度隊列模型和調(diào)度準則 .43.(3) 各類資源的平衡利用各類資源的平衡利用 在大、中型系統(tǒng)中

46、，不僅要使處理機的利用率在大、中型系統(tǒng)中，不僅要使處理機的利用率高，而且還應能有效地利用其它各類資源，如內(nèi)存、高，而且還應能有效地利用其它各類資源，如內(nèi)存、外存和外存和I/O設備等。設備等。 選擇適當?shù)恼{(diào)度方式和算法可以保持系統(tǒng)中各選擇適當?shù)恼{(diào)度方式和算法可以保持系統(tǒng)中各類資源都處于忙碌狀態(tài)。類資源都處于忙碌狀態(tài)。 對于微型機和某些實時系統(tǒng)而言，該準則并不對于微型機和某些實時系統(tǒng)而言，該準則并不重要。重要。 3.2 調(diào)度隊列模型和調(diào)度準則調(diào)度隊列模型和調(diào)度準則 .44.3.3 調(diào)度算法調(diào)度算法 3.2.1先來先服務和短作業(yè)先來先服務和短作業(yè)(進程進程)優(yōu)先調(diào)度算法優(yōu)先調(diào)度算法1先來先服務調(diào)度算

47、法先來先服務調(diào)度算法 先來先服務先來先服務(FCFS)調(diào)度算法調(diào)度算法是一種最簡單的調(diào)度是一種最簡單的調(diào)度算法，該算法可用于作業(yè)調(diào)度和進程調(diào)度。算法，該算法可用于作業(yè)調(diào)度和進程調(diào)度。 作業(yè)調(diào)度采用該算法時，每次調(diào)度都是從后備作作業(yè)調(diào)度采用該算法時，每次調(diào)度都是從后備作業(yè)隊列中選擇一個或多個最先進入該隊列的作業(yè)，將業(yè)隊列中選擇一個或多個最先進入該隊列的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進程，然后放它們調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進程，然后放入就緒隊列。入就緒隊列。 進程調(diào)度中采用進程調(diào)度中采用該該算法時，每次調(diào)度是從就緒隊算法時，每次調(diào)度是從就緒隊列中選擇一個最先進入該隊列的進程，為之

48、分配處理列中選擇一個最先進入該隊列的進程，為之分配處理機，使之投入運行。該進程一直運行到完成或發(fā)生某機，使之投入運行。該進程一直運行到完成或發(fā)生某事件而阻塞后才放棄處理機。事件而阻塞后才放棄處理機。 .45. FCFS 算法有利于長作業(yè)算法有利于長作業(yè)(進程進程)，而不利于短，而不利于短作業(yè)作業(yè)(進程進程)。下表列出了采用。下表列出了采用FCFS算算法時法時 A、B、C、D 四個作業(yè)分別到達系統(tǒng)的時間、要求服務的四個作業(yè)分別到達系統(tǒng)的時間、要求服務的時間、開始執(zhí)行的時間、完成的時間、各自的周轉(zhuǎn)時間、開始執(zhí)行的時間、完成的時間、各自的周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間。時間和帶權(quán)周轉(zhuǎn)時間。 3.3 調(diào)度算法

49、調(diào)度算法 進程名 到達時間 服務時間 開始執(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 不能忍受！.46. 從上表觀察：從上表觀察：其中短作業(yè)其中短作業(yè)C的帶權(quán)周轉(zhuǎn)時間競高的帶權(quán)周轉(zhuǎn)時間競高達達100，這是不能容忍的；而長作業(yè)，這是不能容忍的；而長作業(yè)D的帶權(quán)周轉(zhuǎn)時的帶權(quán)周轉(zhuǎn)時間僅為間僅為1.99。據(jù)此可知，。據(jù)此可知，F(xiàn)CFS調(diào)度算法有利于調(diào)度算法有利于CPU繁忙型的作業(yè)，而不利于繁忙型的作業(yè)，而不利于I/O繁忙型的作業(yè)繁忙型的作業(yè)

50、(進程進程)。 CPU繁忙型作業(yè)是指該類作業(yè)需要大量的繁忙型作業(yè)是指該類作業(yè)需要大量的CPU時時間進行計算，而很少請求間進行計算，而很少請求I/O。通常的。通常的科學計算科學計算便屬便屬于于CPU繁忙型作業(yè)。繁忙型作業(yè)。I/O繁忙型作業(yè)是指繁忙型作業(yè)是指CPU進行處進行處理時需頻繁地請求理時需頻繁地請求I/O。目前的。目前的大多數(shù)事務處理大多數(shù)事務處理都屬都屬于于I/O繁忙型作業(yè)。繁忙型作業(yè)。3.3 調(diào)度算法調(diào)度算法 .47.通過示例說明采用通過示例說明采用FCFS調(diào)度算法時的調(diào)度性能：調(diào)度算法時的調(diào)度性能： 圖圖3-4(a)示出有五個進程示出有五個進程A、B、C、D、E，它們到達的，它們到達

51、的時間分別是時間分別是0、1、2、3和和4，所要求的服務時間分別是，所要求的服務時間分別是4、3、5、2和和4，其完成時間分別是，其完成時間分別是4、7、12、14和和18。3.3 調(diào)度算法調(diào)度算法 進程名 A B C D E 平 均 到達時間 0 1 2 3 4 作業(yè) 情況 調(diào)度 算法 服務時間 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.1 1.5

52、 2.25 2.1 圖圖3-4 FCFS調(diào)度算法的性能調(diào)度算法的性能 .48.2短作業(yè)短作業(yè)(進程進程)優(yōu)先調(diào)度算法優(yōu)先調(diào)度算法短作業(yè)短作業(yè)(進程進程)優(yōu)先調(diào)度算法優(yōu)先調(diào)度算法SJ(P)F，是指對短作，是指對短作業(yè)或短進程優(yōu)先調(diào)度的算法。它們可以分別用于作業(yè)業(yè)或短進程優(yōu)先調(diào)度的算法。它們可以分別用于作業(yè)調(diào)度和進程調(diào)度。調(diào)度和進程調(diào)度。 短作業(yè)優(yōu)先短作業(yè)優(yōu)先(SJF)的調(diào)度算法的調(diào)度算法是從后備隊列中選是從后備隊列中選擇一個或若干個估計運行時間最短的作業(yè)，將它們調(diào)擇一個或若干個估計運行時間最短的作業(yè)，將它們調(diào)入內(nèi)存運行。而入內(nèi)存運行。而短進程優(yōu)先短進程優(yōu)先(SPF)調(diào)度算法調(diào)度算法則是從就則是從

53、就緒隊列中選出一個估計運行時間最短的進程，將處理緒隊列中選出一個估計運行時間最短的進程，將處理機分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)機分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件被阻塞而放棄處理機時再重新調(diào)度。生某事件被阻塞而放棄處理機時再重新調(diào)度。 3.3 調(diào)度算法調(diào)度算法 .49.采用前述示例，將采用前述示例，將FCFS調(diào)度算法，改用調(diào)度算法，改用SJ(P)F算法重算法重新調(diào)度，并進行性能分析：新調(diào)度，并進行性能分析： 由由圖圖3-4中中(a)和和(b)可知，采用可知，采用SJ(P)F算法后，不論是平均周算法后，不論是平均周轉(zhuǎn)時間還是平均帶權(quán)周轉(zhuǎn)時間，都有較明顯的改善。說明

54、轉(zhuǎn)時間還是平均帶權(quán)周轉(zhuǎn)時間，都有較明顯的改善。說明SJF調(diào)調(diào)度算法能有效地降低作業(yè)的平均等待時間，提高系統(tǒng)吞吐量。度算法能有效地降低作業(yè)的平均等待時間，提高系統(tǒng)吞吐量。 3.3 調(diào)度算法調(diào)度算法 進程名 A B C D E 平 均 到達時間 0 1 2 3 4 作業(yè) 情況 調(diào)度 算法 服務時間 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.1 1.5 2

55、.25 2.1 .50.SJ(P)F調(diào)度算法也存在不容忽視的缺點：調(diào)度算法也存在不容忽視的缺點：(1)該算法對長作業(yè)不利。該算法對長作業(yè)不利。更嚴重的是，如果有一長更嚴重的是，如果有一長作業(yè)作業(yè)( (進程進程) )進入系統(tǒng)的后備隊列進入系統(tǒng)的后備隊列( (就緒隊列就緒隊列) )，由于調(diào)，由于調(diào)度程序總是優(yōu)先調(diào)度那些度程序總是優(yōu)先調(diào)度那些( (即使是后進來的即使是后進來的) )短作業(yè)短作業(yè)( (進進程程) )，將導致長作業(yè)，將導致長作業(yè)( (進程進程) )長期不被調(diào)度。長期不被調(diào)度。(2)該算法完全未考慮作業(yè)的緊迫程度。該算法完全未考慮作業(yè)的緊迫程度。因而不能保因而不能保證緊迫性作業(yè)證緊迫性作業(yè)

56、( (進程進程) )會被及時處理。會被及時處理。(3)該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。由于由于作業(yè)作業(yè)( (進程進程) )的長短只是根據(jù)用戶所提供的估計執(zhí)行時的長短只是根據(jù)用戶所提供的估計執(zhí)行時間而定的，而用戶又可能會有意或無意地縮短其作業(yè)間而定的，而用戶又可能會有意或無意地縮短其作業(yè)的估計運行時間。的估計運行時間。3.3 調(diào)度算法調(diào)度算法 .51.3.3.2高優(yōu)先權(quán)優(yōu)先調(diào)度算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法1優(yōu)先權(quán)調(diào)度算法的類型優(yōu)先權(quán)調(diào)度算法的類型為了照顧緊迫型作業(yè)，使之在進入系統(tǒng)后便獲得為了照顧緊迫型作業(yè)，使之在進入系統(tǒng)后便獲得優(yōu)先處理，引入最高優(yōu)先權(quán)優(yōu)先

57、優(yōu)先處理，引入最高優(yōu)先權(quán)優(yōu)先(FPF)調(diào)度算法。此調(diào)度算法。此算法可作為作業(yè)調(diào)度算法，也可作為進程調(diào)度算法，算法可作為作業(yè)調(diào)度算法，也可作為進程調(diào)度算法，還可用于實時系統(tǒng)中。還可用于實時系統(tǒng)中。 該算法用于作業(yè)調(diào)度時，系統(tǒng)將從后備隊列中選該算法用于作業(yè)調(diào)度時，系統(tǒng)將從后備隊列中選擇若干個優(yōu)先權(quán)最高的作業(yè)裝入內(nèi)存。擇若干個優(yōu)先權(quán)最高的作業(yè)裝入內(nèi)存。 該算法用于進程調(diào)度時，把處理機分配給就緒隊該算法用于進程調(diào)度時，把處理機分配給就緒隊列中優(yōu)先權(quán)最高的進程，此時，可進一步把該算法分列中優(yōu)先權(quán)最高的進程，此時，可進一步把該算法分成如下兩種：成如下兩種： 3.3 調(diào)度算法調(diào)度算法 .52.1) 非搶占式

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

59、式優(yōu)先權(quán)調(diào)度算法系統(tǒng)同樣是把處理機分配給優(yōu)先權(quán)最高的進程，系統(tǒng)同樣是把處理機分配給優(yōu)先權(quán)最高的進程，使之執(zhí)行。但在其執(zhí)行期間，只要又出現(xiàn)了另一個其使之執(zhí)行。但在其執(zhí)行期間，只要又出現(xiàn)了另一個其優(yōu)先權(quán)更高的進程，進程調(diào)度程序就立即停止當前進優(yōu)先權(quán)更高的進程，進程調(diào)度程序就立即停止當前進程的執(zhí)行，重新將處理機分配給新到的優(yōu)先權(quán)最高的程的執(zhí)行，重新將處理機分配給新到的優(yōu)先權(quán)最高的進程。進程。 搶占式的優(yōu)先權(quán)調(diào)度算法能更好地滿足緊迫作業(yè)搶占式的優(yōu)先權(quán)調(diào)度算法能更好地滿足緊迫作業(yè)的要求，常用于要求比較嚴格的實時系統(tǒng)中，以及對的要求，常用于要求比較嚴格的實時系統(tǒng)中，以及對性能要求較高的批處理和分時系統(tǒng)中。

60、性能要求較高的批處理和分時系統(tǒng)中。 3.3 調(diào)度算法調(diào)度算法 .54.2優(yōu)先權(quán)的類型優(yōu)先權(quán)的類型對于最高優(yōu)先權(quán)優(yōu)先調(diào)度算法，關(guān)鍵在于是使用對于最高優(yōu)先權(quán)優(yōu)先調(diào)度算法，關(guān)鍵在于是使用靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán)，還是，還是動態(tài)優(yōu)先權(quán)動態(tài)優(yōu)先權(quán)，及如何確定進程的優(yōu)，及如何確定進程的優(yōu)先權(quán)。先權(quán)。1) 靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán)在創(chuàng)建進程時確定，且在進程的整個靜態(tài)優(yōu)先權(quán)在創(chuàng)建進程時確定，且在進程的整個運行期間保持不變。一般地，優(yōu)先權(quán)是利用某一范圍運行期間保持不變。一般地，優(yōu)先權(quán)是利用某一范圍內(nèi)的一個整數(shù)來表示的，例如，內(nèi)的一個整數(shù)來表示的，例如，07或或0255中的某中的某一整數(shù)，該整數(shù)稱為優(yōu)先數(shù)，但一