銀行家算法課件

計算機操作系統(tǒng)銀行家算法1可編輯死鎖的“3W”WhatWhyHow什么是死鎖？為什么會發(fā)生死鎖？怎么解決死鎖？2可編輯死鎖的處理方法

（1）預(yù)防死鎖：通過某些限制條件的設(shè)置，去破壞產(chǎn)生死鎖的四個必要條件；

（2）避免死鎖：在資源的動態(tài)分配過程中，用某種方法去防止系統(tǒng)進(jìn)入不安全狀態(tài)；

（3）檢測死鎖：及時檢測死鎖的發(fā)生，并確定與之相關(guān)的進(jìn)程、資源，從而采取措施清除死鎖；

（4）解除死鎖：撤消或掛起某些進(jìn)程以回收一些資源，用于解脫另一些處于死鎖的進(jìn)程。3可編輯避免死鎖—銀行家算法設(shè)銀行家有10萬周轉(zhuǎn)資金，P,Q,R分別需要8,3,9萬元搞項目，如果P已申請到了4萬，Q要申請2萬，R要申請4萬.Q1：客戶要求分期貸款，一旦得到每期貸款，就能夠歸還貸款Q2：銀行家應(yīng)謹(jǐn)慎的貸款，防止出現(xiàn)壞帳什么是銀行家問題？銀行家->操作系統(tǒng)周轉(zhuǎn)資金->系統(tǒng)資源貸款客戶->進(jìn)程當(dāng)某進(jìn)程請求分配資源時，系統(tǒng)假定先分配給它，之后若能找到一個進(jìn)程完成序列（安全序列），說明系統(tǒng)是安全的，可進(jìn)行實際分配；否則，讓申請者等待。銀行家算法的實現(xiàn)思想4可編輯表示形式含義Available（可用資源數(shù)組）Available[j]＝k現(xiàn)有資源j的數(shù)目為kMax（最大需求矩陣）Max[i,j]＝k進(jìn)程i對資源j的最大需求數(shù)目為k

Allocation（分配矩陣）Allocation[i,j]＝k進(jìn)程i當(dāng)前已分得的資源j的數(shù)目為kNeed（需求矩陣）Need[i,j]＝k進(jìn)程i尚需分配的資源j的數(shù)目為k銀行家算法中的數(shù)據(jù)結(jié)構(gòu)5可編輯銀行家算法當(dāng)Pi發(fā)出資源請求，分配一個Request向量然后系統(tǒng)按下述流程進(jìn)行執(zhí)行：Requesti：是進(jìn)程Pi的請求向量如果Requesti[j]=K，表示進(jìn)程i需要K個Rj類型的資源。銀行家算法實現(xiàn)過程6可編輯7可編輯安全性算法實現(xiàn)過程安全性算法兩個向量：Work和Finish

Work表示系統(tǒng)可提供給進(jìn)程繼續(xù)運行所需的各類資源數(shù)目（即在分配過程中，系統(tǒng)的可用資源數(shù)）。初始值Work∶=Available;

Finish表示系統(tǒng)是否有足夠的資源分配給進(jìn)程i，使之運行完成。初始值

Finish[i]:=false當(dāng)有足夠資源分配給進(jìn)程時Finish[i]:=true8可編輯9可編輯

假定系統(tǒng)中有五個進(jìn)程｛P0,P1,P2,P3,P4｝和三類資源｛A,B,C｝，各種資源的數(shù)量分別為10、5、7，在T0時刻的資源分配情況如下圖所示。

P4P3P2P1P0AvailableA,B,CNeedA,B,CAllocationA,B,CMaxA,B,C進(jìn)程資源情況7,5,33,2,29,0,22,2,24,3,30,1,02,0,03,0,22,1,10,0,27,4,31,2,26,0,00,1,14,3,13,3,2銀行家算法實例10可編輯（1）T0時刻系統(tǒng)是否安全？執(zhí)行安全性算法進(jìn)行檢查：

①

向量初值

Work:＝Available＝(3,3,2)；Finish[i]:＝false；（i＝0,1,…,4）

②

在進(jìn)程集合中找到Need1＝(1,2,2)

≤Work

且Finish[1]＝false；③

則設(shè)P1順利執(zhí)行完成，從而有：

Work:＝Work＋Allocation1＝(3,3,2)＋(2,0,0)＝(5,3,2)

