第3章-處理機調(diào)度與死鎖

12023/1/29第3章處理機調(diào)度與死鎖操作系統(tǒng)22023/1/29第3章處理機調(diào)度與死鎖重點掌握進程調(diào)度算法，各適用于何種情況理解常用的幾種實時調(diào)度算法理解產(chǎn)生死鎖的原因掌握銀行家算法避免死鎖難點多道程序設(shè)計中的各種調(diào)度算法響應(yīng)比高者優(yōu)先調(diào)度算法的計算過程銀行家算法

32023/1/29第3章處理機調(diào)度與死鎖知識點處理機調(diào)度及調(diào)度算法多處理機環(huán)境下的進程（線程）調(diào)度方式產(chǎn)生死鎖的原因和必要條件預(yù)防死鎖的方法，死鎖的檢測與解除銀行家算法42023/1/29本講主要內(nèi)容

處理機調(diào)度的層次調(diào)度隊列模型和調(diào)度準則調(diào)度算法（1）52023/1/293.1處理機調(diào)度的層次作業(yè)是用戶在一次解題或一個事務(wù)處理過程中要求計算機系統(tǒng)所做工作的集合，包括用戶程序、所需的數(shù)據(jù)及命令等作業(yè)的狀態(tài)：一個作業(yè)進入系統(tǒng)到運行結(jié)束，一般需要經(jīng)歷收容、運行、完成三個階段，與之相對應(yīng)的是作業(yè)的三種狀態(tài)：后備狀態(tài)運行狀態(tài)完成狀態(tài)62023/1/29運行狀態(tài)3.1處理機調(diào)度的層次后備狀態(tài)完成狀態(tài)就緒阻塞執(zhí)行I/O完成I/O請求時間片完作業(yè)注冊作業(yè)調(diào)度進程調(diào)度終止作業(yè)作業(yè)狀態(tài)間轉(zhuǎn)換72023/1/29

一個批處理型作業(yè)，從進入系統(tǒng)并駐留在外存的后備隊列上開始，直至作業(yè)運行完畢，可能要經(jīng)歷的三級調(diào)度:高級調(diào)度(后備狀態(tài)→運行狀態(tài))低級調(diào)度(就緒狀態(tài)→執(zhí)行狀態(tài))中級調(diào)度（對換）3.1處理機調(diào)度的層次82023/1/29（一）高級調(diào)度

又稱作業(yè)調(diào)度或長程調(diào)度作用：把外存上處于后備隊列中的作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進程、分配資源、排在就緒隊列上，準備執(zhí)行。主要用在批處理系統(tǒng)，分時系統(tǒng)和實時系統(tǒng)通常不需要作業(yè)調(diào)度。它的執(zhí)行效率較低，通常為幾分鐘調(diào)度一次。3.1處理機調(diào)度的層次92023/1/291、作業(yè)和作業(yè)步：

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

3.1處理機調(diào)度的層次（高級調(diào)度）102023/1/291、作業(yè)和作業(yè)步：

(2)作業(yè)步(JobStep)。在作業(yè)運行期間，都必須經(jīng)過若干個相對獨立又相互關(guān)聯(lián)的順序加工步驟才能得到結(jié)果。把其中每一個加工步驟稱為一個作業(yè)步，往往是把上一個作業(yè)步的輸出作為下一個作業(yè)步的輸入。一個典型的作業(yè)可以分為：編譯作業(yè)步、鏈接裝配作業(yè)步和運行作業(yè)步。3.1處理機調(diào)度的層次（高級調(diào)度）112023/1/291、作業(yè)和作業(yè)步：

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

3.1處理機調(diào)度的層次（高級調(diào)度）122023/1/29

程序作業(yè)由三部分組成數(shù)據(jù)作業(yè)說明書（說明用戶意圖）

作業(yè)控制塊（JCB）：為了管理和調(diào)度已進入系統(tǒng)的各個作業(yè)，系統(tǒng)設(shè)置的用于記錄作業(yè)的基本情況的數(shù)據(jù)結(jié)構(gòu)。3.1處理機調(diào)度的層次（高級調(diào)度）132023/1/292、作業(yè)控制塊（JCB）

1）包含內(nèi)容：

(1)作業(yè)的基本情況用戶名、作業(yè)名、作業(yè)的狀態(tài)和使用的語言等。

