操作系統(tǒng)：第3章 調(diào)度與死鎖

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

在多道程序環(huán)境下，進(jìn)程數(shù)目往往多于處理機(jī)數(shù)目。要求系統(tǒng)能按某種算法，動(dòng)態(tài)地將處理機(jī)分配給就緒隊(duì)列中的一個(gè)進(jìn)程，使之執(zhí)行?，F(xiàn)代OS的運(yùn)行性能，如吞吐量、作業(yè)平均周轉(zhuǎn)時(shí)間、響應(yīng)的及時(shí)性等，在很大程度上取決于調(diào)度，因而，調(diào)度策略成了OS的一個(gè)關(guān)鍵問(wèn)題。3.1處理機(jī)調(diào)度的基本概念3.1.1高級(jí)、中級(jí)和低級(jí)調(diào)度1.高級(jí)調(diào)度又稱作業(yè)調(diào)度或長(zhǎng)期調(diào)度（long-termscheduling)。根據(jù)某種算法，決定把外存上處于后備隊(duì)列的哪些作業(yè)調(diào)入內(nèi)存3.1處理機(jī)調(diào)度的基本概念作業(yè)：（用戶）利用計(jì)算機(jī)進(jìn)行一次運(yùn)行所需工作的集合。要完成一個(gè)工作，用戶必須先提交一個(gè)作業(yè)。如一個(gè)作業(yè)可能由多個(gè)程序構(gòu)成。在PC機(jī)或普通工作站和服務(wù)器上幾乎沒(méi)有作業(yè)的概念在巨型機(jī)和大型服務(wù)器上，主機(jī)的速度高且造價(jià)高，要保證其利用率和效率，用專門的作業(yè)控制軟件作為前端機(jī)向主機(jī)提交作業(yè)的唯一入口。用戶以批文件將作業(yè)提交到前端機(jī)是用戶啟動(dòng)程序的主要方式。2.低級(jí)調(diào)度也稱進(jìn)程調(diào)度或短期調(diào)度。用于決定就緒隊(duì)列中哪個(gè)進(jìn)程獲得處理機(jī)，之后派發(fā)程序（dispatcher）將處理機(jī)分配給該進(jìn)程。進(jìn)程調(diào)度可采用下面兩種方式1）非搶先式調(diào)度（Non-preemptiveMode)一旦把處理機(jī)分配給某進(jìn)程后，便讓該進(jìn)程一直執(zhí)行，直至該進(jìn)程完成或阻塞時(shí)，才再把處理機(jī)分配給其他進(jìn)程。正在執(zhí)行的進(jìn)程正常結(jié)束或由于某種錯(cuò)誤而終止運(yùn)行；執(zhí)行中的進(jìn)程提出I/O請(qǐng)求，在等待I/O完成前，進(jìn)程阻塞，轉(zhuǎn)進(jìn)程調(diào)度；在進(jìn)程通訊中，執(zhí)行中的進(jìn)程執(zhí)行了某種原語(yǔ)操作，如P操作、阻塞原語(yǔ)和喚醒原語(yǔ)。2）搶先式調(diào)度（preemptivemode)允許暫停某個(gè)正在執(zhí)行的進(jìn)程，將已分配給該進(jìn)程的處理機(jī)重新分配給另一進(jìn)程。時(shí)間片原則：在分時(shí)系統(tǒng)中，按照時(shí)間片輪轉(zhuǎn)，分給進(jìn)程的時(shí)間片用完優(yōu)先權(quán)原則：按照優(yōu)先級(jí)調(diào)度，有更高優(yōu)先級(jí)進(jìn)程變?yōu)榫途w短作業(yè)優(yōu)先原則3.中級(jí)調(diào)度在條件允許下，在外存掛起的進(jìn)程集合中選擇哪些進(jìn)程激活并調(diào)回內(nèi)存。為提高效率，加快進(jìn)程運(yùn)行，調(diào)節(jié)系統(tǒng)的負(fù)荷，提高吞吐量。有時(shí)需要在選擇內(nèi)存中阻塞或就緒的進(jìn)程暫時(shí)放到外存（一般是硬盤），即所謂的掛起。當(dāng)這些進(jìn)程又具備了運(yùn)行條件、且內(nèi)存又稍有空閑時(shí)，中級(jí)調(diào)度把外存上的就緒進(jìn)程調(diào)入內(nèi)存，放入就緒隊(duì)列。這種內(nèi)外存的數(shù)據(jù)交換稱為對(duì)換。外存對(duì)換作業(yè)輸入

spooling輸入程序

spooling高級(jí)調(diào)度就緒阻塞就緒運(yùn)行完成阻塞后備作業(yè)輸出4.三種調(diào)度之間的關(guān)系低級(jí)調(diào)度中級(jí)調(diào)度就緒隊(duì)列阻塞隊(duì)列cpu進(jìn)程調(diào)度等待事件時(shí)間片完進(jìn)程完成用戶事件出現(xiàn)3.1.2調(diào)度隊(duì)列模型

1.僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型

特點(diǎn)：?jiǎn)尉途w、單阻塞隊(duì)列就緒隊(duì)列阻塞隊(duì)列cpu進(jìn)程調(diào)度等待事件時(shí)間片完進(jìn)程完成作業(yè)調(diào)度后備隊(duì)列2.具有高級(jí)和低級(jí)的調(diào)度隊(duì)列模型特點(diǎn)：1)具有進(jìn)程調(diào)度、作業(yè)調(diào)度2)根據(jù)阻塞原因設(shè)置了多個(gè)阻塞隊(duì)列3.同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型作業(yè)調(diào)度就隊(duì)列緒CPU進(jìn)程調(diào)度進(jìn)程完成時(shí)間片完事件出現(xiàn)阻塞列起隊(duì)掛阻隊(duì)列塞等待事件就緒掛起隊(duì)列事件出現(xiàn)掛起中級(jí)調(diào)度后隊(duì)列備交互型作業(yè)批量作業(yè)掛起選擇哪種模型應(yīng)根據(jù)系統(tǒng)的規(guī)模及目標(biāo)制定3.1.3選擇調(diào)度方式和算法的若干準(zhǔn)則

