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

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

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

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

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

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

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

什么是lock-free？

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

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

那到底什么是lock-free？

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

我們先看一下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允許單個(gè)線程饑餓但保證系統(tǒng)級吞吐。如果一個(gè)程序的線程執(zhí)行足夠長的時(shí)間，那么至少一個(gè)線程會往前推進(jìn)，那么這個(gè)算法就是lock-free的。
• 第二段：尤其是，如果一個(gè)線程被暫停，lock-free算法保證其他線程依然能夠往前推進(jìn)。

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

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

因?yàn)槿绻覀儠和３钟墟i的線程，那么另一個(gè)線程會被阻塞。

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

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

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

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

我們從反面舉例來看，假設(shè)我們要借助鎖實(shí)現(xiàn)一個(gè)無鎖隊(duì)列，我們可以直接使用線程不安全的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同時(shí)執(zhí)行push方法，最先進(jìn)入的線程A獲得互斥鎖。

線程B和C因?yàn)楂@取不到互斥鎖而陷入等待。

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

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

因?yàn)樗鼈兌紩龅酵瑯拥膯栴}：即如果永久暫停當(dāng)前占有鎖的線程/進(jìn)程的執(zhí)行，將會阻塞其他線程/進(jìn)程的執(zhí)行。

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

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

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

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

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

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

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

當(dāng)然這個(gè)C函數(shù)描述的只是CAS的邏輯，這個(gè)函數(shù)操作不是原子的，因?yàn)樗梢詣澐殖蓭讉€(gè)步驟：讀取內(nèi)存值、判斷、寫入新值，各步驟之間是可以插入其他操作的。

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

通過CAS實(shí)現(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ù)跟本地副本是否相等，如果相等，則把新值復(fù)制到共享數(shù)據(jù)

第三步是關(guān)鍵，雖然CAS是原子的，但加載expect_value跟CAS這2個(gè)步驟，并不是原子的。

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

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

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

ABA問題

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

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

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

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

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

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

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

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

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

何為wait-free？

wiki關(guān)于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有著最強(qiáng)的非阻塞進(jìn)度保證，wait-free有系統(tǒng)級吞吐兼具無饑餓特征。

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

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

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

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

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

但前面講的atomic fetch_add則是wait-free的，因?yàn)樗粫　?/p>

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

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

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

何為Obstruction-free？

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

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

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

無鎖數(shù)據(jù)結(jié)構(gòu)

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

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

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

自旋鎖

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

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