(2)作業(yè)的控制要求控制方式、類型、優(yōu)先數(shù)、操作順序和出錯處理等。

(3)作業(yè)的資源要求作業(yè)建立的時間、要求運行的時間、最遲完成的時間、需要的主存容量、外設(shè)的種類及數(shù)量和資源使用情況。3.1處理機調(diào)度的層次（高級調(diào)度）142023/1/293.1處理機調(diào)度的層次（高級調(diào)度）2、作業(yè)控制塊（JCB）2）JCB（作業(yè)控制塊）的建立:

系統(tǒng)在作業(yè)輸入到外存，進入后備狀態(tài)時為作業(yè)建立JCB，它是作業(yè)存在的惟一標志.152023/1/293、作業(yè)調(diào)度的主要功能

主要功能是根據(jù)作業(yè)控制塊中的信息，審查系統(tǒng)能否滿足用戶作業(yè)的資源需求，以及按照一定的算法，從外存的后備隊列中選取某些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進程、分配必要的資源。然后再將新創(chuàng)建的進程插入就緒隊列，準備執(zhí)行。需要重點考慮以下兩個問題：

1）決定接納多少個作業(yè)（多道程序度）；

2）決定接納哪些作業(yè)（調(diào)度算法）。3.1處理機調(diào)度的層次（高級調(diào)度）162023/1/29（二）低級調(diào)度又稱進程調(diào)度或短程調(diào)度。作用：決定就緒隊列中哪個進程應(yīng)獲得處理機；分派程序執(zhí)行把處理機分配給該進程的具體操作。進程調(diào)度是最基本的一種調(diào)度，在多道批處理、分時和實時三種類型的OS中，都必須配置這級調(diào)度。3.1處理機調(diào)度的層次172023/1/291、低級調(diào)度的功能保存處理機的現(xiàn)場信息；按某種算法選取進程；把處理器分配給進程。3.1處理機調(diào)度的層次（低級調(diào)度）182023/1/292、進程調(diào)度中的三個基本機制

(1)排隊器。

(2)分派器(分派程序)。

(3)上下文切換機制。3.1處理機調(diào)度的層次（低級調(diào)度）192023/1/292、進程調(diào)度中的三個基本機制

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

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

3.1處理機調(diào)度的層次（低級調(diào)度）202023/1/292、進程調(diào)度中的三個基本機制

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

3.1處理機調(diào)度的層次（低級調(diào)度）212023/1/293、進程調(diào)度方式

(1)非搶占方式(NonpreemptiveMode)(2)搶占方式(PreemptiveMode)

3.1處理機調(diào)度的層次（低級調(diào)度）222023/1/293、進程調(diào)度方式

(1)非搶占方式(NonpreemptiveMode)一旦把處理機分配給某進程后，便讓該進程一直執(zhí)行，決不會因為時鐘中斷等原因而搶占正在運行進程的處理機，也不允許其它進程搶占已經(jīng)分配給該進程的處理機，直至該進程完成或阻塞時，才再把處理機分配給其他進程。3.1處理機調(diào)度的層次（低級調(diào)度）232023/1/293、進程調(diào)度方式

(1)非搶占方式(NonpreemptiveMode)

非搶占方式引起進程調(diào)度的三大因素：進程執(zhí)行完畢，或因發(fā)生某事件而不能再繼續(xù)執(zhí)行；執(zhí)行中的進程因提出I/O請求而暫停執(zhí)行在進程通信或同步過程中執(zhí)行了某種原語操作，如P操作（WAIT操作）、BLOCK原語、WAKEUP原語等。

3.1處理機調(diào)度的層次（低級調(diào)度）242023/1/293、進程調(diào)度方式

(1)非搶占方式(NonpreemptiveMode)

優(yōu)點：實現(xiàn)簡單、系統(tǒng)開銷小，適用于大多數(shù)的批處理系統(tǒng)環(huán)境；

缺點：難以滿足緊急任務(wù)的要求——立即執(zhí)行，因而可能造成難以預(yù)料的后果。在要求比較嚴格的實時系統(tǒng)中，不宜采用這種調(diào)度方式。3.1處理機調(diào)度的層次（低級調(diào)度）252023/1/293、進程調(diào)度方式

