第三章處理機調(diào)度與死鎖2023/2/31操作系統(tǒng)講義主要內(nèi)容

3.1處理機調(diào)度的層次

3.2調(diào)度隊列模型和調(diào)度準則

3.3幾種調(diào)度算法

3.4實時調(diào)度

3.5產(chǎn)生死鎖的原因和必要條件

3.6預(yù)防死鎖的方法

3.7

死鎖的檢測和解除2023/2/32第二章進程管理3.1處理機調(diào)度的層次作業(yè)的基本概念1.高級調(diào)度（HighLevelScheduling）主要功能：根據(jù)某種算法，把外存中把處于后備隊列中的那些作業(yè)調(diào)入內(nèi)存，當(dāng)作業(yè)完成時做善后處理。

作業(yè)（Job）：包含通常的程序和數(shù)據(jù)，并且配有作業(yè)說明書；作業(yè)步（JobStep）：“編譯”

->“連接裝配”->“運行”；作業(yè)流：若干個作業(yè)在系統(tǒng)外存形成的輸入流。

作業(yè)控制塊JCB（JobControlBlock）通常包含：作業(yè)標識、用戶名稱、用戶賬戶、作業(yè)類型（CPU繁忙，I/O繁忙，批量型，終端型）、作業(yè)狀態(tài)、調(diào)度信息（優(yōu)先級，作業(yè)運行時間）、資源需求（運行時間，內(nèi)存，I/O類型數(shù)量）、進入系統(tǒng)時間、開始處理時間、作業(yè)完成時間、作業(yè)退出時間、資源使用情況。2023/2/33第二章進程管理3.1處理機調(diào)度的層次1.高級調(diào)度（HighLevelScheduling）作業(yè)調(diào)度：是根據(jù)作業(yè)控制塊中的信息，審查系統(tǒng)能否滿足用戶作業(yè)的資源需求，以及按照一定的算法，從外存后備隊列中選取某些作業(yè)調(diào)入內(nèi)存，為它們創(chuàng)建進程、分配必要的資源，然后將進程插入就緒隊列，準備執(zhí)行。目的：提高內(nèi)存利用率和系統(tǒng)吞吐量，使那些暫時不能運行的進程不再占用內(nèi)存，把它們調(diào)至外存（存儲管理中的對換功能）。

1）接收多少個作業(yè)到內(nèi)存：取決于多道程序度

2）接收哪些作業(yè)：取決于調(diào)度算法最簡單：先來先服務(wù)調(diào)度算法最常用：短作業(yè)優(yōu)先調(diào)度算法較常用：優(yōu)先級調(diào)度算法比較好：響應(yīng)比高者優(yōu)先調(diào)度算法2.中級調(diào)度（IntermediateLevelScheduling）2023/2/34第二章進程管理3.1處理機調(diào)度的層次3.低級調(diào)度（LowLevelScheduling）它所調(diào)度的對象是進程（或內(nèi)核級線程），當(dāng)CPU需要重新分配時，利用一定的算法把它分配給進程，它是最基本的調(diào)度。進程調(diào)度的功能

（1）保存處理機的現(xiàn)場信息；（2）按照某種算法選擇進程（如優(yōu)先數(shù)算法，輪轉(zhuǎn)算法）

（3）把處理器分配給進程。進程調(diào)度的三個基本機制（1）排隊器：事先將系統(tǒng)所有就緒進程排成一個或多個隊列，方便調(diào)度程序最快找到它；（2）分派器（分派程序）：把進程調(diào)度程序選定的進程從就緒隊列移出，切換上下文，然后把CPU分配給它；（3）上下文切換機制：保存當(dāng)前程序的上下文，裝入分派程序的上下文；移出分派程序，裝入新選進程的CPU信息；2023/2/35第二章進程管理3.1處理機調(diào)度的層次進程調(diào)度方式

3.低級調(diào)度（LowLevelScheduling）非搶占方式：一旦處理機分配給某個進程，不管它要運行多長時間，都讓它一直運行下去，決不會因為其它原因而搶占正在運行進程的處理機。這種方式下引起進程調(diào)度的因素包括：執(zhí)行完畢或者發(fā)生某事件不能再執(zhí)行執(zhí)行進程提出I/O請求而暫停執(zhí)行在進程通信或者同步過程中執(zhí)行了某種原語操作，如P，Block等優(yōu)點：實現(xiàn)簡單，系統(tǒng)開銷小，適用于大多數(shù)批處理系統(tǒng)；缺點：難以滿足緊急任務(wù)要求，可能造成難以預(yù)料的后果。2023/2/36第二章進程管理3.1處理機調(diào)度的層次進程調(diào)度方式

