【正文】 第三章 處理機(jī)調(diào)度與死鎖 2． 安全狀態(tài)之例 我們通過(guò)一個(gè)例子來(lái)說(shuō)明安全性。假定系統(tǒng)中有三個(gè)進(jìn)程 P P2和 P3，共有 12臺(tái)磁帶機(jī)。進(jìn)程 P1總共要求 10臺(tái)磁帶機(jī)， P2和 P3分別要求 4臺(tái)和 9臺(tái)。假設(shè)在 T0時(shí)刻，進(jìn)程 P P2和P3已分別獲得 5臺(tái)、 2臺(tái)和 2臺(tái)磁帶機(jī)，尚有 3臺(tái)空閑未分配，如下表所示： 進(jìn) 程 最大需求 已 分 配 可 用 P 1 10 5 3 P 2 4 2 P 3 9 2 此時(shí)已分配 9臺(tái)，安全序列： P2， P1， P3 第三章 處理機(jī)調(diào)度與死鎖 3． 由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換 如果不按照安全序列分配資源，則系統(tǒng)可能會(huì)由安全狀態(tài)進(jìn)入不安全狀態(tài)。例如，在 T0時(shí)刻以后， P3又請(qǐng)求 1臺(tái)磁帶機(jī)，若此時(shí)系統(tǒng)把剩余 3臺(tái)中的 1臺(tái)分配給 P3，則系統(tǒng)便進(jìn)入不安全狀態(tài)。因?yàn)榇藭r(shí)也無(wú)法再找到一個(gè)安全序列，從給 P3分配了第3臺(tái)磁帶機(jī)開始，系統(tǒng)便又進(jìn)入了不安全狀態(tài)。由此可見，在P3請(qǐng)求資源時(shí)，盡管系統(tǒng)中尚有可用的磁帶機(jī)，但卻不能分配給它，必須讓 P3一直等待到 P1和 P2完成，釋放出資源后再將足夠的資源分配給 P3，它才能順利完成。 存在安全狀態(tài)，不代表不可能發(fā)生死鎖， 表示的是有解決死鎖的方法存在。 第三章 處理機(jī)調(diào)度與死鎖 利用銀行家算法避免死鎖 ?銀行家算法： Dijkstra 于 1968年提出。銀行家算法 ?銀行家擁有一筆周轉(zhuǎn)資金 ?客戶要求分期貸款 ， 如果客戶能夠得到各期貸款 ， 就一定能夠歸還貸款 ， 否則就一定不能歸還貸款 ?銀行家應(yīng)謹(jǐn)慎的貸款 ， 防止出現(xiàn)壞帳 ?用銀行家算法避免死鎖 ?操作系統(tǒng) （ 銀行家 ） ?操作系統(tǒng)管理的資源 (周轉(zhuǎn)資金 ) ?進(jìn)程 （ 要求貸款的客戶 ） 第三章 處理機(jī)調(diào)度與死鎖 ?銀行家 算法思想： 該算法需要檢查申請(qǐng)者對(duì)資源的最大需求量，如果系統(tǒng) 現(xiàn)存的各類資源 可以滿足申請(qǐng)者的請(qǐng)求，就滿足申請(qǐng)者的請(qǐng)求。這樣申請(qǐng)者就可很快完成其計(jì)算，然后釋放它占用的資源，從而保證了系統(tǒng)中的所有進(jìn)程都能完成，所以可避免死鎖的發(fā)生。 第三章 處理機(jī)調(diào)度與死鎖 ?銀行家算法中的數(shù)據(jù)結(jié)構(gòu) (1) 可利用資源向量 Available。 這是一個(gè)含有 m個(gè)元素的數(shù)組 ， 其中的每一個(gè)元素代表一類可利用的資源數(shù)目 ， 其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目 ， 其數(shù)值隨 該 類 資 源 的 分 配 和 回 收 而 動(dòng) 態(tài) 地 改 變 。 如果Available[j]=K， 則表示系統(tǒng)中現(xiàn)有 Rj類資源 K個(gè) 。 (2) 最大需求矩陣 Max。 這是一個(gè) n m的矩陣 ， 它定義了系統(tǒng)中 n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì) m類資源的最大需求 。 如果Max[i,j]=K， 則表示進(jìn)程 i需要 Rj類資源的最大數(shù)目為 K。 第三章 處理機(jī)調(diào)度與死鎖 (3) 分配矩陣 Allocation。 這也是一個(gè) n m的矩陣 ， 它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù) 。如果 Allocation[i,j]=K， 則表示進(jìn)程 i當(dāng)前已分得 R j類資源的數(shù)目為 K。 (4) 需求矩陣 Need。 這也是一個(gè) n m的矩陣 ， 用以表示每一個(gè)進(jìn)程尚需的各類資源數(shù) 。 如果 Need[i,j]=K， 則表示進(jìn)程 i還需要 R j類資源 K個(gè) ， 方能完成其任務(wù) 。 上述三個(gè)矩陣間存在下述關(guān)系： Need[i, j]=Max[i, j]Allocation[i, j] 第三章 處理機(jī)調(diào)度與死鎖 銀行家算法避免死鎖 算法： 開始 申請(qǐng)量 =尚需 量 y n n y 申請(qǐng)量 〈 =系統(tǒng)剩余 安全性控制 分配 進(jìn)入下一步驟 預(yù)分配作廢 阻塞 安全 首先為申請(qǐng)預(yù)分配資源 錯(cuò)誤 預(yù)測(cè) n y 第三章 處理機(jī)調(diào)度與死鎖 例 . 多項(xiàng)資源的安全序列 （ a）初始狀態(tài) Max Matrix 第三章 處理機(jī)調(diào)度與死鎖 Max Matrix （ a） P2運(yùn)行完成 第三章 處理機(jī)調(diào)度與死鎖 Max Matrix Max Matrix 第三章 處理機(jī)調(diào)度與死鎖 例 . 進(jìn)入不安全狀態(tài) （ a）初始狀態(tài) Max Matrix 第三章 處理機(jī)調(diào)度與死鎖 例 . 進(jìn)入不安全狀態(tài) Max Matrix （ b） P1申請(qǐng) 1個(gè) R 1個(gè) R3 第三章 處理機(jī)調(diào)度與死鎖 2．銀行家算法 設(shè) Request i是進(jìn)程 Pi的請(qǐng)求向量，如果 Request i[j]=K，表示進(jìn)程 P i需要 K個(gè) R j類型的資源。當(dāng) P i發(fā)出資源請(qǐng)求后，系統(tǒng)按下述步驟進(jìn)行檢查： (1) 如果 Request i[j]≤Need[i,j] ，便轉(zhuǎn)向步驟 (2)；否則認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù)已超過(guò)它所宣布的最大值。 (2) 如果 Requesti[j]≤Available[j] ，便轉(zhuǎn)向步驟 (3)；否則，表示尚無(wú)足夠資源， Pi須等待。 第三章 處理機(jī)調(diào)度與死鎖 (3) 系統(tǒng) 試探著 把資源分配給進(jìn)程 P i， 并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值： Available[j]:= Available[j]Request i[j] ； Allocation[i,j]:= Allocation[i,j]+Request i[j]； Need[i,j]:= Need[i,j]Request i[j]； (4) 系統(tǒng)執(zhí)行安全性算法 ，檢查此次資源分配后系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程 Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復(fù)原來(lái)的資源分配狀態(tài)，讓進(jìn)程 Pi等待。 第三章 處理機(jī)調(diào)度與死鎖 3． 安全性算法 系統(tǒng)所執(zhí)行的安全性算法可描述如下： (1) 設(shè)置兩個(gè)向量： ① 工作向量 Work， 它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目 ， 它含有 m個(gè)元素 ， 在執(zhí)行安全算法開始時(shí) ， Work:=Available。 ② Finish，它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開始時(shí)先做 Finish[i]:=false；當(dāng)有足夠資源分配給進(jìn)程時(shí)，再令 Finish[i]:=true。 第三章 處理機(jī)調(diào)度與死鎖 (2) 從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程： ① Finish[i]=false； ② Need[i,j]≤Work[j] ；若找到 ， 執(zhí)行步驟 (3)， 否則 ，執(zhí)行步驟 (4)。 (3) 當(dāng)進(jìn)程 Pi獲得資源后 ， 可順利執(zhí)行 ， 直至完成 ， 并釋放出分配給它的資源 ， 故應(yīng)執(zhí)行： Work[j]:= Work[j]+Allocation[i,j]； Finish[i]:=true； go to step 2； (4) 如果所有進(jìn)程的 Finish[i]=true都滿足，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。 第三章 處理機(jī)調(diào)度與死鎖 4． 銀行家算法之例 假定系統(tǒng)中有五個(gè)進(jìn)程 {P0， P1， P2， P3， P4}和三類資源{A， B， C}，各種資源的數(shù)量分別為 7，在 T0時(shí)刻的資源分配情況如圖 316所示。 第三章 處理機(jī)調(diào)度與死鎖 圖 316 T0時(shí)刻的資源分配表 Max A l l ocat i on N eed A vai l abl e 資源 情況 進(jìn) 程 A B C A B C A B C A B C P 0 7 5 3 0 1 0 7 4 3 3 3 2 (2 3 0) P 1 3 2 2 2 0 0 1 2 2 ( 3 0 2 ) ( 0 2 0 ) P 2 9 0 2 3 0 2 6 0 0 P 3 2 2 2 2 1 1 0 1 1 P 4 4 3 3 0 0 2 4 3 1 第三章 處理機(jī)調(diào)度與死鎖 (1) T0時(shí)刻的安全性：利用安全性算法對(duì) T0時(shí)刻的資源分配情況進(jìn)行分析 (見圖 317所示 )可知，在 T0時(shí)刻存在著一個(gè)安全序列 {P1， P3， P4， P2， P0}，故系統(tǒng)是安全的。 圖 317 T0時(shí)刻的安全序列 W ork N eed A l l ocat i on W ork +A l l ocat i on 資源 情況 進(jìn) 程 A B C A B C A B C A B C Fini sh P 1 3 3 2 1 2 2 2 0 0 5 3 2 t rue P 3 5 3 2 0 1 1 2 1 1 7 4 3 t rue P 4 7 4 3 4 3 1 0 0 2 7 4 5 t rue P 2 7 4 5 6 0 0 3 0 2 10 4 7 t rue P 0 10 4 7 7 4 3 0 1 0 10 5 7 tr ue {P1， P3， P4， P2， P0}是安全序列嗎？ 第三章 處理機(jī)調(diào)度與死鎖 (2) ?P1請(qǐng)求資源： P1發(fā)出請(qǐng)求向量 Request1(1， 0， 2)， 系統(tǒng)按銀行家算法進(jìn)行檢查： ① Request1(1， 0， 2)≤Need1(1， 2， 2) ② Request1(1， 0， 2)≤Available1(3， 3， 2) ③ 系統(tǒng)先假定可為 P1分配資源，并修改 Available，Allocation1和 Need1向量，由此形成的資源變化情況如圖 316中的圓括號(hào)所示。 第三章 處理機(jī)調(diào)度與死鎖 ④ 再利用安全性算法檢查此時(shí)系統(tǒng)是否安全。如圖 318所示。 圖 318 P1申請(qǐng)資源時(shí)的安全性檢查 W ork N eed A l l ocat i on W ork +A l l ocat i on 資源 情況 進(jìn) 程 A B C A B C A B C A B C Fini sh P 1 2 3 0 0 2 0 3 0 2 5 3 2 t rue P 3 5 3 2 0 1 1 2 1 1 7 4 3 t rue P 4 7 4 3 4 3 1 0 0 2 7 4 5 t rue P 0 7 4 5 7 4 3 0 1 0 7 5 5 t rue P 2 7 5 5 6 0 0 3 0 2 10 5 7 t rue 第三章 處理機(jī)調(diào)度與死鎖 (3) ?P4請(qǐng)求資源： P4發(fā)出請(qǐng)求向量 Request4(3， 3， 0)， 系統(tǒng)按銀行家算法進(jìn)行檢查： ① Request4(3， 3， 0)≤Need4(4， 3， 1)； ② Request4(3， 3， 0)≤Available(2， 3， 0)， 讓 P4等待 。 (4) ?P0請(qǐng)求資源： P0發(fā)出請(qǐng)求向量 Requst0(0， 2， 0)， 系統(tǒng)按銀行家算法進(jìn)行檢查： ① Request0(0， 2， 0)≤Need0(7， 4， 3)； ② Request0(0， 2， 0)≤Available(2， 3， 0)； ③ 系統(tǒng)暫時(shí)先假定可為 P0分配資源，并修改有關(guān)數(shù)據(jù)，如圖 319所示。 第三章 處理機(jī)調(diào)度與死鎖 圖 319 為 P0分配資源后的有關(guān)資源數(shù)據(jù) A l l ocat i on N eed A vai l abl e 資源 情況 進(jìn) 程 A B C A B C A B C P 0 0 3 0 7 3 2 2 1 0 P 1 3 0 2 0 2 0 P 2 3 0 2 6 0 0 P 3 2 1 1 0 1 1 P 4 0 0 2 4 3 1 第三章 處理機(jī)調(diào)度與死鎖 (5) 進(jìn)行安全性檢查：可用資源 Available(2， 1， 0)已不能滿足任何進(jìn)程的需要 ， 故系統(tǒng)進(jìn)入不安全狀態(tài) ， 此時(shí)系統(tǒng)不分配資源 。 如果在銀行家算法中，把 P0發(fā)出的請(qǐng)求向量改為Request0(0， 1， 0)，系統(tǒng)是否能將資源分配給它？ 第三章 處理