(2)搶占方式(PreemptiveMode)允許暫停某個正在執(zhí)行的進程，將已分配給該進程的處理機重新分配給另一進程。優(yōu)點：可以防止一個長進程長時間占用處理機，能為大多數(shù)進程提供更公平的服務(wù)，特別是能滿足對響應(yīng)時間有著較嚴格要求的實時任務(wù)的需求。缺點：搶占方式比非搶占方式調(diào)度所需付出的開銷較大。3.1處理機調(diào)度的層次（低級調(diào)度）262023/1/293、進程調(diào)度方式

(2)搶占方式(PreemptiveMode)搶占不是一種任意行為，必須遵循的原則：優(yōu)先權(quán)原則。優(yōu)先權(quán)高的進程搶占處理機。短作業(yè)優(yōu)先原則。短作業(yè)（進程）搶占當前較長作業(yè)（進程）的處理機。時間片原則。各進程按時間片運行，當一個時間片用完后重新調(diào)度。

3.1處理機調(diào)度的層次（低級調(diào)度）272023/1/29（三）中級調(diào)度（中程調(diào)度）又稱中程調(diào)度。目的：提高內(nèi)存利用率和系統(tǒng)吞吐率作用：使暫時不能運行的進程從內(nèi)存調(diào)至外存，進入就緒駐外存狀態(tài)（靜止就緒）或掛起狀態(tài)。把外存上又具備運行條件的就緒進程，重新調(diào)入內(nèi)存，并修改為就緒狀態(tài)，掛在就緒隊列上。又稱對換。3.1處理機調(diào)度的層次282023/1/293.2調(diào)度隊列模型和調(diào)度準則（一）調(diào)度隊列模型（二）調(diào)度準則292023/1/293.2調(diào)度隊列模型和調(diào)度準則（一）調(diào)度隊列模型僅有進程調(diào)度的調(diào)度隊列模型具有高級和低級調(diào)度的調(diào)度隊列模型同時具有三級調(diào)度的調(diào)度隊列模型302023/1/293.2調(diào)度隊列模型和調(diào)度準則1、僅有進程調(diào)度的調(diào)度隊列模型在分時系統(tǒng)中，通常僅設(shè)有進程調(diào)度，用戶鍵入的命令和數(shù)據(jù)直接送入內(nèi)存；系統(tǒng)可以把處于就緒狀態(tài)的進程組織成棧、隊列、樹或一個無序鏈表；分時系統(tǒng)把這些進程組織成一個FIFO隊列。每當創(chuàng)建新進程時排在就緒隊列的末尾，按時間片輪轉(zhuǎn)方式運行312023/1/291、僅有進程調(diào)度的調(diào)度隊列模型進程在執(zhí)行時，出現(xiàn)三種情況：任務(wù)在時間片內(nèi)完成，進程便在釋放處理機后進入完成狀態(tài)；任務(wù)在時間片內(nèi)未完成，OS便將該任務(wù)再放入就緒隊列的末尾；在執(zhí)行期間，進程因為某事件而被阻塞后，被OS放入阻塞隊列。3.2調(diào)度隊列模型和調(diào)度準則322023/1/29就緒隊列阻塞隊列cpu進程調(diào)度等待事件時間片完進程完成用戶事件出現(xiàn)僅有進程調(diào)度的調(diào)度隊列模型3.2調(diào)度隊列模型和調(diào)度準則332023/1/293.2調(diào)度隊列模型和調(diào)度準則2、具有高級和低級調(diào)度的調(diào)度隊列模型在批處理系統(tǒng)中，不僅需要進程調(diào)度，而且還要有作業(yè)調(diào)度。一般由作業(yè)調(diào)度按一定的作業(yè)調(diào)度算法，從外存的后備隊列中選擇一批作業(yè)調(diào)入內(nèi)存，并為它們建立進程，送入就緒隊列；然后由進程調(diào)度按照一定的進程調(diào)度算法選擇一個進程，把處理機分配給該進程。342023/1/293.2調(diào)度隊列模型和調(diào)度準則2、具有高級和低級調(diào)度的調(diào)度隊列模型與前一模型的差別：就緒隊列的形式。批處理系統(tǒng)中最常用的是優(yōu)先權(quán)隊列。也可采用無序鏈表方式。根據(jù)不同阻塞原因，設(shè)置多個阻塞隊列。352023/1/29就緒隊列阻塞隊列1cpu進程調(diào)度等待事件1時間片完進程完成作業(yè)調(diào)度后備隊列3.2調(diào)度隊列模型和調(diào)度準則等待事件2阻塞隊列2362023/1/293.2調(diào)度隊列模型和調(diào)度準則3、同時具有三級調(diào)度的調(diào)度隊列模型在OS中引入中級調(diào)度后，可把進程的就緒狀態(tài)分為內(nèi)存就緒(表示進程在內(nèi)存中就緒)和外存就緒(進程在外存中就緒)。類似地，也可把阻塞狀態(tài)進一步分成內(nèi)存阻塞和外存阻塞兩種狀態(tài)。372023/1/293.2調(diào)度隊列模型和調(diào)度準則3、同時具有三級調(diào)度的調(diào)度隊列模型在調(diào)出操作的作用下，可使進程狀態(tài)由內(nèi)存就緒轉(zhuǎn)為外存就緒，由內(nèi)存阻塞轉(zhuǎn)為外存阻塞；在中級調(diào)度的作用下，又可使外存就緒轉(zhuǎn)為內(nèi)存就緒。382023/1/293.2調(diào)度隊列模型和調(diào)度準則3、同時具有三級調(diào)度的調(diào)度隊列模型就緒隊列進程調(diào)度就緒，掛起隊列中級調(diào)度阻塞，掛起隊列阻塞隊列等待事件進程完成時間片完作業(yè)調(diào)度交互型作業(yè)后備隊列批量作業(yè)掛起掛起事件出現(xiàn)事件出現(xiàn)CPU392023/1/293.2調(diào)度隊列模型和調(diào)度準則（二）調(diào)度準則如果你是用戶，你希望系統(tǒng)如何為你服務(wù)，如何考慮？