我們可從不同的角度來(lái)判斷處理機(jī)調(diào)度算法的性能。實(shí)際的處理機(jī)調(diào)度算法選擇是一個(gè)綜合的判斷結(jié)果。面向用戶的準(zhǔn)則面向系統(tǒng)的準(zhǔn)則周轉(zhuǎn)時(shí)間短響應(yīng)時(shí)間快

截止時(shí)間的保證

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

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

資源的平衡利用

批處理系統(tǒng)的重要指標(biāo)。作業(yè)從提交到完成（得到結(jié)果）所經(jīng)歷的時(shí)間為周轉(zhuǎn)時(shí)間。包括：在外存后備隊(duì)列中等待，CPU上執(zhí)行，就緒隊(duì)列和阻塞隊(duì)列中等待，結(jié)果輸出等待。平均周轉(zhuǎn)時(shí)間T和平均帶權(quán)周轉(zhuǎn)時(shí)間（帶權(quán)周轉(zhuǎn)時(shí)間W是T(周轉(zhuǎn))/(CPU執(zhí)行)）平均周轉(zhuǎn)時(shí)間:帶權(quán)周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間作業(yè)提交時(shí)間/時(shí)運(yùn)行時(shí)間/h110.002210.101310.250.25例:有如下三道作業(yè)。系統(tǒng)為它們服務(wù)的順序是：1、2、3。求平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。作業(yè)提交時(shí)間運(yùn)行時(shí)間開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間110.002210.101310.250.25解：作業(yè)提交時(shí)間運(yùn)行時(shí)間開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間110.0021012.0022/2210.1011213.002.92.9/1310.250.251313.2533/0.25平均周轉(zhuǎn)時(shí)間：T=(2+2.9+3)/3=2.63h平均帶權(quán)周轉(zhuǎn)時(shí)間：W=(2+2.9+12)/3=5.3h。分時(shí)系統(tǒng)的重要指標(biāo)。用戶輸入一個(gè)請(qǐng)求（如擊鍵）到系統(tǒng)給出首次響應(yīng)（如屏幕顯示）的時(shí)間。包括：從終端的鍵盤輸入的一個(gè)請(qǐng)求信息傳送到處理機(jī)的時(shí)間；處理機(jī)對(duì)請(qǐng)求的處理時(shí)間；處理結(jié)果送到終端顯示器的時(shí)間。

響應(yīng)時(shí)間實(shí)時(shí)系統(tǒng)的重要指標(biāo)。開(kāi)始截止時(shí)間和完成截止時(shí)間某任務(wù)必須開(kāi)始執(zhí)行的最遲時(shí)間，或必須完成的最遲時(shí)間。截止時(shí)間批處理、分時(shí)、實(shí)時(shí)系統(tǒng)都可遵循可以使關(guān)鍵任務(wù)達(dá)到更好的指標(biāo)。

公平性：不因作業(yè)或進(jìn)程本身的特性而使上述指標(biāo)過(guò)分惡化。如長(zhǎng)作業(yè)等待很長(zhǎng)時(shí)間。優(yōu)先權(quán)原則吞吐量批處理系統(tǒng)的重要指標(biāo)。吞吐量指單位時(shí)間內(nèi)所完成的作業(yè)數(shù)，跟作業(yè)本身特性和調(diào)度算法都有關(guān)系。處理機(jī)利用率高大中型主機(jī)多用戶系統(tǒng)性能指標(biāo)，系統(tǒng)價(jià)格昂貴。PC一般不考慮這個(gè)指標(biāo)。各種資源的均衡利用大中型主機(jī)多用戶系統(tǒng)性能指標(biāo)。如CPU繁忙的作業(yè)和I/O繁忙（指次數(shù)多，每次時(shí)間短）的作業(yè)搭配。對(duì)PC及實(shí)時(shí)系統(tǒng)該指標(biāo)并不重要。面向系統(tǒng)準(zhǔn)則易于實(shí)現(xiàn)執(zhí)行開(kāi)銷比

調(diào)度算法本身的調(diào)度性能準(zhǔn)則3.2調(diào)度算法

OS中調(diào)度的實(shí)質(zhì)是一種資源分配，因而調(diào)度算法是指：根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法。有的調(diào)度算法適用于作業(yè)調(diào)度，有的算法適用于進(jìn)程調(diào)度，有的兩者都適應(yīng)。

3.2.1先來(lái)先服務(wù)和短作業(yè)優(yōu)先調(diào)度算法1.FCFS算法(1)算法描述按照作業(yè)提交或進(jìn)程變?yōu)榫途w狀態(tài)的先后次序，分派CPU。當(dāng)前作業(yè)或進(jìn)程占用CPU，直到執(zhí)行完或阻塞，才出讓CPU（非搶占方式）。在作業(yè)或進(jìn)程喚醒后（如I/O完成），并不立即恢復(fù)執(zhí)行，而是進(jìn)入就緒隊(duì)列排隊(duì)。最簡(jiǎn)單的算法。

(2)FCFS的特點(diǎn)比較有利于長(zhǎng)作業(yè)，而不利于短作業(yè)。有利于CPU繁忙的作業(yè)，而不利于I/O繁忙的作業(yè)。例：進(jìn)程

到達(dá)時(shí)間

執(zhí)行時(shí)間

P1 0.0 24

P2 1.0 3

P3 2.0 3Gantt圖:

