銀行家算法課件

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

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

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

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

（4）解除死鎖：撤消或掛起某些進(jìn)程以回收一些資源，用于解脫另一些處于死鎖的進(jìn)程。3死鎖的處理方法（1）預(yù)防死鎖：通過某些限制條件4避免死鎖—銀行家算法設(shè)銀行家有10萬周轉(zhuǎn)資金，P,Q,R分別需要8,3,9萬元搞項(xiàng)目，如果P已申請(qǐng)到了4萬，Q要申請(qǐng)2萬，R要申請(qǐng)4萬.Q1：客戶要求分期貸款，一旦得到每期貸款，就能夠歸還貸款Q2：銀行家應(yīng)謹(jǐn)慎的貸款，防止出現(xiàn)壞帳什么是銀行家問題？銀行家->操作系統(tǒng)周轉(zhuǎn)資金->系統(tǒng)資源貸款客戶->進(jìn)程當(dāng)某進(jìn)程請(qǐng)求分配資源時(shí)，系統(tǒng)假定先分配給它，之后若能找到一個(gè)進(jìn)程完成序列（安全序列），說明系統(tǒng)是安全的，可進(jìn)行實(shí)際分配；否則，讓申請(qǐng)者等待。銀行家算法的實(shí)現(xiàn)思想4避免死鎖—銀行家算法設(shè)銀行家有10萬周轉(zhuǎn)資金，P,Q,5表示形式含義Available（可用資源數(shù)組）Available[j]＝k現(xiàn)有資源j的數(shù)目為kMax（最大需求矩陣）Max[i,j]＝k進(jìn)程i對(duì)資源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表示形式含義AvailableAvailab6銀行家算法當(dāng)Pi發(fā)出資源請(qǐng)求，分配一個(gè)Request向量然后系統(tǒng)按下述流程進(jìn)行執(zhí)行：Requesti：是進(jìn)程Pi的請(qǐng)求向量如果Requesti[j]=K，表示進(jìn)程i需要K個(gè)Rj類型的資源。銀行家算法實(shí)現(xiàn)過程6銀行家算法Requesti：是進(jìn)程Pi的請(qǐng)求向量銀行家算法778安全性算法實(shí)現(xiàn)過程安全性算法兩個(gè)向量：Work和FinishWork表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目（即在分配過程中，系統(tǒng)的可用資源數(shù)）。初始值Work∶=Available;Finish表示系統(tǒng)是否有足夠的資源分配給進(jìn)程i，使之運(yùn)行完成。初始值Finish[i]:=false當(dāng)有足夠資源分配給進(jìn)程時(shí)Finish[i]:=true8安全性算法實(shí)現(xiàn)過程安全性算法兩個(gè)向量：Work和Finis9910

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

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銀行家算法實(shí)例10假定系統(tǒng)中有五個(gè)進(jìn)程｛P0,P1,P11（1）T0時(shí)刻系統(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銀行家算法實(shí)例11（1）T0時(shí)刻系統(tǒng)是否安全？①向量初值12Chapter3處理機(jī)調(diào)度與死鎖FinishWork+AllocationAllocationNeedWorktrue532200122332P1AllocationNeedP0010743P1200122P2302600P3211011P400243112Chapter3處理機(jī)調(diào)度與死鎖FinishWor13Chapter3處理機(jī)調(diào)度與死鎖FinishWork+AllocationAllocationNeedWorktrue743532211011P3true532200122332P1AllocationNeedP0010743P1200122P2302600P3211011P400243113Chapter3處理機(jī)調(diào)度與死鎖FinishWor14Chapter3處理機(jī)調(diào)度與死鎖FinishWork+AllocationAllocationNeedWorktrue753743010743true743211011532true532200122332P0P3P1AllocationNeedP0010743P1200122P2302600P3211011P400243114Chapter3處理機(jī)調(diào)度與死鎖FinishWor15Chapter3處理機(jī)調(diào)度與死鎖FinishWork+AllocationAllocationNeedWorktrue1055753true753010743743302600true743211011532true532200122332P0P2P3P1AllocationNeedP0010743P1200122P2302600P3211011P400243115Chapter3處理機(jī)調(diào)度與死鎖FinishWor16Chapter3處理機(jī)調(diào)度與死鎖AllocationNeedP0010743P1200122P2302600P3211011P4002431true10570024311055P4FinishWork+AllocationAllocationNeedWorktrue1055753true753010743743302600true743211011532true532200122332P0P2P3P116Chapter3處理機(jī)調(diào)度與死鎖Allocatio17

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

→3

→

0→

2

→

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

所以，T0

時(shí)刻系統(tǒng)處于安全狀態(tài)！銀行家算法實(shí)例17④發(fā)現(xiàn)：目前可執(zhí)行的所有資源分配工作完成之18Chapter3處理機(jī)調(diào)度與死鎖由分析知：執(zhí)行完P(guān)1、P3

的資源分配請(qǐng)求之后，系統(tǒng)可用的資源數(shù)量可以滿足其它3個(gè)進(jìn)程的資源請(qǐng)求，則此時(shí)的資源分配順序已無關(guān)緊要。所以：安全序列可以不唯一！true10570024311055P4FinishWork+AllocationAllocationNeedWorktrue1055753true753010743743302600true743211011532true532200122332P0P2P3P118Chapter3處理機(jī)調(diào)度與死鎖由分析知：執(zhí)行完19（2）P1發(fā)出請(qǐng)求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向量：銀行家算法實(shí)例Request1(1,0,2)，Need1，Available19（2）P1發(fā)出請(qǐng)求Request(1,0,2)，系20

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)銀行家算法實(shí)例20Available:＝Availab21