----面向用戶的準則如果你是調(diào)度者，從系統(tǒng)整體角度出發(fā)，應(yīng)如何考慮？

----面向系統(tǒng)的準則402023/1/293.2調(diào)度隊列模型和調(diào)度準則面向用戶的準則面向系統(tǒng)的準則周轉(zhuǎn)時間短響應(yīng)時間快

截止時間的保證

優(yōu)先權(quán)準則

系統(tǒng)吞吐量高處理機利用率高

資源的平衡利用

412023/1/293.2調(diào)度隊列模型和調(diào)度準則1、面向用戶的準則（1）周轉(zhuǎn)時間短所謂周轉(zhuǎn)時間，是指從作業(yè)被提交給系統(tǒng)開始，到作業(yè)完成為止的這段時間間隔(稱為作業(yè)周轉(zhuǎn)時間)。包括四部分時間：作業(yè)在外存后備隊列上等待(作業(yè))調(diào)度的時間；進程在就緒隊列上等待進程調(diào)度的時間；進程在CPU上執(zhí)行的時間；進程等待I/O操作完成的時間。422023/1/293.2調(diào)度隊列模型和調(diào)度準則平均周轉(zhuǎn)時間：帶權(quán)周轉(zhuǎn)時間：進程（或作業(yè)）的周轉(zhuǎn)時間T與系統(tǒng)為它提供服務(wù)的時間TS（真正運行時間）之比，即W=T/TS

。平均帶權(quán)周轉(zhuǎn)時間：432023/1/29作業(yè)提交時間/時運行時間/minute110：00120210：1060310：2525例:有如下三道作業(yè)。系統(tǒng)為它們服務(wù)的順序是：1、2、3。求平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。3.2調(diào)度隊列模型和調(diào)度準則442023/1/29作業(yè)提交時間運行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間110:00120210:1060310:2525452023/1/29作業(yè)提交時間運行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間110:001201012:0022/2210:1060310:2525462023/1/29作業(yè)提交時間運行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間110:001201012:0022/2210:10601213:0017/6(17/6)/1310:2525472023/1/29作業(yè)提交時間運行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間110:001201012:0022/2210:10601213:0017/6(17/6)/1310:25251313:2533/（25/60）482023/1/29平均周轉(zhuǎn)時間：T=(2+17/6+3)/3=2.61h平均帶權(quán)周轉(zhuǎn)時間：W=(1+17/6+7.2)/3=3.68h。492023/1/29（2）響應(yīng)時間快響應(yīng)時間是指從用戶通過鍵盤提交一個請求開始，直至系統(tǒng)中首次產(chǎn)生響應(yīng)為止的時間。它包括三部分時間：