平均等待時(shí)間:(0+23+25)/3=16平均周轉(zhuǎn)時(shí)間：(24+26+28)/3=26平均帶權(quán)周轉(zhuǎn)時(shí)間：(24/24+26/3+28/3)/3=6.33P1P2P324273002.短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法(ShortestJob/ProcessFirst，SJF/SPF）

(1)算法描述對(duì)預(yù)計(jì)執(zhí)行時(shí)間短的作業(yè)（進(jìn)程）優(yōu)先分派處理機(jī)。通常后來(lái)的短作業(yè)不搶先正在執(zhí)行的作業(yè)。是對(duì)FCFS算法的改進(jìn)，其目標(biāo)是減少平均周轉(zhuǎn)時(shí)間。(2)SJF的特點(diǎn)優(yōu)點(diǎn)：比FCFS改善平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間，縮短作業(yè)的等待時(shí)間；提高系統(tǒng)的吞吐量；缺點(diǎn)：對(duì)長(zhǎng)作業(yè)非常不利，可能長(zhǎng)時(shí)間得不到執(zhí)行；未能依據(jù)作業(yè)的緊迫程度來(lái)劃分執(zhí)行的優(yōu)先級(jí)；難以準(zhǔn)確估計(jì)作業(yè)（進(jìn)程）的執(zhí)行時(shí)間，從而影響調(diào)度性能。

進(jìn)程

到達(dá)時(shí)間

執(zhí)行時(shí)間

P1 0.0 7

P2 2.0 4

P3 4.0 1

P4 5.0 4非搶先式SJF平均等待時(shí)間=(0+6+3+7)/4=4平均周轉(zhuǎn)時(shí)間＝（7+10+4＋11）/4=8平均帶權(quán)周轉(zhuǎn)時(shí)間=P1P3P273160P48123.SJF的變型“最短剩余時(shí)間優(yōu)先”SRT(ShortestRemainingTime)（允許比當(dāng)前進(jìn)程剩余時(shí)間更短的進(jìn)程來(lái)?yè)屨迹白罡唔憫?yīng)比優(yōu)先”HRRN(HighestResponseRatioNext)（響應(yīng)比R=(等待時(shí)間+要求執(zhí)行時(shí)間)/要求執(zhí)行時(shí)間，是FCFS和SJF的折衷）

進(jìn)程

到達(dá)時(shí)間

執(zhí)行時(shí)間

P1 0.0 7

P2 2.0 4

P3 4.0 1

P4 5.0 4最短剩余時(shí)間優(yōu)先（搶先式SJF）平均等待時(shí)間=(9+1+0+2)/4=3平均周轉(zhuǎn)時(shí)間＝（16＋5＋1＋6）/4=7P1P3P242110P457P2P1163.2.2優(yōu)先權(quán)調(diào)度算法(PriorityScheduling)

本算法適用于作業(yè)調(diào)度和進(jìn)程調(diào)度。算法用于作業(yè)調(diào)度時(shí)，系統(tǒng)從后備隊(duì)列中選擇優(yōu)先權(quán)最高的作業(yè)裝入內(nèi)存。用于進(jìn)程調(diào)度時(shí)，系統(tǒng)把處理機(jī)派發(fā)給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程。1.

優(yōu)先權(quán)調(diào)度算法的類型可分成搶占式和非搶占式非搶占式方式：除非自愿或時(shí)間片到，當(dāng)前的進(jìn)程不可以被優(yōu)先級(jí)更高的進(jìn)程搶用CPU。搶占方式：當(dāng)前的進(jìn)程在其時(shí)間片未用完時(shí)就可被優(yōu)先級(jí)更高的進(jìn)程搶用CPU（自己則進(jìn)入就緒狀態(tài)）?？蓳屨汲潭仍礁?，對(duì)實(shí)時(shí)系統(tǒng)的滿足越好。完全不可搶占或用戶態(tài)不可搶占：無(wú)論在用戶態(tài)或核心態(tài)下執(zhí)行代碼，都不可被搶用CPU。WINDOWS95,98。這種OS可能會(huì)出現(xiàn)某個(gè)進(jìn)程長(zhǎng)期獨(dú)占CPU的情況，如死循環(huán)，這樣會(huì)影響其他進(jìn)程執(zhí)行的公平和及時(shí)。內(nèi)核完全不可搶占：在用戶態(tài)下執(zhí)行代碼可以隨時(shí)被搶用CPU，但在核心態(tài)下執(zhí)行代碼，則完全不可以被搶用CPU。例如傳統(tǒng)的UNIX（SVR3和4.3BSDUNIX及其以前的版本）、WINDOWSNT。這些OS通常在系統(tǒng)調(diào)用或中斷處理時(shí)屏蔽大部分中斷，系統(tǒng)調(diào)用返回或中斷返回時(shí)再開(kāi)放大部分中斷。

內(nèi)核部分可搶占：在用戶態(tài)下執(zhí)行代碼可以隨時(shí)被搶用CPU，但在核心態(tài)時(shí)則大部分時(shí)間都不可以被搶用CPU，而只在某些時(shí)刻（稱為可搶占點(diǎn)，PreemptionPoint），可以被搶用CPU。例如

UNIXSVR4。

完全可搶占或內(nèi)核完全可搶占：無(wú)論處于用戶態(tài)還是核心態(tài)，都可以隨時(shí)被搶用CPU。例如：Solaris、Windows2000/XP。實(shí)際上，Solaris和Windows2000/XP并不是100%完全可搶先，它只是將內(nèi)核中不可搶先的代碼段盡量減少而已。任何OS都不可能是100%的完全可搶先的。

