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

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

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

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

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

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

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

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

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

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

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

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

作業(yè)控制塊（JCB）：為了管理和調(diào)度已進(jìn)入系統(tǒng)的各個作業(yè)，系統(tǒng)設(shè)置的用于記錄作業(yè)的基本情況的數(shù)據(jù)結(jié)構(gòu)。3.1處理機(jī)調(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è)建立的時間、要求運(yùn)行的時間、最遲完成的時間、需要的主存容量、外設(shè)的種類及數(shù)量和資源使用情況。3.1處理機(jī)調(diào)度的層次（高級調(diào)度）142023/1/293.1處理機(jī)調(diào)度的層次（高級調(diào)度）2、作業(yè)控制塊（JCB）2）JCB（作業(yè)控制塊）的建立:

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

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

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

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

(1)排隊器。

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

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

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

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

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

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

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

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

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

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

(1)非搶占方式(NonpreemptiveMode)

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

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

(1)非搶占方式(NonpreemptiveMode)

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

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

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

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

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

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

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

截止時間的保證

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

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

資源的平衡利用

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

。平均帶權(quán)周轉(zhuǎn)時間：432023/1/29作業(yè)提交時間/時運(yùn)行時間/minute110：00120210：1060310：2525例:有如下三道作業(yè)。系統(tǒng)為它們服務(wù)的順序是：1、2、3。求平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。3.2調(diào)度隊列模型和調(diào)度準(zhǔn)則442023/1/29作業(yè)提交時間運(yùn)行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間110:00120210:1060310:2525452023/1/29作業(yè)提交時間運(yùn)行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間110:001201012:0022/2210:1060310:2525462023/1/29作業(yè)提交時間運(yùn)行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間110:001201012:0022/2210:10601213:0017/6(17/6)/1310:2525472023/1/29作業(yè)提交時間運(yùn)行時間開始時間完成時間周轉(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)度準(zhǔn)則從鍵盤輸入的請求信息傳送到處理機(jī)的時間處理機(jī)對請求信息進(jìn)行處理的時間將響應(yīng)信息回送到終端顯示器的時間。502023/1/29（3）截止時間保證截止時間是指某任務(wù)必須開始執(zhí)行的最遲時間或必須完成的最遲時間截止時間是實時系統(tǒng)中的重要指標(biāo)3.2調(diào)度隊列模型和調(diào)度準(zhǔn)則512023/1/29（4）優(yōu)先權(quán)準(zhǔn)則在批處理、實時和分時系統(tǒng)中都可以選擇優(yōu)先權(quán)準(zhǔn)則，以便讓緊急任務(wù)先處理有時還選擇搶占式調(diào)度方式（5）等待時間短等待時間是在就緒隊列中等待所花的時間調(diào)度算法并不影響進(jìn)程運(yùn)行和執(zhí)行I/O的時間量；只影響進(jìn)程在就緒隊列中等待所花費的時間3.2調(diào)度隊列模型和調(diào)度準(zhǔn)則522023/1/29（二）面向系統(tǒng)的準(zhǔn)則1、系統(tǒng)吞吐量高吞吐量指單位時間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)作業(yè)調(diào)度的方式和算法對吞吐量的大小有較大影響2、處理機(jī)利用率高3、各類資源的平衡利用使內(nèi)存、外存和I/O設(shè)備的利用率高3.2調(diào)度隊列模型和調(diào)度準(zhǔn)則532023/1/293.3調(diào)度算法在OS中調(diào)度的實質(zhì)是一種資源分配，因而調(diào)度算法是指：根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法。如何制定分配策略：對不同的系統(tǒng)和系統(tǒng)目標(biāo)，通常采用不同的算法，如短作業(yè)優(yōu)先，時間片輪轉(zhuǎn)等。有些算法適用于作業(yè)調(diào)度，有些適用于進(jìn)程調(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)度也可用于進(jìn)程調(diào)度。FCFS(firstcomefirstserve)算法有利長作業(yè)（進(jìn)程），而不利于短作業(yè)（進(jìn)程）。有利CPU繁忙型作業(yè)，而不利于I/O繁忙型作業(yè)。一、先來先服務(wù)和短作業(yè)(進(jìn)程)調(diào)度算法562023/1/29（一）先來先服務(wù)(FCFS)調(diào)度算法作業(yè)調(diào)度中每次從后備作業(yè)隊列中，選擇一個或多個最先進(jìn)入該隊列的作業(yè)調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進(jìn)程，然后放入就緒隊列。進(jìn)程調(diào)度時每次從就緒隊列中，選擇一個最先進(jìn)入該隊列的進(jìn)程分配處理機(jī)使之運(yùn)行。直到完成或阻塞后，才放棄處理機(jī)。一、先來先服務(wù)和短作業(yè)(進(jìn)程)調(diào)度算法572023/1/29進(jìn)程名到達(dá)時間服務(wù)時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間平均04A13B25C32D44E044476先來先服務(wù)：712101214111418141225.53.592.8一、先來先服務(wù)和短作業(yè)(進(jìn)程)調(diào)度算法決定服務(wù)順序開始+服務(wù)完成-到達(dá)周轉(zhuǎn)/服務(wù)582023/1/29一、先來先服務(wù)和短作業(yè)(進(jìn)程)調(diào)度算法進(jìn)程到達(dá)時間服務(wù)時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間A010111/1B11001101100100/100C21101102100100/1D3100102202199199/100592023/1/29

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

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

