第三講 進程調(diào)度

操作系統(tǒng)原理2013-91總目錄第1章操作系統(tǒng)引論第2章進程管理第3章處理機調(diào)度與死鎖第4章存儲器管理第5章設備管理第6章文件管理第7章操作系統(tǒng)接口2第3章處理機調(diào)度與死鎖3.1處理機調(diào)度的基本概念3.2調(diào)度算法第二次上機實驗進程調(diào)度3.3實時調(diào)度3.4多處理機系統(tǒng)中的調(diào)度

(第三版刪)3.5產(chǎn)生死鎖的原因和必要條件3.6預防和避免死鎖的方法3.7

死鎖的檢測和解除第三次上機實驗演示銀行家算法實時調(diào)度和多處理機調(diào)度，考研不要求。33.1處理機調(diào)度的基本概念3.1.1

高級、中級和低級調(diào)度

1．高級調(diào)度——又稱作業(yè)調(diào)度或長調(diào)度

用于決定把外存上后備隊列中哪些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進程、分配必要的資源，然后將新創(chuàng)建的進程插入到就緒隊列中，準備運行。定義每次作業(yè)調(diào)度，都需做以下兩個決定：●接納多少個作業(yè)——取決于多道程序度▲內(nèi)存中同時運行的作業(yè)數(shù)目太多，會影響系統(tǒng)的服務質(zhì)量。如，周轉(zhuǎn)時間長?！鴥?nèi)存中同時運行的作業(yè)數(shù)目太少，會導致系統(tǒng)資源利用率和系統(tǒng)吞吐量低。

●接納哪些作業(yè)——取決于調(diào)度算法43.1處理機調(diào)度的基本概念2．低級調(diào)度

又稱進程調(diào)度或短調(diào)度。是最基本的調(diào)度，三種類型OS中，都必須配置此調(diào)度。

定義用來決定就緒隊列中的哪個進程應獲得處理機，然后再由分派程序執(zhí)行把處理機分配給該進程的具體操作。

進程調(diào)度可采用下述兩種調(diào)度方式：

（1）非搶占方式（2）搶占方式

一旦把處理機分配給某進程后，便讓它一直執(zhí)行，直到該進程完成或發(fā)生某事件而被阻塞時，才把處理機分配給其它進程，決不允許某進程搶占已經(jīng)分配出去的處理機。優(yōu)點：實現(xiàn)簡單，系統(tǒng)開銷小。缺點：難于滿足緊急任務的要求。允許調(diào)度程序根據(jù)某種原則，暫停某個正在執(zhí)行的進程，將已分配給該進程的處理機重新分配給另一進程。搶占原則有：

優(yōu)先權原則；

短作業(yè)優(yōu)先原則；

時間片原則。

非搶占調(diào)度方式中，可能引起進程調(diào)度的因素：（1）正在執(zhí)行的進程執(zhí)行完畢，或因某事件不能繼續(xù)執(zhí)行（2）執(zhí)行中的進程提出I/O請求（3）執(zhí)行了wait\block\signal等原語53.1處理機調(diào)度的基本概念3.中級調(diào)度

掛起和激活，存儲器管理中的對換功能。

主要目的：

為了提高內(nèi)存的利用率和系統(tǒng)的吞吐量。

主要介紹進程調(diào)度和作業(yè)調(diào)度。三種調(diào)度相比較：進程調(diào)度的運行頻率最高

作業(yè)調(diào)度頻率最低

中級調(diào)度界于之間

63.1.2調(diào)度隊列模型三種類型的調(diào)度隊列模型：

1.僅有進程調(diào)度的調(diào)度隊列模型在分時系統(tǒng)中，通常僅設置了進程調(diào)度。常把就緒進程組織成FIFO隊列形式。阻塞隊列一般可能有多個。就緒隊列阻塞隊列交互用戶進程調(diào)度CPU時間片完等待事件進程完成事件出現(xiàn)圖3-1僅具有進程調(diào)度的調(diào)度隊列模型73.1.2調(diào)度隊列模型2.具有高級和低級調(diào)度的調(diào)度隊列模型批處理系統(tǒng)中的調(diào)度模型比第一種情況多了后備隊列就緒隊列阻塞隊列1作業(yè)調(diào)度進程調(diào)度CPU時間片完等待事件1進程完成圖3-2具有高、低兩級調(diào)度的調(diào)度隊列模型阻塞隊列2等待事件2阻塞隊列n等待事件n………事件1出現(xiàn)事件2出現(xiàn)事件n出現(xiàn)后備隊列83.1.2調(diào)度隊列模型3.同時具有三級調(diào)度的調(diào)度隊列模型

具有掛起狀態(tài)的系統(tǒng)。

93.1.3選擇調(diào)度方式和調(diào)度算法的若干準則1．面向用戶的準則

（1）周轉(zhuǎn)時間短。

評價批處理系統(tǒng)的準則之一周轉(zhuǎn)時間——是指從作業(yè)被提交給系統(tǒng)開始，到作業(yè)完成這段時間間隔。平均周轉(zhuǎn)時間

舉例說明（2）響應時間快

評價分時系統(tǒng)的準則之一響應時間——是從用戶通過鍵盤提交一個請求開始，到系統(tǒng)首次產(chǎn)生響應為止的時間。

10在批處理、分時和實時系統(tǒng)中選擇調(diào)度算法時，都可以遵循優(yōu)先權準則，以便讓某些緊急的作業(yè)能得到及時處理。在要求嚴格的場合，往往還須選擇搶占式調(diào)度方式

（4）優(yōu)先權準則

截止時間——

是指某任務必須開始執(zhí)行的最遲時間，或必須完成的最遲時間。

（3）截止時間的保證

評價實時系統(tǒng)的準則之一113.1.3選擇調(diào)度方式和調(diào)度算法的若干準則2.面向系統(tǒng)的準則

（1）系統(tǒng)吞吐量高（2）處理機利用率好（3）各類資源的均衡利用

吞吐量——單位時間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)

調(diào)度方式和算法對處理機的利用率起著十分重要的作用

對于單用戶微機或某些實時系統(tǒng)，該準則并不重要

123.2調(diào)度算法3.2.1先來先服務調(diào)度算法3.2.2短作業(yè)(進程)優(yōu)先調(diào)度算法3.2.3高優(yōu)先權優(yōu)先調(diào)度算法3.2.4高響應比優(yōu)先調(diào)度算法3.2.5基于時間片的輪轉(zhuǎn)調(diào)度算法133.2.1先來先服務調(diào)度算法FCFS調(diào)度算法是一種最簡單的調(diào)度算法。既可用于作業(yè)調(diào)度，也可用于進程調(diào)度。用于作業(yè)調(diào)度中：從后備隊列作業(yè)中，選擇一個或幾個最先進入該隊列的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進程，然后放入進程就緒隊列。用于進程調(diào)度時：從就緒隊列中，選擇一個最先進入該隊列的進程，為之分配處理機，使之投入運行。該進程一直運行到完成或發(fā)生某事件而阻塞后，才放棄處理機?！菗屨际?4【例3-1】設在單道系統(tǒng)中用FCFS算法調(diào)度如下作業(yè)，請完成下表。進程名

ABCDE平

均

到達時間

9:00

9:10

9:30

10:00

10:15

服務時間

30分鐘

1小時

10分鐘

50分鐘

20分鐘

完成時間

周轉(zhuǎn)時間

帶權周轉(zhuǎn)時間

80分鐘

9:30

30分鐘10:3070分鐘

10:4011:3090分鐘

11:5095分鐘

11.3371.84.7573分鐘

3.176FCFS算法比較有利于長作業(yè)（進程），不利于短作業(yè)（進程）。有利于CPU繁忙型作業(yè)（進程），不利于I/O繁忙型作業(yè)（進程）——因非搶占式CPU繁忙型作業(yè)——需要大量的CPU時間進行計算，而很少請求I/O。如，科學計算I/O繁忙型作業(yè)——是指CPU進行處理時，需頻繁地請求I/O。如，大多數(shù)事務處理153.2.2短作業(yè)(進程)優(yōu)先調(diào)度算法

短作業(yè)優(yōu)先（SJF）調(diào)度算法——