3.低級調(diào)度（LowLevelScheduling）搶占方式：允許調(diào)度程序根據(jù)某種原則去暫停某個正在執(zhí)行的進程，這些原則主要包括：優(yōu)先權(quán)原則：優(yōu)先權(quán)高的進程可以搶占當(dāng)前優(yōu)先權(quán)低的進程的CPU；短作業(yè)（進程）優(yōu)先原則：短作業(yè)（進程）可以搶占當(dāng)前較長作業(yè)（進程的）CPU；時間片原則：時間片輪轉(zhuǎn)；優(yōu)點：防止一個長進程長時間占用處理機，公平服務(wù)，適合實時任務(wù)的需求；缺點：需要付出較大的開銷。2023/2/37第二章進程管理3.2

調(diào)度隊列模型和調(diào)度準則僅有進程調(diào)度的調(diào)度隊列模型通常在分時系統(tǒng)中只設(shè)置進程調(diào)度，每個用戶建立一個進程，系統(tǒng)利用堆棧、樹或者鏈表來管理就緒進程隊列，就緒進程以FIFO隊列形式組織。

1.調(diào)度隊列模型進程執(zhí)行時可能出現(xiàn)的三種情況：在給定時間片完成，釋放處理機進入完成狀態(tài)；本次時間片內(nèi)未完成，放入就緒隊列尾部；因為某事件被阻塞，放入阻塞隊列。就緒隊列CPU阻塞隊列交互用戶時間片完進程調(diào)度等待事件進程完成事件出現(xiàn)2023/2/38第二章進程管理3.2

調(diào)度隊列模型和調(diào)度準則具有高級和低級調(diào)度的調(diào)度隊列模型在批處理系統(tǒng)中，作業(yè)調(diào)度按照一定的算法從外存的后備隊列選擇一批作業(yè)調(diào)入內(nèi)存，建立進程，送入就緒隊列，然后按照一定的進程調(diào)度算法選擇進程，分配CPU。

1.調(diào)度隊列模型就緒隊列CPU阻塞隊列作業(yè)調(diào)度時間片完進程調(diào)度等待事件1進程完成事件1出現(xiàn)隊列后備阻塞隊列阻塞隊列等待事件2等待事件n事件2出現(xiàn)事件n出現(xiàn)……隊……2023/2/39第二章進程管理3.2

調(diào)度隊列模型和調(diào)度準則

1.調(diào)度隊列模型具有高級和低級調(diào)度的調(diào)度隊列模型的特點：（1）采用優(yōu)先權(quán)就緒隊列，隊首進程優(yōu)先權(quán)最高，或者采用無序鏈表方式；（2）設(shè)置多個阻塞隊列，每個隊列對應(yīng)于某一種進程阻塞事件；2023/2/310第二章進程管理3.2

調(diào)度隊列模型和調(diào)度準則同時具有三級調(diào)度的調(diào)度隊列模型可把進程的就緒狀態(tài)分成內(nèi)存就緒和外存就緒，類似地，阻塞狀態(tài)也可進一步分成內(nèi)存阻塞和外存阻塞，調(diào)出操作可使進程狀態(tài)由內(nèi)存就緒轉(zhuǎn)為外存就緒，內(nèi)存阻塞轉(zhuǎn)為外存阻塞；中級調(diào)度可使外存就緒轉(zhuǎn)為內(nèi)存就緒。

1.調(diào)度隊列模型就緒隊列CPU緒掛起隊列就作業(yè)調(diào)度時間片完進程調(diào)度進程完成事件出現(xiàn)隊列后備塞掛隊隊列阻阻塞隊列等待事件起批量作業(yè)掛起事件出現(xiàn)中級調(diào)度2023/2/311第二章進程管理3.2

調(diào)度隊列模型和調(diào)度準則面向用戶的準則

（1）周轉(zhuǎn)時間短（批處理系統(tǒng)）