響應(yīng)時間是分時系統(tǒng)中的重要原則!3.2調(diào)度隊列模型和調(diào)度準則從鍵盤輸入的請求信息傳送到處理機的時間處理機對請求信息進行處理的時間將響應(yīng)信息回送到終端顯示器的時間。502023/1/29（3）截止時間保證截止時間是指某任務(wù)必須開始執(zhí)行的最遲時間或必須完成的最遲時間截止時間是實時系統(tǒng)中的重要指標3.2調(diào)度隊列模型和調(diào)度準則512023/1/29（4）優(yōu)先權(quán)準則在批處理、實時和分時系統(tǒng)中都可以選擇優(yōu)先權(quán)準則，以便讓緊急任務(wù)先處理有時還選擇搶占式調(diào)度方式（5）等待時間短等待時間是在就緒隊列中等待所花的時間調(diào)度算法并不影響進程運行和執(zhí)行I/O的時間量；只影響進程在就緒隊列中等待所花費的時間3.2調(diào)度隊列模型和調(diào)度準則522023/1/29（二）面向系統(tǒng)的準則1、系統(tǒng)吞吐量高吞吐量指單位時間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)作業(yè)調(diào)度的方式和算法對吞吐量的大小有較大影響2、處理機利用率高3、各類資源的平衡利用使內(nèi)存、外存和I/O設(shè)備的利用率高3.2調(diào)度隊列模型和調(diào)度準則532023/1/293.3調(diào)度算法在OS中調(diào)度的實質(zhì)是一種資源分配，因而調(diào)度算法是指：根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法。如何制定分配策略：對不同的系統(tǒng)和系統(tǒng)目標，通常采用不同的算法，如短作業(yè)優(yōu)先，時間片輪轉(zhuǎn)等。有些算法適用于作業(yè)調(diào)度，有些適用于進程調(diào)度，有些兩者皆可。542023/1/29

先來先服務(wù)和短作業(yè)優(yōu)先算法

高優(yōu)先權(quán)優(yōu)先調(diào)度算法基于時間片的輪轉(zhuǎn)調(diào)度算法3.3調(diào)度算法552023/1/29（一）先來先服務(wù)(FCFS)調(diào)度算法是一種最簡單的調(diào)度算法既可用于作業(yè)調(diào)度也可用于進程調(diào)度。FCFS(firstcomefirstserve)算法有利長作業(yè)（進程），而不利于短作業(yè)（進程）。有利CPU繁忙型作業(yè)，而不利于I/O繁忙型作業(yè)。一、先來先服務(wù)和短作業(yè)(進程)調(diào)度算法562023/1/29（一）先來先服務(wù)(FCFS)調(diào)度算法作業(yè)調(diào)度中每次從后備作業(yè)隊列中，選擇一個或多個最先進入該隊列的作業(yè)調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進程，然后放入就緒隊列。進程調(diào)度時每次從就緒隊列中，選擇一個最先進入該隊列的進程分配處理機使之運行。直到完成或阻塞后，才放棄處理機。一、先來先服務(wù)和短作業(yè)(進程)調(diào)度算法572023/1/29進程名到達時間服務(wù)時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間平均04A13B25C32D44E044476先來先服務(wù)：712101214111418141225.53.592.8一、先來先服務(wù)和短作業(yè)(進程)調(diào)度算法決定服務(wù)順序開始+服務(wù)完成-到達周轉(zhuǎn)/服務(wù)582023/1/29一、先來先服務(wù)和短作業(yè)(進程)調(diào)度算法進程到達時間服務(wù)時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間A010111/1B11001101100100/100C21101102100100/1D3100102202199199/100592023/1/29

先來先服務(wù)（先進先出）優(yōu)缺點

