對于改進避免死鎖安全算法的策略研究

戴家剛

摘 要：隨著社會的不斷進步以及科技的發展，避免死鎖的安全算法也成為了目前最為關注的問題，因此為了能夠有效地節省檢測開銷，將對避免死鎖的算法進行相應改進，筆者也將針對改進避免死鎖安全算法的策略進行深入的探討和研究，為以后鎖的應用發展奠定了堅實基礎。本文將首先分析產生死鎖的必要因素，概述處理死鎖的具體方法，詳細闡述如何改進避免死鎖安全算法的相關策略，希望可以為相關工作人員提供有用的參考。

關鍵詞：改進策略 死鎖安全算法 研究 必要因素

中圖分類號：TP273 文獻標識碼：A 文章編號：1672-3791（2018）10（b）-0008-02

1 產生死鎖的必要因素

在計算機的系統中，如果出現了死鎖的情況，那么必然是由如下因素造成的。

（1）互斥性。在規定的時間里，一個進程只能被一個資源獨占應用，一旦有別的進程也想尋求此資源，那么必然需要進行相應的等待和釋放。

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

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

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

2 處理死鎖的方法

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

2.1 阻止死鎖的方法

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

2.2 避免死鎖的方法

由dijkstra和habermann兩種共同結合而成稱之為銀行家算法，在所有的算法中具有典型的作用，并且它可以適用于任何一個資源系統中。像是對于有很多種資源以及進程的系統，都需要很多次的運算，因此也就致使了有很大的開銷。

其實每一個不同的資源類型中幾乎只含有一個獨立個體，同時也只有一個最為有效的運算方式，但是這個方式也是受限于分配圖的[2]。判定系統的安全狀態不但需要對系統圖中的閉合環路形成進行尋找，而且還要進行一定的n2運算。筆者將針對此種方法進行一定的改進，將運算級次降到n。

2.3 改進的安全算法

當進程pi要請求資源分配的時候，只需要對r資源進行相應的檢查和標志，同時和進程pi所有請求邊以及宣告邊相連的資源頂點標志為{F，r，j1，F，r，j2，…，F，r，jk}是否等同。如果F.rj=F.r.j，并且其中至少存在著一個資源頂點標志與其它的相同，那么就說明了此系統屬于安全不佳的狀態；相反是處于一個安全的狀態[3]。

例如：在圖1中顯示，系統是不具有一定的分配資源的。假如說進程p1對r1資源發出請求，系統所處的狀態是安全的，因此有效把資源r1分配給p1，這時候的資源分配圖就會變成圖1這種模式。

如果此時的進程p3對資源r3進行歸還，那么這時候的資源分配圖為如圖2所示。

3 改進避免死鎖安全算法的相關策略

3.1 E-策略

有國外的相關研究人員提出了一種死鎖預防措施叫做E-策略，這種方法也是避免死鎖的一種有效措施。E-策略的實施就是將網中的全部嚴格極小信標，之后再對全部的嚴格極小信標添加一個控制庫，而控制庫所的輸出弧均指向原始網模型的源變遷，從而能夠有效保證擴展網系統不會出現新的嚴格極小信標，并且擴展網系統也是一個良好的活性控制器。這種方法在使用的過程中雖然有著一定優點，然而隨著使用時間的增加，也暴露出了很多的問題。首先，E-策略的結構比較復雜，這就導致其許可行為限制過大，還提升了計算復雜度。產生許可行為限制過大的問題是因為輸出弧均指向原始網模型的源變遷所造成的；而計算復雜度過大的問題是因為要計算全部極小信標本身就十分復雜；造成結構復雜問題出現的主要原因則是：E-策略需要對原始網模型全部的嚴格極小信標增加控制庫所導致的。所以要想更好地使用E-策略，就需要根據實際情況進行控制和調整，從而提升E-策略的使用效果。

3.2 H1-策略

H1-策略的在控制系統的過程也就是一個迭代過程，這是一種基于混合整數規劃技術避免出現死鎖的有效策略，這種策略可以找到在網絡中存在的最大可被清空信標，這樣就可以有效將最大可被清空信標中的對應嚴格極小信標導出，從而有效的避免出現死鎖問題。而這種策略的使用同樣分為兩個步驟。第一步就是如E-策略相同的添加控制庫所，然后可以被清空信標檢測出來，在對其添加控制庫所，然后如此一直迭代進行，一直到沒有能夠被清空的信標為止。完成這一步之后，就進入第二步，然后還是使用如是B策略中的方法，也就是控制庫所的輸出弧均指向原始網模型的源變遷，在完成了這兩個步驟之后，控制庫所中就不會出現新的嚴格極小信標，就能夠有效的避免出現死鎖的問題。

3.3 H2-策略

H2-策略是一種基于H1-策略的有效改進措施，這一策略的核心概念就是基本信標的概念。這種策略主要是改進H1-策略的第一個步驟，第二個步驟則與H1-策略相同。H2-策略的第一步是要將系統中的全部基本信標找到，然后對每一個基本信標添加控制庫所。這種方法的優點是相比H1-策略所添加的控制庫所要更少。

4 結語

總而言之，需要重點強調的是只要系統處于安全狀態，那么必然不會出現死鎖的狀況；但是只要系統是不安全狀態，那么會致使死鎖狀況的發生，但是也有可能不會發生死鎖狀況，因此導致必要的等待出現。但是這種方法與其他的檢測方法相比造成的等待還是較少的?，F如今我們可以將方法進行重新的命名，像是“觸網式”安全檢測。并且這種方法與直接檢測環路相比更具有一定的優勢，能夠將運算級次進行有效降低，在一定程度上節約了成本和檢測開銷。除此以外，這種觸網式檢測在等待圖中的充分應用取得了明顯的效果。

參考文獻

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

[2] 侯欣蕾，于蓮芝.基于改進蟻群算法的移動機器人路徑規劃[J].軟件導刊，2017（12）：162-164.

[3] 高思宇，余敬，馬林茂.稀土安全評價：集成算法改進與實證[J].數學的實踐與認識，2017，47（3）：90-101.