從后備隊列中選擇一個或幾個估計運行時間最短的作業(yè)，將它調(diào)入內(nèi)存運行。短進程優(yōu)先（SPF）調(diào)度算法——從就緒隊列中選擇一個估計運行時間最短的進程，將處理機分配給它，使它立即執(zhí)行并一直到完成，或發(fā)生某事件而被阻塞放棄處理機時，再重新調(diào)度。(非搶占式)16【例3-2】設在單道系統(tǒng)中用SJF算法調(diào)度如下作業(yè)，請完成下表。進程名

ABCDE平

均

到達時間

9:00

9:10

9:30

10:00

10:15

服務時間

30分鐘

1小時

10分鐘

50分鐘

20分鐘

完成時間

周轉(zhuǎn)時間

帶權周轉(zhuǎn)時間9:3010:409:4011:5011:0030分鐘90分鐘10分鐘110分鐘45分鐘57分鐘11.512.22.251.5917SJF調(diào)度算法的優(yōu)點：SJF調(diào)度算法的缺點：該算法對長作業(yè)不利——長作業(yè)可能長期不被調(diào)度，甚至“餓死”。未考慮作業(yè)的緊迫性，不能保證緊迫作業(yè)（進程）會被及時調(diào)度。由于作業(yè)（進程）的長短只是根據(jù)用戶所提供的估計時間而定的，致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。

當多個作業(yè)同時到達時，SJF算法可使平均周轉(zhuǎn)時間最短。183.2.3高優(yōu)先權優(yōu)先調(diào)度算法

引入的目的：為了照顧緊迫型作業(yè)，使之在進入系統(tǒng)后便獲得優(yōu)先處理。優(yōu)先權作業(yè)調(diào)度——

系統(tǒng)從后備中選擇一個或幾個優(yōu)先權最高的作業(yè)，將它調(diào)入內(nèi)存運行。

優(yōu)先權進程調(diào)度——

系統(tǒng)將處理機分配給就緒隊列中一個優(yōu)先權最高的進程。

適用范圍：

批處理系統(tǒng)的作業(yè)調(diào)度

多種操作系統(tǒng)的進程調(diào)度

還適用于實時系統(tǒng)

191．優(yōu)先權進程調(diào)度算法的類型非搶占式優(yōu)先權算法

搶占式優(yōu)先權算法

非搶占式優(yōu)先權算法——系統(tǒng)一旦把處理機分配給就緒隊列中優(yōu)先權最高的進程后，該進程便一直執(zhí)行下去，直到完成，或因發(fā)生某事件使該進程放棄處理機時，系統(tǒng)方可再將處理機重新分配給另一個優(yōu)先權最高的進程。

搶占式優(yōu)先權算法——系統(tǒng)把處理機分配給就緒隊列中優(yōu)先權最高的進程，使之執(zhí)行，但在其執(zhí)行期間，只要出現(xiàn)了另一個優(yōu)先權更高的進程，系統(tǒng)就立即停止當前進程的執(zhí)行，重新將處理機分配給新的優(yōu)先權最高的進程。

它能更好地滿足緊迫作業(yè)的要求。常用于實時系統(tǒng)中，以及對實時性能要求較高的批處理系統(tǒng)和分時系統(tǒng)中。

202．優(yōu)先權的類型

靜態(tài)優(yōu)先權動態(tài)優(yōu)先權

1）靜態(tài)優(yōu)先權

靜態(tài)優(yōu)先權——它是在創(chuàng)建進程時確定的，且在進程整個運行期間保持不變。優(yōu)先權一般用某一范圍內(nèi)的一個整數(shù)來表示。有的系統(tǒng)用“0”表示最高優(yōu)先權，數(shù)值越大，優(yōu)先權越低；有的系統(tǒng)恰恰相反。

確定優(yōu)先權的依據(jù)：——常有三方面

進程類型系統(tǒng)進程（如接收進程、對換進程、磁盤I/O進程等）的優(yōu)先權高于一般用戶進程的優(yōu)先權。進程對資源的需求如進程的估計執(zhí)行時間及內(nèi)存需求量的多少，對這些要求少的進程賦予較高的優(yōu)先權。

用戶要求這是由用戶進程的緊迫程度和用戶所付費用的多少來確定優(yōu)先權的。

靜態(tài)優(yōu)先權的優(yōu)缺點：優(yōu)點：簡單易行，系統(tǒng)開銷小。

缺點：優(yōu)先權低的作業(yè)（進程）可能長期得不到調(diào)度。

212）動態(tài)優(yōu)先權

動態(tài)優(yōu)先權——在創(chuàng)建進程時所賦予的優(yōu)先權，是可以隨進程得推進，或隨其等待時間的增加而改變的，以便獲得更好的調(diào)度性。

例如：

在就緒隊列中的進程，隨其等待時間的增長，其優(yōu)先權以速率α提高；

在采用搶占式優(yōu)先權調(diào)度算法時，如果再規(guī)定當前執(zhí)行進程以速率β下降，則可防止一個長作業(yè)長期壟斷處理機。

22UNIX采用計算的方法動態(tài)改變進程的優(yōu)先數(shù)。在UNIXSystemV版本中，進程優(yōu)先數(shù)p_pri的算式如下：

p_pri=p_cpu/2+PUSER+p_nice+NZERO其中，PUSER和NZERO是偏置常數(shù)，分別為25和20。p_cpu和p_nice是基本進程控制塊中的兩個項，分別表示進程使用處理器的情況和用戶自己設置的計算優(yōu)先數(shù)的偏置量。系統(tǒng)對正在占用CPU的進程每隔一個時鐘周期(20ms)對其p_cpu加1。這使得占用處理器時間長的進程的p_cpu值增大，其優(yōu)先數(shù)也增大，優(yōu)先權就相應降低。系統(tǒng)每隔1s對所有進程執(zhí)行p_cpu/2，這使就緒進程優(yōu)先級提高。p_nice的值允許用戶根據(jù)任務的輕重緩急程度來設置，其值在0～39之間。一旦一個進程的p_nice設置后，此后用戶只能使其值增加。23【例3-3】設有一個最多可有兩道作業(yè)同時裝入內(nèi)存執(zhí)行的批處理系統(tǒng)，作業(yè)調(diào)度采用最短作業(yè)優(yōu)先調(diào)度算法，進程調(diào)度采用搶占式靜態(tài)優(yōu)先權調(diào)度算法，今有如下純計算型作業(yè)序列（表中所列進程優(yōu)先數(shù)中，數(shù)值越小優(yōu)先權越高）：

(1)列出所有作業(yè)進入內(nèi)存時間及結(jié)束時間。

(2)計算平均周轉(zhuǎn)時間。

作業(yè)名到達時間估計運行時間進程優(yōu)先數(shù)J110:1020分鐘5J210:2030分鐘3J310:3025分鐘4J410:5020分鐘624作業(yè)名提交時間進入時間結(jié)束時間周轉(zhuǎn)時間J110：10J210：20J310：30J410：50平均周轉(zhuǎn)時間=(50+30+55+55)4=47.5(分鐘)作業(yè)名到達時間估計運行時間進程優(yōu)先數(shù)J110:1020分鐘5J210:2030分鐘3J310:3025分鐘4J410:5020分鐘610:1011:0050分鐘10:2010:5030分鐘11:0011:2555分鐘10:5011:4555分鐘253.2.4高響應比優(yōu)先調(diào)度算法

響應比＝(等待時間+要求服務時間)/要求服務時間（實際上響應比是動態(tài)優(yōu)先權）

高響應比優(yōu)先調(diào)度算法——

每次要進行作業(yè)調(diào)度時，系統(tǒng)首先計算后備隊列中各作業(yè)的響應比，然后選擇一個或若干個響應比最高的作業(yè)調(diào)入內(nèi)存執(zhí)行。