平均周轉(zhuǎn)時間T的計算如下：平均帶權(quán)周轉(zhuǎn)時間W的計算如下：

（2）響應(yīng)時間快（分時系統(tǒng)）：是指從用戶通過鍵盤提交一個請求開始，直到系統(tǒng)首次響應(yīng)為止的時間必須快；

（3）截止時間的保證（實時系統(tǒng)）：是指某任務(wù)必須開始執(zhí)行的最遲時間，或必須完成的最遲時間必須有保證；

（4）優(yōu)先權(quán)準則：遵循優(yōu)先權(quán)準則讓某些緊急的作業(yè)得到及時處理。2.選擇調(diào)度方式和算法的若干準則2023/2/312第二章進程管理3.2

調(diào)度隊列模型和調(diào)度準則面向系統(tǒng)的準則

2.選擇調(diào)度方式和算法的若干準則（1）系統(tǒng)吞吐量高：這個是評價批處理系統(tǒng)性能的另一個重要指標，因此是選擇批處理作業(yè)調(diào)度的重要準則。吞吐量是指單位時間內(nèi)系統(tǒng)完成的作業(yè)數(shù)，它直接和作業(yè)的平均長度有關(guān)；（2）處理機利用率好：CPU價格昂貴，利用率成為衡量系統(tǒng)性能的重要指標；（3）各類資源的平衡利用：不僅要使處理機利用率高，還要有效地利用其它各類資源，如內(nèi)存、外存和I/O設(shè)備，適當(dāng)?shù)恼{(diào)度方式和算法可以使系統(tǒng)中的各類資源處于忙碌狀態(tài)。2023/2/313第二章進程管理3.3

調(diào)度算法是一種最簡單的調(diào)度算法，適用于作業(yè)調(diào)度和進程調(diào)度，每次調(diào)度都是從后備隊列中選擇一個或者多個最先進入該隊列的作業(yè)，將它們調(diào)入內(nèi)存，分配資源，創(chuàng)建進程，然后放入就緒隊列。

1.先來先服務(wù)調(diào)度算法FCFS（FirstComeFirstService）FCFS算法比較有利于長作業(yè)（進程），不利于短作業(yè)（進程）進程名到達時間服務(wù)時間開始執(zhí)行時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間A010111B110011011001C21101102100100D31001022021991.992023/2/314第二章進程管理3.3

調(diào)度算法是指對短作業(yè)或者短進程優(yōu)先調(diào)度的算法，適用于作業(yè)調(diào)度和進程調(diào)度，SJF算法就是從后備隊列中選擇一個運行時間最短的作業(yè)，然后把它們調(diào)入內(nèi)存運行。

2.短作業(yè)優(yōu)先調(diào)度算法SJF（ShortJobFirst）SJF的優(yōu)點：能有效地降低作業(yè)的平均等待時間，提高系統(tǒng)吞吐量；進程名到達時間服務(wù)時間開始執(zhí)行時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間A030331B145982C223531.5D35914112.2SJF的缺點：1）對長作業(yè)不利；2）未考慮作業(yè)的緊迫度；3）用戶估計執(zhí)行時間的不準確性。2023/2/315第二章進程管理3.3

調(diào)度算法

3.FCFS和SJF的性能比較算法進程名ABCDE平均到達時間01234服務(wù)時間43524FCFS完成時間47121418周轉(zhuǎn)時間461011149帶權(quán)周轉(zhuǎn)時間1225.53.52.8SJF完成時間4918613周轉(zhuǎn)時間4816398帶權(quán)周轉(zhuǎn)時間12.673.21.52.252.12023/2/316第二章進程管理3.3

調(diào)度算法是為了照顧緊迫型作業(yè)，使之在進入系統(tǒng)后便獲得優(yōu)先處理，該算法會把處理機分配給優(yōu)先級最高的作業(yè)（或者進程）。1）非搶占式優(yōu)先權(quán)調(diào)度算法，適用于批處理系統(tǒng)或?qū)崟r性要求不高的系統(tǒng)；

2）搶占式優(yōu)先權(quán)調(diào)度算法，能更好地滿足緊迫作業(yè)，適合于嚴格的實時系統(tǒng)或者對性能要求較高的批處理和分時系統(tǒng)中。

4.高優(yōu)先權(quán)優(yōu)先調(diào)度算法（PriorityJobFirst）2023/2/317第二章進程管理3.3