例題：在單CPU和兩臺(tái)I/O（I1,I2)設(shè)備的多道程序環(huán)境下，同時(shí)投入三個(gè)作業(yè)運(yùn)行，它們的執(zhí)行軌跡如下：Job1:I2(30ms)CPU(10ms)I1(30ms)CPU(10ms)Job2:I1(20ms)CPU(20ms)I2(40ms)Job3:CPU(30ms)I1(20ms)如果CPU、I1、I2都能并行工作，優(yōu)先級(jí)從高到低為Job1、Job2、Job3，采用可搶占式優(yōu)先級(jí)調(diào)度方式。求(1)每個(gè)作業(yè)的周轉(zhuǎn)時(shí)間(2)CPU的利用率(3)I/O設(shè)備利用率Job1的周轉(zhuǎn)時(shí)間80ms，Job2和Job3周轉(zhuǎn)時(shí)間各為90msCPU利用率＝70ms/90ms=77.78%I1利用率＝I2利用率=70ms/90ms＝77.78%0ms102030405060708090時(shí)間CPUJob3Job2Job1Job2Job3Job1I1Job2Job1Job3I2Job1Job22.優(yōu)先權(quán)的類型1）靜態(tài)優(yōu)先級(jí)創(chuàng)建進(jìn)程時(shí)就確定，直到進(jìn)程終止前都不改變。通常是一個(gè)整數(shù)。依據(jù)：進(jìn)程類型（系統(tǒng)進(jìn)程優(yōu)先級(jí)較高）對(duì)資源的需求（對(duì)CPU和內(nèi)存需求較少的進(jìn)程，優(yōu)先級(jí)較高）用戶要求（緊迫程度和付費(fèi)多少）

特點(diǎn)：簡(jiǎn)單，系統(tǒng)開(kāi)銷小不精確，僅在要求不高的系統(tǒng)中使用2)動(dòng)態(tài)優(yōu)先級(jí)在創(chuàng)建進(jìn)程時(shí)賦予的優(yōu)先級(jí)，在進(jìn)程運(yùn)行過(guò)程中可以自動(dòng)改變，以便獲得更好的調(diào)度性能。如：在就緒隊(duì)列中，等待時(shí)間延長(zhǎng)則優(yōu)先級(jí)提高，從而使優(yōu)先級(jí)較低的進(jìn)程在等待足夠的時(shí)間后，其優(yōu)先級(jí)提高到可被調(diào)度執(zhí)行；進(jìn)程每執(zhí)行一個(gè)時(shí)間片，就降低其優(yōu)先級(jí)，從而一個(gè)進(jìn)程持續(xù)執(zhí)行時(shí)，其優(yōu)先級(jí)降低到出讓CPU。

響應(yīng)比R=(等待時(shí)間+要求執(zhí)行時(shí)間)/要求執(zhí)行時(shí)間＝1＋等待時(shí)間/要求執(zhí)行時(shí)間是FCFS和SJF的折衷：作業(yè)等待時(shí)間相同，服務(wù)時(shí)間越短，優(yōu)先權(quán)越高--SJF；要求服務(wù)時(shí)間相同，等待時(shí)間越長(zhǎng)，優(yōu)先權(quán)越高--FCFS；長(zhǎng)作業(yè)隨著等待時(shí)間的增加，優(yōu)先權(quán)增加。

缺點(diǎn)：響應(yīng)比的計(jì)算增加系統(tǒng)開(kāi)銷3.高響應(yīng)比優(yōu)先調(diào)度算法(HighestResponseRatioNext，HRRN，HRN)例：如表所示四個(gè)作業(yè)進(jìn)入系統(tǒng)，分別計(jì)算HRRN算法下的平均周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間。作業(yè)提交時(shí)間（時(shí)）運(yùn)行時(shí)間（分）12348:008:509:009:50120501020作業(yè)開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間12348:0010:1010:0011:0010:0011:0010:1011:201201307090Job1完成后的響應(yīng)比：Job2:70/50=1.4Job3:60/10=6Job4:10/20=0.5所以調(diào)度Job3執(zhí)行。Job3完成后的響應(yīng)比：Job2:80/50=1.8Job4:20/20=1所以調(diào)度Job2執(zhí)行平均周轉(zhuǎn)時(shí)間＝102.5帶權(quán)周轉(zhuǎn)時(shí)間W=

T(周轉(zhuǎn))/(CPU執(zhí)行)平均帶權(quán)周轉(zhuǎn)時(shí)間＝(120/120+130/50+70/10+90/20)/4=3.775例：滿足短作業(yè)優(yōu)先且不會(huì)發(fā)生饑餓現(xiàn)象的調(diào)度算法是：AFCFSB高響應(yīng)比優(yōu)先C時(shí)間片輪轉(zhuǎn)D非搶先式SJF3.2.3基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法1.時(shí)間片輪轉(zhuǎn)法（RoundRobin,RR)本算法主要用于微觀調(diào)度（進(jìn)程調(diào)度）設(shè)計(jì)目標(biāo)是提高資源利用率基本思路是通過(guò)時(shí)間片輪轉(zhuǎn)，提高進(jìn)程并發(fā)性和響應(yīng)時(shí)間特性，從而提高資源利用率

時(shí)間片輪轉(zhuǎn)法(1)算法描述將系統(tǒng)中所有的就緒進(jìn)程按照FCFS原則，排成一個(gè)隊(duì)列。每次調(diào)度時(shí)將CPU分派給隊(duì)首進(jìn)程，讓其執(zhí)行一個(gè)時(shí)間片。在一個(gè)時(shí)間片結(jié)束時(shí)，發(fā)生時(shí)鐘中斷。調(diào)度程序據(jù)此暫停當(dāng)前進(jìn)程的執(zhí)行，將其送到就緒隊(duì)列的末尾，并通過(guò)上下文切換執(zhí)行當(dāng)前的隊(duì)首進(jìn)程。時(shí)間片的長(zhǎng)度從幾個(gè)ms到幾百ms。進(jìn)程可以未使用完一個(gè)時(shí)間片，就出讓CPU（如阻塞）。時(shí)間片輪轉(zhuǎn)法(2)時(shí)間片長(zhǎng)度的確定時(shí)間片長(zhǎng)度變化的影響過(guò)長(zhǎng)－>退化為FCFS算法過(guò)短－>用戶的一次請(qǐng)求需要多個(gè)時(shí)間片才能處理完，上下文切換次數(shù)增加，響應(yīng)時(shí)間長(zhǎng)。就緒進(jìn)程的數(shù)目：數(shù)目越多，時(shí)間片越小系統(tǒng)的處理能力：應(yīng)當(dāng)使用戶輸入通常在一個(gè)時(shí)間片內(nèi)能處理完，否則使響應(yīng)時(shí)間，平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間延長(zhǎng)。例：降低進(jìn)程優(yōu)先級(jí)的合理時(shí)機(jī)是A進(jìn)程的時(shí)間片用完B進(jìn)程剛完成IO，進(jìn)入就緒隊(duì)列C進(jìn)程長(zhǎng)期處于就緒隊(duì)列中D進(jìn)程從就緒態(tài)轉(zhuǎn)為運(yùn)行態(tài)輪轉(zhuǎn)調(diào)度算法（時(shí)間片＝20）

