對(duì)于改進(jìn)避免死鎖安全算法的策略研究

戴家剛

摘 要：隨著社會(huì)的不斷進(jìn)步以及科技的發(fā)展，避免死鎖的安全算法也成為了目前最為關(guān)注的問(wèn)題，因此為了能夠有效地節(jié)省檢測(cè)開(kāi)銷(xiāo)，將對(duì)避免死鎖的算法進(jìn)行相應(yīng)改進(jìn)，筆者也將針對(duì)改進(jìn)避免死鎖安全算法的策略進(jìn)行深入的探討和研究，為以后鎖的應(yīng)用發(fā)展奠定了堅(jiān)實(shí)基礎(chǔ)。本文將首先分析產(chǎn)生死鎖的必要因素，概述處理死鎖的具體方法，詳細(xì)闡述如何改進(jìn)避免死鎖安全算法的相關(guān)策略，希望可以為相關(guān)工作人員提供有用的參考。

關(guān)鍵詞：改進(jìn)策略 死鎖安全算法 研究 必要因素

中圖分類(lèi)號(hào)：TP273 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-3791（2018）10（b）-0008-02

1 產(chǎn)生死鎖的必要因素

在計(jì)算機(jī)的系統(tǒng)中，如果出現(xiàn)了死鎖的情況，那么必然是由如下因素造成的。

（1）互斥性。在規(guī)定的時(shí)間里，一個(gè)進(jìn)程只能被一個(gè)資源獨(dú)占應(yīng)用，一旦有別的進(jìn)程也想尋求此資源，那么必然需要進(jìn)行相應(yīng)的等待和釋放。

（2）等待以及保持。使進(jìn)程允許在不釋放已得資源的情況下，進(jìn)行等待新資源的分配。

（3）非剝奪性。一旦進(jìn)程獲得了一定資源，那么如果沒(méi)有使用完，是不能被其他的進(jìn)程掠奪的，必須由自身進(jìn)行一定的釋放。

（4）循環(huán)性等待。有一個(gè)等待的集合存在著，如{p1，p2，…，pn}，p1所等待的資源是被p2占用的，然而p2的是被p3占用的，……，一直到pn等待下一個(gè)可占用的資源。

2 處理死鎖的方法

處理死鎖的主要方法如下：（1）可以設(shè)定一定的規(guī)則使相應(yīng)的系統(tǒng)不受到損害，處于死鎖狀態(tài)；（2）在設(shè)定死鎖狀態(tài)后還要設(shè)定相應(yīng)的復(fù)活模式，但是如果想要能夠使系統(tǒng)及時(shí)的進(jìn)行復(fù)活，那么必然面臨著一定的困難同時(shí)還會(huì)付出昂貴的代價(jià)。然而在一般情況下將處理死鎖方法分為避免死鎖和阻止死鎖兩種方法。

2.1 阻止死鎖的方法

一旦發(fā)生死鎖的狀況，那么肯定是具備了上述四個(gè)必然因素，只要有其中一條不成立，那么就可能有效阻止死鎖的發(fā)生，但是阻止死鎖的辦法多種多樣，就不一一介紹了。

2.2 避免死鎖的方法

由dijkstra和habermann兩種共同結(jié)合而成稱(chēng)之為銀行家算法，在所有的算法中具有典型的作用，并且它可以適用于任何一個(gè)資源系統(tǒng)中。像是對(duì)于有很多種資源以及進(jìn)程的系統(tǒng)，都需要很多次的運(yùn)算，因此也就致使了有很大的開(kāi)銷(xiāo)。

其實(shí)每一個(gè)不同的資源類(lèi)型中幾乎只含有一個(gè)獨(dú)立個(gè)體，同時(shí)也只有一個(gè)最為有效的運(yùn)算方式，但是這個(gè)方式也是受限于分配圖的[2]。判定系統(tǒng)的安全狀態(tài)不但需要對(duì)系統(tǒng)圖中的閉合環(huán)路形成進(jìn)行尋找，而且還要進(jìn)行一定的n2運(yùn)算。筆者將針對(duì)此種方法進(jìn)行一定的改進(jìn)，將運(yùn)算級(jí)次降到n。

2.3 改進(jìn)的安全算法

當(dāng)進(jìn)程pi要請(qǐng)求資源分配的時(shí)候，只需要對(duì)r資源進(jìn)行相應(yīng)的檢查和標(biāo)志，同時(shí)和進(jìn)程pi所有請(qǐng)求邊以及宣告邊相連的資源頂點(diǎn)標(biāo)志為{F，r，j1，F(xiàn)，r，j2，…，F(xiàn)，r，jk}是否等同。如果F.rj=F.r.j，并且其中至少存在著一個(gè)資源頂點(diǎn)標(biāo)志與其它的相同，那么就說(shuō)明了此系統(tǒng)屬于安全不佳的狀態(tài)；相反是處于一個(gè)安全的狀態(tài)[3]。

例如：在圖1中顯示，系統(tǒng)是不具有一定的分配資源的。假如說(shuō)進(jìn)程p1對(duì)r1資源發(fā)出請(qǐng)求，系統(tǒng)所處的狀態(tài)是安全的，因此有效把資源r1分配給p1，這時(shí)候的資源分配圖就會(huì)變成圖1這種模式。

如果此時(shí)的進(jìn)程p3對(duì)資源r3進(jìn)行歸還，那么這時(shí)候的資源分配圖為如圖2所示。

3 改進(jìn)避免死鎖安全算法的相關(guān)策略