④

執(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銀行家算法實(shí)例21④執(zhí)行安全性算法：在進(jìn)程集合中找22c’.則設(shè)P3順利執(zhí)行完成，從而有：

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

Finish[3]:＝true………執(zhí)行安全性算法檢查時(shí)，仍能夠得到安全序列{P1，P3，P0，P2，P4}，故請(qǐng)求向量Request1(1,0,2)發(fā)出時(shí)系統(tǒng)安全！銀行家算法實(shí)例22c’.則設(shè)P3順利執(zhí)行完成，從而有：………23（3）P4發(fā)出請(qǐng)求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資源請(qǐng)求失敗，讓其等待?。俱y行家算法實(shí)例23（3）P4發(fā)出請(qǐng)求Request(3,2,1)，系統(tǒng)24（4）P0發(fā)出請(qǐng)求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ù)：銀行家算法實(shí)例24（4）P0發(fā)出請(qǐng)求Request(0,2,0)，系統(tǒng)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＝(7,4,3)－(0,2,0)＝(7,2,3)銀行家算法實(shí)例25Available:＝Availab26MaxAllocationNeedAvailableP0753030723210P1322302020P2902302600P3222211011P4433002431顯然，對(duì)于所有進(jìn)程，條件Needi≤Available，均不成立。因此，P0

此次資源請(qǐng)求預(yù)分配的結(jié)果，使系統(tǒng)進(jìn)入不安全狀態(tài)，故應(yīng)撤消此次預(yù)分配。銀行家算法實(shí)例26MaxAllocationNeedAvailableP027練習(xí)資源進(jìn)程AllocationNeedAvailabler1r2r3r1r2r3r1r2r3P0P1P2P3P4311000110101000100012300010210120在銀行家算法中，若出現(xiàn)下面的資源分配情況：27練習(xí)資源AllocationNeedAva28試問：該狀態(tài)是否安全？如果進(jìn)程P2提出請(qǐng)求Request(0，1，0)，系統(tǒng)能否將資源分配給它？如果系統(tǒng)立即滿足P2的上述請(qǐng)求，則系統(tǒng)是否立即進(jìn)入死鎖狀態(tài)？練習(xí)28試問：練習(xí)計(jì)算機(jī)操作系統(tǒng)銀行家算法計(jì)算機(jī)操作系統(tǒng)銀行家算法30死鎖的“3W”WhatWhyHow什么是死鎖？為什么會(huì)發(fā)生死鎖？怎么解決死鎖？2死鎖的“3W”What什么是死鎖？為什么會(huì)發(fā)生死鎖？怎么解31死鎖的處理方法

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

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

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

