鎖是操作系統(tǒng)提供的一種同步原語，通過在訪問共享資源前加鎖，結束訪問共享資源后解鎖，讓任何時刻只有一個線程訪問共享，本質是做串行化。

程序對共享資源的訪問任務，一般包括三步驟，讀原值，修改值，將新值寫回，用鎖同步的話，就是在確保這三個步驟，不會被打斷，訪問共享資源的臨近代碼區(qū)只有一個線程在同時運行，第一個獲得鎖的線程能往前推進，其他線程只能等著直到持有鎖的線程釋放鎖。

線程同步分為阻塞型同步和非阻塞型同步。

互斥量、信號、條件變量這些系統(tǒng)提供的機制都屬于阻塞型同步，在爭用資源的時候，會導致調用線程阻塞。

而非阻塞型同步是在無鎖的情況下，通過某種算法和技術手段實現(xiàn)不用阻塞而同步。

鎖是阻塞（Blocking）同步機制，阻塞同步機制的缺陷是可能掛起你的程序，如果持有鎖的線程crash，則鎖永遠得不到釋放，而其他線程則將陷入無限等待，另外，它也可能導致優(yōu)先級倒轉等問題。

所以，我們需要非阻塞（Non-Blocking）的同步機制。

什么是lock-free？

lock-free沒有鎖同步的問題，所有線程無阻礙的執(zhí)行原子指令，而不是等待。

比如一個線程讀atomic類型變量，一個線程寫atomic變量，它們沒有任何等待，硬件原子指令確保不會出現(xiàn)數(shù)據(jù)不一致，寫入數(shù)據(jù)不會出現(xiàn)半完成，讀取數(shù)據(jù)也不會讀一半。

那到底什么是lock-free？

有人說lock-free就是不使用mutex / semaphores之類的無鎖（lock-Less）編程，這句話嚴格來說并不對。

我們先看一下wiki對Lock-free的描述:

> Lock-freedom allows individual threads to starve but guarantees system-wide throughput. An algorithm is lock-free if, when the program threads are run for a sufficiently long time, at least one of the threads makes progress (for some sensible definition of progress). All wait-free algorithms are lock-free.

> In particular, if one thread is suspended, then a lock-free algorithm guarantees that the remaining threads can still make progress. Hence, if two threads can contend for the same mutex lock or spinlock, then the algorithm is not lock-free. (If we suspend one thread that holds the lock, then the second thread will block.)

• 第一段：lock-free允許單個線程饑餓但保證系統(tǒng)級吞吐。如果一個程序的線程執(zhí)行足夠長的時間，那么至少一個線程會往前推進，那么這個算法就是lock-free的。
• 第二段：尤其是，如果一個線程被暫停，lock-free算法保證其他線程依然能夠往前推進。

第一段是給lock free下定義，第二段是解釋。

因此，如果2個線程競爭同一個互斥鎖或者自旋鎖，那它就不是lock-free的。

因為如果我們暫停持有鎖的線程，那么另一個線程會被阻塞。

wiki的這段描述很抽象，它不夠直觀，稍微再解釋一下：

lock-free描述的是代碼邏輯的屬性，不使用鎖的代碼，大部分具有這種屬性。所以，我們經(jīng)常會混淆這lock-free和無鎖這2個概念。

其實，lock-free是對代碼（算法）性質的描述，是屬性，而無鎖是說代碼如何實現(xiàn)，是手段。

lock-free的關鍵描述是：如果一個線程被暫停，那么其他線程應能繼續(xù)前進，它需要有系統(tǒng)級（system-wide）的吞吐。

我們從反面舉例來看，假設我們要借助鎖實現(xiàn)一個無鎖隊列，我們可以直接使用線程不安全的std::queue + std::mutex來做：

template <typename T>
class Queue {
public:
   void push(const T& t) {
       q_mutex.lock();
       q.push(t);
       q_mutex.unlock();
   }
private:
   std::queue<T> q;
   std::mutex q_mutex;
};

如果有線程A/B/C同時執(zhí)行push方法，最先進入的線程A獲得互斥鎖。