該算法綜合了FCFS和SJF算法的優(yōu)點——既考慮公平性，又考慮平均周轉(zhuǎn)時間缺點是會增加系統(tǒng)開銷——每次調(diào)度都要計算響應比。優(yōu)先權＝(等待時間+要求服務時間)/要求服務時間2624．下列進程調(diào)度算法中，綜合考慮進程等待時間和執(zhí)行時間的是_____。(2009全國考研第24題)A．時間片輪轉(zhuǎn)調(diào)度算法B．短進程優(yōu)先調(diào)度算法 C．先來先服務調(diào)度算法D．高響應比優(yōu)先調(diào)度算法27【例3-4】設有一個最多可有兩道作業(yè)同時裝入內(nèi)存執(zhí)行的批處理系統(tǒng)，作業(yè)調(diào)度采用高響應比優(yōu)先調(diào)度算法，進程調(diào)度采用搶占式靜態(tài)優(yōu)先權調(diào)度算法，今有如下純計算型作業(yè)序列（假設表中所列進程優(yōu)先數(shù)中，數(shù)值越小優(yōu)先權越高）：

(1)列出所有作業(yè)進入內(nèi)存時間及結(jié)束時間。

(2)計算平均周轉(zhuǎn)時間。

作業(yè)名到達時間估計運行時間進程優(yōu)先數(shù)J110:1020分鐘5J210:2030分鐘3J310:3025分鐘4J410:5020分鐘628J1CPU10:1010:20J210:5010:50J3響應比高，J3調(diào)入內(nèi)存并執(zhí)行。11:15J311:15J4調(diào)入內(nèi)存，J1恢復執(zhí)行。J111:25J411:4510:10只有J1一個作業(yè)，調(diào)入內(nèi)存執(zhí)行。10:20J2到達，調(diào)入內(nèi)存，因其優(yōu)先級高，J2執(zhí)行。29J1J2J3J1J4CPU10:1010:2010:5011:1511:2511:45作業(yè)名到達時間調(diào)入時間結(jié)束時間周轉(zhuǎn)時間J110:1010:1011:2575分鐘J210:2010:2010:5030分鐘J310:3010:5011:1545分鐘J410:5011:1511:4555分鐘平均周轉(zhuǎn)時間=(75+30+45+55)/4=51.25(分鐘)303.2.5基于時間片的輪轉(zhuǎn)調(diào)度算法

用于進程調(diào)度。早期，分時系統(tǒng)采用的是簡單的時間片輪轉(zhuǎn)法；90年代后，廣泛采用多級反饋隊列調(diào)度算法。

1．時間片輪轉(zhuǎn)法

系統(tǒng)把就緒隊列中的所有進程，按先來先服務的原則，排成一個隊列；

每次調(diào)度時，把CPU分配給隊首進程，并讓它執(zhí)行一個時間片；

每當執(zhí)行的時間片用完，調(diào)度程序便停止該進程的執(zhí)行，將其送入就緒隊列尾部；然后進行下一次進程調(diào)度。

時間片的大?。簬譵s～幾百ms。

31【例3-5】設有一個最多可有兩道作業(yè)同時裝入內(nèi)存執(zhí)行的批處理系統(tǒng)，作業(yè)調(diào)度采用高響應比優(yōu)先調(diào)度算法，進程調(diào)度采用時間片輪轉(zhuǎn)調(diào)度算法(假設時間片為100ms)，今有如下純計算型作業(yè)序列：

(1)列出所有作業(yè)進入內(nèi)存時間及結(jié)束時間。

(2)計算平均周轉(zhuǎn)時間。

作業(yè)名到達時間估計運行時間J110:1020分鐘J210:2030分鐘J310:3025分鐘J410:5020分鐘32先在草稿上分析如下：10:10J1到達，調(diào)入內(nèi)存執(zhí)行10:20J2到達，調(diào)入內(nèi)存與J1一起均分CPU運行。J1已運行10分鐘，還需與J2一起運行20分鐘10:30J3到達，不調(diào)入內(nèi)存10:40J1結(jié)束，J3調(diào)入內(nèi)存與J2一起均分CPU運行。J2已運行10分鐘，還需與J3一起運行40分鐘10:50J4到達，不調(diào)入內(nèi)存11:20J2結(jié)束，J4調(diào)入內(nèi)存與J3一起均分CPU運行。J3已運行20分鐘，還需與J4一起運行10分鐘11:30J3結(jié)束，J4還需單獨運行15分鐘11:45J4結(jié)束33作業(yè)名調(diào)入時間結(jié)束時間周轉(zhuǎn)時間J110:1010:4030分鐘J210:2011:2060分鐘J310:4011:3060分鐘J411:2011:4555分鐘(2)平均周轉(zhuǎn)時間=(30+60+60+55)/4=51.25(分鐘)解：(1)各作業(yè)進入內(nèi)存時間及結(jié)束時間如下表所示。342．多級反饋隊列調(diào)度算法

不必事先知道各進程所需的執(zhí)行時間，而且還可以滿足各種類型進程的需要。目前被公認的一種較好的進程調(diào)度算法。CPU完成就緒隊列1S1時間片用完CPU完成就緒隊列2S2時間片用完CPU完成就緒隊列3S3時間片用完CPU完成就緒隊列nSn時間片用完新進程就緒(時間片：S1<S2<S3<…<Sn)優(yōu)先級：S1<S2<S3<…<Sn)圖3-4多級反饋隊列調(diào)度算法阻塞進程I/O完成或等待的事件發(fā)生CPU運行態(tài)353.多級反饋隊列調(diào)度算法的性能多級反饋隊列調(diào)度算法具有較好的性能，能很好地滿足各種類型用戶的需要。終端型作業(yè)用戶。交互型作業(yè)通常較小，系統(tǒng)只要能使這些作業(yè)(進程)在第一隊列所規(guī)定的時間片內(nèi)完成，便可使終端型作業(yè)用戶感到滿意。短批處理作業(yè)用戶。如果僅在第一隊列中執(zhí)行一個時間片即可完成，便可獲得終端型用戶一樣的響應時間。對于稍長的作業(yè)，通常也只需在第二或第三隊列各執(zhí)行一個時間片即可完成，其周轉(zhuǎn)時間仍然較短。長批處理作業(yè)用戶。將依次在第1,2,…,n個隊列中運行，然后再按輪轉(zhuǎn)方式運行，用戶不必擔心其作業(yè)長期得不到服務。36演示進程調(diào)度算法進程調(diào)度實驗一373.3實時調(diào)度由于在實時系統(tǒng)中都存在著若干個實時進程或任務，它們用來反應或控制某個(些)外部事件，往往帶有某種程度的緊迫性，因而對實時系統(tǒng)的調(diào)度提出了某些特殊要求，前面介紹的多種調(diào)度算法，并不能滿足實時系統(tǒng)對調(diào)度的要求，為此需引入一種新的調(diào)度，即實時調(diào)度。跳過實時調(diào)度和多處理機調(diào)度383.3.1實現(xiàn)實時調(diào)度的基本條件

在實時系統(tǒng)中，硬實時任務(存在著必須滿足的時間限制)和軟實時任務(偶爾超過時間限制是可以容忍的)都聯(lián)系著一個截止時間。為了保證系統(tǒng)能正常工作，實時調(diào)度必須滿足實時任務對截止時間的要求，為此，實現(xiàn)實時調(diào)度應具備下述幾個條件：1．提供必要的信息系統(tǒng)應向調(diào)度程序提供有關任務的下述信息：(1)就緒時間。這是該任務成為就緒狀態(tài)的起始時間(2)開始截止時間和完成截止時間。對于典型的實時應用，只需知道開始截止時間，或者知道完成截止時間。(3)處理時間。一個任務從開始執(zhí)行直至完成所需的時間。在某些情況下，該時間也是系統(tǒng)提供的。(4)資源要求。(5)優(yōu)先級。若某任務的開始截止時間已經(jīng)錯過，就會引起故障，則應賦予該任務“絕對”優(yōu)先級；如果對系統(tǒng)的繼續(xù)運行無重大影響，則可賦予“相對”優(yōu)先級，供調(diào)度參考。392．系統(tǒng)處理能力強

若處理機的處理能力不強，則有可能因處理機忙不過來而使某些實時任務不能得到及時處理，從而導致發(fā)生難于預料的后果。假定系統(tǒng)中有m個周期性硬實時任務，它們的處理時間為Ci，周期時間為Pi，則在單處理機情況下，必須滿足下面的限制條件：系統(tǒng)才是可調(diào)度的。40例如設系統(tǒng)中有6個硬實時任務，它們的周期都是50ms，而每次的處理時間都是10ms，此時不能滿足上式，因而系統(tǒng)是不可調(diào)度的。又例如一個實時系統(tǒng)中有3個實時事件流，其周期分別為100ms、200ms和500ms，每次的處理時間分別為50ms、30ms和100ms，則因為