（4）解除死鎖：撤消或掛起某些進(jìn)程以回收一些資源，用于解脫另一些處于死鎖的進(jìn)程。3死鎖的處理方法（1）預(yù)防死鎖：通過某些限制條件32避免死鎖—銀行家算法設(shè)銀行家有10萬周轉(zhuǎn)資金，P,Q,R分別需要8,3,9萬元搞項(xiàng)目，如果P已申請(qǐng)到了4萬，Q要申請(qǐng)2萬，R要申請(qǐng)4萬.Q1：客戶要求分期貸款，一旦得到每期貸款，就能夠歸還貸款Q2：銀行家應(yīng)謹(jǐn)慎的貸款，防止出現(xiàn)壞帳什么是銀行家問題？銀行家->操作系統(tǒng)周轉(zhuǎn)資金->系統(tǒng)資源貸款客戶->進(jìn)程當(dāng)某進(jìn)程請(qǐng)求分配資源時(shí)，系統(tǒng)假定先分配給它，之后若能找到一個(gè)進(jìn)程完成序列（安全序列），說明系統(tǒng)是安全的，可進(jìn)行實(shí)際分配；否則，讓申請(qǐng)者等待。銀行家算法的實(shí)現(xiàn)思想4避免死鎖—銀行家算法設(shè)銀行家有10萬周轉(zhuǎn)資金，P,Q,33表示形式含義Available（可用資源數(shù)組）Available[j]＝k現(xiàn)有資源j的數(shù)目為kMax（最大需求矩陣）Max[i,j]＝k進(jìn)程i對(duì)資源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表示形式含義AvailableAvailab34銀行家算法當(dāng)Pi發(fā)出資源請(qǐng)求，分配一個(gè)Request向量然后系統(tǒng)按下述流程進(jìn)行執(zhí)行：Requesti：是進(jìn)程Pi的請(qǐng)求向量如果Requesti[j]=K，表示進(jìn)程i需要K個(gè)Rj類型的資源。銀行家算法實(shí)現(xiàn)過程6銀行家算法Requesti：是進(jìn)程Pi的請(qǐng)求向量銀行家算法35736安全性算法實(shí)現(xiàn)過程安全性算法兩個(gè)向量：Work和FinishWork表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目（即在分配過程中，系統(tǒng)的可用資源數(shù)）。初始值Work∶=Available;Finish表示系統(tǒng)是否有足夠的資源分配給進(jìn)程i，使之運(yùn)行完成。初始值Finish[i]:=false當(dāng)有足夠資源分配給進(jìn)程時(shí)Finish[i]:=true8安全性算法實(shí)現(xiàn)過程安全性算法兩個(gè)向量：Work和Finis37938

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

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銀行家算法實(shí)例10假定系統(tǒng)中有五個(gè)進(jìn)程｛P0,P1,P39（1）T0時(shí)刻系統(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銀行家算法實(shí)例11（1）T0時(shí)刻系統(tǒng)是否安全？①向量初值40Chapter3處理機(jī)調(diào)度與死鎖FinishWork+AllocationAllocationNeedWorktrue532200122332P1AllocationNeedP0010743P1200122P2302600P3211011P400243112Chapter3處理機(jī)調(diào)度與死鎖FinishWor41Chapter3處理機(jī)調(diào)度與死鎖FinishWork+AllocationAllocationNeedWorktrue743532211011P3true532200122332P1AllocationNeedP0010743P1200122P2302600P3211011P400243113Chapter3處理機(jī)調(diào)度與死鎖FinishWor42Chapter3處理機(jī)調(diào)度與死鎖FinishWork+AllocationAllocationNeedWorktrue753743010743true743211011532true532200122332P0P3P1AllocationNeedP0010743P1200122P2302600P3211011P400243114Chapter3處理機(jī)調(diào)度與死鎖FinishWor43Chapter3處理機(jī)調(diào)度與死鎖FinishWork+AllocationAllocationNeedWorktrue1055753true753010743743302600true743211011532true532200122332P0P2P3P1AllocationNeedP0010743P1200122P2302600P3211011P400243115Chapter3處理機(jī)調(diào)度與死鎖FinishWor44Chapter3處理機(jī)調(diào)度與死鎖AllocationNeedP0010743P1200122P2302600P3211011P4002431true10570024311055P4FinishWork+AllocationAllocationNeedWorktrue1055753true753010743743302600true743211011532true532200122332P0P2P3P116Chapter3處理機(jī)調(diào)度與死鎖Allocatio45

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

→3

→

0→

2

→

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

所以，T0

時(shí)刻系統(tǒng)處于安全狀態(tài)！銀行家算法實(shí)例17④發(fā)現(xiàn)：目前可執(zhí)行的所有資源分配工作完成之46Chapter3處理機(jī)調(diào)度與死鎖由分析知：執(zhí)行完P(guān)1、P3

的資源分配請(qǐng)求之后，系統(tǒng)可用的資源數(shù)量可以滿足其它3個(gè)進(jìn)程的資源請(qǐng)求，則此時(shí)的資源分配順序已無關(guān)緊要。所以：安全序列可以不唯一！true10570024311055P4FinishWork+AllocationAllocationNeedWorktrue1055753true753010743743302600true743211011532true532200122332P0P2P3P118Chapter3處理機(jī)調(diào)度與死鎖由分析知：執(zhí)行完47（2）P1發(fā)出請(qǐng)求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向量：銀行家算法實(shí)例Request1(1,0,2)，Need1，Available19（2）P1發(fā)出請(qǐng)求Request(1,0,2)，系48

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)銀行家算法實(shí)例20Available:＝Availab49

④

執(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銀行家算法實(shí)例21④執(zhí)行安全性算法：在進(jìn)程集合中找50c’.則設(shè)P3順利執(zhí)行完成，從而有：

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

Finish[3]:＝true………執(zhí)行安全性算法檢查時(shí)，仍能夠得到安全序列{P1，P3，P0，P2，P4}，故請(qǐng)求向量Request1(1,0,2)發(fā)出時(shí)系統(tǒng)安全！銀行