進(jìn)程執(zhí)行時(shí)間 P1 53

P2 17

P3 68

P4 24TheGanttchartis:

P1P2P3P4P1P3P4P1P3P302037577797117121134154162進(jìn)程

到達(dá)時(shí)間

執(zhí)行時(shí)間

P1 03

P2 16

P3 44

P4 62時(shí)間片=2

P1P2P3P4P1P2P3P2

2

4

6

8

9

11

1315作業(yè)進(jìn)程到達(dá)時(shí)間執(zhí)行時(shí)間

P1010P218P322P434P548

畫Gantt圖說(shuō)明使用FCFS、非搶先式SJF、搶先式SJF、RR（時(shí)間片＝3）調(diào)度算法進(jìn)程調(diào)度情況。并分別求四種算法的平均周轉(zhuǎn)時(shí)間，平均等待時(shí)間。例：假設(shè)某操作系統(tǒng)采用時(shí)間片輪轉(zhuǎn)調(diào)度策略，時(shí)間片大小為100ms，就緒進(jìn)程隊(duì)列的平均長(zhǎng)度為5，如果在系統(tǒng)中運(yùn)行一個(gè)需要在CPU上執(zhí)行0.8s時(shí)間的程序，則該程序的平均周轉(zhuǎn)時(shí)間是

,平均等待時(shí)間是

。（不考慮IO情況及系統(tǒng)調(diào)度開(kāi)銷）答：排在隊(duì)列尾的周轉(zhuǎn)時(shí)間4s，排在隊(duì)列第四的周轉(zhuǎn)時(shí)間3.9s……排在頭的周轉(zhuǎn)時(shí)間3.6s，平均：3.8s同理：平均等待3.0s2.多級(jí)反饋隊(duì)列調(diào)度算法(RoundRobinwithMultipleFeedback)

多級(jí)反饋隊(duì)列算法是時(shí)間片輪轉(zhuǎn)算法和優(yōu)先級(jí)算法的綜合和發(fā)展。1)算法描述設(shè)置多個(gè)就緒隊(duì)列，分別賦予不同的優(yōu)先級(jí)，隊(duì)列1的優(yōu)先級(jí)最高。每個(gè)隊(duì)列執(zhí)行時(shí)間片的長(zhǎng)度也不同，規(guī)定優(yōu)先級(jí)越低則時(shí)間片越長(zhǎng)。假設(shè)有三個(gè)就緒隊(duì)列：Q1－－時(shí)間片為8Q2－－時(shí)間片為16Q3－－FCFS新進(jìn)程進(jìn)入內(nèi)存后，先投入隊(duì)列1的末尾，若按隊(duì)列1一個(gè)時(shí)間片未能執(zhí)行完，則降低投入到隊(duì)列2的末尾，若仍未完成，降低到最后的隊(duì)列，按FCFS算法調(diào)度直到完成。僅當(dāng)較高優(yōu)先級(jí)的隊(duì)列為空，才調(diào)度較低優(yōu)先級(jí)的隊(duì)列中的進(jìn)程執(zhí)行。如果進(jìn)程執(zhí)行時(shí)有新進(jìn)程進(jìn)入較高優(yōu)先級(jí)的隊(duì)列，則搶先執(zhí)行新進(jìn)程，并把被搶先的進(jìn)程投入原隊(duì)列的末尾。多級(jí)反饋隊(duì)列調(diào)度算法2）算法性能終端型進(jìn)程：讓其進(jìn)入最高優(yōu)先級(jí)隊(duì)列，以及時(shí)響應(yīng)I/O交互。通常執(zhí)行一個(gè)小時(shí)間片，可處理完一次I/O請(qǐng)求的數(shù)據(jù)，然后轉(zhuǎn)入到阻塞隊(duì)列。計(jì)算型進(jìn)程（長(zhǎng)批處理作業(yè)）：每次都執(zhí)行完時(shí)間片，進(jìn)入更低級(jí)隊(duì)列。最終采用最大時(shí)間片來(lái)執(zhí)行，減少調(diào)度次數(shù)。短批處理作業(yè)：