Finish[1]:＝true銀行家算法實例11可編輯Chapter3處理機調(diào)度與死鎖FinishWork+AllocationAllocationNeedWorktrue532200122332P1AllocationNeedP0010743P1200122P2302600P3211011P400243112可編輯Chapter3處理機調(diào)度與死鎖FinishWork+AllocationAllocationNeedWorktrue743532211011P3true532200122332P1AllocationNeedP0010743P1200122P2302600P3211011P400243113可編輯Chapter3處理機調(diào)度與死鎖FinishWork+AllocationAllocationNeedWorktrue753743010743true743211011532true532200122332P0P3P1AllocationNeedP0010743P1200122P2302600P3211011P4002431142024/12/2015可編輯Chapter3處理機調(diào)度與死鎖FinishWork+AllocationAllocationNeedWorktrue1055753true753010743743302600true743211011532true532200122332P0P2P3P1AllocationNeedP0010743P1200122P2302600P3211011P400243116可編輯Chapter3處理機調(diào)度與死鎖AllocationNeedP0010743P1200122P2302600P3211011P4002431true10570024311055P4FinishWork+AllocationAllocationNeedWorktrue1055753true753010743743302600true743211011532true532200122332P0P2P3P117可編輯

④發(fā)現(xiàn)：目前可執(zhí)行的所有資源分配工作完成之后，各個進(jìn)程對應(yīng)的狀態(tài)向量Finish[i]＝true；且對應(yīng)于該向量置為“true”的進(jìn)程編號依次為：1

→3

→

0→

2

→

4，故：系統(tǒng)存在安全序列{P1，P3，P0，P2，P4}

所以，T0

時刻系統(tǒng)處于安全狀態(tài)！銀行家算法實例18可編輯Chapter3處理機調(diào)度與死鎖由分析知：執(zhí)行完P(guān)1、P3

的資源分配請求之后，系統(tǒng)可用的資源數(shù)量可以滿足其它3個進(jìn)程的資源請求，則此時的資源分配順序已無關(guān)緊要。所以：安全序列可以不唯一！true10570024311055P4FinishWork+AllocationAllocationNeedWorktrue1055753true753010743743302600true743211011532true532200122332P0P2P3P119可編輯（2）P1發(fā)出請求Request(1,0,2)，系統(tǒng)能分配資源嗎？

執(zhí)行銀行家算法：

①

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

②Request1(1,0,2)≤Available(3,3,2)；

③系統(tǒng)為P1進(jìn)行預(yù)分配，并修改Available，Allocation1和Need1向量：銀行家算法實例Request1(1,0,2)，Need1，Available20可編輯

Available:＝Available－Request1＝(3,3,2)－(1,0,2)＝(2,3,0)

Allocation1:＝Allocation1＋Request1＝(2,0,0)＋(1,0,2)＝(3,0,2)

Need1:＝Need1－Request1＝(1,2,2)－(1,0,2)＝(0,2,0)銀行家算法實例21可編輯

④

執(zhí)行安全性算法：a.Work:＝Available＝(2,3,0)；Finish[i]:＝false；在進(jìn)程集合中找到Need1＝(0,2,0)

≤Work；b’.在進(jìn)程集合中找到Need3＝(0,1,1)

≤Work（5，3，2）

且Finish[3]＝false；c.則設(shè)P1可順利執(zhí)行完成，從而有：

Work:＝Work＋Allocation1＝(2,3,0)＋(3,0,2)＝(5,3,2)

Finish[1]:＝true銀行家算法實例22可編輯c’.則設(shè)P3順利執(zhí)行完成，從而有：

Work:＝Work＋Allocation3＝(5,3,2)＋(2,1,1)＝(7,4,3)

Finish[3]:＝true………執(zhí)行安全性算法檢查時，仍能夠得到安全序列{P1，P3，P0，P2，P4}，故請求向量Request1(1,0,2)發(fā)出時系統(tǒng)安全！銀行家算法實例23可編輯（3）P4發(fā)出請求Request(3,2,1)，系統(tǒng)能分配資源嗎？

執(zhí)行銀行家算法進(jìn)行檢查：①

Request4(3,2,0)≤Need4(4,3,1)；②Request4(3,2,1)

Available(2,3,0)

故：P4資源請求失敗，讓其等待！＞銀行家算法實例24可編輯（4）P0發(fā)出請求Request(0,2,0)，系統(tǒng)能分配資源嗎？

執(zhí)行銀行家算法進(jìn)行檢查：

①

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

②Request0(0,2,0)≤Available(2,3,0)；

③

系統(tǒng)為P0作預(yù)分配，并修改有關(guān)數(shù)據(jù)：銀行家算法實例25可編輯

Available:＝Available－Request0＝(2,3,0)－(0,2,0)＝(2,1,0)

Allocation0:＝Allocation0＋Request0＝(0,1,0)＋(0,2,0)＝(0,3,0)

Need0

:＝Need0－Request0