0.5+0.15+0.2≤1故系統(tǒng)是可調(diào)度的。如果加入周期為1秒的第4個任務，則只要其處理時間不超過150ms，系統(tǒng)仍是可調(diào)度的。當然，上述運算的隱含條件是進行切換的時間足夠小，可以忽略。41設實時任務A、B、C，周期分別為100ms、200ms、500ms，處理時間分別為50ms、30ms、100ms，又設它們同時開始計時，則設想可有如下調(diào)度順序(假設優(yōu)先級順序為A、B、C)：ABCt(ms)100200300400500600700800900100011000思考：考慮加入一個周期為1秒，處理時間為150ms的實時任務后的情況。42提高系統(tǒng)的可調(diào)度性的解決方法是提高系統(tǒng)的處理能力，其途徑有二：上述限制條件并未考慮任務的切換時間，包括執(zhí)行調(diào)度算法和進程任務切換，以及消息的傳遞時間等開銷，因此，當利用上述限制條件來確定系統(tǒng)是否可調(diào)度時，還應適當?shù)亓粲杏嗟?。仍采用單處理機系統(tǒng)，但需提高其處理能力，以顯著減少對每一個任務的處理時間；采用多處理機系統(tǒng)，假設系統(tǒng)中處理機數(shù)為N，則應將上述限制條件改為：433．采用搶占式調(diào)度機制

含有硬實時任務的實時系統(tǒng)中，廣泛采用搶占機制。這樣可滿足硬實時任務對截止時間的要求，但這種調(diào)度機制比較復雜。對于一些小的實時系統(tǒng)，如果能預知任務的開始截止時間，則對實時任務的調(diào)度可采用非搶占調(diào)度機制以簡化調(diào)度程序和對任務調(diào)度所花費的系統(tǒng)開銷。但在設計這種調(diào)度機制時，應使所有的實時任務都比較小，并在執(zhí)行完關鍵性程序和臨界區(qū)后，能及時地把自己阻塞起來，以便釋放處理機，供調(diào)度程序去調(diào)度那種開始截止時間即將到達的任務。444．具有快速切換機制

為了保證要求較高的硬實時任務能及時運行，在實時系統(tǒng)中還應具有快速切換機制，以保證能進行任務的快速切換。該機制應具有下述兩方面的能力：對外部中斷的快速響應能力。要求系統(tǒng)具有快速硬件中斷機構，還應使禁止中斷的時間間隔盡量短，以免耽誤其它緊迫任務?？焖俚娜蝿辗峙赡芰?。在完成任務調(diào)度后，便應進行任務切換。為了提高分派程序進行任務切換時的速度，應使系統(tǒng)中的每個運行功能單位適當?shù)男?，以減少任務切換的時間開銷。453.3.2實時調(diào)度算法的分類按實時任務性質(zhì)不同來劃分：硬實時調(diào)度算法軟實時調(diào)度算法按調(diào)度方式的不同非搶占調(diào)度算法搶占調(diào)度算法因調(diào)度程序調(diào)度時間的不同靜態(tài)調(diào)度算法——進程執(zhí)行前，調(diào)度程序便已經(jīng)決定了個進程間的執(zhí)行順序動態(tài)調(diào)度算法多處理機環(huán)境下集中式調(diào)度分布式調(diào)度46下面討論按調(diào)度方式的不同對調(diào)度算法進行分類：1．非搶占式調(diào)度算法算法比較簡單，易于實現(xiàn)，故在一些小型實時系統(tǒng)或要求不太嚴格的實時控制系統(tǒng)中，經(jīng)常采用之。又可分成兩種：非搶占式輪轉(zhuǎn)調(diào)度算法。常用于工業(yè)生產(chǎn)的群控系統(tǒng)中,可用于要求不太嚴格的實時控制系統(tǒng)中。非搶占式優(yōu)先調(diào)度算法。如果系統(tǒng)中存在要求較為嚴格的任務(響應時間為數(shù)百毫秒)，可采用此算法?？捎糜谟幸欢ㄒ蟮膶崟r控制系統(tǒng)中。47進程1進程2…進程n實時進程實時進程請求調(diào)度調(diào)度實時進程運行調(diào)度時間(a)非搶占輪轉(zhuǎn)調(diào)度當前進程

實時進程實時進程請求調(diào)度當前進程運行完成或阻塞調(diào)度時間(b)非搶占優(yōu)先權調(diào)度圖3-6實時進程調(diào)度(非搶占式)482．搶占式調(diào)度算法在要求較嚴格(響應時間為數(shù)十毫秒以下)的實時系統(tǒng)中采用，可根據(jù)搶占發(fā)生時間的不同進而分成以下兩種算法：基于時鐘中斷的搶占式優(yōu)先權調(diào)度算法。在某實時任務到達后，如果任務的優(yōu)先級高于當前任務的優(yōu)先級，這時并不立即搶占當前任務的處理機，而是等到時鐘中斷到來時，調(diào)度程序才剝奪當前任務執(zhí)行，將處理機分配給新到的高優(yōu)先權任務。這種調(diào)度算法能獲得較好的響應效果，其調(diào)度延時可降到幾十毫秒到幾毫秒。因此，此算法可用于大多數(shù)的實時系統(tǒng)。49立即搶占的優(yōu)先權調(diào)度算法。這種調(diào)度策略要求操作系統(tǒng)具有快速響應外部中斷事件的能力。一旦出現(xiàn)外部中斷，只要當前任務未處于臨界區(qū)，便可立即剝奪當前任務的執(zhí)行，把處理機分配給請求中斷的緊迫任務。這種算法能獲得非常快的響應，可把調(diào)度延遲時間降低到幾毫秒至100微秒，甚至更低。50當前進程

實時進程實時進程請求調(diào)度時鐘中斷到來時調(diào)度時間(c)基于時鐘中斷搶占的優(yōu)先權調(diào)度當前進程