先放入第1級(jí)，一般經(jīng)過(guò)1，2級(jí)即可完成。多級(jí)反饋隊(duì)列調(diào)度算法3）優(yōu)點(diǎn)：為提高系統(tǒng)吞吐量和縮短平均周轉(zhuǎn)時(shí)間而照顧短進(jìn)程為獲得較好的I/O設(shè)備利用率和縮短響應(yīng)時(shí)間而照顧I/O型進(jìn)程不必估計(jì)進(jìn)程的執(zhí)行時(shí)間，動(dòng)態(tài)調(diào)節(jié)多級(jí)反饋隊(duì)列調(diào)度算法3.4實(shí)時(shí)調(diào)度3.4.1實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件1.提供必要的信息系統(tǒng)應(yīng)向調(diào)度程序提供有關(guān)任務(wù)的下述信息：（1）就緒時(shí)間：該任務(wù)成為就緒狀態(tài)的起始時(shí)間。（2）開(kāi)始截止時(shí)間和完成截止時(shí)間（3）處理時(shí)間（4）資源要求（5）優(yōu)先級(jí)2.系統(tǒng)處理能力強(qiáng)設(shè)有m個(gè)周期性硬實(shí)時(shí)任務(wù)，處理時(shí)間為Ci，周期時(shí)間為Pi，在單處理機(jī)環(huán)境下滿足：若采用多處理機(jī)系統(tǒng)，設(shè)系統(tǒng)中處理機(jī)數(shù)目為N，則應(yīng)滿足3.采用搶占式調(diào)度機(jī)制4.具有快速切換機(jī)制（1）對(duì)外部中斷的快速響應(yīng)能力具有快速硬件中斷機(jī)構(gòu)，且禁止中斷的時(shí)間間隔盡量短。（2）快速任務(wù)分派能力為提高任務(wù)切換的速度，系統(tǒng)中每個(gè)運(yùn)行單位要適當(dāng)?shù)匦　?.4.2實(shí)時(shí)調(diào)度算法的分類1.非搶占式調(diào)度算法1）非搶占式輪轉(zhuǎn)調(diào)度算法該算法用于工業(yè)生成的群控系統(tǒng)中，同于前面的RR算法。2）非搶占式優(yōu)先調(diào)度算法在實(shí)時(shí)系統(tǒng)中給要求嚴(yán)格的任務(wù)賦予高優(yōu)先級(jí)，置于隊(duì)首，當(dāng)前任務(wù)自我終止或運(yùn)行完才能被調(diào)度執(zhí)行。2.搶占式調(diào)度算法1）基于時(shí)鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法在某實(shí)時(shí)任務(wù)到達(dá)后，若其優(yōu)先級(jí)高于占有處理機(jī)的進(jìn)程優(yōu)先級(jí)，并不搶占，等到時(shí)鐘中斷到達(dá)時(shí)再搶占。調(diào)度延遲可降為幾十至幾毫秒。2）立即搶占操作系統(tǒng)具有快速響應(yīng)外部中斷的能力。一旦出現(xiàn)外部中斷，只要當(dāng)前進(jìn)程未處于臨界區(qū)，立即搶占CPU。3.4.3常用的幾種實(shí)時(shí)調(diào)度算法1.最早截止時(shí)間優(yōu)先EDF（EarliestDeadlineFirst）根據(jù)任務(wù)的開(kāi)始截止時(shí)間確定任務(wù)的優(yōu)先級(jí)。具有最早截止時(shí)間的任務(wù)排在隊(duì)列的最前面。即可用于搶占式調(diào)度，又可用于非搶占式調(diào)度。1）非搶占式調(diào)度方式用于非周期實(shí)時(shí)任務(wù)1342開(kāi)始截止時(shí)間任務(wù)執(zhí)行任務(wù)到達(dá)123412342）

搶占式調(diào)度方式用于周期實(shí)時(shí)任務(wù)A1A2B1B1A3B2A4B2A5B2固定優(yōu)先級(jí)調(diào)度A優(yōu)先級(jí)高102030405060708090100A1最后期限B1A1A2B2A3A2最后期限A4A3最后期限A5A4最后期限A5最后期限B1最后期限B2最后期限0B1A2A3B2A5固定優(yōu)先級(jí)調(diào)度B優(yōu)先級(jí)高B1錯(cuò)過(guò)A1錯(cuò)過(guò)A4錯(cuò)過(guò)102030405060708090100A1最后期限B1A1A2B2A3A2最后期限A4A3最后期限A5A4最后期限A5最后期限B1最后期限B2最后期限0A1B1A2B1A3B2A4B2A5搶占式EDF2.最低松弛度優(yōu)先LLF（LeastLaxityFirst）算法任務(wù)的緊急程度愈高，該任務(wù)的優(yōu)先級(jí)愈高。如，某任務(wù)在200ms時(shí)必須完成，他本身執(zhí)行的時(shí)間是100ms，則其松弛度為100ms。LLF算法按松弛度排就緒隊(duì)列，松弛度最低的排在隊(duì)列最前面，優(yōu)先被調(diào)度執(zhí)行。LLF主要用于可搶占調(diào)度方式中。A1A2A3A4A5A6A7A8020406080100120140160B1B2B3A、B任務(wù)必須完成的時(shí)間t1A1(10)A2(10)A3(10)A4(10)B1(20)B1(5)B2(15)B2(10)01020304050607080LLF調(diào)度3.5產(chǎn)生死鎖的原因和必要條件

死鎖：指多個(gè)進(jìn)程因競(jìng)爭(zhēng)共享資源而造成的一種僵局，若無(wú)外力作用，這些進(jìn)程永遠(yuǎn)不能向前推進(jìn)。

3.5.1產(chǎn)生死鎖的原因

q

競(jìng)爭(zhēng)資源q

順序不當(dāng)一.

競(jìng)爭(zhēng)資源引起死鎖1.

可剝奪和不可剝奪資源可剝奪的如：處理機(jī)、內(nèi)存（優(yōu)先權(quán)高的剝奪優(yōu)先權(quán)低的）不可剝奪資源如：磁帶、打印機(jī)2.

競(jìng)爭(zhēng)不可剝奪資源可能會(huì)引起死鎖死鎖發(fā)生：雙方都擁有部分資源，同時(shí)在請(qǐng)求對(duì)方已占有的資源。

3.競(jìng)爭(zhēng)臨時(shí)性資源可能會(huì)引起死鎖可以動(dòng)態(tài)生成和消耗，一般不限制數(shù)量。如硬件中斷、信號(hào)、消息、緩沖區(qū)內(nèi)的數(shù)據(jù)。

二、進(jìn)程推進(jìn)順序不當(dāng)引起死鎖多個(gè)進(jìn)程并發(fā)執(zhí)行，相互的推進(jìn)順序不確定，可能會(huì)導(dǎo)致兩種結(jié)果：不出現(xiàn)死鎖和出現(xiàn)死鎖。

3.5.2產(chǎn)生死鎖的必要條件

只有4個(gè)條件都滿足時(shí)，才會(huì)出現(xiàn)死鎖。(1)

互斥：任一時(shí)刻只允許一個(gè)進(jìn)程使用資源(2)

