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

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

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

高級、中級和低級調度

1．高級調度——又稱作業調度或長調度

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

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

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

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

進程調度可采用下述兩種調度方式：

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

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

優先權原則；

短作業優先原則；

時間片原則。

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

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

主要目的：

為了提高內存的利用率和系統的吞吐量。

主要介紹進程調度和作業調度。三種調度相比較：進程調度的運行頻率最高

作業調度頻率最低

中級調度界于之間

63.1.2調度隊列模型三種類型的調度隊列模型：

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

具有掛起狀態的系統。

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

（1）周轉時間短。

評價批處理系統的準則之一周轉時間——是指從作業被提交給系統開始，到作業完成這段時間間隔。平均周轉時間

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

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

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

（4）優先權準則

截止時間——

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

（3）截止時間的保證

評價實時系統的準則之一113.1.3選擇調度方式和調度算法的若干準則2.面向系統的準則

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

吞吐量——單位時間內系統所完成的作業數

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

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

123.2調度算法3.2.1先來先服務調度算法3.2.2短作業(進程)優先調度算法3.2.3高優先權優先調度算法3.2.4高響應比優先調度算法3.2.5基于時間片的輪轉調度算法133.2.1先來先服務調度算法FCFS調度算法是一種最簡單的調度算法。既可用于作業調度，也可用于進程調度。用于作業調度中：從后備隊列作業中，選擇一個或幾個最先進入該隊列的作業，將它們調入內存，為它們分配資源、創建進程，然后放入進程就緒隊列。用于進程調度時：從就緒隊列中，選擇一個最先進入該隊列的進程，為之分配處理機，使之投入運行。該進程一直運行到完成或發生某事件而阻塞后，才放棄處理機。——非搶占式14【例3-1】設在單道系統中用FCFS算法調度如下作業，請完成下表。進程名

ABCDE平

均

到達時間

9:00

9:10

9:30

10:00

10:15

服務時間

30分鐘

1小時

10分鐘

50分鐘

20分鐘

完成時間

周轉時間

帶權周轉時間

80分鐘

9:30

30分鐘10:3070分鐘

10:4011:3090分鐘

11:5095分鐘

11.3371.84.7573分鐘

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

短作業優先（SJF）調度算法——

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

ABCDE平

均

到達時間

9:00

9:10

9:30

10:00

10:15

服務時間

30分鐘

1小時

10分鐘

50分鐘

20分鐘

完成時間

周轉時間

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

當多個作業同時到達時，SJF算法可使平均周轉時間最短。183.2.3高優先權優先調度算法

引入的目的：為了照顧緊迫型作業，使之在進入系統后便獲得優先處理。優先權作業調度——

系統從后備中選擇一個或幾個優先權最高的作業，將它調入內存運行。

優先權進程調度——

系統將處理機分配給就緒隊列中一個優先權最高的進程。

適用范圍：

批處理系統的作業調度

多種操作系統的進程調度

還適用于實時系統

191．優先權進程調度算法的類型非搶占式優先權算法

搶占式優先權算法

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

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

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

202．優先權的類型

靜態優先權動態優先權

1）靜態優先權

靜態優先權——它是在創建進程時確定的，且在進程整個運行期間保持不變。優先權一般用某一范圍內的一個整數來表示。有的系統用“0”表示最高優先權，數值越大，優先權越低；有的系統恰恰相反。

確定優先權的依據：——常有三方面

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

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

靜態優先權的優缺點：優點：簡單易行，系統開銷小。

缺點：優先權低的作業（進程）可能長期得不到調度。

212）動態優先權

動態優先權——在創建進程時所賦予的優先權，是可以隨進程得推進，或隨其等待時間的增加而改變的，以便獲得更好的調度性。

例如：

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

在采用搶占式優先權調度算法時，如果再規定當前執行進程以速率β下降，則可防止一個長作業長期壟斷處理機。

22UNIX采用計算的方法動態改變進程的優先數。在UNIXSystemV版本中，進程優先數p_pri的算式如下：

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

(1)列出所有作業進入內存時間及結束時間。

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

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

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

高響應比優先調度算法——

每次要進行作業調度時，系統首先計算后備隊列中各作業的響應比，然后選擇一個或若干個響應比最高的作業調入內存執行。

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

(1)列出所有作業進入內存時間及結束時間。

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

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

用于進程調度。早期，分時系統采用的是簡單的時間片輪轉法；90年代后，廣泛采用多級反饋隊列調度算法。

1．時間片輪轉法

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

每次調度時，把CPU分配給隊首進程，并讓它執行一個時間片；

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

時間片的大小：幾ms～幾百ms。

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

(1)列出所有作業進入內存時間及結束時間。

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

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

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

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

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

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

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

為了保證要求較高的硬實時任務能及時運行，在實時系統中還應具有快速切換機制，以保證能進行任務的快速切換。該機制應具有下述兩方面的能力：對外部中斷的快速響應能力。要求系統具有快速硬件中斷機構，還應使禁止中斷的時間間隔盡量短，以免耽誤其它緊迫任務。快速的任務分派能力。在完成任務調度后，便應進行任務切換。為了提高分派程序進行任務切換時的速度，應使系統中的每個運行功能單位適當的小，以減少任務切換的時間開銷。453.3.2實時調度算法的分類按實時任務性質不同來劃分：硬實時調度算法軟實時調度算法按調度方式的不同非搶占調度算法搶占調度算法因調度程序調度時間的不同靜態調度算法——進程執行前，調度程序便已經決定了個進程間的執行順序動態調度算法多處理機環境下集中式調度分布式調度46下面討論按調度方式的不同對調度算法進行分類：1．非搶占式調度算法算法比較簡單，易于實現，故在一些小型實時系統或要求不太嚴格的實時控制系統中，經常采用之。又可分成兩種：非搶占式輪轉調度算法。常用于工業生產的群控系統中,可用于要求不太嚴格的實時控制系統中。非搶占式優先調度算法。如果系統中存在要求較為嚴格的任務(響應時間為數百毫秒)，可采用此算法。可用于有一定要求的實時控制系統中。47進程1進程2…進程n實時進程實時進程請求調度調度實時進程運行調度時間(a)非搶占輪轉調度當前進程

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

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

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