實時進程實時進程請求調(diào)度實時進程搶占當前進程，并立即執(zhí)行調(diào)度時間(d)立即搶占的優(yōu)先權調(diào)度圖3-6實時進程調(diào)度(搶占式)513.3.3常用的幾種實時調(diào)度算法1．最早截止時間優(yōu)先算法即EDF(Earliest

DeadlingFirst)算法根據(jù)任務的開始截止時間來確定任務的優(yōu)先級。截止時間愈早，其優(yōu)先級愈高。實時任務就緒隊列按各任務的截止時間的早晚排序?？捎糜趽屨际秸{(diào)度，也可用于非搶占式調(diào)度。52

1342開始截止時間任務執(zhí)行任務到達12341342t圖3-7EDF算法用于非搶占調(diào)度方式設有4個非周期任務，它們先后到達。系統(tǒng)首先調(diào)度任務1執(zhí)行，在任務1執(zhí)行期間，任務2、3又先后到達。由于任務3的開始截止時間早于任務2，故系統(tǒng)在任務1后將調(diào)度任務3執(zhí)行。任務3執(zhí)行時，又到達任務4，其開始截止時間早于任務2，故任務3執(zhí)行完后，系統(tǒng)又調(diào)度任務4執(zhí)行，最后才調(diào)度任務2執(zhí)行。532．最低松弛度優(yōu)先算法即LLF(LeastLaxityFirst)算法根據(jù)任務緊急(或松弛)的程度來確定任務的優(yōu)先級。任務緊急程度愈高，其優(yōu)先級愈高。實現(xiàn)該算法要求系統(tǒng)中有一個按松弛度排序的實時任務就緒隊列，松弛度最低的任務排在隊列的最前面。主要用于可搶占式調(diào)度方式中。例：松弛度的計算一個任務在200ms之前必須完成，它本身需要運行100ms，則該任務的緊急程度(松弛程度)為100ms。54利用LLF算法進行調(diào)度的例子在一個實時系統(tǒng)中，有2個周期性實時任務A和B，任務A要求每20ms執(zhí)行一次，執(zhí)行時間為10ms；任務B要求每50ms執(zhí)行一次，執(zhí)行時間為25ms。由此可知任務A和任務B每次必須完成的時間分別為：A1、A2、A3…和B1、B2、B3…，見圖3-8。為保證不遺漏任何一次截止時間，應采用最低松弛優(yōu)先的搶占調(diào)度策略。020406080100120140160A1A2A3A4A5A6A7A8B1B2B3t圖3-8A和B任務每次必須完成時間55在剛開始時(t1=0)，A1必須在20ms時完成，而它本身運行需要10ms，可算出A1的松弛度為10ms；B1必須在50ms時完成，而它本身就需25ms，可算出B1的松弛度為25ms，故調(diào)度程序應先調(diào)度A1執(zhí)行。在t2=10ms時，A2的松弛度可按下式算出：A2的松弛度=必須完成的時間-其本身的運行時間-當前時間

=40ms-10ms-10ms=20ms

類似地，可算出B1的松弛度為15ms，故調(diào)度程序應選擇B1執(zhí)行。在t3=30ms時，A2的松弛度已減為0(即40-10-30)，而B1的松弛度為15ms(50-5-30)，于是調(diào)度程序應搶占B1的處理機而調(diào)度A2運行。在t4=40ms時，A2完畢，A3的松弛度為10ms(即60-10-40)，而B1的松弛度為5ms(50-5-40)，故又重新調(diào)度B1執(zhí)行。在t5=45ms時，B1

執(zhí)行完畢，而此時A3的松弛度已減為5(即60-10-45)，而B2的松弛度為30ms(100-25-45)，于是又應調(diào)度A2執(zhí)行。56在t6=55ms時，A3

執(zhí)行完畢，任務A此時尚未進入A4，而任務B已進入B2周期，故調(diào)度B2執(zhí)行。在t7=70ms時，A4的松弛度已減為0(即80-10-70)，而B2的松弛度為20ms(100-10-70)，于是調(diào)度程序應搶占B2的處理機而調(diào)度A4運行。在t8=80ms時，A4執(zhí)行完畢。A5的松弛度為10ms(即100-10-80)，而B2的松弛度為0ms(100-10-80)，故又重新調(diào)度B2執(zhí)行?！?tt1t2t3t8t4t5t6t7A1(10)1080

203040506070A2(10)A3(10)A4(10)B1(20)B2(15)B1(5)B2(10)圖3-9利用LLF算法進行調(diào)度的情況573.4多處理機系統(tǒng)中的調(diào)度(略)提高計算機系統(tǒng)性能的主要途徑有兩條：提高構成計算機的元器件的運行速度，特別是處理器芯片的速度；改進計算機系統(tǒng)的體系結(jié)構，特別是在系統(tǒng)中引入多個處理器或多臺計算機，以實現(xiàn)對信息的高度并行處理，達到提高系統(tǒng)吞吐量和可靠性的目的。

20世紀70年代出現(xiàn)了多處理器系統(tǒng)，即MPS(MultiProcessorSystem)；90年代中后期，功能較強的主機系統(tǒng)和服務器，幾乎都毫無例外地采用了多處理器(機)系統(tǒng)，處理器的數(shù)目可為2個至數(shù)千個，甚至更多。本章介紹多處理器(機)的調(diào)度。583.4.1多處理器系統(tǒng)的類型緊密耦合MPS和松弛耦合MPS緊密耦合(TightlyCoupled)MPS。這通常是通過高速總線或高速交叉開關，來實現(xiàn)多個處理器之間的互連的。它們共享主存和I/O設備，并要求將主存劃分為若干個能獨立訪問的存儲器模塊，以便多個處理器能同時對主存進行訪問。系統(tǒng)中所有的資源和進程，都由OS實施統(tǒng)一的控制和管理。松散耦合(LooselyCoupled)MPS。通常是通過通道或通信線路來實現(xiàn)多臺計算機之間的互連。每臺計算機都有自己的內(nèi)存和I/O設備，并配置了OS來管理本地資源和本地運行的進程。因此，每臺計算機都能獨立地工作，必要時可通過通信線路與其它計算機交換信息，以及協(xié)調(diào)它們之間的工作。59對稱多處理器系統(tǒng)和非對稱多處理器系統(tǒng)根據(jù)系統(tǒng)中所用處理器的相同與否，可將MPS分為：（1）對稱多處理器系統(tǒng)（SymmetricMultiProcessorSystem，SMPS）。在系統(tǒng)中所包含的各處理器，在功能和結(jié)構上都是相同的。當前絕大多數(shù)MPS都屬于SMP系統(tǒng)。如，IBM公司的SR/6000ModelF50，便是利用4片PowerPC處理器構成的。（2）非對稱多處理器系統(tǒng)。在系統(tǒng)中有多種類型的處理單元，它們的功能和結(jié)構各不相同，其中只有一個主處理器，有多個從處理器。603.3.2進程分配方式在多處理器系統(tǒng)中，進程的調(diào)度與系統(tǒng)結(jié)構有關。在同構系統(tǒng)中，由于所有處理其都是相同的，因而可將進程分配到任一處理器上運行；對于非對稱多處理器系統(tǒng)，則對任一進程而言，只能把進程分配到某一合適于其運行的處理器上去執(zhí)行。611．對稱多處理器系統(tǒng)中的進程分配方式在對稱多處理器（SMP）系統(tǒng)中，所有處理器相同，因而可把所有處理器作為一個處理器池（Processorpool）,由調(diào)度程序或基于處理器的請求，將進程分配到池中的任一處理器上運行。在進程分配時，可采用以下兩種方式之一：（1）靜態(tài)分配方式是指一個進程從開始執(zhí)行直至其完成，都被固定地分配到一個固定的處理器上執(zhí)行。需為每個處理器設置一個專用的就緒隊列。進程阻塞后再次就緒時，仍被掛在它原先所在的就緒隊列中。此方式與單處理機環(huán)境下的進程調(diào)度一樣。優(yōu)點：進程調(diào)度的開銷小。缺點：各處理器的忙閑不均。62（2）動態(tài)分配方式為了防止多個處理器忙閑不均，可在系統(tǒng)中設置一個公共的就緒隊列，系統(tǒng)中所有就緒進程都被放在該隊列中。分配進程時，可將進程分配到任何一個處理器上?！M程下次被調(diào)度時，可能被分配到另一個處理器上去執(zhí)行?！@稱為進程的動態(tài)分配方式。優(yōu)點：

消除了各處理器忙閑不均的現(xiàn)象。對于緊密偶合共享存儲器的MPS，其每個處理器保存在存儲器中的進程信息，可被各處理器共享。因此不會增加調(diào)度開銷。缺點：對于松散偶合的MPS，在把一個處理器A上運行的進程轉(zhuǎn)至處理器B運行時，還必須將在處理器A中所保存的該進程的信息，傳送到處理器B，這無疑會造成調(diào)度開銷的明顯增加。緊密偶合對稱MPS——更適宜進程動態(tài)分配方式松散偶合對稱MPS——更適宜進程靜態(tài)分配方式632．非對稱多處理器系統(tǒng)中的進程分配方式對于非對稱多處理器系統(tǒng)，其OS大多采用主-從（Master－Slave）式OS，即OS的核心部分駐留在一臺主機（Master）上，而從機（Slave）上只是用戶程序，進程調(diào)度只由主機執(zhí)行。每當從機空閑時，便向主機發(fā)送一個索求進程的信號，等待主機為它分配進程。在主機中保持有一個就緒隊列，只要就緒隊列不空，主機便從其隊首摘下一進程分配給請求的從機。從機接收到分配的進程后便運行該進程，該進程結(jié)束后從機又向主機發(fā)出請求。64優(yōu)點：系統(tǒng)處理比較簡單。因為所有進程分配都由一臺主機獨自處理，使進程的同步問題得以簡化；且進程調(diào)度程序也很易于從單處理機的進程調(diào)度程序演化而來。缺點：由一臺主機控制一切，潛在著不可靠性，即主機一旦出現(xiàn)故障，將導致整個系統(tǒng)癱瘓；很易于因主機太忙，來不及處理而形成系統(tǒng)瓶頸?？朔姆椒ǎ豪枚嗯_而非一臺處理機來管理整個系統(tǒng)。653.3.3進程(線程)調(diào)度方式自20世紀90年代以來，已出現(xiàn)了多種調(diào)度方式，許多都是以線程作為基本調(diào)度單位。比較有代表性的進(線)程調(diào)度方式有：自調(diào)度方式成組調(diào)度方式專用處理機分配方式661．自調(diào)度(Self–Scheuling)方式是最簡單的一種調(diào)度方式，直接由單處理機環(huán)境下的調(diào)度方式演變而來。自調(diào)度機制：在系統(tǒng)中設置一個公共的進程（或線程）就緒隊列，所有處理器在空閑時，都可自己到該隊列中取得一進程（或線程）來運行?？刹捎脝翁幚頇C環(huán)境下所用的調(diào)度算法。如，F(xiàn)CFS調(diào)度算法最高優(yōu)先權優(yōu)先（FPF）調(diào)度算法搶占式最高優(yōu)先權優(yōu)先調(diào)度算法等在單處理機環(huán)境下，F(xiàn)CFS并不是一種好的調(diào)度算法；在多處理器環(huán)境中的線程調(diào)度，F(xiàn)CFS反而優(yōu)于FPF和搶占式FPF調(diào)度算法。FCFS算法簡單、開銷小，目前已成為一種較好的自調(diào)度算法67自調(diào)度方式的優(yōu)點：系統(tǒng)中的公共就緒隊列可以按照單處理機系統(tǒng)中所采用的各種方式加以組織；很容易將單處理機環(huán)境下的調(diào)度算法移植到多處理器系統(tǒng)中；只要公共就緒隊列不空，就不會出現(xiàn)處理機空閑的情況，也不會發(fā)生處理器忙閑不均現(xiàn)象，有利于提高處理器的利用率。68自調(diào)度方式的缺點：瓶頸問題。一個就緒隊列供多個處理器共享，這些處理器必須互斥地訪問該隊列，容易形成系統(tǒng)瓶頸。尤其是系統(tǒng)中處理器數(shù)目在數(shù)十乃至數(shù)百個時，就會產(chǎn)生嚴重的瓶頸問題。低效性。當線程阻塞后重新就緒時，它將只能進入這唯一的就緒隊列，但卻很少可能仍在阻塞前的處理器上運行。如果在每臺處理器上都配有高速緩存（Cache），則這時其中保留的該線程的數(shù)據(jù)將失效，而在該線程新獲得的處理器上，又須重新建立這些數(shù)據(jù)的拷貝。由于一個線程在其整個生命期內(nèi)，可能要多次更換處理器，因而使高速緩存的使用效率很低。線程切換頻繁。通常，一個應用中的多個線程都屬于相互合作型的，但在采用自調(diào)度方式時，這些線程很難同時獲得處理器而同時運行，這將會使某些線程因其合作線程未獲得處理器運行而阻塞，進而被切換下來。692．成組調(diào)度方式為了解決自調(diào)度方式中線程切換頻繁的問題而提出的。成組調(diào)度方式——將一個進程中的一組線程，分配到一組處理器上去執(zhí)行。如何為應用程序分配處理器時間，可有兩種方式：1）面向所有應用程序平均分配處理器時間2）面向所有線程平均分配處理器時間701）面向所有應用程序平均分配處理器時間假定系統(tǒng)中有：N個處理器M個應用程序，每個應用程序有N個線程則每個應用程序至多有1/M的時間去占有N個處理器。例如，系統(tǒng)有4個處理器，2個應用程序。應用程序A有4個線程，B有1個線程。A、B各占一半時間。應用程序運行時，只有1臺處理器忙碌，因此有3/8的處理器時間（即37.5%）被浪費。712）面向所有線程平均分配處理器時間由于應用程序A有4個線程，B有1個線程，因此為A分配4/5的時間，為B分配1/5時間，此時將只有15%的處理器時間浪費（20%×3/4=15%）。若B有2個線程，則將只有16.67%的處理器時間浪費（2/6×2/4=16.67%）。若B有3個線程，則將只有10.7%的處理器時間浪費（3/7×1/4=10.7%）。成組調(diào)度的優(yōu)點：如果一組相互合作的進程或線程能并行執(zhí)行，減少線程的切換，使系統(tǒng)性能改善。因每次調(diào)度可以解決一組線程的處理器分配問題，故可減少調(diào)度頻率，減少調(diào)度開銷。723．專用處理器分配方式1989年Tucker提出。該方式是指在一個應用程序執(zhí)行期間，專門為該應用程序分配一組處理器。這組處理器僅供該應用程序?qū)Ｓ?。直至該應用程序完成。很明顯，這會造成處理機的嚴重浪費。例如，有一個線程為了和另一個線程保持同步而阻塞起來時，為該線程分配的處理器就會空閑。73把專用處理器分配方式用于并發(fā)程度相當高的多處理機環(huán)境，是根據(jù)下述理由：具有數(shù)十乃至數(shù)百個處理機的高度并行系統(tǒng)中，每個處理機的投資費用在整個系統(tǒng)中只占很小的一部分。對系統(tǒng)性能和效率來說，單個處理器的利用率已遠不像在單機系統(tǒng)中那么重要。在一個應用程序的整個運行過程中，由于每個進程或線程專用一臺處理器，因此可以完全避免進程或線程的切換，從而大大加速了程序的運行。74Tucker在一個具有16個處理器的系統(tǒng)中，運行兩個應用程序：一個是矩陣相乘程序，另一個是快速傅里葉變換(FFT)。每個應用程序所包含線程數(shù)是可以改變的，從1個到24個。應用程序的加速比與線程數(shù)目有關。當每個應用程序中含有7～8個線程時，可獲得最高加速比；當每個應用程序含有的線程數(shù)大于8個時，加速比開始下降。這是因為該系統(tǒng)總共有16個處理器，當兩個進程各有8個線程時，正好是每個線程能分得1臺處理器；當超過8個線程時，就不能保證每個線程有1個處理器，因而會出現(xiàn)線程切換問題。線程愈多切換就會愈頻繁，反而會使加速比下降。結(jié)論：在同時加工的應用程序中，其線程數(shù)的總和，不應超過系統(tǒng)中處理器數(shù)目。類似單機系統(tǒng)中的請求頁式內(nèi)存分配753.5產(chǎn)生死鎖的原因和必要條件

