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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

系統(tǒng)在作業(yè)輸入到外存，進(jìn)入后備狀態(tài)時(shí)為作業(yè)建立JCB，它是作業(yè)存在的惟一標(biāo)志.152023/1/293、作業(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í)行。需要重點(diǎn)考慮以下兩個(gè)問題：

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

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

(1)排隊(duì)器。

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

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

(1)排隊(duì)器。為了提高進(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.1處理機(jī)調(diào)度的層次（低級(jí)調(diào)度）202023/1/292、進(jìn)程調(diào)度中的三個(gè)基本機(jī)制

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

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

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

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

(1)非搶占方式(NonpreemptiveMode)一旦把處理機(jī)分配給某進(jìn)程后，便讓該進(jìn)程一直執(zhí)行，決不會(huì)因?yàn)闀r(shí)鐘中斷等原因而搶占正在運(yùn)行進(jìn)程的處理機(jī)，也不允許其它進(jìn)程搶占已經(jīng)分配給該進(jìn)程的處理機(jī)，直至該進(jìn)程完成或阻塞時(shí)，才再把處理機(jī)分配給其他進(jìn)程。3.1處理機(jī)調(diào)度的層次（低級(jí)調(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請(qǐng)求而暫停執(zhí)行在進(jìn)程通信或同步過程中執(zhí)行了某種原語操作，如P操作（WAIT操作）、BLOCK原語、WAKEUP原語等。

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

(1)非搶占方式(NonpreemptiveMode)

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

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

(2)搶占方式(PreemptiveMode)允許暫停某個(gè)正在執(zhí)行的進(jìn)程，將已分配給該進(jìn)程的處理機(jī)重新分配給另一進(jìn)程。優(yōu)點(diǎn)：可以防止一個(gè)長(zhǎng)進(jìn)程長(zhǎng)時(shí)間占用處理機(jī)，能為大多數(shù)進(jìn)程提供更公平的服務(wù)，特別是能滿足對(duì)響應(yīng)時(shí)間有著較嚴(yán)格要求的實(shí)時(shí)任務(wù)的需求。缺點(diǎn)：搶占方式比非搶占方式調(diào)度所需付出的開銷較大。3.1處理機(jī)調(diào)度的層次（低級(jí)調(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)前較長(zhǎng)作業(yè)（進(jìn)程）的處理機(jī)。時(shí)間片原則。各進(jìn)程按時(shí)間片運(yùn)行，當(dāng)一個(gè)時(shí)間片用完后重新調(diào)度。

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

截止時(shí)間的保證

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

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

資源的平衡利用

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

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

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

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

高優(yōu)先權(quán)優(yōu)先調(diào)度算法基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法3.3調(diào)度算法552023/1/29（一）先來先服務(wù)(FCFS)調(diào)度算法是一種最簡(jiǎn)單的調(diào)度算法既可用于作業(yè)調(diào)度也可用于進(jìn)程調(diào)度。FCFS(firstcomefirstserve)算法有利長(zhǎng)作業(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è)隊(duì)列中，選擇一個(gè)或多個(gè)最先進(jìn)入該隊(duì)列的作業(yè)調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進(jìn)程，然后放入就緒隊(duì)列。進(jìn)程調(diào)度時(shí)每次從就緒隊(duì)列中，選擇一個(gè)最先進(jìn)入該隊(duì)列的進(jìn)程分配處理機(jī)使之運(yùn)行。直到完成或阻塞后，才放棄處理機(jī)。一、先來先服務(wù)和短作業(yè)(進(jìn)程)調(diào)度算法572023/1/29進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間平均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á)時(shí)間服務(wù)時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間A010111/1B11001101100100/100C21101102100100/1D3100102202199199/100592023/1/29

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

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

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