比較有利于長作業(yè)（進程），而不利于短作業(yè)（進程）有利于CPU繁忙型作業(yè)（進程），而不利于I/O繁忙型作業(yè)（進程）主要用于批處理系統(tǒng)，不適于分時系統(tǒng)一、先來先服務(wù)和短作業(yè)(進程)調(diào)度算法602023/1/29（二）短作業(yè)(進程)優(yōu)先調(diào)度算法SJ(P)F以要求運行時間長短進行調(diào)度，即啟動要求運行時間最短的作業(yè)SJF從后備隊列中選擇一個或若干個估計運行時間最短的作業(yè)，將它們調(diào)入內(nèi)存運行；短進程優(yōu)先(SPF)調(diào)度算法，是從就緒隊列中選出一估計運行時間最短的進程，將處理機分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機時，再重新調(diào)度。一、先來先服務(wù)和短作業(yè)(進程)調(diào)度算法612023/1/29進程名到達時間服務(wù)時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間平均04A13B25C32D44E0441短作業(yè)/短進程優(yōu)先（SJF/SPF）：4633/26988/391399/413181616/540/52.1一、先來先服務(wù)和短作業(yè)(進程)調(diào)度算法決定服務(wù)順序開始+服務(wù)完成-到達622023/1/29FCFS/SJF調(diào)度算法的性能2.259133.5141844E1.5365.5111423D3.116182101252C2.678926731B2.11帶權(quán)周轉(zhuǎn)時間84周轉(zhuǎn)時間4完成時間SJF2.81帶權(quán)周轉(zhuǎn)時間94周轉(zhuǎn)時間4完成時間FCFS4服務(wù)時間0到達時間平均A進程名