調(diào)度算法

4.高優(yōu)先權(quán)優(yōu)先調(diào)度算法（PriorityJobFirst）優(yōu)先權(quán)的類型靜態(tài)優(yōu)先權(quán)：創(chuàng)建進程時確定，在整個運行期間保持不變；進程類型，系統(tǒng)進程要比用戶進程優(yōu)先級高；進程對資源的要求，要求少的優(yōu)先級高；用戶要求，用戶進程的緊迫程度。優(yōu)點：簡單易行，系統(tǒng)開銷小缺點：不夠精確，可能使優(yōu)先權(quán)低的作業(yè)（進程）長期得不到調(diào)度動態(tài)優(yōu)先權(quán)：創(chuàng)建時賦予，可以隨著進程的推進或隨其等待時間的增加而改變，以便獲得更好的調(diào)度性能。優(yōu)點：使調(diào)度更加公平，調(diào)度性能高缺點：系統(tǒng)開銷稍大2023/2/318第二章進程管理3.3

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

每個作業(yè)的優(yōu)先級動態(tài)計算，作業(yè)的優(yōu)先級隨等待時間的增加而不斷提高。

4.高優(yōu)先權(quán)優(yōu)先調(diào)度算法（PriorityJobFirst）結(jié)論：如果作業(yè)等待時間相同，要求服務(wù)時間越短，優(yōu)先級越高，該算法利于短作業(yè)；如果要求服務(wù)時間相同，那么等待時間越長，優(yōu)先權(quán)越高，它實現(xiàn)的是先來先服務(wù)；對于長作業(yè)，作業(yè)的優(yōu)先級隨著等待時間的增加而提高，如果等待時間足夠長也可以獲得處理機。優(yōu)點：既照顧了短作業(yè)，又考慮了作業(yè)的先后順序，使長作業(yè)也可以得到服務(wù)；缺點：但優(yōu)先級的計算增加了系統(tǒng)的開銷。響應(yīng)比RP=等待時間+要求服務(wù)時間要求服務(wù)時間=響應(yīng)時間要求服務(wù)時間2023/2/319第二章進程管理3.3

調(diào)度算法基本原理系統(tǒng)將所有就緒進程按照先來先服務(wù)的原則排成一個隊列，每次調(diào)度把CPU分配給隊首進程，并令其執(zhí)行一個時間片，當(dāng)執(zhí)行時間片用完，調(diào)度程序停止其執(zhí)行，并把它送到隊列尾部。

5.基于時間片的輪轉(zhuǎn)調(diào)度算法（RoundRobin）時間片大小如果太小利于短作業(yè)，但是會頻繁中斷，進程上下文切換，增加系統(tǒng)開銷；如果太大則每個進程都能在時間片內(nèi)完成，則退化為FCFS算法，無法滿足交互式用戶的需求。2023/2/320第二章進程管理3.3

調(diào)度算法

5.基于時間片的輪轉(zhuǎn)調(diào)度算法（RoundRobin）(a)q=1(b)q=4123456789101112131415161718ABACBDAECBDAECABCDEECECC2023/2/321第二章進程管理3.3

調(diào)度算法——隊列（q=1）時間隊列狀態(tài)時間隊列狀態(tài)0A10DAECB完成1BA11AECD完成2ACB12ECA完成3CBDA13CE4BDAEC14EC5DAECB15CE6AECBD16EC7ECBDA17CE完成8CBDAE18C完成9BDAEC2023/2/322第二章進程管理3.3

調(diào)度算法——隊列（q=4）時間隊列狀態(tài)0A4BCDEA完成7CDEB完成11DEC13ECD完成17CE完成18C完成2023/2/323第二章進程管理3.3

調(diào)度算法

5.時間片輪轉(zhuǎn)法RR算法進程名ABCDE平均到達時間01234服務(wù)時間43524RRq=1完成時間1210181117周轉(zhuǎn)時間1291681311.6帶權(quán)周轉(zhuǎn)時間333.243.253.29RRq=4完成時間47181317周轉(zhuǎn)時間461610139.8帶權(quán)周轉(zhuǎn)時間123.253.252.892023/2/324第二章進程管理3.3