作業(yè)算法一、先來先服務(wù)和短作業(yè)(進(jìn)程)調(diào)度算法632023/1/29SJ(P)F調(diào)度算法的缺點對長作業(yè)不利。由于調(diào)度程序總是優(yōu)先調(diào)度短作業(yè)(進(jìn)程)，將導(dǎo)致長作業(yè)(進(jìn)程)長期不被調(diào)度——饑餓；完全未考慮作業(yè)(進(jìn)程)的緊迫程度，因而不能保證緊迫性作業(yè)(進(jìn)程)會被及時處理；由于作業(yè)(進(jìn)程)的長短只是根據(jù)用戶所提供的估計執(zhí)行時間而定的，而用戶又可能會有意或無意地縮短其作業(yè)的估計運(yùn)行時間，致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。一、先來先服務(wù)和短作業(yè)(進(jìn)程)調(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)把處理機(jī)分配給優(yōu)先級最高的就緒進(jìn)程。分為兩大類：（1）非搶占式優(yōu)先級調(diào)度算法（2）搶占式優(yōu)先級調(diào)度算法662023/1/29662023/1/29非搶占式優(yōu)先級算法把處理機(jī)分配給就緒隊列中優(yōu)先級最高的進(jìn)程后便一直執(zhí)行下去直至完成；或發(fā)生某事件使該進(jìn)程放棄處理機(jī)時，可再將處理機(jī)重新分配給另一優(yōu)先級最高的進(jìn)程。用于批處理系統(tǒng)和某些對實時性要求不嚴(yán)的實時系統(tǒng)中。672023/1/29672023/1/29搶占式優(yōu)先級調(diào)度算法把處理機(jī)分配給優(yōu)先級最高的進(jìn)程，使之執(zhí)行。在執(zhí)行期間，只要又出現(xiàn)優(yōu)先級更高的進(jìn)程，就重新將處理機(jī)分配給新到的優(yōu)先級最高的進(jìn)程。能更好地滿足緊迫作業(yè)的要求，常用于要求比較嚴(yán)格的實時系統(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)建進(jìn)程時確定在進(jìn)程的整個運(yùn)行期間保持不變。一般地，用某一范圍內(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)先級確定進(jìn)程靜態(tài)優(yōu)先級的依據(jù)進(jìn)程類型:系統(tǒng)進(jìn)程，用戶進(jìn)程（系統(tǒng)進(jìn)程高于用戶進(jìn)程）進(jìn)程對資源的需求：要求少的進(jìn)程應(yīng)賦予較高優(yōu)先級。用戶要求：這是由用戶進(jìn)程的緊迫程度及所付費多少來確定。二、優(yōu)先級調(diào)度算法和高響應(yīng)比調(diào)度算法712023/1/29712023/1/29簡單，系統(tǒng)開銷小不精確，僅在要求不高的系統(tǒng)中使用。可能會出現(xiàn)優(yōu)先級低的進(jìn)程長期沒有被調(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進(jìn)程到達(dá)時間服務(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)先級。隨進(jìn)程的推進(jìn)或隨其等待時間的增加而改變，以獲得更好的調(diào)度性能；可規(guī)定，在就緒隊列中的進(jìn)程，隨其等待時間的增長，其優(yōu)先級以速率a提高；當(dāng)采用搶占式優(yōu)先級調(diào)度算法時，如果再規(guī)定當(dāng)前進(jìn)程的優(yōu)先級以速率b下降，則可防止一個長作業(yè)長期地壟斷處理機(jī)。二、優(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)法把就緒進(jìn)程組織成FIFO隊列，把CPU分配給隊首進(jìn)程，規(guī)定它執(zhí)行一個時間片。時間片完時排在就緒隊列的末尾，重新把處理機(jī)分配給就緒隊列中新的隊首進(jìn)程，也執(zhí)行一個時間片。就緒隊列中的所有進(jìn)程在一給定時間內(nèi)，均可獲得一個時間片的CPU時間.時間片的大小從幾ms到幾百ms772023/1/29772023/1/29說明：（1）時間片選擇問題固定時間片可變時間片時間片大?。?）與時間片大小有關(guān)的因素系統(tǒng)響應(yīng)時間就緒進(jìn)程個數(shù)CPU能力三、基于時間片的輪轉(zhuǎn)調(diào)度算法782023/1/29782023/1/29三、基于時間片的輪轉(zhuǎn)調(diào)度算法說明：時間片大小對系統(tǒng)性能有很大影響：很小，有利于短作業(yè)，因為它能在該時間片內(nèi)完成，但時間片小，意味著頻繁進(jìn)行進(jìn)程調(diào)度和上下文切換，會增加系統(tǒng)開銷。如果過大，每個作業(yè)都可以在一個時間片內(nèi)完成，直接褪化為FCFS算法，無法滿足短作業(yè)和交互式作業(yè)的需求。792023/1/29792023/1/29進(jìn)程名到達(dá)時間服務(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進(jìn)程名到達(dá)時間服務(wù)時間開始時間完成時間周轉(zhuǎn)時間