存在三種不同型別的“無鎖”演算法。Concurrency in Action中給出的定義是：
- 無阻塞：如果所有其他執行緒都暫停，那么任何給定執行緒都將在有限步內完成其操作。
- 無鎖：如果多個執行緒正在對一個資料結構進行操作，那么經過一定數量的步驟后，其中一個執行緒將完成其操作。
- Wait-Free：每個對資料結構進行操作的執行緒都將在有限步數內完成其操作，即使其他執行緒也在對該資料結構進行操作。
Herb Sutter 在他的無鎖編程演講中說：
非正式地，“無鎖”≈“不使用互斥鎖”==其中任何一個。
我不明白為什么基于鎖的演算法不能落入上面給出的無鎖定義。這是一個簡單的基于鎖的程式：
#include <iostream>
#include <mutex>
#include <thread>
std::mutex x_mut;
void print(int& x) {
std::lock_guard<std::mutex> lk(x_mut);
std::cout << x;
}
void add(int& x, int y) {
std::lock_guard<std::mutex> lk(x_mut);
x = y;
}
int main() {
int i = 3;
std::thread thread1{print, std::ref(i)};
std::thread thread2(add, std::ref(i), 4);
thread1.join();
thread2.join();
}
如果這兩個執行緒都在運行，那么在有限數量的步驟之后，其中一個必須完成。為什么我的程式不滿足“無鎖”的定義？
uj5u.com熱心網友回復：
我會小心地說“有界”而不定義什么。
規范的無鎖原語 - CAS 回圈沒有給出任何界限，如果存在嚴重的爭用，執行緒可能會反復倒霉并永遠等待，這是允許的。無鎖演算法的定義屬性是總有系統范圍的進步。在任何時候，一些執行緒都會取得進展。
對每個執行緒在每個時間點的某些進展的更強保證稱為無等待。
換句話說，無鎖保證行為不端的執行緒不會致命地影響所有其他執行緒，無等待不能致命地影響任何執行緒。
如果這兩個執行緒都在運行，那么在有限數量的步驟之后，其中一個必須完成。為什么我的程式不滿足“無鎖”的定義？
因為必須考慮（不公平的）調度程式。*如果持有鎖的執行緒進入睡眠狀態，則沒有其他執行緒能夠取得任何進展 -> 非無鎖并且當然沒有限制。無鎖編程不會發生這種情況，資源總是可用的，一個執行緒的不幸調度只會使其他執行緒的操作完成得更快，而不是更慢。
* 特別是，任何執行緒的暫停時間不受頻率或持續時間的限制。如果是這樣，根據定義，任何演算法都將是無等待的（具有一些巨大的常數）。
uj5u.com熱心網友回復：
您對Concurrency in Action的參考斷章取義。
事實上，這本書實際上說的是：
7.1 定義和后果
使用互斥體、條件變數和期貨來同步資料的演算法和資料結構稱為阻塞資料結構和演算法。
不使用阻塞庫函式的資料結構和演算法被稱為非阻塞的。并非所有這些資料結構都是無鎖的......
然后它繼續將非阻塞演算法進一步分解為Obstruction-Free、Lock-Free和Wait-Free。
所以無鎖演算法是
- 非阻塞演算法（它不像互斥鎖那樣使用鎖）和
- 它能夠在有限數量的步驟中至少在一個執行緒中取得進展。
所以赫伯·薩特和安東尼·威廉姆斯都是正確的。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/482313.html
上一篇：如何從多個txt檔案中讀取資訊？