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

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

spooling輸入程序

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

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

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

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

截止時間的保證

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

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

資源的平衡利用

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

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

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

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

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

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

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

到達時間

執(zhí)行時間

P1 0.0 24

P2 1.0 3

P3 2.0 3Gantt圖:

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

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

進程

到達時間

執(zhí)行時間

P1 0.0 7

P2 2.0 4

P3 4.0 1

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

進程

到達時間

執(zhí)行時間

P1 0.0 7

P2 2.0 4

P3 4.0 1

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

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

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

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

UNIXSVR4。

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

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

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

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

缺點：響應(yīng)比的計算增加系統(tǒng)開銷3.高響應(yīng)比優(yōu)先調(diào)度算法(HighestResponseRatioNext，HRRN，HRN)例：如表所示四個作業(yè)進入系統(tǒng)，分別計算HRRN算法下的平均周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間。作業(yè)提交時間（時）運行時間（分）12348:008:509:009:50120501020作業(yè)開始時間完成時間周轉(zhuǎn)時間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)時間＝102.5帶權(quán)周轉(zhuǎn)時間W=

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

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

進程執(zhí)行時間 P1 53

P2 17

P3 68

P4 24TheGanttchartis:

P1P2P3P4P1P3P4P1P3P302037577797117121134154162進程

到達時間

執(zhí)行時間

P1 03

P2 16

P3 44

P4 62時間片=2

P1P2P3P4P1P2P3P2

2

4

6

8

9

11

1315作業(yè)進程到達時間執(zhí)行時間

P1010P218P322P434P548

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

,平均等待時間是

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

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

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

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

死鎖：指多個進程因競爭共享資源而造成的一種僵局，若無外力作用，這些進程永遠不能向前推進。

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

q

競爭資源q

順序不當一.

競爭資源引起死鎖1.

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

競爭不可剝奪資源可能會引起死鎖死鎖發(fā)生：雙方都擁有部分資源，同時在請求對方已占有的資源。

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

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

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

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

互斥：任一時刻只允許一個進程使用資源(2)

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

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

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

3.5.3處理死鎖的方法

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

3.6.1死鎖的預(yù)防

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

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

一.

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

P392

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

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

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

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

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

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

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

的向量，

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

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

Finish[i]=true

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

3.資源請求算法Requesti為進程Pi

的請求向量。如果

Requesti

[j]=k，表示進程Pi

需要Rj類型資源k個.。1.

如果

Requesti

Needi，轉(zhuǎn)去執(zhí)行第2步。否則產(chǎn)生錯誤，因為進程對資源的請求已經(jīng)超過它事先聲明的最大數(shù)量。2. 如果

Requesti

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

否則進程Pi必須等待，因為現(xiàn)有資源不夠分配。3. 假設(shè)將進程Pi

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

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

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

,C(7個實例).假設(shè)在T0時刻,系統(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)目前是安全的，因為存在安全序列：<P1,P3,P4,P2,P0>.假設(shè)這時進程P1發(fā)出資源請求：Request1=(1,0,2)首先檢查：Request1Need1(1,0,2)(1,2,2)再檢查Request1Available(1,0,2)(3,3,2)即滿足申請資源的條件。假設(shè)將資源分配給它，則得到如下的新狀態(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>接下來進程P4請求資源(3,3,0)能夠滿足它嗎?若是進程P0請求資源(0,2,0)能滿足它嗎?3.銀行家算法的特點：允許互斥、部分分配和不可搶占，可提高資源利用率；要求事先說明最大資源要求，在現(xiàn)實中很困難；作業(yè)P11522(第三版）3.7死鎖的檢測和解除

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

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

的向量，各自初始化為：

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

Allocationi

0,那么

Finish[i]=false；否則Finish[i]=true.(2)查找這樣的下標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)如果對某個i

（1in

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

Finish[i]==false，那么進程Pi

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

xn2)