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

（1）預防死鎖：通過某些限制條件的設置，去破壞產生死鎖的四個必要條件；

（2）避免死鎖：在資源的動態分配過程中，用某種方法去防止系統進入不安全狀態；

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

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

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

Work表示系統可提供給進程繼續運行所需的各類資源數目（即在分配過程中，系統的可用資源數）。初始值Work∶=Available;

Finish表示系統是否有足夠的資源分配給進程i，使之運行完成。初始值

Finish[i]:=false當有足夠資源分配給進程時Finish[i]:=true8可編輯9可編輯

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

P4P3P2P1P0AvailableA,B,CNeedA,B,CAllocationA,B,CMaxA,B,C進程資源情況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時刻系統是否安全？執行安全性算法進行檢查：

①

向量初值

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

②

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

≤Work

且Finish[1]＝false；③

則設P1順利執行完成，從而有：

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

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

④發現：目前可執行的所有資源分配工作完成之后，各個進程對應的狀態向量Finish[i]＝true；且對應于該向量置為“true”的進程編號依次為：1

→3

→

0→

2

→

4，故：系統存在安全序列{P1，P3，P0，P2，P4}

所以，T0

時刻系統處于安全狀態！銀行家算法實例18可編輯Chapter3處理機調度與死鎖由分析知：執行完P1、P3

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

執行銀行家算法：

①

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

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

③系統為P1進行預分配，并修改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可編輯

④

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

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

≤Work（5，3，2）

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

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

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

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

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

執行銀行家算法進行檢查：①

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

Available(2,3,0)

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

執行銀行家算法進行檢查：

①

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

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

③

系統為P0作預分配，并修改有關數據：銀行家算法實例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