10 操作系统第二章 进程管理 死锁、死锁的处理策略 银行家算法
文章目錄
- 1 死鎖
- 1.1 死鎖定義
- 1.2 死鎖、饑餓、死循環的區別
- 1.3 死鎖產生的必要條件
- 1.4 什么時候會發生死鎖
- 1.5 死鎖的處理策略
- 1.6 死鎖的概念小結
- 2 死鎖預防
- 2.1 破壞互斥條件
- 2.2 破壞不剝奪條件
- 2.3 破壞請求和保持條件
- 2.4 破壞循環等待條件
- 2.5 預防死鎖小結
- 3 死鎖避免
- 3.1 安全序列
- 3.2 銀行家算法
- 3.2.1 手動實現銀行家算法
- 3.2.2 銀行家算法描述
- 4 死鎖的檢測和解除
- 4.1 死鎖的檢測
- 4.2 死鎖的避免
- 4.3 死鎖的檢測與避免小結
1 死鎖
1.1 死鎖定義
產生條件：每個人都占有一個資源，同時又在等待另一個人手里的資源。發生“死鎖”
在并發環境下，各進程因競爭資源而造成的一種互相等待對方手里的資源，導致各進程都阻塞，都無法向前推進的現象，這就是“死鎖”。發生死鎖后若無外力干涉，這些進程都將無法向前推進。
1.2 死鎖、饑餓、死循環的區別
1.3 死鎖產生的必要條件
產生死鎖必須同時滿足一下四個條件，只要其中任一條件不成立，死鎖就不會發生。
注意：
1.4 什么時候會發生死鎖
各進程對不可剝奪的資源（如打印機）的競爭可能引起死鎖，對可剝奪的資源（CPU）的競爭是不會引起死鎖的。
請求和釋放資源的順序不當，也會導致死鎖。例如，并發執行的進程P1、P2分別申請并占用了資源R1、R2，之后進程P1又緊接著申請資源R2，而進程P2又申請資源R1，兩者會因為申請的資源被對方占有而阻塞，從而發生死鎖
在生產者-消費者問題中，若實現互斥的P操作在實現同步的P操作之前，就有可能導致死鎖。（可以把互斥信號量、同步信號量也看做是一種抽象的系統資源）
總之，對不可剝奪資源的不合理分配，可能導致死鎖。
1.5 死鎖的處理策略
1.6 死鎖的概念小結
2 死鎖預防
2.1 破壞互斥條件
互斥條件：只有對必須互斥使用的資源的爭搶才會導致死鎖。
如果把只能互斥使用的資源改造為允許共享使用，則系統不會進入死鎖狀態。比如:SPOOLing技術。 操作系統可以采用SPOOLing 技術把獨占設備在邏輯上改造成共享設備。比如，用SPOOLing技術將打印機改造為共享設備…
該策略的缺點：
并不是所有的資源都可以改造成可共享使用的資源。并且為了系統安全，很多地方還必須保護這種互斥性。因此，很多時候都無法破壞互斥條件。
2.2 破壞不剝奪條件
不剝奪條件：進程所獲得的資源在未使用完之前，不能由其他進程強行奪走，只能主動釋放。
破壞不剝奪條件：
方案一：當某個進程請求新的資源得不到滿足時，它必須立即釋放保持的所有資源，待以后需要時再重新申請。也就是說，即使某些資源尚未使用完，也需要主動釋放，從而破壞了不可剝奪條件。
方案二：當某個進程需要的資源被其他進程所占有的時候，可以由操作系統協助，將想要的資源強行剝奪。這種方式一般需要考慮各進程的優先級（比如：剝奪調度方式，就是將處理機資源強行剝奪給優先級更高的進程使用）
該策略的缺點：
2.3 破壞請求和保持條件
請求和保持條件：進程已經保持了至少一個資源，但又提出了新的資源請求，而該資源又被其他進程占有，此時請求進程被阻塞，但又對自己已有的資源保持不放。
可以采用靜態分配方法，即進程在運行前一次申請完它所需要的全部資源，在它的資源未滿足前， 不讓它投入運行。一旦投入運行后，這些資源就一直歸它所有，該進程就不會再請求別的任何資源了。
該策略實現起來簡單，但也有明顯的缺點： 有些資源可能只需要用很短的時間，因此如果進程的整個運行期間都一直保持著所有資源，就會造成嚴重的資源浪費，資源利用率極低。另外，該策略也有可能導致某些進程饑餓。
2.4 破壞循環等待條件
循環等待條件：存在一種進程資源的循環等待鏈，鏈中的每一個進程已獲得的資源同時被下一個進程所請求。
可采用順序資源分配法。首先給系統中的資源編號，規定每個進程必須按編號遞增的順序請求資源， 同類資源（即編號相同的資源）一次申請完。
原理分析：一個進程只有已占有小編號的資源時，才有資格申請更大編號的資源。按此規則，已持有大編號資源的進程不可能逆向地回來申請小編號的資源，從而就不會產生循環等待的現象。
該策略的缺點：
2.5 預防死鎖小結
3 死鎖避免
3.1 安全序列
所謂安全序列，就是指如果系統按照這種序列分配資源，則每個進程都能順利完成。只要能找出一個安全序列，系統就是安全狀態。當然，安全序列可能有多個。
如果分配了資源之后，系統中找不出任何一個安全序列，系統就進入了不安全狀態。這就意味著之后可能所有進程都無法順利的執行下去。當然，如果有進程提前歸還了一些資源，那系統也有可能重新回到安全狀態，不過我們在分配資源之前總是要考慮到最壞的情況。
如果系統處于安全狀態，就一定不會發生死鎖，如果系統進入不安全，就可能發生死鎖（處于不安全狀態未必就是發生了死鎖，但發生死鎖時一定是在不安全狀態）
因此可以在資源分配之前預先判斷這次分配是否會導致系統進入不安全狀態，以此決定是否答應資源分配請求。這也是“銀行家算法”的核心思想。
3.2 銀行家算法
核心思想：在進程提出資源申請時，先預判此次分配是否會導致系統進入不安全狀態。如果會進入不安全狀態，就暫時不答應這次請求，讓該進程先阻塞等待。
思考：在計算機系統中會有多種多樣的資源，如何用銀行家算法多種資源的分配情況呢？
3.2.1 手動實現銀行家算法
可以把多種資源拓展為多維的向量。比如：系統中有5個進程PO~P4，3種資源RO~R2，初始數量為（10，5，7），則某一時刻的情況可表示如下：
| P0 | （7,5,3） | （0,1,0） |
| P1 | （3,2,2） | （2,0,0） |
| P2 | （9,0,2） | （3,0,2） |
| P3 | （2,2,2） | （2,1,1） |
| P4 | （4,3,3） | （0,0,2） |
此時總共已分配（7，2，5），還剩余（3，3，2）
可把最大需求、已分配的數據看作矩陣，兩矩陣相減，就可算出各進程最多還需要多少資源了
| P0 | （7,5,3） | （0,1,0） | （7,4,3） |
| P1 | （3,2,2） | （2,0,0） | （1,2,2） |
| P2 | （9,0,2） | （3,0,2） | （6,0,0） |
| P3 | （2,2,2） | （2,1,1） | （0,1,1） |
| P4 | （4,3,3） | （0,0,2） | （4,3,1） |
思考：此時系統是否處于安全狀態？
思路：嘗試找出一個安全序列…
（2，1，1）+（5，3，2）=（7，4，3）
（7，5，3）>（6,0,0），此時P2滿足需求，加入安全序列，等P2結束了就會歸還資源。于是，資源數就可以增加到（3，0，2）+（7，5，3）=（10，5，5）
（10，5，3）>（4,3,0），此時P4滿足需求，加入安全序列，等P4結束了就會歸還資源。于是，資源數就可以增加到（0，0，2）+（10，5，3）=（10，5，7），恢復到原來初始數量。
以此類推，共五次循環檢查即可將5個進程都加入安全序列中，最終可得一個安全序列。本次安全系列即：P1、P3、P0、P2、P4。
該算法稱為安全性算法，可以很方便地用代碼實現以上流程，每一輪檢查都從編號較小的進程開始檢查。
實際做題時可以更快速的得到安全序列。
資源總數（10，5，7），剩余可用資源（10，5，7）-（7，2，5）=（3，3，2）
| P0 | （7,5,3） | （0,1,0） | （7,4,3） |
| P1 | （3,2,2） | （2,0,0） | （1,2,2） |
| P2 | （9,0,2） | （3,0,2） | （6,0,0） |
| P3 | （2,2,2） | （2,1,1） | （0,1,1） |
| P4 | （4,3,3） | （0,0,2） | （4,3,1） |
經對比發現，（3，3，2）可滿足P1、P3，說明無論如何，這兩個進程的資源需求一定是可以依次被滿足的，因此P1、P3一定可以順利的執行完，并歸還資源。可把P1、P3先加入安全序列。
（2，0，0）+（2，1，1）+（3，3，2）=（7，4，3）
去除P1、P3，分析PO、P2、P4
資源總數（10，5，7），剩余可用資源（7，4，3）
| P0 | （7,5,3） | （0,1,0） | （7,4,3） |
| P2 | （9,0,2） | （3,0,2） | （6,0,0） |
| P4 | （4,3,3） | （0,0,2） | （4,3,1） |
剩下的PO、P2、P4都可被滿足。同理，這些進程都可以加入安全序列。
于是，5個進程全部加入安全序列，說明此時系統處于安全狀態，暫不可能發生死鎖。
3.2.2 銀行家算法描述
假設系統中有n個進程，m種資源
每個進程在運行前先聲明對各種資源的最大需求數，則可用一個n*m的矩陣（可用二維數組實現）表示所有進程對各種資源的最大需求數。
不妨稱為最大需求矩陣Max，Max[i，j]=K表示進程Pi最多需要K個資源Rj。同理，系統可以用一個n*m的分配矩陣Allocation表示對所有進程的資源分配情況。Max-Allocation= Need矩陣，表示各進程最多還需要多少各類資源。
另外，還要用一個長度為m的一維數組Available表示當前系統中還有多少可用資源。
某進程Pi向系統申請資源，可用一個長度為m的一維數組Request；表示本次申請的各種資源量。
可用銀行家算法預判本次分配是否會導致系統進入不安全狀態：
銀行家算法數據結構：
- 長度為m的一維數組Available表示還有多少可用資源
- n*m矩陣Max表示各進程對資源的最大需求數
- n*m矩陣Allocation表示已經給各進程分配了多少資源
- Max-Allocation=Need矩陣表示各進程最多還需要多少資源
- 用長度為m的一位數組Request表示進程此次申請的各種資源數
銀行家算法步驟：
安全性算法步驟：
系統處于不安全狀態未必死鎖，但死鎖時一定處于不安全狀態。系統處于安全狀態一定不會死鎖。
4 死鎖的檢測和解除
4.1 死鎖的檢測
為了能對系統是否已發生了死鎖進行檢測，必須：
R2資源有2個，R1資源有3個，P1進程請求1個R2資源，P2進程請求1個R1資源，R1給P1分配了兩個資源，R1給P2進程分配了1個資源，R2給P2進程分配了兩個資源
以下就是圖的表示：
如何由圖形判斷系統是否處于死鎖狀態？
上圖中P1進程僅請求1個R2資源，而R2資源只分配出去了1個，而R2資源有2個，所以還有一個空閑可分配給P1，P1進程此次請求可以被滿足，因此不會被阻塞，可以順利執行下去；
P2進程請求1個R1資源，而R1的3個資源都被分配出去了，無空閑可分配給P2，P1進程此次請求不可以被滿足，因此會被阻塞，無法順利執行下去。
P1執行完畢，把所有資源歸還系統，不會在申請資源，可以將P1進程所連的邊抹去
此時P2可以申請1個R1資源，P2進程被喚醒執行，執行完畢后，歸還系統資源，并且不對任何一種資源提出請求，將P2進程所連的邊抹去
如果最終不能消除所有邊，那么此時就是發生了死鎖
P1要申請2個R2資源，此時R2無空閑可分配，P2要請求1個R1資源，此時R1無空閑可分配，P3可順利執行，執行完畢歸還1個R2，此時R2有1個空閑資源，但P1申請仍然阻塞，同樣P2也被阻塞
最終還連著邊的那些進程就是處于死鎖狀態的進程。
所以P3進程不是死鎖進程，P1、P2進程是死鎖進程
檢測死鎖的算法：
（即找出一條有向邊與它相連，且該向邊對應資源的申請數量小于等于系統中已有空閑資源數量。
如下圖中，R1沒有空閑資源，R2有 1個空閑資源。若所有的連接該進程的邊均滿足上述條件，則這個進程能繼續運行直至完成，然后釋放它所占有的所有資源）。消去它所有的請求邊和分配邊，使之稱為孤立的結點。在下圖中， P1是滿足這一條件的進程結點，于是將P1的所有邊消去。
4.2 死鎖的避免
一旦檢測出死鎖的發生，就應該立即解除死鎖。
并不是系統中所有的進程都是死鎖狀態，用死鎖檢測算法化簡資源分配圖后，還連著邊的那些進程就是死鎖進程
解除死鎖的主要方法有：
如何決定對哪一進程實現以上3個方法解除死鎖呢？
從以下5個角度考慮：
4.3 死鎖的檢測與避免小結
總結
以上是生活随笔為你收集整理的10 操作系统第二章 进程管理 死锁、死锁的处理策略 银行家算法的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： ASP.NET MVC教程六：两个配置文
- 下一篇： 知识图谱最新权威综述论文解读：时序知识图