3.1 E-策略

有國(guó)外的相關(guān)研究人員提出了一種死鎖預(yù)防措施叫做E-策略，這種方法也是避免死鎖的一種有效措施。E-策略的實(shí)施就是將網(wǎng)中的全部嚴(yán)格極小信標(biāo)，之后再對(duì)全部的嚴(yán)格極小信標(biāo)添加一個(gè)控制庫(kù)，而控制庫(kù)所的輸出弧均指向原始網(wǎng)模型的源變遷，從而能夠有效保證擴(kuò)展網(wǎng)系統(tǒng)不會(huì)出現(xiàn)新的嚴(yán)格極小信標(biāo)，并且擴(kuò)展網(wǎng)系統(tǒng)也是一個(gè)良好的活性控制器。這種方法在使用的過(guò)程中雖然有著一定優(yōu)點(diǎn)，然而隨著使用時(shí)間的增加，也暴露出了很多的問(wèn)題。首先，E-策略的結(jié)構(gòu)比較復(fù)雜，這就導(dǎo)致其許可行為限制過(guò)大，還提升了計(jì)算復(fù)雜度。產(chǎn)生許可行為限制過(guò)大的問(wèn)題是因?yàn)檩敵龌【赶蛟季W(wǎng)模型的源變遷所造成的；而計(jì)算復(fù)雜度過(guò)大的問(wèn)題是因?yàn)橐?jì)算全部極小信標(biāo)本身就十分復(fù)雜；造成結(jié)構(gòu)復(fù)雜問(wèn)題出現(xiàn)的主要原因則是：E-策略需要對(duì)原始網(wǎng)模型全部的嚴(yán)格極小信標(biāo)增加控制庫(kù)所導(dǎo)致的。所以要想更好地使用E-策略，就需要根據(jù)實(shí)際情況進(jìn)行控制和調(diào)整，從而提升E-策略的使用效果。

3.2 H1-策略

H1-策略的在控制系統(tǒng)的過(guò)程也就是一個(gè)迭代過(guò)程，這是一種基于混合整數(shù)規(guī)劃技術(shù)避免出現(xiàn)死鎖的有效策略，這種策略可以找到在網(wǎng)絡(luò)中存在的最大可被清空信標(biāo)，這樣就可以有效將最大可被清空信標(biāo)中的對(duì)應(yīng)嚴(yán)格極小信標(biāo)導(dǎo)出，從而有效的避免出現(xiàn)死鎖問(wèn)題。而這種策略的使用同樣分為兩個(gè)步驟。第一步就是如E-策略相同的添加控制庫(kù)所，然后可以被清空信標(biāo)檢測(cè)出來(lái)，在對(duì)其添加控制庫(kù)所，然后如此一直迭代進(jìn)行，一直到?jīng)]有能夠被清空的信標(biāo)為止。完成這一步之后，就進(jìn)入第二步，然后還是使用如是B策略中的方法，也就是控制庫(kù)所的輸出弧均指向原始網(wǎng)模型的源變遷，在完成了這兩個(gè)步驟之后，控制庫(kù)所中就不會(huì)出現(xiàn)新的嚴(yán)格極小信標(biāo)，就能夠有效的避免出現(xiàn)死鎖的問(wèn)題。

3.3 H2-策略

H2-策略是一種基于H1-策略的有效改進(jìn)措施，這一策略的核心概念就是基本信標(biāo)的概念。這種策略主要是改進(jìn)H1-策略的第一個(gè)步驟，第二個(gè)步驟則與H1-策略相同。H2-策略的第一步是要將系統(tǒng)中的全部基本信標(biāo)找到，然后對(duì)每一個(gè)基本信標(biāo)添加控制庫(kù)所。這種方法的優(yōu)點(diǎn)是相比H1-策略所添加的控制庫(kù)所要更少。

4 結(jié)語(yǔ)

總而言之，需要重點(diǎn)強(qiáng)調(diào)的是只要系統(tǒng)處于安全狀態(tài)，那么必然不會(huì)出現(xiàn)死鎖的狀況；但是只要系統(tǒng)是不安全狀態(tài)，那么會(huì)致使死鎖狀況的發(fā)生，但是也有可能不會(huì)發(fā)生死鎖狀況，因此導(dǎo)致必要的等待出現(xiàn)。但是這種方法與其他的檢測(cè)方法相比造成的等待還是較少的?，F(xiàn)如今我們可以將方法進(jìn)行重新的命名，像是“觸網(wǎng)式”安全檢測(cè)。并且這種方法與直接檢測(cè)環(huán)路相比更具有一定的優(yōu)勢(shì)，能夠?qū)⑦\(yùn)算級(jí)次進(jìn)行有效降低，在一定程度上節(jié)約了成本和檢測(cè)開(kāi)銷(xiāo)。除此以外，這種觸網(wǎng)式檢測(cè)在等待圖中的充分應(yīng)用取得了明顯的效果。

參考文獻(xiàn)

[1] 朱淑芹，李俊青，王文宏.對(duì)改進(jìn)的基于DNA編碼和混沌的圖像加密算法的安全性分析[J].計(jì)算機(jī)應(yīng)用研究，2017，34（10）：3090-3093.

[2] 侯欣蕾，于蓮芝.基于改進(jìn)蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃[J].軟件導(dǎo)刊，2017（12）：162-164.

[3] 高思宇，余敬，馬林茂.稀土安全評(píng)價(jià)：集成算法改進(jìn)與實(shí)證[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2017，47（3）：90-101.