3.1處理機調(diào)度的層次高級調(diào)度高級調(diào)度又稱為作業(yè)調(diào)度或長程調(diào)度

1、第三章 處理機調(diào)度與死鎖,3.1　 處理機調(diào)度的層次,高級調(diào)度,高級調(diào)度又稱為作業(yè)調(diào)度或長程調(diào)度，其主要功能是根據(jù)某種算法，把外存上處于后備隊列中的那些作業(yè)調(diào)入內(nèi)存，也就是說的調(diào)度對象是作業(yè)。,,作業(yè) 作業(yè)由三部分組成，即程序、數(shù)據(jù)和作業(yè)說明書。一個作業(yè)可以包含多個程序和多個數(shù)據(jù)集，但必須至少包含一個程序。否則將不成為作業(yè)。作業(yè)中包含的程序和數(shù)據(jù)完成用戶所要求的業(yè)務(wù)處理工作。作業(yè)說明書則體現(xiàn)用戶的控制意圖。由作業(yè)說

2、明書在系統(tǒng)中生成一個稱為作業(yè)控制塊(job control block，JCB)的表格。,,作業(yè)說明書主要包含三方面內(nèi)容，即作業(yè)的基本描述、作業(yè)控制描述和資源要求描述。作業(yè)基本描述包括用戶名、作業(yè)名、使用的編程語言名、允許的最大處理時間等。而作業(yè)控制描述則大致包括作業(yè)在執(zhí)行過程中的控制方式。資源要求描述包括要求內(nèi)存大小、外設(shè)種類和臺數(shù)、處理機優(yōu)先級、所需處理時間、所需庫函數(shù)或?qū)嵱贸绦虻取?一般來說，作業(yè)說明書方式主要用在批處

3、理系統(tǒng)中，且各計算機廠家都對自己的系統(tǒng)定義有各自的作業(yè)說明書的格式和內(nèi)容。 在微機系統(tǒng)和工作站系統(tǒng)中，人們常用批處理文件或shell程序方式編寫作業(yè)說明書。,,作業(yè)步：通常，在作業(yè)運行期間，每個作業(yè)都必須經(jīng)過若干個相對獨立，又相互關(guān)聯(lián)的順序加工步驟才能得到結(jié)果，我們把其中的每一個加工步驟稱為一個作業(yè)步，各作業(yè)步之間存在著相互聯(lián)系，往往是把上一個作業(yè)步的輸出作為下一個作業(yè)步的輸入?！　?作業(yè)流：若干個作業(yè)進入系統(tǒng)后，被依次

4、存放在外存上，這便形成了輸入的作業(yè)流；在操作系統(tǒng)的控制下，逐個作業(yè)進行處理，于是便形成了處理作業(yè)流。,,作業(yè)控制塊JCB(Job Control Block)　　 為了管理和調(diào)度作業(yè)，在多道批處理系統(tǒng)中為每個作業(yè)設(shè)置了一個作業(yè)控制塊，如同進程控制塊是進程在系統(tǒng)中存在的標志一樣，它是作業(yè)在系統(tǒng)中存在的標志，其中保存了系統(tǒng)對作業(yè)進行管理和調(diào)度所需的全部信息。作業(yè)控制塊是由作業(yè)說明書在系統(tǒng)中生成的一個表格。該表格登記該作業(yè)所要求的資源情況

5、、預(yù)計執(zhí)行時間和執(zhí)行優(yōu)先級等。從而，操作系統(tǒng)通過該表了解到作業(yè)要求，并分配資源和控制作業(yè)中程序和數(shù)據(jù)的編譯、鏈接、裝入和執(zhí)行等。,,每當(dāng)作業(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è)進行控制。當(dāng)一個作業(yè)執(zhí)行結(jié)束進入完成狀態(tài)時，系統(tǒng)負責(zé)回收分配給它的資源，撤消它的作業(yè)控制塊。,,作業(yè)調(diào)

6、度 作業(yè)調(diào)度的主要功能是根據(jù)作業(yè)控制塊中的信息，審查系統(tǒng)能否滿足用戶作業(yè)的資源需求，以及按照一定的算法，從外存的后備隊列中選取某些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進程、分配必要的資源。然后再將新創(chuàng)建的進程插入就緒隊列，準備執(zhí)行。因此，有時也把作業(yè)調(diào)度稱為接納調(diào)度(Admission Scheduling)。,,每個系統(tǒng)在選擇作業(yè)調(diào)度算法時，既應(yīng)考慮用戶的要求，又能確保系統(tǒng)具有較高的效率。在每次執(zhí)行作業(yè)調(diào)度時，都須做出以下兩個決定。

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

8、哪些作業(yè)　　 應(yīng)將哪些作業(yè)從外存調(diào)入內(nèi)存，這將取決于所采用的調(diào)度算法。最簡單的是先來先服務(wù)調(diào)度算法，這是指將最早進入外存的作業(yè)最先調(diào)入內(nèi)存；較常用的一種算法是短作業(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)度算法。,,在批處理系統(tǒng)中，作業(yè)進入系統(tǒng)后，總是先駐留在外存的后備隊列上，因此需要有作業(yè)調(diào)度的過