線程B和C因為獲取不到互斥鎖而陷入等待。

這個時候，線程A如果因為某個原因（如出現(xiàn)異常，或者等待某個資源）而被永久掛起，那么同樣執(zhí)行push的線程B/C將被永久掛起，系統(tǒng)整體（system-wide）沒法推進。這顯然不符合lock-free的要求。

因此：所有基于鎖（包括spinlock）的并發(fā)實現(xiàn)，都不是lock-free的。

因為它們都會遇到同樣的問題：即如果永久暫停當前占有鎖的線程/進程的執(zhí)行，將會阻塞其他線程/進程的執(zhí)行。

而對照lock-free的描述，它允許部分process（理解為執(zhí)行流）餓死但必須保證整體邏輯的持續(xù)前進，基于鎖的并發(fā)顯然是違背lock-free要求的。

CAS loop實現(xiàn)lock-free

Lock-Free同步主要依靠CPU提供的read-modify-write原語，著名的“比較和交換”CAS（Compare And Swap）在X86機器上是通過cmpxchg系列指令實現(xiàn)的原子操作，CAS邏輯上用代碼表達是這樣的：

bool CAS(T* ptr, T expect_value, T new_value) {
  if (*ptr != expect_value) {
     return false;
  }
  *ptr = new_value;
  return true;
}

CAS接受3個參數(shù)：

• 內存地址
• 期望值，這個值通常傳第一個參數(shù)所指內存地址中的舊值
• 新值

邏輯描述：CAS比較內存地址中的值和期望值，如果不相同就返回失敗，如果相同就將新值寫入內存并返回成功。

當然這個C函數(shù)描述的只是CAS的邏輯，這個函數(shù)操作不是原子的，因為它可以劃分成幾個步驟：讀取內存值、判斷、寫入新值，各步驟之間是可以插入其他操作的。

不過前面講了，原子指令相當于把這些步驟打包，它可能是通過`lock; cmpxchg`實現(xiàn)的，但那是實現(xiàn)細節(jié)，程序員更應該注重在邏輯上理解它的行為。

通過CAS實現(xiàn)Lock-free的代碼通常借助循環(huán)，代碼如下：

do {
   T expect_value = *ptr;
} while (!CAS(ptr, expect_value, new_value));

• 創(chuàng)建共享數(shù)據(jù)的本地副本，expect_value
• 根據(jù)需要修改本地副本，從ptr指向的共享數(shù)據(jù)里load后賦值給expect_value
• 檢查共享的數(shù)據(jù)跟本地副本是否相等，如果相等，則把新值復制到共享數(shù)據(jù)

第三步是關鍵，雖然CAS是原子的，但加載expect_value跟CAS這2個步驟，并不是原子的。

所以，我們需要借助循環(huán)，如果ptr內存位置的值沒有變（*ptr == expect_value），那就存入新值返回成功；否則說明加載expect_value后，ptr指向的內存位置被其他線程修改了，這時候就返回失敗，重新加載expect_value，重試，直到成功為止。

CAS loop支持多線程并發(fā)寫，這個特點太有用了，因為多線程同步，很多時候都面臨多寫的問題，我們可以基于cas實現(xiàn)Fetch-and-add(FAA)算法，它看起來像這樣：

T faa(T& t) {
   T temp = t;
   while (!compare_and_swap(x, temp, temp + 1));
}

第一步加載共享數(shù)據(jù)的值到temp，第二步比較+存入新值，直到成功。

lock-free棧

下面是C++ atomic compare_exchange_weak()實現(xiàn)的一個lock-free堆棧（來自CppReference）：

template <typename T>
struct node {
   T data;
   node* next;
   node(const T& data) : data(data), next(nullptr) {}
};

template <typename T>
class stack {
   std::atomic<node<T>*> head;
public:
   void push(const T& data) {
     node<T>* new_node = new node<T>(data);
     new_node->next = head.load(std::memory_order_relaxed);
     while (!head.compare_exchange_weak(new_node->next, new_node,
                                       std::memory_order_release,
                                       std::memory_order_relaxed));
   }
};

