【正文】 lable 則 go to 3，否則表示無足夠資源， Pi等待。 ?系統(tǒng) 進行試探分配，并求該相應(yīng)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù) Available： = Available Requesti Allocationi： = Allocationi+ Requesti Needi： = NeediRequesti ?系統(tǒng) 執(zhí)行安全性算法：安全，把資源分配給 Pi，否則， Pi等待。 第三章 處理機調(diào)度與死鎖 ?設(shè) Work 和 Finish是長度分別為 m,n的向量 初試值 Work： =Available ， Finishi： = False（所有） ?從進程集合中找到一個能滿足下列條件的進程 a. Finishi= False b. Needi ? Work 如找到 go to 3 否則 go to 4 ?當進程 Pi 獲得資源后，順利執(zhí)行，直至完成，并釋放分 配給它的資源。 Work： = Work+ Allocationi Finishi： = True go to 2 ?如果所有進程的 Finishi= True 則表示系統(tǒng)安全，否則為不安全。 第三章 處理機調(diào)度與死鎖 4. 銀行家算法之例 假定系統(tǒng)中有五個進程 ｛ P0, P1, P2, P3, P4｝ 和三類資源 ｛ A, B, C｝ ， 各種資源的數(shù)量分別為 7， 在 T0時刻的資源分配情況如圖 315 所示 。 圖 315 T0時刻的資源分配表 第三章 處理機調(diào)度與死鎖 (1) T0時刻的安全性： 圖 316 T0時刻的安全序列 第三章 處理機調(diào)度與死鎖 (2) P1請求資源： P1發(fā)出請求向量 Request1(1， 0， 2)，系統(tǒng)按銀行家算法進行檢查： ① Request1(1, 0, 2)≤Need1(1, 2, 2) ② Request1(1, 0, 2)≤Available1(3, 3, 2) ③ 系統(tǒng)先假定可為 P1分配資源 ， 并修改 Available, Allocation1和 Need1向量 ， 由此形成的資源變化情況如圖 315 中的圓括號所示 。 ④ 再利用安全性算法檢查此時系統(tǒng)是否安全。 第三章 處理機調(diào)度與死鎖 圖 317 P1申請資源時的安全性檢查 第三章 處理機調(diào)度與死鎖 (3) P4請求資源： P4發(fā)出請求向量 Request4(3， 3， 0)， 系 ① Request4(3, 3, 0)≤Need4(4, 3, 1)。 ② Request4(3, 3, 0) Available(2, 3, 0)， 讓 P4等待 。 (4) P0請求資源： P0發(fā)出請求向量 Requst0(0， 2， 0)， 系統(tǒng)按 ① Request0(0, 2, 0)≤Need 0(7, 4, 3)。 ② Request0(0, 2, 0)≤Available(2, 3, 0)。 ③ 系統(tǒng)暫時先假定可為 P0分配資源，并修改有關(guān)數(shù)據(jù)，如圖 318 所示。 ??第三章 處理機調(diào)度與死鎖 圖 318 為 P0分配資源后的有關(guān)資源數(shù)據(jù) 第三章 處理機調(diào)度與死鎖 死鎖的檢測與解除 死鎖的檢測 1. 資源分配圖 (Resource Allocation Graph) 圖 319 每類資源有多個時的情況 P1P2r1r2第三章 處理機調(diào)度與死鎖 (2) 凡屬于 E中的一個邊 e∈ E， 都連接著 P中的一個結(jié)點和 R中的一個結(jié)點 ， e={pi, rj}是資源請求邊 ， 由進程 pi指向資源 rj， 它表示進程 pi請求一個單位的 rj資源 。 e={rj, pi}是資源分配邊 ， 由資源 rj指向進程 pi, 它表示把一個單位的資源 rj分配給進程 pi。 第三章 處理機調(diào)度與死鎖 2. 死鎖定理 圖 320 資源分配圖的簡化 ( a ) ( b )P1( c )P1P2P1P2P2第三章 處理機調(diào)度與死鎖 3. 死鎖檢測中的數(shù)據(jù)結(jié)構(gòu) (1) 可利用資源向量 Available， 它表示了 m類資源中每一類資源的可用數(shù)目 。 (2) 把不占用資源的進程 (向量 Allocation∶ =0)記入 L表中 ， 即 Li∪ L。 (3) 從進程集合中找到一個 Requesti≤Work的進程 ， 做如下處理： ① 將其資源分配圖簡化 ， 釋放出資源 ， 增加工作向量Work∶ =Work+Allocationi。 ② 將它記入 L表中 。 第三章 處理機調(diào)度與死鎖 (4) 若不能把所有進程都記入 L表中 ， 便表明系統(tǒng)狀態(tài) S的資源分配圖是不可完全簡化的 。 因此 ， 該系統(tǒng)狀態(tài)將發(fā)生死鎖 。 Work ∶ =Available。 L ∶ = {Li|Allocationi=0∩Requesti=0} for all Li L do begin for all Requesti≤Work do begin Work ∶ =Work+Allocationi。 Li∪ L。 end end deadlock∶ = (L={p1, p2, …, p n})。 ?第三章 處理機調(diào)度與死鎖 死鎖的解除 (1) 剝奪資源。 (2) 撤消進程。 為把系統(tǒng)從死鎖狀態(tài)中解脫出來 ， 所花費的代價可表示為： R(S)min=min{Cui}+min{Cuj}+min{Cuk}+… 第三章 處理機調(diào)度與死鎖 圖 321 付出代價最小的死鎖解除方法 U1V12V13V1kW132W134W13kP2P3……P2P4… Pk…PkU2V21V22V2kW231W234W23k…P1P4… Pk…UkVk1Vk2VkkWk21Wk22Wk2k……Pk… …SP1(cu1) P1(cuk)P1(cud)第三章 處理機調(diào)度與死鎖 作業(yè) 1： 假定一個處理機上執(zhí)行的作業(yè)如下： 作業(yè) 提交時間 短暫時間段長度 優(yōu)先數(shù) 1 0 7 3 2 1 4 1 3 2 2 6 4 3 1 4 5 3 5 2 且規(guī)定優(yōu)先數(shù)大優(yōu)先級別高 。 試分別用先來先服務(wù) ， 時間片 （ 時間片為 2） ， 短作業(yè)優(yōu)先 ， 非搶占優(yōu)先調(diào)度算法調(diào)度這些作業(yè) ， 并計算它們的平均周轉(zhuǎn) 時間 。 第三章 處理機調(diào)度與死鎖 作業(yè) 2： 設(shè)有三個作業(yè) ， 它們到達系統(tǒng)的時間和計 算時間如下： J1： 8： 00到達 計算時間 2個小時 J2： 8： 30到達 計算時間 1個小時 J3： 9： 30到達 計算時間 系統(tǒng)按單道方式運行 ， 采用響應(yīng)比高者優(yōu) 先調(diào)度 ， 在 9： 30開始調(diào)度時 ， 試寫出作業(yè) 調(diào)度次序 。