作業(yè)算法一、先來先服務(wù)和短作業(yè)(進程)調(diào)度算法632023/1/29SJ(P)F調(diào)度算法的缺點對長作業(yè)不利。由于調(diào)度程序總是優(yōu)先調(diào)度短作業(yè)(進程)，將導致長作業(yè)(進程)長期不被調(diào)度——饑餓；完全未考慮作業(yè)(進程)的緊迫程度，因而不能保證緊迫性作業(yè)(進程)會被及時處理；由于作業(yè)(進程)的長短只是根據(jù)用戶所提供的估計執(zhí)行時間而定的，而用戶又可能會有意或無意地縮短其作業(yè)的估計運行時間，致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。一、先來先服務(wù)和短作業(yè)(進程)調(diào)度算法642023/1/29642023/1/293.3調(diào)度算法先來先服務(wù)和短作業(yè)優(yōu)先算法優(yōu)先級調(diào)度算法和高響應(yīng)比調(diào)度算法基于時間片的輪轉(zhuǎn)調(diào)度算法652023/1/29652023/1/29二、優(yōu)先級調(diào)度算法和高響應(yīng)比調(diào)度算法1、優(yōu)先級調(diào)度算法的類型調(diào)度時，系統(tǒng)把處理機分配給優(yōu)先級最高的就緒進程。分為兩大類：（1）非搶占式優(yōu)先級調(diào)度算法（2）搶占式優(yōu)先級調(diào)度算法662023/1/29662023/1/29非搶占式優(yōu)先級算法把處理機分配給就緒隊列中優(yōu)先級最高的進程后便一直執(zhí)行下去直至完成；或發(fā)生某事件使該進程放棄處理機時，可再將處理機重新分配給另一優(yōu)先級最高的進程。用于批處理系統(tǒng)和某些對實時性要求不嚴的實時系統(tǒng)中。672023/1/29672023/1/29搶占式優(yōu)先級調(diào)度算法把處理機分配給優(yōu)先級最高的進程，使之執(zhí)行。在執(zhí)行期間，只要又出現(xiàn)優(yōu)先級更高的進程，就重新將處理機分配給新到的優(yōu)先級最高的進程。能更好地滿足緊迫作業(yè)的要求，常用于要求比較嚴格的實時系統(tǒng)中，以及對性能要求較高的批處理和分時系統(tǒng)中。682023/1/29682023/1/29二、優(yōu)先級調(diào)度算法和高響應(yīng)比調(diào)度算法2、優(yōu)先級的類型（1）靜態(tài)優(yōu)先級（2）動態(tài)優(yōu)先級692023/1/29692023/1/29（1）靜態(tài)優(yōu)先級在創(chuàng)建進程時確定在進程的整個運行期間保持不變。一般地，用某一范圍內(nèi)的一個整數(shù)來表示的，例如，0~7或0~255中的某一整數(shù)，又把該整數(shù)稱為優(yōu)先數(shù)。二、優(yōu)先級調(diào)度算法和高響應(yīng)比調(diào)度算法702023/1/29702023/1/29（1）靜態(tài)優(yōu)先級確定進程靜態(tài)優(yōu)先級的依據(jù)進程類型:系統(tǒng)進程，用戶進程（系統(tǒng)進程高于用戶進程）進程對資源的需求：要求少的進程應(yīng)賦予較高優(yōu)先級。用戶要求：這是由用戶進程的緊迫程度及所付費多少來確定。二、優(yōu)先級調(diào)度算法和高響應(yīng)比調(diào)度算法712023/1/29712023/1/29簡單，系統(tǒng)開銷小不精確，僅在要求不高的系統(tǒng)中使用?？赡軙霈F(xiàn)優(yōu)先級低的進程長期沒有被調(diào)度的情況。（1）靜態(tài)優(yōu)先級靜態(tài)優(yōu)先級法優(yōu)缺點：二、優(yōu)先級調(diào)度算法和高響應(yīng)比調(diào)度算法722023/1/29722023/1/29進程到達時間服務(wù)時間靜態(tài)優(yōu)先級開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間平均靜態(tài)優(yōu)先級，非搶占式（1為高優(yōu)先級）04A413B225C332D544E1044148418111010/311161414/516181515/29.42.93二、優(yōu)先級調(diào)度算法和高響應(yīng)比調(diào)度算法732023/1/29732023/1/29（2）動態(tài)優(yōu)先級在創(chuàng)建之初，先賦予其一個優(yōu)先級。隨進程的推進或隨其等待時間的增加而改變，以獲得更好的調(diào)度性能；可規(guī)定，在就緒隊列中的進程，隨其等待時間的增長，其優(yōu)先級以速率a提高；當采用搶占式優(yōu)先級調(diào)度算法時，如果再規(guī)定當前進程的優(yōu)先級以速率b下降，則可防止一個長作業(yè)長期地壟斷處理機。二、優(yōu)先級調(diào)度算法和高響應(yīng)比調(diào)度算法742023/1/29742023/1/293、高響應(yīng)比優(yōu)先調(diào)度算法是FCFS和SJF的結(jié)合，克服了兩種算法的缺點調(diào)度策略：響應(yīng)比最高的作業(yè)優(yōu)先調(diào)度二、優(yōu)先級調(diào)度算法和高響應(yīng)比調(diào)度算法752023/1/29752023/1/293.3調(diào)度算法先來先服務(wù)和短作業(yè)優(yōu)先算法優(yōu)先級調(diào)度算法和高響應(yīng)比調(diào)度算法基于時間片的輪轉(zhuǎn)調(diào)度算法762023/1/29762023/1/29三、基于時間片的輪轉(zhuǎn)調(diào)度算法1、時間片輪轉(zhuǎn)法分時系統(tǒng)中多采用時間片輪轉(zhuǎn)法把就緒進程組織成FIFO隊列，把CPU分配給隊首進程，規(guī)定它執(zhí)行一個時間片。時間片完時排在就緒隊列的末尾，重新把處理機分配給就緒隊列中新的隊首進程，也執(zhí)行一個時間片。就緒隊列中的所有進程在一給定時間內(nèi)，均可獲得一個時間片的CPU時間.時間片的大小從幾ms到幾百ms772023/1/29772023/1/29說明：（1）時間片選擇問題固定時間片可變時間片時間片大?。?）與時間片大小有關(guān)的因素系統(tǒng)響應(yīng)時間就緒進程個數(shù)CPU能力三、基于時間片的輪轉(zhuǎn)調(diào)度算法782023/1/29782023/1/29三、基于時間片的輪轉(zhuǎn)調(diào)度算法說明：時間片大小對系統(tǒng)性能有很大影響：很小，有利于短作業(yè)，因為它能在該時間片內(nèi)完成，但時間片小，意味著頻繁進行進程調(diào)度和上下文切換，會增加系統(tǒng)開銷。如果過大，每個作業(yè)都可以在一個時間片內(nèi)完成，直接褪化為FCFS算法，無法滿足短作業(yè)和交互式作業(yè)的需求。792023/1/29792023/1/29進程名到達時間服務(wù)時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間A04015153.75B13112113.67C24216143.5D323963E44417133.33平均11.83.46三、基于時間片的輪轉(zhuǎn)調(diào)度算法(q=1)802023/1/29802023/1/29進程名到達時間服務(wù)時間開始時間完成時間周轉(zhuǎn)時間