代碼解析：

• 節(jié)點（node）保存T類型的數(shù)據(jù)data，并且持有指向下一個節(jié)點的指針
• `std::atomic<node<T>*>`類型表明atomic里放置的是Node的指針，而非Node本身，因為指針在64位系統(tǒng)上是8字節(jié)，等于機器字長，再長沒法保證原子性
• stack類包含head成員，head是一個指向頭結點的指針，頭結點指針相當于堆頂指針，剛開始沒有節(jié)點，head為NULL
• push函數(shù)里，先根據(jù)data值創(chuàng)建新節(jié)點，然后要把它放到堆頂
• 因為是用鏈表實現(xiàn)的棧，所以，如果新節(jié)點要成為新的堆頂（相當于新節(jié)點作為新的頭結點插入），那么新節(jié)點的next域要指向原來的頭結點，并讓head指向新節(jié)點
• `new_node->next = head.load`把新節(jié)點的next域指向原頭結點，然后`head.compare_exchange_weak(new_node->next, new_node)`，讓head指向新節(jié)點
• C++ atomic的compare_exchange_weak()跟上述的CAS稍有不同，head.load()不等于new_node->next的時候，它會把head.load()的值重新加載到new_node->next
• 所以，在加載head值和cas之間，如果其他線程調用push操作，改變了head的值，那沒有關系，該線程的本次cas失敗，下次重試便可以了
• 多個線程同時push時，任一線程在任意步驟阻塞/掛起，其他線程都會繼續(xù)執(zhí)行并最終返回，無非就是多執(zhí)行幾次while循環(huán)

這樣的行為邏輯顯然符合lock-free的定義，注意用cas+loop實現(xiàn)自旋鎖不符合lock-free的定義，注意區(qū)分。

ABA問題

CAS經(jīng)常伴隨ABA問題，考慮前面的CAS邏輯，CAS里會做判等，判等的2個操作數(shù)，一個是前步加載的內存地址的值，另一個是再次從內存地址讀取的值，如果2個操作數(shù)相等，它便認為內存位置的值沒變。

但實際上，如果“兩次讀取一個內存位置的值相同，則說明該內存位置沒變”，這個假設不一定成立，為什么呢？

假設線程1在前面一步從內存位置加載數(shù)據(jù)后。

線程2切入，將該內存位置的數(shù)據(jù)從A修改為B，然后又修改為A。

等到線程1繼續(xù)執(zhí)行CAS的時候，它觀測到的內存位置值未變（依然是A），因為線程2將數(shù)據(jù)從A修改到B，再修改成A。

線程1兩次讀到了相同的值，它便斷定內存位置沒有被修改，實際并非如此，線程2改了內存位置。

基于上述邏輯行事，就有可能出現(xiàn)未定義的結果。

這就是經(jīng)典的ABA問題，會不會出問題，完全取決于你的程序邏輯，有些邏輯可以容忍ABA問題，而有些不可以。

ABA問題很多時候由內存復用引起，比如一塊內存被回收后又被分配，地址值不變，但這個對象已經(jīng)不是之前的那個對象了，有很多解決ABA問題的技術手段，比如增加版本號等等，目的無非是去識別這種變化。

何為wait-free？

wiki關于wait-free的詞條解釋：

> Wait-freedom is the strongest non-blocking guarantee of progress, combining guaranteed system-wide throughput with starvation-freedom

> An algorithm is wait-free if every operation has a bound on the number of steps the algorithm will take before the operation completes.[15] This property is critical for real-time systems and is always nice to have as long as the performance cost is not too high

翻譯過來就是：wait-free有著最強的非阻塞進度保證，wait-free有系統(tǒng)級吞吐兼具無饑餓特征。

如果一個算法的每個操作完成都只有有限操作步數(shù)，那么這個算法就是wait-free的。

這個特征對于實時系統(tǒng)非常關鍵，且它的性能成本不會太高。