調(diào)度算法調(diào)度算法的實施過程設(shè)置多個就緒隊列，賦予不同的優(yōu)先級，各個隊列優(yōu)先級遞減，時間片遞增；新進程放入第一個隊列尾部，F(xiàn)CFS原則排隊調(diào)度，時間片內(nèi)完成則撤離系統(tǒng)，如果沒完則轉(zhuǎn)入下個隊列尾部，以此類推，在第n個隊列采取時間片輪轉(zhuǎn)調(diào)度；第一隊列空閑，調(diào)度第二隊列，以此類推，新進程如果優(yōu)先級高，可搶占處理機。

6.多級反饋隊列調(diào)度算法（RoundRobinWithMultipleFeedback）2023/2/325第二章進程管理3.3

調(diào)度算法

6.多級反饋隊列調(diào)度算法（RoundRobinWithMultipleFeedback）算法的性能終端型作業(yè)用戶，大多屬于交互型作業(yè)，作業(yè)小；短批處理作業(yè)用戶，周轉(zhuǎn)時間短；長批處理用戶，不用擔(dān)心作業(yè)長期得不到處理。就緒隊列1就緒隊列2就緒隊列3就緒隊列4至CPU至CPU至CPU至CPUS1S2S3（時間片：S1<S2<

S3）新進程2023/2/326第二章進程管理3.4

實時調(diào)度提供必要的信息就緒時間，任務(wù)就緒的起始時間；開始截止時間和完成截止時間；處理時間，一個任務(wù)從開始執(zhí)行直至完成所需的時間；資源要求，任務(wù)執(zhí)行的時候需要的一組資源；優(yōu)先級，對緊迫任務(wù)設(shè)置“絕對”優(yōu)先級，松弛任務(wù)設(shè)置“相對”優(yōu)先級。

1.實現(xiàn)實時調(diào)度的基本條件2023/2/327第二章進程管理3.4

實時調(diào)度

1.實現(xiàn)實時調(diào)度的基本條件具有快速切換機制對外部中斷的快速響應(yīng)能力；快速的任務(wù)分派能力。系統(tǒng)處理能力強采用搶占式調(diào)度機制采用單處理機系統(tǒng)，增強處理能力，減少每個任務(wù)處理時間；采用多處理機調(diào)度單處理機實時調(diào)度條件：2023/2/328第二章進程管理3.4

實時調(diào)度非搶占式調(diào)度算法非搶占式輪轉(zhuǎn)調(diào)度算法；非搶占式優(yōu)先級調(diào)度算法。搶占式調(diào)度算法基于時鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法立即搶占的優(yōu)先權(quán)調(diào)度算法

2.實時調(diào)度算法分類最早截止時間優(yōu)先EDF（EarliestDeadlineFirst）算法

3.常用的幾種實時調(diào)度算法最低松弛度優(yōu)先級LLF（LeastLaxityFirst）算法

任務(wù)的松弛度=必須完成時間-其本身運行時間-當(dāng)前時間

松弛度=0表示該任務(wù)必須馬上執(zhí)行，否則會造成嚴重后果。2023/2/329第二章進程管理3.5

產(chǎn)生死鎖的原因和必要條件競爭資源：多個進程共享資源，資源數(shù)目不足所引起進程對資源的競爭；可剝奪資源和非剝奪性資源競爭非剝奪性資源競爭臨時性資源

1.產(chǎn)生死鎖的原因死鎖（Deadlock）：是指多個進程在運行過程中因爭奪資源而造成的一種僵局（DeadlyEmbrace），當(dāng)進程出現(xiàn)這種僵持狀態(tài)時，若無外力作用，它們將無法再向前推進。2023/2/330第二章進程管理3.5

產(chǎn)生死鎖的原因和必要條件

1.產(chǎn)生死鎖的原因進程推進順序非法：請求和釋放資源順序不當(dāng)。1）進程推進順序合法2）進程推進順序非法P1：Request(R1);Request(R2);P1：Release(R1);Release(R2);P2：Request(R1);Request(R2);P2：Release(R1);Release(R2);P1：Request(R1);P2：Request(R2);P1：Request(R2);P2：Request(R1);P1P2R1R22023/2/331第二章進程管理3.5

產(chǎn)生死鎖的原因和必要條件（1）互斥條件，一段時間內(nèi)某資源只能由一個進程占用；（2）請求和保持條件，部分分配資源；（3）不剝奪條件，進程已獲得資源不能被剝奪，直至使用完畢；（4）環(huán)路等待條件，發(fā)生死鎖時必然存在進程-資源的環(huán)形鏈。

