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

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

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

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

4、存放在外存上，這便形成了輸入的作業(yè)流；在操作系統(tǒng)的控制下，逐個(gè)作業(yè)進(jìn)行處理，于是便形成了處理作業(yè)流。,,作業(yè)控制塊JCB(Job Control Block)　　 為了管理和調(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)對作業(yè)進(jìn)行管理和調(diào)度所需的全部信息。作業(yè)控制塊是由作業(yè)說明書在系統(tǒng)中生成的一個(gè)表格。該表格登記該作業(yè)所要求的資源情況

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

6、度 作業(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)度(Admission Scheduling)。,,每個(gè)系統(tǒng)在選擇作業(yè)調(diào)度算法時(shí)，既應(yīng)考慮用戶的要求，又能確保系統(tǒng)具有較高的效率。在每次執(zhí)行作業(yè)調(diào)度時(shí)，都須做出以下兩個(gè)決定。

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

8、哪些作業(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)先級的調(diào)度算法，該算法是將外存上優(yōu)先級最高的作業(yè)優(yōu)先調(diào)入內(nèi)存；比較好的一種算法是“響應(yīng)比高者優(yōu)先”的調(diào)度算法。,,在批處理系統(tǒng)中，作業(yè)進(jìn)入系統(tǒng)后，總是先駐留在外存的后備隊(duì)列上，因此需要有作業(yè)調(diào)度的過

9、程，以便將它們分批地裝入內(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)度。,低級調(diào)度,低級調(diào)度稱為進(jìn)程調(diào)度或短程調(diào)度，它所調(diào)度的對象是進(jìn)程(或內(nèi)核級線程)。進(jìn)程調(diào)度是最基本的一種調(diào)度，在多道批處理、分時(shí)和實(shí)時(shí)三種

10、類型的OS中，都必須配置這級調(diào)度。,,低級調(diào)度的功能　　 低級調(diào)度用于決定就緒隊(duì)列中的哪個(gè)進(jìn)程(或內(nèi)核級線程，為敘述方便，以后只寫進(jìn)程)應(yīng)獲得處理機(jī)，然后再由分派程序執(zhí)行把處理機(jī)分配給該進(jìn)程的具體操作。 主要功能如下： 　　 (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)按某種算法

11、選取進(jìn)程。低級調(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)行。,,進(jìn)程調(diào)度中的三個(gè)基本機(jī)制　　 (1)排隊(duì)

12、器。為了提高進(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)對處理機(jī)進(jìn)行切換時(shí)，會發(fā)生兩對上下文切換操作。在第一對上下文切換時(shí)，操作系統(tǒng)將保存當(dāng)前進(jìn)程的上下文，而裝入分派程序的上下文，以便分派程序運(yùn)行；在第二

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

14、生某事件而被阻塞時(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請求而暫停執(zhí)行；　　 (3)在進(jìn)程通信或同步過程中執(zhí)行了某種原語操作，如P操作(wait操作)、Block原語、Wakeup原語等。　　 這種調(diào)度方式的優(yōu)點(diǎn)是實(shí)現(xiàn)簡單，系統(tǒng)開銷小，適用于大多數(shù)的批處理系統(tǒng)

15、環(huán)境。但它難以滿足緊急任務(wù)的要求——立即執(zhí)行，因而可能造成難以預(yù)料的后果。顯然，在要求比較嚴(yán)格的實(shí)時(shí)系統(tǒng)中，不宜采用這種調(diào)度方式。,,2)搶占方式(Preemptive Mode)　　 這種調(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ù)，特別是能滿足對響應(yīng)時(shí)間有著較嚴(yán)格要求的實(shí)時(shí)任務(wù)的需求。但搶

16、占方式比非搶占方式調(diào)度所需付出的開銷較大。搶占調(diào)度方式是基于一定原則的，主要有如下幾條：,,(1)優(yōu)先權(quán)原則。通常是對一些重要的和緊急的作業(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í)，

17、將暫停當(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)。,,中級調(diào)度 中級調(diào)度又稱中程調(diào)度。引入中級調(diào)度的主要目的是為了提高內(nèi)存利用率和系統(tǒng)吞吐量。為此，應(yīng)使那些暫時(shí)

18、不能運(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í)，由中級調(diào)度來決定把外存上的那些又具備運(yùn)行條件的就緒進(jìn)程重新調(diào)入內(nèi)存，并修改其狀態(tài)為就緒狀態(tài)，掛在就緒隊(duì)列上等待進(jìn)程調(diào)度。中級調(diào)度實(shí)際上就是存儲器管理中的對換功能。,,在上述三種調(diào)度中，進(jìn)程調(diào)度的運(yùn)行頻率最高，在分時(shí)系統(tǒng)中通常是10～100 ms便進(jìn)行一次進(jìn)程調(diào)度，因此把它稱為短程調(diào)度