在并發(fā)程序設計中,死鎖 (deadlock) 是一種十分常見(jiàn)的邏輯錯誤。通過(guò)采用正確的編程方式,死鎖的發(fā)生不難避免。
死鎖的四個(gè)必要條件
在計算機專(zhuān)業(yè)的本科教材中,通常都會(huì )介紹死鎖的四個(gè)必要條件。這四個(gè)條件缺一不可,或者說(shuō)只要破壞了其中任何一個(gè)條件,死鎖就不可能發(fā)生。我們來(lái)復習一下,這四個(gè)條件是:
?互斥(Mutual exclusion):存在這樣一種資源,它在某個(gè)時(shí)刻只能被分配給一個(gè)執行緒(也稱(chēng)為線(xiàn)程)使用;
?持有(Hold and wait):當請求的資源已被占用從而導致執行緒阻塞時(shí),資源占用者不但無(wú)需釋放該資源,而且還可以繼續請求更多資源;
?不可剝奪(No preemption):執行緒獲得到的互斥資源不可被強行剝奪,換句話(huà)說(shuō),只有資源占用者自己才能釋放資源;
?環(huán)形等待(Circular wait):若干執行緒以不同的次序獲取互斥資源,從而形成環(huán)形等待的局面,想象在由多個(gè)執行緒組成的環(huán)形鏈中,每個(gè)執行緒都在等待下一個(gè)執行緒釋放它持有的資源。
解除死鎖的必要條件
不難看出,在死鎖的四個(gè)必要條件中,第二、三和四項條件比較容易消除。通過(guò)引入事務(wù)機制,往往可以消除第二、三兩項條件,方法是將所有上鎖操作均作為事務(wù)對待,一旦開(kāi)始上鎖,即確保全部操作均可回退,同時(shí)通過(guò)鎖管理器檢測死鎖,并剝奪資源(回退事務(wù))。這種做法有時(shí)會(huì )造成較大開(kāi)銷(xiāo),而且也需要對上鎖模式進(jìn)行較多改動(dòng)。
消除第四項條件是比較容易且代價(jià)較低的辦法。具體來(lái)說(shuō)這種方法約定:上鎖的順序必須一致。具體來(lái)說(shuō),我們人為地給鎖指定一種類(lèi)似“水位”的方向性屬性。無(wú)論已持有任何鎖,該執行緒所有的上鎖操作,必須按照一致的先后順序從低到高(或從高到低)進(jìn)行,且在一個(gè)系統中,只允許使用一種先后次序。
請注意,放鎖的順序并不會(huì )導致死鎖。也就是說(shuō),盡管按照 鎖A, 鎖B, 放A, 放B 這樣的順序來(lái)進(jìn)行鎖操作看上去有些怪異,但是只要大家都按先A后B的順序上鎖,便不會(huì )導致死鎖。
舉例
假如有三個(gè)對象A、B、C,我們人為約定它們的鎖序是: A 先于 B 先于 C。舉例說(shuō)來(lái),下列鎖序均為合法:
? 鎖C,放C
? 鎖B,放B
? 鎖B,鎖C,放B,放C
? 鎖B,鎖C,放C,放B
? 鎖A,放A
? 鎖A,鎖C,放A,放C
? 鎖A,鎖C,放C,放A
? 鎖A,鎖B,放A,放B
? 鎖A,鎖B,放B,放A
? 鎖A,鎖B,鎖C,放A,放B,放C
? 鎖A,鎖B,鎖C,放C,放B,放A
而在上面定義的系統中,可能導致發(fā)生死鎖典型上鎖序列包括:
? 鎖B,鎖A,鎖C,放C,放A,放B
(因為先B后A的上鎖順序違反了鎖序約定,如果另一執行緒同時(shí)按照先A后B的順序上鎖,則可能由于執行緒甲獲得了B,執行緒乙獲得了A,而導致雙方同時(shí)等待對方釋放所持有的鎖,從而形成死鎖局面;解法是將操作序列中增加適當的鎖操作,即改為鎖B,放B,鎖A,鎖B,鎖C,放C,放A,放B)
或者說(shuō),只要拿鎖的時(shí)候不出現逆序(例如拿著(zhù)C的時(shí)候試圖抓B或A,或者拿著(zhù)B的時(shí)候試圖抓A),并出現潛在逆序的時(shí)候先放掉“小”鎖再抓大的,就一定不造成死鎖了。
1、避免給一個(gè)鎖嵌套上鎖,在持有一個(gè)鎖的時(shí)候,不要再給這個(gè)鎖上鎖。
如果使用多個(gè)鎖,使用std::lock。2、在持有鎖時(shí),不要調用別人提供的函數,因為你不清楚別人的代碼怎么實(shí)現的,不知道它是不是在使用鎖。
3、給多個(gè)鎖上鎖時(shí),固定順序。如果在給多個(gè)所上鎖,并且無(wú)法使用std::lock,最好的做法就是在每一個(gè)線(xiàn)程中,都按照同樣的順序。
4、分層次來(lái)使用鎖,把程序分成幾個(gè)層次。區分每個(gè)層次中使用的鎖,當一個(gè)線(xiàn)程已經(jīng)持有更低層次的鎖時(shí),不允許使用高層次的鎖。
可以在程序運行時(shí)給不同的鎖加上層次號,記錄每個(gè)線(xiàn)程持有的鎖。擴展資料:解決方法在系統中已經(jīng)出現死鎖后,應該及時(shí)檢測到死鎖的發(fā)生,并采取適當的措施來(lái)解除死鎖。
死鎖預防。這是一種較簡(jiǎn)單和直觀(guān)的事先預防的方法。
方法是通過(guò)設置某些限制條件,去破壞產(chǎn)生死鎖的四個(gè)必要條件中的一個(gè)或者幾個(gè),來(lái)預防發(fā)生死鎖。預防死鎖是一種較易實(shí)現的方法,已被廣泛使用。
但是由于所施加的限制條件往往太嚴格,可能會(huì )導致系統資源利用率和系統吞吐量降低。死鎖避免。
系統對進(jìn)程發(fā)出的每一個(gè)系統能夠滿(mǎn)足的資源申請進(jìn)行動(dòng)態(tài)檢查,并根據檢查結果決定是否分配資源;如果分配后系統可能發(fā)生死鎖,則不予分配,否則予以分配。這是一種保證系統不進(jìn)入死鎖狀態(tài)的動(dòng)態(tài)策略。
死鎖檢測和解除。先檢測:這種方法并不須事先采取任何限制性措施,也不必檢查系統是否已經(jīng)進(jìn)入不安全區,此方法允許系統在運行過(guò)程中發(fā)生死鎖。
但可通過(guò)系統所設置的檢測機構,及時(shí)地檢測出死鎖的發(fā)生,并精確地確定與死鎖有關(guān)的進(jìn)程和資源。檢測方法包括定時(shí)檢測、效率低時(shí)檢測、進(jìn)程等待時(shí)檢測等。
然后解除死鎖:采取適當措施,從系統中將已發(fā)生的死鎖清除掉。這是與檢測死鎖相配套的一種措施。
當檢測到系統中已發(fā)生死鎖時(shí),須將進(jìn)程從死鎖狀態(tài)中解脫出來(lái)。常用的實(shí)施方法是撤銷(xiāo)或掛起一些進(jìn)程,以便回收一些資源,再將這些資源分配給已處于阻塞狀態(tài)的進(jìn)程,使之轉為就緒狀態(tài),以繼續運行。
死鎖的檢測和解除措施,有可能使系統獲得較好的資源利用率和吞吐量,但在實(shí)現上難度也最大。參考資料:死鎖百度百科。
破壞互斥條件
破壞互斥條件即允許多個(gè)進(jìn)程同時(shí)訪(fǎng)問(wèn)資源。由于多數資源的必須互斥訪(fǎng)問(wèn)這一固有特性不能改變,因此,死鎖的預防通過(guò)破壞這個(gè)必要條件實(shí)現在很多場(chǎng)合是行不通的。例如,打印機資源必須互斥使用,否則幾個(gè)進(jìn)程同時(shí)使用,每個(gè)進(jìn)程各打印一行,這種輸出信息的方式顯然是不能被用戶(hù)接受的。
破壞占有和等待條件
采用資源靜態(tài)分配法可破壞這一條件,該方法是指在進(jìn)程運行前,一次性地_請分配它運行所需的全部資源。若系統有足夠的資源分配給某一進(jìn)程,則一次性地將其所需資源分配給該進(jìn)程,這樣,在進(jìn)程運行期間便不會(huì )再提出任何資源請求,從而使等待條件不成立。如果分配時(shí)有一種資源要求不能滿(mǎn)足,則進(jìn)程需要的其他資源也先不分配給進(jìn)程,從而避免進(jìn)程在等待期間占用任何資源,破壞了占用條件,從而避免死鎖的發(fā)生。
該方法控制簡(jiǎn)單且容易實(shí)現,但由于進(jìn)程運行期間對所需資源的全部占用,使得某些使用時(shí)間很短的資源被長(cháng)時(shí)間占用,這樣會(huì )嚴重影響系統資源的充分利用,導致資源利用率降低,同吋也影響到未獲得全部資源的進(jìn)程推遲運行。
破壞不剝奪條件
采用剝奪式控制方法可以破壞該條件,該方法是使一個(gè)已保持了某些資源的進(jìn)程,由于新的資源要求目前得不到滿(mǎn)足,它必須先暫時(shí)釋放巳保持的所有資源(一種剝奪式),然后去等待,以后再一起向系統提出巾請,這樣也能防止死鎖。這種方法實(shí)現起來(lái)相對W難,為了保護進(jìn)程自動(dòng)放棄資源的現場(chǎng)以及后來(lái)的再次恢復,需要付出高昂的代價(jià),并且這種方法只適用于處理機和存儲器資源,對其他資源,此法不宜使用。
破壞循環(huán)等待條件
采用資源順序分配法可破壞該條件。這種分配方法的基本思想是:把系統的全部資源分成多個(gè)層次,一個(gè)進(jìn)程得到某一層的一個(gè)資源后,它只能再_請較高一層的資源;當一個(gè)進(jìn)程要釋放某層的一個(gè)資源時(shí),必須先釋放所占有的較高層的資源;當一個(gè)進(jìn)程獲得了某一層的一個(gè)資源后,它想再申請該層中的另一個(gè)資源,就必須先釋放在該層中巳占有的資源。或者說(shuō),進(jìn)程釋放資源的順序是按照中請資源的相反順序進(jìn)行的。這樣可以預防循環(huán)等待現象的發(fā)生,因此不會(huì )發(fā)生死鎖。使用該方法要特別注意的問(wèn)題是對資源所處層次的安排。在通常情況下,把各進(jìn)程經(jīng)常用到的、比較普遍的資源安排在較低的層次上,把重要且相對匱乏的資源安排在較高的層次上,以便實(shí)現對各資源的最大限度的利用。該方法相對于前面介紹的方法,在資源利用率和系統吞吐量上都有明顯的改善。但也存在一些缺陷。
(1)低層次的資源必須在進(jìn)程請求分配髙層次的資源之前提前申請,這對于暫時(shí)不需使用的低層次資源來(lái)說(shuō),會(huì )因空閑等待而產(chǎn)生浪費。
(2)各類(lèi)設備的資源層次一經(jīng)設定,便不能經(jīng)常隨意改動(dòng),這就限制了新類(lèi)型設備的增加。
(3)各資源的層次是按照大多數進(jìn)程使用資源的順序設置的。對于資源使用與此層次相閃配的進(jìn)程,資源能得到有效的利用,否則,資源的浪費現象將仍然存在。
聲明:本網(wǎng)站尊重并保護知識產(chǎn)權,根據《信息網(wǎng)絡(luò )傳播權保護條例》,如果我們轉載的作品侵犯了您的權利,請在一個(gè)月內通知我們,我們會(huì )及時(shí)刪除。
蜀ICP備2020033479號-4 Copyright ? 2016 學(xué)習?shū)B(niǎo). 頁(yè)面生成時(shí)間:3.071秒