9、程，以便將它們分批地裝入內(nèi)存。然而在分時系統(tǒng)中，為了做到及時響應(yīng)，用戶通過鍵盤輸入的命令或數(shù)據(jù)等都是被直接送入內(nèi)存的，因而無需再配置上述的作業(yè)調(diào)度機制，但也需要有某些限制性措施來限制進入系統(tǒng)的用戶數(shù)。即，如果系統(tǒng)尚未飽和，將接納所有授權(quán)用戶，否則，將拒絕接納。類似地，在實時系統(tǒng)中通常也不需要作業(yè)調(diào)度。,低級調(diào)度,低級調(diào)度稱為進程調(diào)度或短程調(diào)度，它所調(diào)度的對象是進程(或內(nèi)核級線程)。進程調(diào)度是最基本的一種調(diào)度，在多道批處理、分時和實時三種

10、類型的OS中，都必須配置這級調(diào)度。,,低級調(diào)度的功能　　 低級調(diào)度用于決定就緒隊列中的哪個進程(或內(nèi)核級線程，為敘述方便，以后只寫進程)應(yīng)獲得處理機，然后再由分派程序執(zhí)行把處理機分配給該進程的具體操作。 主要功能如下： 　　 (1)保存處理機的現(xiàn)場信息。在進程調(diào)度進行調(diào)度時，首先需要保存當(dāng)前進程的處理機的現(xiàn)場信息，如程序計數(shù)器、多個通用寄存器中的內(nèi)容等，將它們送入該進程的進程控制塊(PCB)中的相應(yīng)單元。,,(2)按某種算法

11、選取進程。低級調(diào)度程序按某種算法如優(yōu)先數(shù)算法、輪轉(zhuǎn)法等，從就緒隊列中選取一個進程，把它的狀態(tài)改為運行狀態(tài)，并準備把處理機分配給它。 　　 (3)把處理器分配給進程。由分派程序(Dispatcher)把處理器分配給進程。此時需為選中的進程恢復(fù)處理機現(xiàn)場，即把選中進程的進程控制塊內(nèi)有關(guān)處理機現(xiàn)場的信息裝入處理器相應(yīng)的各個寄存器中，把處理器的控制權(quán)交給該進程，讓它從取出的斷點處開始繼續(xù)運行。,,進程調(diào)度中的三個基本機制　　 (1)排隊

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

13、對上下文切換時，將移出分派程序，而把新選進程的CPU現(xiàn)場信息裝入到處理機的各個相應(yīng)寄存器中。,,進程調(diào)度方式　　進程調(diào)度可采用下述兩種調(diào)度方式。　　 1)非搶占方式(Nonpreemptive Mode)　　 在采用這種調(diào)度方式時，一旦把處理機分配給某進程后，不管它要運行多長時間，都一直讓它運行下去，決不會因為時鐘中斷等原因而搶占正在運行進程的處理機，也不允許其它進程搶占已經(jīng)分配給它的處理機。直至該進程完成，自愿釋放處理機，或發(fā)

14、生某事件而被阻塞時，才再把處理機分配給其他進程。,,在采用非搶占調(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)開銷小，適用于大多數(shù)的批處理系統(tǒng)

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

16、占方式比非搶占方式調(diào)度所需付出的開銷較大。搶占調(diào)度方式是基于一定原則的，主要有如下幾條：,,(1)優(yōu)先權(quán)原則。通常是對一些重要的和緊急的作業(yè)賦予較高的優(yōu)先權(quán)。當(dāng)這種作業(yè)到達時，如果其優(yōu)先權(quán)比正在執(zhí)行進程的優(yōu)先權(quán)高，便停止正在執(zhí)行(當(dāng)前)的進程，將處理機分配給優(yōu)先權(quán)高的新到的進程，使之執(zhí)行；或者說，允許優(yōu)先權(quán)高的新到進程搶占當(dāng)前進程的處理機?！　?(2)短作業(yè)(進程)優(yōu)先原則。當(dāng)新到達的作業(yè)(進程)比正在執(zhí)行的作業(yè)(進程)明顯的短時，

17、將暫停當(dāng)前長作業(yè)(進程)的執(zhí)行，將處理機分配給新到的短作業(yè)(進程)，使之優(yōu)先執(zhí)行； 或者說，短作業(yè)(進程)可以搶占當(dāng)前較長作業(yè)(進程)的處理機?！　?(3)時間片原則。各進程按時間片輪流運行，當(dāng)一個時間片用完后，便停止該進程的執(zhí)行而重新進行調(diào)度。這種原則適用于分時系統(tǒng)、大多數(shù)的實時系統(tǒng)，以及要求較高的批處理系統(tǒng)。,,中級調(diào)度 中級調(diào)度又稱中程調(diào)度。引入中級調(diào)度的主要目的是為了提高內(nèi)存利用率和系統(tǒng)吞吐量。為此，應(yīng)使那些暫時

18、不能運行的進程不再占用寶貴的內(nèi)存資源，而將它們調(diào)至外存上去等待，把此時的進程狀態(tài)稱為就緒駐外存狀態(tài)或掛起狀態(tài)。當(dāng)這些進程重又具備運行條件且內(nèi)存又稍有空閑時，由中級調(diào)度來決定把外存上的那些又具備運行條件的就緒進程重新調(diào)入內(nèi)存，并修改其狀態(tài)為就緒狀態(tài)，掛在就緒隊列上等待進程調(diào)度。中級調(diào)度實際上就是存儲器管理中的對換功能。,,在上述三種調(diào)度中，進程調(diào)度的運行頻率最高，在分時系統(tǒng)中通常是10～100 ms便進行一次進程調(diào)度，因此把它稱為短程調(diào)度