銀行家算法安全性序列分析

1、銀行家算法安全性序列分析摘要：在操作系統(tǒng)的處理機(jī)調(diào)度的過程中，由于競爭資源或者進(jìn)程間推進(jìn)順序非法，都會(huì)導(dǎo)致死鎖的發(fā)生。本文主要研究如何利用銀行家算法可以避免死鎖，并分析銀行家算法安全性序列。關(guān)鍵詞：銀行家算法；安全性序列；避免死鎖引言處理死鎖的方法主要包括預(yù)防死鎖、避免死鎖、檢測死鎖和解除死鎖。而利用銀行家算法可以避免死鎖，在這一避免死鎖的過程中，銀行家算法安全性序列分析是尤為重要的。1. 銀行家算法中的數(shù)據(jù)結(jié)構(gòu) （1） 空閑資源向量Available。這是一個(gè)數(shù)組，它里面包括m個(gè)元素，這些元素都可以分別用來表示一種空閑的資源的數(shù)量的多少，系統(tǒng)中存儲(chǔ)的這種全部空閑的資源的數(shù)量的多少為它的初始值

2、，隨該類資源的分配和回收，其數(shù)值發(fā)生動(dòng)態(tài)地改變。如果Availablej=K，那么，系統(tǒng)中當(dāng)前存在K個(gè)Rj類資源。（2） 最大需求矩陣Max。Max矩陣是n×m維的，該矩陣定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對m類資源的最大需求。如果Maxi,j=K，那么，進(jìn)程i需要Rj類資源的最大數(shù)量的多少為K。（3） 分配矩陣Allocation。Allocation矩陣是n×m維的，該矩陣定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果Allocationi,j=K，那么，進(jìn)程i當(dāng)前已分得Rj類資源的數(shù)量的多少為K。（4） 需求矩陣Need。Need矩陣是n×m維的，

3、該矩陣定義了所有進(jìn)程仍然需求的各類資源數(shù)。如果Needi,j=K，那么，為了能夠完成其任務(wù)，進(jìn)程i還需要Rj類資源K個(gè)。 Needi,j=Maxi,j-Allocationi,j2. 銀行家算法設(shè)Requesti是進(jìn)程Pi的請求向量，如果Requestij=K，表示進(jìn)程Pi需要K個(gè)Rj類型的資源。當(dāng)Pi發(fā)出資源請求后，系統(tǒng)按下述步驟進(jìn)行檢查：（1） 如果RequestijNeedi,j，便轉(zhuǎn)向步驟2；否則認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù)大于它仍然需要的最大值。（2） 如果RequestijAvailablej，便轉(zhuǎn)向步驟（3）；否則， 表示尚無足夠資源，Pi須等待。（3） 系統(tǒng)試探著把資源分配給

4、進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值： Availablej=Availablej-Requestij; Allocationi,j=Allocationi,j+Requestij; Needi,j=Needi,j-Requestij;（4） 系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。如果安全，就正式將資源分配給進(jìn)程Pi，從而實(shí)現(xiàn)本次分配；反之，取消這次的試探分配，保持上一次的資源分配狀態(tài)，讓進(jìn)程Pi等待。3. 安全性算法 （1） 設(shè)置兩個(gè)向量： 工作向量Work：它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)量的多少，它含有m個(gè)元素，在執(zhí)行安全算法開始時(shí)，Work=Ava

5、ilable； Finish：它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開始時(shí)先做Finishi=false；當(dāng)有足夠資源分配給進(jìn)程時(shí)， 再令Finishi=true。（2） 從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程： Finishi=false； Needi,jWorkj； 如果找到，那么，執(zhí)行步驟（3）， 否則，執(zhí)行步驟（4）。（3） 當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行： Workj=Worki+Allocationi,j; Finishi=true; go to step 2;（4） 如果所有進(jìn)程的Finishi=true都滿足， 則表

6、示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。4. 銀行家算法安全性序列分析之例 假定系統(tǒng)中有五個(gè)進(jìn)程P0, P1, P2, P3, P4和三類資源A, B, C，各種資源的數(shù)量分別為10、5、7，在T0時(shí)刻的資源分配情況如表1 所示。表1 T0時(shí)刻的資源分配表資源情況進(jìn)程MaxAllocationNeedAvailableA B CA B CA B CA B CP07 5 30 1 07 4 33 3 2P13 2 22 0 01 2 2P29 0 23 0 26 0 0P32 2 22 1 10 1 1P44 3 30 0 24 3 1（1）T0時(shí)刻的安全性： 表2 T0時(shí)刻的安全序列資源

7、情況進(jìn)程WorkNeedAllocationWork+AllocationFinishA B CA B CA B CA B CP13 3 21 2 22 0 05 3 2TRUEP35 3 20 1 12 1 17 4 3TRUEP47 4 34 3 10 0 27 4 5TRUEP27 4 56 0 03 0 210 4 7TRUEP010 4 77 4 30 1 010 5 7TRUE（2） P1請求資源：P1發(fā)出請求向量Request1（1，0，2），系統(tǒng)按銀行家算法進(jìn)行檢查： Request1（1, 0, 2）Need1（1, 2, 2） Request1（1, 0, 2）Availa

8、ble1（3, 3, 2） 系統(tǒng)先假定可為P1分配資源，并修改Available, Allocation1和Need1向量，由此形成的資源變化情況如表2所示。表2 系統(tǒng)先假定可為P1分配資源時(shí)刻的資源分配表資源情況進(jìn)程MaxAllocationNeedAvailableA B CA B CA B CA B CP07 5 30 1 07 4 32 3 0P13 2 23 0 20 2 0P29 0 23 0 26 0 0P32 2 22 1 10 1 1P44 3 30 0 24 3 1 再利用安全性算法檢查此時(shí)系統(tǒng)是否安全。表3 P1申請資源時(shí)的安全性檢查資源情況進(jìn)程WorkNeedAlloc

9、ationWork+AllocationFinishA B CA B CA B CA B CP12 3 00 2 03 0 25 3 2TRUEP35 3 20 1 12 1 17 4 3TRUEP47 4 34 3 10 0 27 4 5TRUEP27 4 56 0 03 0 210 4 7TRUEP010 4 77 4 30 1 010 5 7TRUE（3） P4請求資源：P4發(fā)出請求向量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等待。參考文獻(xiàn)：1 崔建平. 深入探討銀行家算法J. 科技信息(學(xué)術(shù)研究), 2008,(17) . 2 侯剛. 深入解析銀行家算法J. 濰坊學(xué)院學(xué)報(bào), 2006,(02) . 3 曹現(xiàn)玲. 淺談銀行家算法J