2.產(chǎn)生死鎖的必要條件（1）預(yù)防死鎖：通過設(shè)置某些限制條件，去破壞產(chǎn)生死鎖的四個必要條件中的一個或者幾個，預(yù)防死鎖的發(fā)生；（2）避免死鎖：在資源的動態(tài)分配過程中，用某種方法去防止系統(tǒng)進入不安全狀態(tài)，從而避免發(fā)生死鎖；（3）檢測死鎖：通過系統(tǒng)所設(shè)置的檢測機制，及時地檢測出死鎖的發(fā)生，并精確地確定與死鎖有關(guān)的進程和資源；（4）解除死鎖：與死鎖檢測配合，通過撤銷和掛起一些進程，以便回收一些資源，再將這些資源分配給處于阻塞狀態(tài)的進程，使之就緒，以繼續(xù)運行。

3.處理死鎖的基本方法2023/2/332第二章進程管理3.6

預(yù)防死鎖的方法（1）摒棄“請求和保持”條件，要么全部分配，要么一個也不分配；（2）摒棄“不剝奪”條件，資源在進程運行過程中可被暫時釋放；（3）摒棄“環(huán)路等待”條件，進程對資源的請求按照某種順序依次進行。

1.預(yù)防死鎖安全狀態(tài)是指系統(tǒng)能按某種進程順序（P1，P2，…，Pn），來為每個進程Pi分配其所需資源，直至滿足每個進程對資源的最大需求，使每個進程都順利執(zhí)行。安全狀態(tài)實例:假設(shè)系統(tǒng)中有三個進程P1，P2，P3，共12臺磁帶機。2.系統(tǒng)安全狀態(tài)進程最大需求已分配可用P11053P242P3922023/2/333第二章進程管理3.6

預(yù)防死鎖的方法數(shù)據(jù)結(jié)構(gòu)

3.銀行家算法（1）可利用資源向量Available（m個元素的數(shù)組），其中Available[j]=k，表示系統(tǒng)中Rj類資源有k個。（2）最大需求矩陣Max（n×m）的矩陣，Max[i,j]=k，表示進程Pi需要Rj類資源的最大數(shù)目是k個。（3）分配矩陣Allocation（n×m）的矩陣，Allocation[i,j]=k，表示Pi已經(jīng)分得Rj類資源的數(shù)目是k個。（4）需求矩陣Need（n×m）的矩陣，Need[i,j]=k，表示Pi還需要Rj類資源的數(shù)目是k個。上述關(guān)系：Need[i,j]=Max[i,j]-Allocation[i,j]；2023/2/334第二章進程管理3.6

預(yù)防死鎖的方法算法描述

3.銀行家算法假設(shè)Requesti

是Pi的請求向量，Requesti[j]=k表示Pi請求k個Rj類資源，Pi申請后，系統(tǒng)進行檢查：（1）如果Requesti[j]

≤Need

[i,j]

，則轉(zhuǎn)（2），否則出錯（需要資源超過它宣布的最大值）。（2）如果Requesti[j]

≤Available

[j]

，則轉(zhuǎn)（3），否則尚無足夠的資源，Pi必須等待。（3）系統(tǒng)為Pi分配資源（試探性的分配）：

Available[j]:=Available[j]-Requesti[j]

;Allocation[i,j]:=Allocation[i,j]+Requesti[j];Need[i,j]:=Need[i,j]-Requesti[j];（4）執(zhí)行安全性算法，若安全則分配（為Pi），否則不分配，令Pi等待。2023/2/335第二章進程管理3.6

預(yù)防死鎖的方法安全性算法

3.銀行家算法（1）設(shè)置兩個向量：工作向量Work，表示系統(tǒng)可提供給進程繼續(xù)運行所需的各類資源數(shù)目，含有m個元素，初始work:=Available；向量Finish，表示系統(tǒng)是否有足夠的資源分配給進程，使之運行完成，初始時Finish:=false，有足夠資源分配時，F(xiàn)inish:=true；（2）在進程集合中找到一個能滿足下述條件的進程：

