活鎖指的是任務或者執行者沒有被阻塞,由於某些條件沒有滿足,導致一直重複嘗試—失敗—嘗試—失敗的過程。處於活鎖的實體是在不斷的改變狀態,活鎖有可能自行解開。
基本介紹
- 中文名:活鎖
- 外文名:livelock
- 詞性:名詞
- 涉及範圍:編程、計算機資源調度
概述,事例,解決方法,死鎖與活鎖,
概述
活鎖指的是任務或者執行者沒有被阻塞,由於某些條件沒有滿足,導致一直重複嘗試,失敗,嘗試,失敗。 活鎖和死鎖的區別在於,處於活鎖的實體是在不斷的改變狀態,所謂的“活”, 而處於死鎖的實體表現為等待;活鎖有可能自行解開,死鎖則不能。
活鎖可以認為是一種特殊的飢餓。 下面這個例子在有的文章裡面認為是活鎖。實際上這只是一種飢餓。因為沒有體現出“活”的特點。 假設事務T2再不斷的重複嘗試獲取鎖R,那么這個就是活鎖。
如果事務T1封鎖了數據R,事務T2又請求封鎖R,於是T2等待。T3也請求封鎖R,當T1釋放了R上的封鎖後,系統首先批准了T3的請求,T2仍然等待。然後T4又請求封鎖R,當T3釋放了R上的封鎖之後,系統又批准了T4的請求......T2可能永遠等待。
活鎖應該是一系列進程在輪詢地等待某個不可能為真的條件為真。活鎖的時候進程是不會blocked,這會導致耗盡CPU資源。
事例
單一實體的活鎖
例如執行緒從佇列中拿出一個任務來執行,如果任務執行失敗,那么將任務重新加入佇列,繼續執行。假設任務總是執行失敗,或者某種依賴的條件總是不滿足,那么執行緒一直在繁忙卻沒有任何結果。
協同導致的活鎖
生活中的典型例子: 兩個人在窄路相遇,同時向一個方向避讓,然後又向另一個方向避讓,如此反覆。
通信中也有類似的例子,多個用戶共享信道(最簡單的例子是大家都用對講機),同一時刻只能有一方傳送信息。傳送信號的用戶會進行衝突檢測, 如果發生衝突,就選擇避讓,然後再傳送。 假設避讓算法不合理,就導致每次傳送,都衝突,避讓後再傳送,還是衝突。
計算機中的例子:兩個執行緒發生了某些條件的碰撞後重新執行,那么如果再次嘗試後依然發生了碰撞,長此下去就有可能發生活鎖。
解決方法
解決協同活鎖的一種方案是調整重試機制。
比如引入一些隨機性。例如如果檢測到衝突,那么就暫停隨機的一定時間進行重試。這回大大減少碰撞的可能性。 典型的例子是乙太網的CSMA/CD檢測機制。
另外為了避免可能的死鎖,適當加入一定的重試次數也是有效的解決辦法。儘管這在業務上會引起一些複雜的邏輯處理。
比如約定重試機制避免再次衝突。 例如自動駕駛的防碰撞系統(假想的例子),可以根據序列號約定檢測到相撞風險時,序列號小的飛機朝上飛, 序列號大的飛機朝下飛。
死鎖與活鎖
死鎖:迎面開來的汽車A和汽車B過馬路,汽車A得到了半條路的資源(滿足死鎖發生條件1:資源訪問是排他性的,我占了路你就不能上來,除非你爬我頭上去),汽車B占了汽車A的另外半條路的資源,A想過去必須請求另一半被B占用的道路(死鎖發生條件2:必須整條車身的空間才能開過去,我已經占了一半,尼瑪另一半的路被B占用了),B若想過去也必須等待A讓路,A是輛蘭博基尼,B是開奇瑞QQ的屌絲,A素質比較低開窗對B狂罵:快給老子讓開,B很生氣,你媽逼的,老子就不讓(死鎖發生條件3:在未使用完資源前,不能被其他執行緒剝奪),於是兩者相互僵持一個都走不了(死鎖發生條件4:環路等待條件),而且導致整條道上的後續車輛也走不了。
活鎖:馬路中間有條小橋,只能容納一輛車經過,橋兩頭開來兩輛車A和B,A比較禮貌,示意B先過,B也比較禮貌,示意A先過,結果兩人一直謙讓誰也過不去。