請(qǐng)求和保持：進(jìn)程保持了至少一個(gè)資源，但又提出了新的資源請(qǐng)求，該資源又被其他進(jìn)程占用。(3)

不剝奪：進(jìn)程已經(jīng)占用的資源，未使用完，不能被剝奪。(4)

環(huán)路等待：存在進(jìn)程－資源環(huán)形鏈，即有進(jìn)程集合{P0,P1,P2,….Pn},P0等待P1占用的資源，P1等待P2占用的資源…..Pn等待P0占用的資源。

3.5.3處理死鎖的方法

1.預(yù)防死鎖—加限制條件，破壞產(chǎn)生死鎖的四個(gè)必要條件中的一個(gè)或幾個(gè)。2.避免死鎖—在資源的動(dòng)態(tài)分配過(guò)程中，防止系統(tǒng)進(jìn)入不安全狀態(tài)。3.檢測(cè)死鎖－允許系統(tǒng)進(jìn)入死鎖，但系統(tǒng)及時(shí)檢測(cè)，并采取措施。4.解除死鎖－當(dāng)檢測(cè)到系統(tǒng)進(jìn)入了死鎖，采取措施解除。3.6預(yù)防和避免死鎖的方法

3.6.1死鎖的預(yù)防

預(yù)防：是采用某種策略，限制并發(fā)進(jìn)程對(duì)資源的請(qǐng)求，使系統(tǒng)在任何時(shí)刻都不滿足死鎖的四個(gè)必要條件。一.摒棄“請(qǐng)求保持”條件預(yù)先靜態(tài)分配法：（針對(duì)死鎖的第2個(gè)條件）預(yù)先分配進(jìn)程運(yùn)行所需的全部資源，保證不等待資源；優(yōu)點(diǎn)：簡(jiǎn)單、易于實(shí)現(xiàn)、安全缺點(diǎn)：降低了對(duì)資源的利用率，降低進(jìn)程的并發(fā)程度；有可能無(wú)法預(yù)先知道所需資源；二、摒棄“不可剝奪”條件當(dāng)一個(gè)已經(jīng)保持了某些資源的進(jìn)程，再提出新的資源請(qǐng)求而不能立即得到滿足時(shí)，必須釋放它已持有的資源。缺點(diǎn)：需付出代價(jià)。反復(fù)申請(qǐng)釋放資源，降低系統(tǒng)吞吐率。三、摒棄“環(huán)路等待”條件有序資源使用法：把資源分類按順序排列，所有進(jìn)程對(duì)資源的請(qǐng)求必須按照資源序號(hào)遞增次序提出。保證不形成環(huán)路；缺點(diǎn)：資源序號(hào)固定，限制新設(shè)備的增加；降低資源利用率；限制了用戶簡(jiǎn)單、自主地編程；

3.6.2系統(tǒng)的安全狀態(tài)

一.

安全狀態(tài)是指系統(tǒng)能按某種進(jìn)程順序（P1,P2,….Pn），為進(jìn)程Pi分配其所需資源，直至進(jìn)程的最大需求，使每個(gè)進(jìn)程都可順利完成。則（P1,P2,….Pn）稱為安全序列。若系統(tǒng)無(wú)法找到安全序列，則稱系統(tǒng)處于不安全狀態(tài)。二、安全狀態(tài)之例設(shè)系統(tǒng)共有12臺(tái)磁帶機(jī)，T0時(shí)刻系統(tǒng)狀態(tài)如下：進(jìn)程最大需求已分配可用P11053P242

P392

安全序列：〈P2,P1,P3>，當(dāng)前系統(tǒng)為安全狀態(tài)

三、由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換若不按照安全序列分配資源，系統(tǒng)可能會(huì)由安全狀態(tài)進(jìn)入不安全狀態(tài)。例：T0時(shí)刻后，P3請(qǐng)求1臺(tái)磁帶機(jī)，系統(tǒng)分配給它，則進(jìn)入不安全狀態(tài)。安全、不安全、死鎖狀態(tài)的關(guān)系3.6.3避免死鎖--銀行家算法銀行家算法（Dijkstra,1965）問(wèn)題一個(gè)銀行家把他的資金（capital）貸給若干顧客。只要不出現(xiàn)一個(gè)顧客借走所有資金后還不夠（故無(wú)法還貸），銀行家的資金應(yīng)是安全的。銀行家需一個(gè)算法保證借出去的資金在有限時(shí)間內(nèi)可收回。

1.銀行家算法中的數(shù)據(jù)結(jié)構(gòu)設(shè)系統(tǒng)中共有n個(gè)進(jìn)程，m類資源(1)可利用資源向量Available[m]。若Available[i]＝k，表示系統(tǒng)中Ri類資源有k個(gè)。(2)最大需求矩陣Max[n,m]若Max[i,j]=k，表示進(jìn)程i需要Rj類資源k個(gè)。(3)分配矩陣Allocation[n,m]若Allocation[i,j]=k，表示進(jìn)程Pi

現(xiàn)在擁有Rj類型的資源K個(gè)。

(4)需求矩陣Need[n,m]若Need[i,j]=k，表示進(jìn)程

Pi最多還需要Rj類型的資源k個(gè)，它才能完成任務(wù)Need[i,j]=Max[i,j]–

Allocation[i,j]2.安全算法(1)Work和Finish分別是長(zhǎng)度為m和n

的向量，

分別初始化為：Work=AvailableFinish[i]=false(i=1,3,…,n)(2)查找這樣的i使其滿足：(a)Finish[i]=false(b)Needi

Work如果沒(méi)有這樣的i存在就轉(zhuǎn)去執(zhí)行第4步.(3)Work=Work+Allocationi

Finish[i]=true

轉(zhuǎn)去執(zhí)行第2步.(4)如果對(duì)所有的i，F(xiàn)inish[i]==true，那么系統(tǒng)是安全的。否則，系統(tǒng)處于不安全狀態(tài)。

3.資源請(qǐng)求算法Requesti為進(jìn)程Pi

的請(qǐng)求向量。如果