死鎖(deadLock)定義——多個進程在運行過程中因爭奪資源而造成的一種僵局，當進程處于這種僵局狀態(tài)時，若無外力作用，它們都將無法再向前推進。死鎖定義——一組進程處于死鎖狀態(tài)是指：如果在一個進程集合中的每一個進程都在等待只能由該集合中的其它一個進程才能引發(fā)的事件，則稱一組進程或系統(tǒng)發(fā)生了死鎖?！獙O鐘秀主編《操作系統(tǒng)教程》死鎖定義：一組競爭系統(tǒng)資源或相互通信的進程間相互的“永久”阻塞?！猍美]WilliamStallings著《操作系統(tǒng)——內(nèi)核與設計原理(第四版）》763.5.1產(chǎn)生死鎖的原因可歸結(jié)為兩點：競爭資源進程間推進順序非法

773.5.2產(chǎn)生死鎖的必要條件四個必要條件：互斥條件：進程對所分配到的資源進行排他性使用請求和保持條件：進程提出了新的資源請求，但又對自己已獲得的資源保持不放不剝奪條件：進程已獲得的資源，在未使用完之前，不能被剝奪環(huán)路等待條件：發(fā)生死鎖時，存在進程-資源的等待鏈783.5.3處理死鎖的基本方法可歸結(jié)為四種：預防死鎖、避免死鎖、檢測死鎖、解除死鎖預防死鎖——通過設置某些限制條件，去破壞產(chǎn)生死鎖的四個必要條件中的一個或幾個條件，來預防發(fā)生死鎖。缺點：可能導致系統(tǒng)資源利用率和系統(tǒng)吞吐量的降低。——較嚴格的限制條件

避免死鎖——并不需要事先采取各種限制措施去破壞產(chǎn)生死鎖的四個必要條件，而是在資源動態(tài)分配過程中，用某種方法防止系統(tǒng)進入不安全狀態(tài)，從而避免死鎖。目前在較完善的系統(tǒng)中，常用此方法來避免死鎖?！灰^弱的限制條件

79檢測死鎖——并不事先采取任何限制措施，也不必檢查系統(tǒng)是否已經(jīng)進入不安全區(qū)，允許系統(tǒng)在運行過程中發(fā)生死鎖，但可通過系統(tǒng)設置的檢測機構，及時檢測出死鎖的發(fā)生，然后采取適當?shù)拇胧瑥南到y(tǒng)中將已發(fā)生的死鎖清除掉。