wait-free比lock-free更嚴格，所有wait-free算法都是lock-free的，反之不成立，wait-free是lock-free的子集。

wait-free的關鍵特征是所有步驟都在有限步驟完成，所以前面的`cas + loop`實現(xiàn)的lock-free棧就不是wait-free的。

因為理論上，如果調用push的線程是個倒霉蛋，一直有其他線程push且恰好又都成功了，則這個倒霉蛋線程的cas會一直失敗，一直循環(huán)下去，這與wait-free每個操作都必須在有限步驟完成的要求相沖突。wait-free的嘗試次數(shù)通常跟線程數(shù)有關，線程數(shù)越多，則這個有限的上限就越大。

但前面講的atomic fetch_add則是wait-free的，因為它不會失敗。

簡單點說，lock-free可以有循環(huán)，而wait-free連循環(huán)都不應該有。

wait-free非常難做，以前一直看不到wait-free的數(shù)據(jù)結構和算法實現(xiàn)，直到2011才有人搞出了一個wait-free隊列，雖然這個隊列也用到了cas，但是它為每一步發(fā)送的操作提供了一個state array，為每個操作賦予一個number，從而保證有限步完成入隊出隊操作，論文鏈接：

(wait-free queue)：[http://www.cs.technion.ac.il/~erez/Papers/wfquque-ppopp.pdf]

何為Obstruction-free？

Obstruction-free提供比lock-free更弱的一個非阻塞進度保證，所有l(wèi)ock-free都屬于Obstruction-free。

Obstruction-free翻譯過來叫無障礙，是指在任何時間點，一個孤立運行線程的每一個操作可以在有限步之內結束。只要沒有競爭，線程就可以持續(xù)運行，一旦共享數(shù)據(jù)被修改，Obstruction-free要求中止已經(jīng)完成的部分操作，并進行回滾，obstruction-free是并發(fā)級別更低的非阻塞并發(fā)，該算法在不出現(xiàn)沖突性操作的情況下提供單線程式的執(zhí)行進度保證。

obstruction-freedom要求可以中止任何部分完成的操作并且能夠回滾已做的更改，為了內容完備性，把obstruction-free列在這里。

無鎖數(shù)據(jù)結構

一些無鎖（阻塞）數(shù)據(jù)結構不需要特殊原子操作原語即可實現(xiàn)，例如：

• 支持單線程讀和單線程寫的Ring Buffer先進先出隊列，通過把容量設置為2^n，利用整型回繞特點+內存屏障就可以實現(xiàn)，參考linux內核的kfifo
• 帶單寫線程和任意數(shù)讀線程的讀拷貝更新（RCU），通常，讀無等待（wait-free），寫無鎖（lock-free）
• 帶多寫線程和任意數(shù)讀線程的讀拷貝更新（RCU），通常，讀無等待（wait-free），寫用鎖做串行化

無鎖數(shù)據(jù)結構實現(xiàn)起來比較困難，非必要不要自己去實現(xiàn)。

自旋鎖

在cpu核上自旋，粘著cpu不停的測試，直到其他cpu解鎖，這是一種消耗cpu的加鎖方式，適合持有鎖的時間非常短的情況，它基于一種假設：睡眠導致的調度開銷大于在cpu上自旋測試的開銷。

• 自旋鎖也叫優(yōu)雅粒度的鎖，跟操作系統(tǒng)提供的阻塞機制的粗粒度鎖（mutex和信號量）對應。
• 自旋鎖一般不應該被長時間持有，如果持有鎖的時間可能比較長，那就用操作系統(tǒng)為你提供的粗粒度的鎖就好了。
• 線程持有自旋鎖的時候，線程一般不應該被調度走，內核層可以禁中斷禁調度保障這一點，但應用層程序一般無法避免線程被調度走，所以應用層使用自旋鎖其實得不到保障。
• 自旋鎖不可遞歸。
• 自旋鎖常用來追求低延時，而不是為了提升系統(tǒng)吞吐，因為自旋鎖，不會把執(zhí)行線程調度走，不會阻塞（睡眠）。