DeadlingFirst)算法根據任務的開始截止時間來確定任務的優先級。截止時間愈早，其優先級愈高。實時任務就緒隊列按各任務的截止時間的早晚排序。可用于搶占式調度，也可用于非搶占式調度。52

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

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

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

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

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

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

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

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

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

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

避免死鎖——并不需要事先采取各種限制措施去破壞產生死鎖的四個必要條件，而是在資源動態分配過程中，用某種方法防止系統進入不安全狀態，從而避免死鎖。目前在較完善的系統中，常用此方法來避免死鎖。——只要較弱的限制條件

79檢測死鎖——并不事先采取任何限制措施，也不必檢查系統是否已經進入不安全區，允許系統在運行過程中發生死鎖，但可通過系統設置的檢測機構，及時檢測出死鎖的發生，然后采取適當的措施，從系統中將已發生的死鎖清除掉。

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

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

優點：簡單，易實現。

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

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

1.安全狀態

安全狀態——

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

不安全狀態——

如果系統無法找到這樣一個安全序列，則稱系統處于不安全狀態。

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

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

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

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

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

最大需求矩陣Max

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

分配矩陣Allocation

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

需求矩陣Need

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

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

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

（1）設置兩個向量

①工作向量Work——

它表示系統目前可提供的各類資源數，有m個元素。在執行本算法開始時，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)若找到，轉步驟（3）執行；否則，執行步驟（4）。

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

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

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

MaxABCAllocationABCNeedABCAvailableABCP0P1P2P3P4753322902222433010200（302）

302211002743122（020）600

011

431332（230）

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

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

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

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

死鎖的檢測1.利用資源分配圖檢測死鎖系統死鎖可利用資源分配圖來描述。用圓圈代表一個進程；方框代表一類資源。由于一類資源可能有多個，用方框中的一個點代表該類資源中的一個資源；請求邊由進程(圓圈)指向方框；分配邊始于方框中的一個點，指向圓圈。檢測死鎖的方法很多，下面介紹3種：死鎖定理(資源分配圖法)、Warshell循環、利用安全性檢測程序。97【例】假設系統中包含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)若資源分配圖中無環路，則此時系統中無死鎖；(2)如果資源分配圖中有環路，且每個資源類中僅有一個資源，則系統中發生了死鎖。此時，環路是系統發生死鎖的充要條件，環路中的進程便為死鎖進程；R1P1R2P2P3P4P5P6R3R4R5R6P7P4P5R3R4R5P7P4、P5、P7為死鎖進程圖3-7可利用資源分配圖來檢測系統中是否存在死鎖：99(3)如果資源分配圖中有環路，且涉及的資源類中有多個資源，則環路的存在只是產生死鎖的必要條件而不是充要條件，系統未必一定會發生死鎖。圖3-8有環路而無死鎖的例子P1??R1??R2P2P3100對于資源分配圖中有環路，且涉及的資源類中有多個資源的情況，可利用把資源分配圖簡化的方法，來檢測系統是否存在死鎖（死鎖定理）：①在資源分配圖中，找出一個既非阻塞又非獨立的進程結點Pi，若其可以獲得所需的全部資源，直到運行結束，再釋放其占有的全部資源，相當于消去此進程的所有請求邊和分配邊，使之成為孤立結點。例如，在圖3-9(a)中，將P1的一個分配邊和一個請求邊消去，便形成圖(b)所示的情況。圖3-9資源分配圖的簡化(a)P1??R1??R2P2P3(b)P1??R1??R2P2P3101②P1釋放資源后，便可使P2獲得所需的全部資源，直到運行結束，再釋放其占有的全部資源，形成圖(c)所示的情況。③經過一系列簡化后，若能消去圖中所有的邊，使所有進程結點都成為孤立結點，則稱該圖是可完全簡化的；否則稱該圖為不可完全簡化的。死鎖定理：系統為死鎖狀態的充要條件是：當且僅當該狀態的資源分配圖是不可完全簡化的。P1??R1??R2P2P3(b)P1??R1??R2P2P3(c)R1P1????R2P2P3(d)1022.死鎖檢測算法(一)每個資源類中含有一個資源的死鎖檢測算法：例假設系統中包含P1～P3三個進程，R1～R5五種資源(每種資源有1個資源)，資源占有情況和進程對資源請求情況如下：P1進程持有資源R1

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

、R4，且等待資源R2

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

。進程占用資源P1R1P3R2P2R3P2R4P1R5進程等待資源P1R3P2R2P3R5資源占用表資源等待表圖3-10資源占用表和等待表用資源“占用表”和“等待表”來記錄上述情況：103(1)死鎖檢測程序根據兩張表中記錄的情況用一個矩陣來表示，矩陣的每個元素指出進程間是否存在“等待占用關系”。矩陣的結構如下所示：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”時，就表示存在一組進程，它們循環等待資源，即出現了環路(死鎖)。此法不適用于每類資源有多個資源的情況。為什么？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進行