——這是與檢測死鎖相配套的措施。常用的方法是撤消或掛起一些進程，以便回收一些資源，分配給已處于阻塞狀態(tài)的進程，使之轉(zhuǎn)為就緒狀態(tài)，以繼續(xù)運行。——實現(xiàn)上難度最大。

解除死鎖803.6預防和避免死鎖的方法3.6.1預防死鎖3.6.2避免死鎖813.6.1預防死鎖方法是使四個必要條件中的一個或幾個條件不能成立，來防止死鎖的發(fā)生。2．屏棄“請求并保持”條件資源的一次性分配（靜態(tài)分配）

優(yōu)點：簡單，易實現(xiàn)。

缺點：資源利用率低；使進程延遲運行（僅當能獲得全部資源時，才能開始運行）1．破壞“互斥”條件采用Spooling技術，可以允許若干個進程同時產(chǎn)生輸出。不足：Spooling技術并不適用于所有資源，而且它對磁盤空間的競爭也可能引起死鎖。823．屏棄“不剝奪”條件4．屏棄“環(huán)路等待”條件采用資源“按號分配”缺點：限制了新類型設備的增加；經(jīng)常發(fā)生進程使用資源的順序與系統(tǒng)規(guī)定的順序不同，造成資源浪費；會限制用戶簡單、自主地編程。缺點：▲實現(xiàn)起來比較復雜且要付出很大代價。（前后兩次打印輸出的信息，中間有一段是另一進程的）▲可能因為反復申請資源而使進程的執(zhí)行被無限地推遲，增加了系統(tǒng)開銷，降低了系統(tǒng)吞吐量。當一個進程已經(jīng)保持了某些資源，再提出新的資源請求而不能滿足時，必須釋放它已經(jīng)保持了的資源，待以后需要時再重新申請。

833.6.2避免死鎖——銀行家算法

1.安全狀態(tài)

安全狀態(tài)——

系統(tǒng)能按某種進程順序P1，P2，…，Pn（稱<P1，P2，…，Pn>為安全序列），來為每個進程P分配其所需資源，直至滿足每個進程對資源的最大需求，使每個進程都可順利地完成。

不安全狀態(tài)——

如果系統(tǒng)無法找到這樣一個安全序列，則稱系統(tǒng)處于不安全狀態(tài)。

并非所有不安全狀態(tài)都是死鎖狀態(tài)，但它遲早會進入死鎖狀態(tài)。只要系統(tǒng)處于安全狀態(tài)，便可避免進入死鎖狀態(tài)。842.安全狀態(tài)之例

設系統(tǒng)中有3個進程P1、P2、P3，共有12臺磁帶機。

進程P1總共需要10臺磁帶機，P2和P3分別要求4臺和9臺。

假設在T0時刻，進程P1、P2、P3已分別獲得5、2、2臺磁帶機，尚有3臺空閑未分配，如下表所示：

進程最大需求已分配可用數(shù)P1P2P310495223經(jīng)分析，T0時刻系統(tǒng)是安全的，因為這時存在一個安全序列<P2，P1，P3>，即只要系統(tǒng)按此進程序列分配資源，就能使每一個進程都順利完成。如果不按安全序列分配資源，則系統(tǒng)可能進入不安全狀態(tài)。例如，在T0時刻以后，P3又申請1臺，系統(tǒng)將剩余的3臺中的1臺分配給P3，則系統(tǒng)便進入不安全狀態(tài)。85銀行家算法銀行家算法:在資源動態(tài)分配過程中，若分配后系統(tǒng)狀態(tài)仍是安全的，則同意分配，否則將拒絕分配，這樣可防止系統(tǒng)進入不安全狀態(tài)，從而避免死鎖。最具代表性的避免死鎖的算法，是Dijkstra的銀行家算法。863.利用銀行家算法避免死鎖1）銀行家算法中的數(shù)據(jù)結(jié)構可利用資源向量Available是一個含有m個元素的數(shù)組，其中每一個元素代表一類可用資源數(shù)目，m是資源種類數(shù)。如……

最大需求矩陣Max

是一個n×m矩陣，它定義了系統(tǒng)中n個進程中的每一個進程對m類資源的最大需求數(shù)。如……

分配矩陣Allocation

也是一個n×m矩陣，它定義了系統(tǒng)中每一類資源當前已分配給每一個進程的資源數(shù)。如……

需求矩陣Need

也是一個n×m矩陣，用于表示每個進程尚需的各類資源數(shù)。

關系：Need[i，j]=Max[i，j]–Allocation[i，j]872）銀行家算法步驟設Requesti是進程Pi的請求向量，如果Requesti[j]＝K，表示進程Pi需要K個Rj類的資源。當Pi發(fā)出資源請求后，系統(tǒng)按下述步驟進行檢查：①若Requesti[j]≤Need[i,j]，轉(zhuǎn)向步驟②；否則認為出錯，因為它需要的資源數(shù)已超過它所宣布的最大值。②若Requesti[j]≤Available[j]，轉(zhuǎn)向步驟③；否則表示尚無足夠資源，Pi須等待。③系統(tǒng)試探著把資源分配給進程Pi，并修改下面的數(shù)值：Available[j]=Available[j]-Requesti[j]Allocation[i,j]=Allocation[i,j]+Requesti[j]Need[i,j]=Need[i,j]-Requesti[j]④系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才真正將資源分配給進程Pi，以完成本次分配；否則，將本次資源分配作廢，恢復原來的資源分配狀態(tài)，讓進程Pi等待（阻塞）。883）安全性算法

判斷安全性的算法可描述如下：

（1）設置兩個向量

①工作向量Work——

它表示系統(tǒng)目前可提供的各類資源數(shù)，有m個元素。在執(zhí)行本算法開始時，Work=Available。

②標志向量Finish——

開始時Finish[i]=false(i=1,2,…,n)；當有足夠資源分配給進程Pi時，再令Finish[i]=True（2）從進程集合中尋找一個能滿足下述條件的進程：

①Finish[i]=False；②Need[i,j]≤Work[j](j=1,2,…,m)若找到，轉(zhuǎn)步驟（3）執(zhí)行；否則，執(zhí)行步驟（4）。

（3）進程Pi可獲得所需全部資源，可執(zhí)行結(jié)束并釋放分配給它的資源。故應執(zhí)行：Work[j]=Work[j]+Allocation[i,j]；Finish[i]=True；返回步驟（2）。

（4）如果所有進程的Finish[i]==True都滿足，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。

894.銀行家算法之例設系統(tǒng)中有5個進程{P0，P1，P2，P3，P4}和3類資源{A，B，C}，各類資源總數(shù)分別為10、5、7，在T0時刻的資源分配情況如下表所示：

MaxABCAllocationABCNeedABCAvailableABCP0P1P2P3P4753322902222433010200（302）

302211002743122（020）600

011

431332（230）

回答問題：（1）T0時刻系統(tǒng)是否安全，為什么？（2）P1發(fā)出請求向量Request1（1，0，2），分析系統(tǒng)是否可同意請求。（3）P4發(fā)出請求向量Request4（3，3，0），分析系統(tǒng)是否可同意請求。（4）P0發(fā)出請求向量Request4（0，2，0），分析系統(tǒng)是否可同意請求。（5）在（4）中，如果P0發(fā)出請求向量Request4（0，1，0），系統(tǒng)是否可同意請求。進程況資源情90（1）T0時刻系統(tǒng)是否安全，為什么？WorkABCNeedABCAllocationABCWork+Available

