系統(tǒng)安全狀態(tài)的定義

1．安全狀態(tài)

在避免死鎖的方法中度秘，允許進(jìn)程動(dòng)態(tài)地申請(qǐng)資源，但系統(tǒng)在進(jìn)行資源分配之前喝峦，應(yīng)先計(jì)算此次資源分配的安全性势誊。若此次分配不會(huì)導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，則將資源分配給進(jìn)程谣蠢；否則粟耻，令進(jìn)程等待。

雖然并非所有的不安全狀態(tài)都必然會(huì)轉(zhuǎn)為死鎖狀態(tài)眉踱，但當(dāng)系統(tǒng)進(jìn)入不安全狀態(tài)后挤忙，便有可能進(jìn)而進(jìn)入死鎖狀態(tài)；反之谈喳，只要系統(tǒng)處于安全狀態(tài)册烈，系統(tǒng)便可避免進(jìn)入死鎖狀態(tài)。

因此婿禽，避免死鎖的實(shí)質(zhì)在于：系統(tǒng)在進(jìn)行資源分配時(shí)赏僧，如何使系統(tǒng)不進(jìn)入不安全狀態(tài)。

利用銀行家算法避免死鎖

1．銀行家算法中的數(shù)據(jù)結(jié)構(gòu)

(1) 可利用資源向量Available扭倾。這是一個(gè)含有m個(gè)元素的數(shù)組淀零，其中的每一個(gè)元素代表一類(lèi)可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類(lèi)全部可用資源的數(shù)目膛壹，其數(shù)值隨該類(lèi)資源的分配和回收而動(dòng)態(tài)地改變驾中。如果Available[j]=K，則表示系統(tǒng)中現(xiàn)有Rj類(lèi)資源K個(gè)模聋。

(2) 最大需求矩陣Max肩民。這是一個(gè)n×m的矩陣，它定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì)m類(lèi)資源的最大需求撬槽。如果Max[i,j]=K此改，則表示進(jìn)程i需要Rj類(lèi)資源的最大數(shù)目為K。

(3) 分配矩陣Allocation侄柔。這也是一個(gè)n×m的矩陣共啃，它定義了系統(tǒng)中每一類(lèi)資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果Allocation[i,j]=K暂题，則表示進(jìn)程i當(dāng)前已分得R j類(lèi)資源的數(shù)目為K移剪。

(4) 需求矩陣Need。這也是一個(gè)n×m的矩陣薪者，用以表示每一個(gè)進(jìn)程尚需的各類(lèi)資源數(shù)纵苛。如果Need[i,j]=K，則表示進(jìn)程i還需要R j類(lèi)資源K個(gè)言津，方能完成其任務(wù)攻人。

上述三個(gè)矩陣間存在下述關(guān)系：

Need[i, j]=Max[i, j]-Allocation[i, j]

2．銀行家算法

設(shè)Request i是進(jìn)程Pi的請(qǐng)求向量，如果Request i[j]=K悬槽，表示進(jìn)程P i需要K個(gè)R j類(lèi)型的資源怀吻。當(dāng)P i發(fā)出資源請(qǐng)求后，系統(tǒng)按下述步驟進(jìn)行檢查：

(1) 如果Request i[j]≤Need[i,j]初婆，便轉(zhuǎn)向步驟(2)蓬坡；否則認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù)已超過(guò)它所宣布的最大值磅叛。

(2) 如果Request i[j]≤Available[j]屑咳，便轉(zhuǎn)向步驟(3)；否則弊琴，表示尚無(wú)足夠資源兆龙，Pi須等待。

(3) 系統(tǒng)試探著把資源分配給進(jìn)程P i敲董，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：

Available[j]:= Available[j]-Request i[j]详瑞；

Allocation[i,j]:= Allocation[i,j]+Request i[j]；

Need[i,j]:= Need[i,j]-Request i[j]臣缀；

(4)系統(tǒng)執(zhí)行安全性算法坝橡，檢查此次資源分配后系統(tǒng)是否處于安全狀態(tài)。若安全精置，才正式將資源分配給進(jìn)程Pi计寇，以完成本次分配；否則脂倦，將本次的試探分配作廢番宁，恢復(fù)原來(lái)的資源分配狀態(tài)，讓進(jìn)程Pi等待赖阻。