a）Finish[i]=false;b）Need[i,j]≤Work[j]；如果找到則轉(zhuǎn)（3），否則轉(zhuǎn)（4）；（3）進程Pi獲得資源可順利完成，并釋放資源，則執(zhí)行

Work[j]:=Work[j]+Allocation[i,j];Finish[i]:=true;轉(zhuǎn)（2）；（4）如果所有進程的Finish[i]=true都滿足，表示系統(tǒng)處于安全狀態(tài)，否則系統(tǒng)進入不安全狀態(tài)。2023/2/336第二章進程管理3.6

預(yù)防死鎖的方法假設(shè)系統(tǒng)中有五個進程{P0,P1,P2,P3,P4}和三類資源{A,B,C}，各種資源的數(shù)量分別為10、5、7，在T0時刻的資源分配情況下表：

4.銀行家算法的實例進程/資源MaxAllocationNeedAvailableABCABCABCABCP0P1P2P3P4753322902222433010200(302)302211002743122(020)600011431332(230)2023/2/337第二章進程管理3.6

預(yù)防死鎖的方法

4.銀行家算法的實例進程/資源WorkNeedAllocationWork+AllocationFinishABCABCABCABCP1P3P4P2P0332532743745104712201143160074320021100230201053274374510471057truetruetruetruetrue(1)T0時刻的安全性：存在安全序列{P1,P3,P4,P2,P0}。2023/2/338第二章進程管理3.6

預(yù)防死鎖的方法

4.銀行家算法的實例進程/資源WorkNeedAllocationWork+AllocationFinishABCABCABCABCP1P3P4P0P2230532743745755020011431743600302211002010302

5327437457551057truetruetruetruetrue(2)P1請求資源，發(fā)出請求向量Request1(1,0,2)，進行檢查Request1(1,0,2)≤

Need1(1,2,2);Request1(1,0,2)≤

Available1(3,3,2);存在安全序列{P1,P3,P4,P0,P2}。(3)P4請求資源，發(fā)出請求向量Request4(3,3,0)，檢查Request4(3,3,0)≤

Need4(4,3,1);Request4(3,3,0)≤

Available4(2,3,0);讓P4等待。2023/2/339第二章進程管理3.6

預(yù)防死鎖的方法

4.銀行家算法的實例進程/資源AllocationNeedAvailableABCABCABCP0P1P2P3P4030302302211002723020600011431210(4)P0請求資源，發(fā)出請求向量Request0(0,2,0)，進行檢查Request0(0,2,0)≤

Need0(7,4,3);Request0(0,2,0)≤

Available0(2,3,0);假定為P0分配資源，修改相關(guān)數(shù)據(jù)如下。(5)進行安全性檢查，Available(2,1,0)已不能滿足任何進程需要，故系統(tǒng)進入不安全狀態(tài)。2023/2/340第二章進程管理3.7

死鎖的檢測與解除資源分配圖（ResourceAllocationGraph）RAG是由一組結(jié)點N和一組邊E組成的一個對偶RAG=（N，E），對它的約定如下：

（1）P={p1,p2,…,pn}R={r1,r2,…,rn}P和R是兩個互斥的子集，N=P∪R

（2）e∈E，它連接P中的一個結(jié)點和R中的一個結(jié)點

e=（pi,rj)–資源請求邊（pi指向rj

）表示pi請求一個單位的rj

；

e=（rj,pi)–資源分配邊（rj

指向pi

）表示pi分配到一個單位的rj

；

1.死鎖的檢測P1P2R1R22023/2/341第二章進程管理3.7

死鎖的檢測與解除資源分配圖的簡化

（1）從RAG中找出既不阻塞又不是孤點的進程Pi，消去由Pi出發(fā)的和指向Pi的所有邊（請求邊和分配邊），這等價于Pi獲得它所需的資源，不斷向前推進，一直運行完畢，釋放出它所占有的全部資源。（2）進程Pi所釋放的資源可以喚醒某些阻塞于該資源的進程Pj，消去Pj所有的邊，使之成為孤點。（3）如此下去，最后，若消去圖中所有的邊，則稱該圖是可完全化簡的。（4）若有向圖不能通過任何過程予以簡化，則稱該圖是不可完全簡化的。

1.死鎖的檢測死鎖定理

引理：一個給定的進程資源分配圖，對所有的簡化順序，將導(dǎo)致相同的結(jié)果（再也不能簡化）。