Requesti

[j]=k，表示進(jìn)程Pi

需要Rj類型資源k個(gè).。1.

如果

Requesti

Needi，轉(zhuǎn)去執(zhí)行第2步。否則產(chǎn)生錯(cuò)誤，因?yàn)檫M(jìn)程對(duì)資源的請(qǐng)求已經(jīng)超過(guò)它事先聲明的最大數(shù)量。2. 如果

Requesti

Available，轉(zhuǎn)去執(zhí)行第3步。

否則進(jìn)程Pi必須等待，因?yàn)楝F(xiàn)有資源不夠分配。3. 假設(shè)將進(jìn)程Pi

請(qǐng)求的資源分配給它，并按如下方式修改狀態(tài)Available=Available–RequestiAllocationi

=Allocationi+RequestiNeedi=Needi–Requesti則系統(tǒng)進(jìn)入新?tīng)顟B(tài)，用安全算法驗(yàn)證新?tīng)顟B(tài)是安全的。如果安全將資源分配給進(jìn)程Pi，系統(tǒng)進(jìn)入新?tīng)顟B(tài)。如果不安全進(jìn)程Pi必須等待，系統(tǒng)保持原狀態(tài)。5個(gè)進(jìn)程：

P0~P4；3類資源：A(10個(gè)實(shí)例),B(5個(gè)實(shí)例)

,C(7個(gè)實(shí)例).假設(shè)在T0時(shí)刻,系統(tǒng)狀態(tài)如下：

Allocation

Max

Available ABC ABCABC P0010 753332P1200 322P2302 902 P3211222P4002 433 需要導(dǎo)出Need矩陣。Need矩陣定義為：Need=Max–Allocation。則得到：

Need ABC P0 743 P1 122 P2 600 P3 011 P4 431用安全算法可證明系統(tǒng)目前是安全的，因?yàn)榇嬖诎踩蛄校?lt;P1,P3,P4,P2,P0>.假設(shè)這時(shí)進(jìn)程P1發(fā)出資源請(qǐng)求：Request1=(1,0,2)首先檢查：Request1Need1(1,0,2)(1,2,2)再檢查Request1Available(1,0,2)(3,3,2)即滿足申請(qǐng)資源的條件。假設(shè)將資源分配給它，則得到如下的新?tīng)顟B(tài)：

Allocation

Need

Available ABC ABC ABC P0 010743 230 P1 302 020 P2 302 600 P3 211 011 P4 002 431執(zhí)行安全算法可以找到安全序列：

<P1,P3,P4,P0,P2>接下來(lái)進(jìn)程P4請(qǐng)求資源(3,3,0)能夠滿足它嗎?若是進(jìn)程P0請(qǐng)求資源(0,2,0)能滿足它嗎?3.銀行家算法的特點(diǎn)：允許互斥、部分分配和不可搶占，可提高資源利用率；要求事先說(shuō)明最大資源要求，在現(xiàn)實(shí)中很困難；作業(yè)P11522(第三版）3.7死鎖的檢測(cè)和解除

系統(tǒng)為進(jìn)程分配資源時(shí)，若未采取避免和預(yù)防死鎖的措施，系統(tǒng)必須提供檢測(cè)和解除死鎖的手段。即：保存資源的請(qǐng)求和分配信息利用某種算法對(duì)這些信息加以檢查，以判斷是否存在死鎖。1.資源分配圖(resourceallocationgraph)有向圖G的頂點(diǎn)為資源或進(jìn)程從資源R到進(jìn)程P的邊表示資源R已分配1個(gè)給進(jìn)程P從進(jìn)程P到資源R的邊表示P正因請(qǐng)求R而處于等待狀態(tài)。資源分配圖2.死鎖定理資源分配圖的化簡(jiǎn)方法：刪除即不處于等待狀態(tài)又不獨(dú)立的進(jìn)程的所有?。òㄕ?qǐng)求邊和分配邊），該點(diǎn)變?yōu)楣铝Ⅻc(diǎn)。重復(fù)上述過(guò)程，若最后所有進(jìn)程結(jié)點(diǎn)是孤立點(diǎn)，則稱該資源圖是完全可簡(jiǎn)化的，否則是不可完全簡(jiǎn)化的。死鎖定理：S為死鎖狀態(tài)的充分條件是：當(dāng)且僅當(dāng)S狀態(tài)的資源分配圖不可完全簡(jiǎn)化。其中的有邊進(jìn)程為死鎖進(jìn)程。p1p2R1R23.死鎖檢測(cè)算法1）檢測(cè)算法中的數(shù)據(jù)結(jié)構(gòu)設(shè)系統(tǒng)中有n個(gè)進(jìn)程，m類資源Available:長(zhǎng)度為m的向量，表示各種類型資源的可用實(shí)例數(shù)Allocation:為nxm矩陣，表示目前已分配給各個(gè)進(jìn)程的各種資源的數(shù)量Request:為nxm矩陣，表示目前各個(gè)進(jìn)程請(qǐng)求資源的情況。若Request[i,j]=k,表示進(jìn)程Pi

正在請(qǐng)求k個(gè)類型為Rj的資源。2）算法描述(1)設(shè)Work和Finish分別是長(zhǎng)度為m和n

的向量，各自初始化為：

(a)Work=Available(b)對(duì)于i=1,2,…,n，如果

Allocationi

0,那么

Finish[i]=false；否則Finish[i]=true.(2)查找這樣的下標(biāo)i，使其滿足：(a)Finish[i]==false(b)Requesti

Work如果不存在這樣的i，轉(zhuǎn)去執(zhí)行第4步(3)Work=Work+Allocationi

Finish[i]=true

轉(zhuǎn)去執(zhí)行第2步。(4)如果對(duì)某個(gè)i

（1in

），若Finish[i]==false，那么系統(tǒng)死鎖。而且，如果

Finish[i]==false，那么進(jìn)程Pi

正處于死鎖狀態(tài)。該算法需要O(m

xn2)