為什麼要放棄那把鎖？
到現在，一把互斥鎖感覺像個已解決的問題：把共享資料包起來，進去時上鎖，出來時解鎖，而你上一級遇到的記憶體順序讓中間的一切都安全。它正確、幾乎總是夠快，而且應該繼續當你的預設選擇。那為什麼還有人想要一個從不上鎖的資料結構？答案不是「鎖很慢」——一把無爭用的互斥鎖很便宜。答案在於：當持鎖者停止執行時，鎖對其他執行緒做了什麼。
想像執行緒 A 拿到了鎖，然後在下一瞬間就被排程器搶佔——一次脈絡切換把 CPU 從它手裡奪走，交給別的東西用上十毫秒。每一個需要那把鎖的其他執行緒現在都卡住了，不是因為它們在做事，而是因為它們正等著一個在睡覺的執行緒。更糟的情況也存在：A 的優先權較低，當一個忙碌的高優先權執行緒為同一把鎖空轉時 A 永遠排不到（優先權反轉），或者 A 在臨界區中途當掉，鎖根本永遠不會被釋放。有了鎖，整個系統的進展就被那一個持鎖的執行緒當作人質。
一個非阻塞（non-blocking）演算法拒絕這種人質局面。它的保證是結構性的：任何一個執行緒被暫停、甚至死亡，都不能阻止其他執行緒取得進展。不存在某個臨界區，一旦被棄置就凍結所有人。這一個性質——系統的進展不依賴任何單一執行緒繼續執行——正是非阻塞、無鎖、無等待這幾個詞所描述的東西，分成三個逐漸增強的等級。這一級其餘部分講的是怎麼真的把這種東西造出來；本篇講的是誠實地讀懂這些標籤。
三種保證，由弱到強
這些標籤構成一個精確的階層，而把它們理清的唯一方法，是對每一個都問：「在什麼條件下，某個執行緒、或每個執行緒，被保證會完成？」從最底層開始。無阻礙（obstruction-free）最弱：一個執行緒被保證完成它的操作，只要它單獨執行得夠久——也就是說，只要其他所有執行緒都暫停。這聽起來幾乎沒用，而單獨來看它確實弱，因為如果兩個執行緒持續互相干擾，它們可以反覆把對方打回去，誰都完成不了。但它排除了真正的死結，而且是個有用的踏腳石。
升一級到無鎖（lock-free），這是實務上最重要的一級。它的保證是：在所有爭用的執行緒之中，至少有一個總是在有限步數內取得進展——整個系統永遠不會卡死，即使個別執行緒可能運氣不好、必須重試。心智圖像是一群人擠在門口：碰撞會發生、有人被推回去，但人群整體持續流過去，因為每一次碰撞都意味著有人穿過去才造成它。沒有任何執行緒會永遠等另一個執行緒，但某個運氣特別差的執行緒可能被餓著，眼睜睜看別人一個個流過。
最頂層是無等待（wait-free），最強也最稀有。它的保證是：每一個執行緒都在它自己有限的步數內完成操作，無論其他執行緒做什麼。沒有人會被餓著；任何單一操作能耗費多久都有一個硬上限。這正是硬即時系統渴求的，因為它給出一個你真能算出來的最差情況界限。代價——而且是個大代價——是無等待演算法設計起來困難得多，而且通常帶有更多額外開銷，因為要保證最慢的執行緒有個界限，往往意味著較快的執行緒必須停下來幫它，這個技巧叫做協助技術（helping），你會在這一級後面看到。
guarantee who is guaranteed to finish? rules out ---------------- ---------------------------------- ------------------- blocking (mutex) nobody, if lock-holder is suspended nothing structural obstruction-free a thread that runs ALONE long enough deadlock lock-free AT LEAST ONE thread, always deadlock + livelock-of-system wait-free EVERY thread, in bounded own steps deadlock + livelock + starvation strength: blocking < obstruction-free < lock-free < wait-free
這些保證沒有承諾的東西
也要注意「無鎖」這個尖銳的字眼。它不只是指「我沒有呼叫 pthread_mutex_lock()」。一個演算法可以避開互斥鎖的 API，卻仍然是阻塞的——例如一個用原子旗標手刻的自旋鎖（spinlock）仍然是一把鎖：如果它的持有者被暫停，所有在空轉的人都卡住，這正是我們一開始要逃離的人質局面。「無鎖」是由進展的性質定義的，不是由你避開了哪些函式庫函式定義的。測試永遠是：如果我在任何一點凍結任何一個執行緒，其餘的還能完成嗎？如果答案是不能，那它就是阻塞的，不管程式碼長什麼樣。
而這些保證本身對正確性隻字未提。一個無鎖結構可以是無鎖的，卻仍然回傳錯誤答案，如果它的操作之間沒有被妥善排序的話。進展與正確性是兩條彼此獨立的軸：進展告訴你有人完成了，正確性告訴你他們以正確的結果完成。那第二條軸有它自己精確的名字，也是本篇的另一半。
另一條軸：線性化
當單一執行緒操作一個堆疊時，「正確」是顯然的：先 push 再 pop 會回傳你 push 進去的東西。當許多執行緒的操作在時間上重疊時，光是說清楚正確是什麼意思都很難。如果執行緒 A 的 push 和執行緒 B 的 pop 同時在跑，它們「真正」是以什麼順序發生的？線性化（linearizability）是這個問題的黃金標準答案。它說：每個操作彷彿在你呼叫它與它回傳之間的某個單一瞬間——它的線性化點（linearization point）——瞬間生效，而整個並行執行看起來，與某個尊重那些瞬間的循序執行完全相同。簡言之：它表現得彷彿存在一個真正的順序，即使操作在物理上彼此重疊。
為什麼那個瞬間必須落在呼叫與回傳之間？因為那是操作真正存活的時間窗。如果一個 push 在時刻 t 回傳，那麼到 t 為止那個值一定已經在堆疊裡——任何在 t 之後開始的 pop 都必須能看見它。線性化禁止那些荒謬：你不能 pop 一個從未被 push 進去的值，你不能把同一個值 pop 兩次，而一旦一個操作已經回傳，世界就必須同意它發生過。這就是為什麼它是我們對並行資料結構想要的合約——它讓你能把結構當作一個簡單的循序物件來推理，正如一級之前那本循序一致性筆記本給你的那份禮物，現在以每個物件為單位地套用。
這裡有個必須牢牢鎖進腦子的關鍵區分：進展與線性化彼此獨立。一個結構可以是無鎖卻非線性化的（進展快、答案錯），也可以是線性化卻阻塞的（一個用互斥鎖守護的普通堆疊是完美線性化的——它的線性化點就在臨界區裡）。你在這一級會造的無鎖資料結構，目標是同時做到兩者，而正是這個組合讓它們困難。大部分的困難、以及大部分著名的臭蟲，都住在「釘下一個能熬過每一種可能交錯的正確線性化點」這件事上。
底下的引擎，以及前方的路
一個執行緒怎麼能不用鎖就更新一個共享結構、還保持正確？整個把戲倚靠一個硬體原語：一個不會撕裂的原子讀-改-寫。主力是比較並交換（compare-and-swap，CAS）：在一個不可分割的步驟裡，它讀一個位置、檢查它是否仍等於一個預期值、只有在這時才寫入新值，並回報是否成功。模式是：讀取目前狀態、算出新狀態、然後用 CAS 把它放進去——而如果 CAS 失敗（因為別人搶先改了那個位置），就迴圈重試。那個迴圈就是 CAS 重試迴圈，它是幾乎每一個無鎖演算法跳動的心臟。有些晶片，像 ARM，改提供 連結載入／條件儲存（LL/SC），一個近親，你會在下一篇遇到。
有了這套詞彙，你現在可以把這一級其餘部分讀成單一條弧線。下一篇深入 CAS 本身，以及它最惡名昭彰的陷阱：ABA 問題，一個值先變成 A、又變回 A，而天真的 CAS 完全察覺不到中間發生過什麼。接著我們造出真正的結構——一個無鎖堆疊、一個佇列、一個單生產者單消費者環形緩衝區——並發現一個鎖原本替我們完全藏住的問題：一旦你在沒有鎖的情況下移除一個節點，什麼時候 free() 它才安全？另一個執行緒可能還在讀它。那個回收問題正是危險指標、紀元、與 RCU 存在的理由，也是最後兩篇要去的地方。緊抓住這兩條軸——進展與線性化——整趟攀登就會始終保持方向。