3．安全性算法

系統(tǒng)所執(zhí)行的安全性算法可描述如下：

(1) 設(shè)置兩個(gè)向量：

① 工作向量Work蝶押，它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類(lèi)資源數(shù)目，它含有m個(gè)元素火欧，在執(zhí)行安全算法開(kāi)始時(shí)棋电，Work:=Available茎截。

② Finish，它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程赶盔，使之運(yùn)行完成企锌。開(kāi)始時(shí)先做Finish[i]:=false；當(dāng)有足夠資源分配給進(jìn)程時(shí)于未，再令Finish[i]:=true撕攒。

(2) 從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程：

① Finish[i]=false；

② Need[i,j]≤Work[j]烘浦；若找到抖坪，執(zhí)行步驟(3)，否則闷叉，執(zhí)行步驟(4)擦俐。

(3) 當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行片习，直至完成捌肴，并釋放出分配給它的資源，故應(yīng)執(zhí)行：

Work[j]:= Work[j]+Allocation[i,j]藕咏；

Finish[i]:=true状知；

go to step （2）；

(4) 如果所有進(jìn)程的Finish[i]=true都滿足孽查，則表示系統(tǒng)處于安全狀態(tài)饥悴；否則，系統(tǒng)處于不安全狀態(tài)盲再。

4．銀行家算法實(shí)例

假定系統(tǒng)中有五個(gè)進(jìn)程{P0西设，P1，P2答朋，P3贷揽，P4}和三類(lèi)資源{A，B梦碗，C}禽绪，各種資源的數(shù)量分別為10、5洪规、7印屁，在T0時(shí)刻的資源分配情況如圖示。 （先忽略P1第二行的括號(hào)）

(1)T0時(shí)刻的安全性：利用安全性算法對(duì)T0時(shí)刻的資源分配情況進(jìn)行分析如下圖可知斩例，在T0時(shí)刻存在著一個(gè)安全序列{P1雄人，P3，P4念赶，P2础钠，P0}恰力，故系統(tǒng)是安全的。

(2) ?P1請(qǐng)求資源：P1發(fā)出請(qǐng)求向量Request1(1珍坊，0牺勾，2)正罢，系統(tǒng)按銀行家算法進(jìn)行檢查：

① Request1(1阵漏，0，2)≤Need1(1翻具，2履怯，2)

② Request1(1，0裆泳，2)≤Available1(3叹洲，3，2)

③ 系統(tǒng)先假定可為P1分配資源工禾，并修改Available运提，Allocation1和Need1向量，形成的資源變化情況如下圖圓括號(hào)所示

④ 再利用安全性算法檢查此時(shí)系統(tǒng)是否安全闻葵。如圖所示民泵。

(3) ?P4請(qǐng)求資源：P4發(fā)出請(qǐng)求向量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等待祥得。（附：操作系統(tǒng)第三版這里寫(xiě)成了≤符號(hào)兔沃，需更正）

(4) ?P0請(qǐng)求資源：P0發(fā)出請(qǐng)求向量Requst0(0，2级及，0)乒疏，系統(tǒng)按銀行家算法進(jìn)行檢查：

① Request0(0，2饮焦，0)≤Need0(7怕吴，4窍侧，3)；

② Request0(0转绷，2伟件，0)≤Available(2，3议经，0)斧账；

③ 系統(tǒng)暫時(shí)先假定可為P0分配資源，并修改有關(guān)數(shù)據(jù)煞肾，如圖所示咧织。

(5) 進(jìn)行安全性檢查：可用資源Available(2，1籍救，0)已不能滿足任何進(jìn)程的需要习绢，故系統(tǒng)進(jìn)入不安全狀態(tài)，此時(shí)系統(tǒng)不分配資源蝙昙。

本文由Cout_Sev 搜集整理

自《計(jì)算機(jī)操作系統(tǒng)（第三版）》（西安電子科技大學(xué)出版社）闪萄，

轉(zhuǎn)載注明出處。

謝謝奇颠！