Posted on 2014-09-03 21:11
鑫龍 閱讀(3241)
評論(0) 編輯 收藏 引用 所屬分類:
linux編程
轉自：
http://www.isnowfy.com/understand-to-lock-free/
以前一直不明白lock free是什么，后來發現原來是完全理解錯了概念，lock free看到大家有的翻譯為無鎖，有的翻譯為鎖無關，其實用不用鎖和lock free是不相關的，用了鎖也可能是lock free，而不用鎖有可能不是lock free。
一個lock free的解釋是
一個“鎖無關”的程序能夠確保執行它的所有線程中至少有一個能夠繼續往下執行。
其實看我們那副圖就是說你的各個線程不會互相阻塞，那么你的程序才能成為lock free的。像我們平常用的互斥鎖，當有線程獲得鎖，其他線程就被阻塞掉了，這里的問題就是如果獲得鎖的線程掛掉了，而且鎖也沒有釋放，那么整個程序其實就被block在那了，而如果程序是lock free的那么即使有線程掛掉，也不影響整個程序繼續向下進行，也就是系統在整體上而言是一直前進的。
那么，不用鎖就是lock free的嗎，一開始就提到了，不用鎖也可能不是lock free的，舉個例子
-
while (x == 0) {
-
x = 1-x;
-
}
在這里如果兩個線程同時執行，可能同時進入while循環，然后x兩次改變值之后，依然是0，那么兩個線程就會一直互相在這里阻塞掉了，所以這里雖然沒有鎖，依然不是lock free的。
現在大家寫lock free的時候一般都會使用CAS（compare and set）操作來寫，因為現在很多的cpu都是支持CAS操作并作為原子操作來處理的，CAS操作一般是這樣的
-
bool compare_and_swap (int *oldval, int *dest, int newval) {
-
if (*oldval == *dest) {
-
*dest = newval;
-
return true;
-
}
-
return false;
-
}
其實這樣一個操作和樂觀鎖很像，并且操作簡單，相應的比互斥鎖的代價要小。所以現在大家都是喜歡用lock free的技術來提高系統的performance。
最后如果大家對于如何編寫lock free的數據結構感興趣的話，可以參考我后面給出的鏈接。
一種高效無鎖內存隊列的實現
無鎖隊列的實現
鎖無關的(Lock-Free)數據結構
An Introduction to Lock-Free Programming