ABCFinish743745104743160074200230201074510471057truetruetrue進程況資源情利用安全性算法對T0時刻的資源分配情況進行分析(見上表)可知，在T0時刻存在著一個安全序列{P1,P3,P4,P2,P0}，故系統(tǒng)是安全的。332122P1P3P4P2P0200true532011211743true53291（2）P1發(fā)出請求向量Request1（1，0，2），按銀行家算法，分析系統(tǒng)是否可同意請求。(見前頁表格)Request1(1,0,2)≤Need1(1,2,2)Request1(1,0,2)≤Available(3,3,2)系統(tǒng)先假定可為P1分配資源，并修改Available,Allocation1和Need1向量，由此形成資源變化情況如下表所示。MaxABCAllocationABCNeedABCAvailableABCP0P1P2P3P4753322902222433010302302211002743020600011431230進程況資源情92即存在安全序列{P1,P3,P4,P2,P0}，故系統(tǒng)是安全的，可以立即將P1所申請的資源分配給它。實際上，(1)中的安全序列中的第一個進程就是P1，當然對P1的請求可以滿足。再利用安全性算法檢查此時系統(tǒng)是否安全。如下表所示。WorkABCNeedABCAllocationABCWork+Available

ABCFinishP1P3P4P2P0230532743745104702001143160074230221100230201053274374510471057truetruetruetruetrue進程況資源情93（3）P4發(fā)出請求向量Request4(3,3,0)，按銀行家算法，分析系統(tǒng)是否可同意請求。Request4(3,3,0)≤Need4(4,3,1)Request4(3,3,0)≤Available(2,3,0)，讓P4等待。（4）P0發(fā)出請求向量Request4（0，2，0），按銀行家算法，分析系統(tǒng)是否可同意請求。Request0(0,2,0)≤Need0(7,4,3)Request0(3,3,0)≤Available(2,3,0)系統(tǒng)暫時先假定可為P0分配資源，并修改有關數(shù)據(jù)，如書上圖3-19所示。94進行安全性檢查，可用資源Available(2,1,0)已不能滿足任何進程的需要，系統(tǒng)進入不安全狀態(tài)，故系統(tǒng)不能同意P0的請求，讓其阻塞。MaxABCAllocationABCNeedABCAvailableABCP0P1P2P3P4753322902222433030302302211002723020600011431210進程況資源情953.7

死鎖的檢測和解除復習：處理死鎖的方法：預防、避免、檢測、解除預防死鎖的方法——破壞死鎖必要條件破壞“互斥條件”破壞“請求和保持條件”破壞“不剝奪條件”破壞“環(huán)路等待條件”避免死鎖——銀行家算法安全狀態(tài)數(shù)據(jù)結(jié)構算法步驟（安全性算法）963.7.1

死鎖的檢測1.利用資源分配圖檢測死鎖系統(tǒng)死鎖可利用資源分配圖來描述。用圓圈代表一個進程；方框代表一類資源。由于一類資源可能有多個，用方框中的一個點代表該類資源中的一個資源；請求邊由進程(圓圈)指向方框；分配邊始于方框中的一個點，指向圓圈。檢測死鎖的方法很多，下面介紹3種：死鎖定理(資源分配圖法)、Warshell循環(huán)、利用安全性檢測程序。97【例】假設系統(tǒng)中包含P1～P7七個進程，R1～R6六種資源，資源的占有情況和進程對資源的請求情況如下：P1進程持有資源R1

，且等待資源R2；P2進程不持有資源，但等待資源R3

；P3進程不持有資源，但等待資源R2；P4進程持有資源R4

，且等待資源R2、R3

；P5進程持有資源R3

，且等待資源R5；P6進程持有資源R6

，且等待資源R2；P7進程持有資源R5

，且等待資源R4；R1P1R2P2P3P4P5P6R3R4R5R6P7其資源分配圖如圖3-6所示。圖3-6資源分配圖98(1)若資源分配圖中無環(huán)路，則此時系統(tǒng)中無死鎖；(2)如果資源分配圖中有環(huán)路，且每個資源類中僅有一個資源，則系統(tǒng)中發(fā)生了死鎖。此時，環(huán)路是系統(tǒng)發(fā)生死鎖的充要條件，環(huán)路中的進程便為死鎖進程；R1P1R2P2P3P4P5P6R3R4R5R6P7P4P5R3R4R5P7P4、P5、P7為死鎖進程圖3-7可利用資源分配圖來檢測系統(tǒng)中是否存在死鎖：99(3)如果資源分配圖中有環(huán)路，且涉及的資源類中有多個資源，則環(huán)路的存在只是產(chǎn)生死鎖的必要條件而不是充要條件，系統(tǒng)未必一定會發(fā)生死鎖。圖3-8有環(huán)路而無死鎖的例子P1??R1??R2P2P3100對于資源分配圖中有環(huán)路，且涉及的資源類中有多個資源的情況，可利用把資源分配圖簡化的方法，來檢測系統(tǒng)是否存在死鎖（死鎖定理）：①在資源分配圖中，找出一個既非阻塞又非獨立的進程結(jié)點Pi，若其可以獲得所需的全部資源，直到運行結(jié)束，再釋放其占有的全部資源，相當于消去此進程的所有請求邊和分配邊，使之成為孤立結(jié)點。例如，在圖3-9(a)中，將P1的一個分配邊和一個請求邊消去，便形成圖(b)所示的情況。圖3-9資源分配圖的簡化(a)P1??R1??R2P2P3(b)P1??R1??R2P2P3101②P1釋放資源后，便可使P2獲得所需的全部資源，直到運行結(jié)束，再釋放其占有的全部資源，形成圖(c)所示的情況。③經(jīng)過一系列簡化后，若能消去圖中所有的邊，使所有進程結(jié)點都成為孤立結(jié)點，則稱該圖是可完全簡化的；否則稱該圖為不可完全簡化的。死鎖定理：系統(tǒng)為死鎖狀態(tài)的充要條件是：當且僅當該狀態(tài)的資源分配圖是不可完全簡化的。P1??R1??R2P2P3(b)P1??R1??R2P2P3(c)R1P1????R2P2P3(d)1022.死鎖檢測算法(一)每個資源類中含有一個資源的死鎖檢測算法：例假設系統(tǒng)中包含P1～P3三個進程，R1～R5五種資源(每種資源有1個資源)，資源占有情況和進程對資源請求情況如下：P1進程持有資源R1

、R5，且等待資源R3；P2進程持有資源R3

、R4，且等待資源R2

；P3進程持有資源R2，且等待資源R5

。進程占用資源P1R1P3R2P2R3P2R4P1R5進程等待資源P1R3P2R2P3R5資源占用表資源等待表圖3-10資源占用表和等待表用資源“占用表”和“等待表”來記錄上述情況：103(1)死鎖檢測程序根據(jù)兩張表中記錄的情況用一個矩陣來表示，矩陣的每個元素指出進程間是否存在“等待占用關系”。矩陣的結(jié)構如下所示：P1P2…PnP1b11b12…b1nP2b21b22…b2n……………Pnbn1bn2…bnn矩陣的元素bij=1表示Pi等待Pj占用的資源0表示Pi與Pj不存在等待占用關系104(2)死鎖檢測程序運行如下程序(Warshell的傳遞閉包算法)：

fork:=1tondofori:=1tondoforj:=1tondo

bij:=bij∨(bik∧bkj)“∨”為“或”；“∧”為“與”運算符。如果bik∧bkj為1，表示Pi與Pj之間有間接等待關系，bij:=bij∨(bik∧bkj)能夠使Pi與Pj原來就有的等待占有關系保持bij為“1”，并且在Pi與Pj之間有間接等待關系時也把bij置為“1”。當死鎖檢測程序運行上述程序后，矩陣中有某個bii取值為“1”時，就表示存在一組進程，它們循環(huán)等待資源，即出現(xiàn)了環(huán)路(死鎖)。此法不適用于每類資源有多個資源的情況。為什么？105P1P2P3P1010P2001P3100例如，對于圖3-10的兩張表，可構造出如下矩陣：對k=1,對各i,j進行檢測，因b31=1和b12=1,故b32被置為“1”；1對k=2,對各i,j進行檢測，通過(b12∧b23)使b13=1,通過(b32∧b23)使b33=1；11對k=3,對各i,j進行