從單一機器字到整個資料結構
第二篇留給你一個基本操作和它一個出名的臭蟲：比較並交換會原子地更新單一機器字，而 CAS 重試迴圈把它變成「讀出目前的值、算出一個新值、只有在沒人在我底下動過它時才換進去，否則再試一次」。這足以遞增一個計數器。但一個堆疊或佇列不是一個機器字——它是一張由指標連起來的節點網，而 CAS 一次只能擺動一個指標。無鎖資料結構的全部手藝，就在於把佈局安排成：你每一步唯一被允許的那一個 CAS，恰好落在那個能原子地發佈你的改動的指標上，讓結構從一個合法的舊狀態直接走到一個合法的新狀態，中間沒有任何破碎、可能讓另一個執行緒絆倒的中介狀態。
我們會造三個難度遞增的結構。堆疊只有一個可變指標——頂端——所以單一 CAS 就夠，程式碼短到能整個放進腦袋裡。佇列有頭、尾兩端必須保持一致，所以需要更聰明的舞步以及互助的點子。環形緩衝區在它最簡單的單生產者單消費者形態下完全不需要 CAS——只要兩個索引加上正確的 acquire／release 順序——這使它成為最快、也是你最常會伸手去拿的那一個。按順序看它們，會看出難度如何隨可變指標的數量上升，以及每個結構各自撞上哪一道牆——而那道牆正是接下來兩篇要打破的。
Treiber 堆疊：一個指標，一個 CAS
Treiber 堆疊（R. Kent Treiber，IBM，1986）是第一個親切的無鎖結構，因為它恰好只有一個可變的東西：一個指向頭節點的原子指標 `top`，而每個節點都帶一個 `next` 指標。要推入（push）一個新節點 n，你讀出目前的 top，把 n->next 指向它，然後把 top 從那個舊值 CAS 成 n。若 CAS 失敗，表示中間有人推入或彈出，於是你重讀 top、重新接好 n->next、再試一次——一個教科書式的重試迴圈。要彈出（pop），你讀出 top、讀它的 next，然後把 top 從該節點 CAS 成那個 next；成功時舊的 top 就歸你拿去回傳。一個 CAS 就發佈了整個改動，因為堆疊的全部身分都活在那一個指標裡。
// push(n) // pop() -> node or NULL
do { do {
old = top.load(acquire); old = top.load(acquire);
n->next = old; if (old == NULL) return NULL;
} while (!top.compare_exchange_weak( next = old->next; // <-- ABA reads here
old, n, release, relaxed)); } while (!top.compare_exchange_weak(
old, next, acquire, relaxed));
// success: n is the new top // success: 'old' is unlinked, return it有兩個細節讓它真正正確、而不只是看似可信，兩者都是先前各級的成果。記憶體順序不是裝飾：push 在它成功的 CAS 上用 release，好讓填入新節點的那些寫入被封在它後面；pop 用 acquire，好讓彈出的執行緒真的看得見那個節點的內容——這正是記憶體模型那級的「發佈／訂閱」握手，如今在一個真實結構裡承重了。把順序弄錯，節點的資料在另一顆核心上就會呈現寫到一半的樣子。CAS 是無鎖的，則是另一個成果：一次失敗的 CAS 意味著某個執行緒有了進展（它改了 top），所以整個系統作為一體永不停滯，即使你這個特定執行緒可能一直繞圈。
Michael-Scott 佇列：兩端與互助技巧
一個先進先出佇列更難，因為它有兩個必須一致的指標：`head`（你出列的地方）與 `tail`（你入列的地方）。你沒辦法用一個 CAS 同時移動兩者，所以天真的設計會有一段 head 與 tail 不一致的視窗，讓另一個執行緒看見一個破碎的佇列。Michael-Scott 佇列（Maged Michael 與 Michael Scott，1996）是真正落地的答案——它活在 `java.util.concurrent` 與無數 C 函式庫裡。它的第一個點子是一個永久的虛擬節點（dummy node）：佇列永遠不會真正空著，所以 head 與 tail 永遠指向真實節點，而「空」這個狀況就不再是一個特殊、脆弱的分支。
聰明的部分在入列，它把入列拆成兩個 CAS 步驟，並用互助讓它安全。第一步：把最後一個節點的 `next` 指標從 NULL CAS 成你的新節點——這才是真正、會「線性化」的發佈，是你的節點加入佇列的那一瞬間。第二步：把 `tail` 從舊的最後節點往前 CAS 到你的新節點。在這兩步之間，佇列處於一個合法但「落後」的狀態：節點已接上，但 `tail` 仍少指了一個。突破在於：任何注意到 tail 落後的執行緒，會替那個落隊的人把工作做完——它自己去做第二步的 CAS，然後才繼續。因為人人互助，沒有任何執行緒的停滯能卡住佇列，而一個在第一步與第二步之間死掉的執行緒，留下的是一個別人會自動修復的狀態。
- 讀 tail，再讀 tail->next。若 next 非 NULL，表示 tail 落後了——透過把 tail 往前 CAS 到 next 來互助，然後重新開始。（這就是修復「只做了一半的入列」的互助步驟。）
- 若 next 為 NULL，讀到的 tail 真的是最後一個節點。把它的 next 從 NULL CAS 成你的新節點。若失敗，表示有人搶先；整個迴圈重來。
- 成功時你的節點已接上——那條連結就是「線性化點」，也就是入列「正式」發生的時刻。接著盡力做一個把 tail 往前擺的 CAS；就算失敗也無妨，下一個執行緒會來互助。
出列是它的鏡像：讀 head、讀 head->next（虛擬節點後面的第一個真實元素）、把它的值複製出來，然後把 head 往前 CAS 到那個 next，把舊的虛擬節點退役。MS 佇列在兩端都是真正無鎖的，而互助正是買到這份保證的東西——它把「我必須等慢執行緒做完」換成「我自己把慢執行緒的剩料做完」。但請注意同樣的陰影：出列解開一個節點的連結，而另一個執行緒可能仍透過它自己陳舊的 `head` 在讀那個節點。兩個由 CAS 驅動的端點並沒有讓回收問題消失；它們把問題加倍了。
SPSC 環形緩衝區：不用 CAS，只要兩個索引
現在是驚喜：最快的無鎖佇列往往完全不用 CAS。一個單生產者單消費者環形緩衝區是一個有 N 個槽位的固定陣列，外加兩個索引：一個只有消費者推進的 `head`，與一個只有生產者推進的 `tail`。因為每個索引恰好只有一個執行緒去寫，對它就沒有讀—改—寫的爭奪——沒有 CAS、沒有重試迴圈、沒有 ABA。生產者寫一個槽位、然後推進 tail；消費者讀一個槽位、然後推進 head。陣列被當成一個圓圈看待：索引 N 繞回 0，當 N 是 2 的次方時通常用 `& (N-1)` 來做，於是繞回是一次便宜的遮罩而非除法。
取代 CAS 的是順序。生產者必須在發佈新的 tail 之前寫完那個槽位，而消費者必須在讀那個槽位之前讀到新的 tail——否則消費者會讀到生產者尚未填好的槽位。這恰好就是一次 acquire／release 握手：生產者對 tail 做 release 儲存（把槽位的寫入封在它後面），消費者對 tail 做 acquire 載入（於是看見新的 tail 就保證看見那個槽位）。當 head 等於 tail 時結構為空，當推進 tail 會撞上 head 時為滿。這正是記憶體模型那級的 happens-before 機制，如今成了整個同步機制——沒有鎖、沒有 CAS，只有兩道單向柵欄。
這裡的「正確」是什麼意思，又有什麼還在洩漏
當不同執行緒的操作以無數種方式交錯時，我們憑什麼宣稱它們正確？標準是 線性化（linearizability）：每個操作看起來都在它的呼叫與回傳之間某個單一時點上瞬間生效，而由此得到的序列是一個普通單執行緒堆疊或佇列的合法歷史。這就是為什麼我們一直在指認那個線性化點——擺動 top 的那個 CAS、接上佇列節點的那個 CAS、對 tail 的那個 release 儲存。為每個操作釘住那一個瞬間，一團並行呼叫就等價於一個整齊的循序順序，而那正是你對一個正常資料結構早已具備的心智模型。線性化就是那紙契約，讓你不必手動追蹤每一種交錯就能推理這些結構。
但誠實比一個漂亮的結尾更重要。這三個結構裡有兩個唯有搭配一套我們刻意沒提供的回收策略才正確。Treiber 堆疊的 pop 與 MS 佇列的 dequeue，都解開一個別的執行緒可能仍在讀的節點——太早釋放就得到釋放後使用、或讓 ABA 問題復活；永不釋放就得到一個無界的記憶體洩漏。有界的環形緩衝區因為從不配置而完全閃過這一切，這很大一部分正是它最簡單也最快的原因，也暗示了「把記憶體設成有界」是你手上最強的工具之一。對於無界結構，我什麼時候才能釋放這個節點？是那個尚未回答的問題，而它是真的難。
所以這就是本級誠實的樣貌。你現在能造出這三匹主力——也已看見同一道裂縫貫穿其中兩個。下一篇正是接住那道裂縫：危險指標（hazard pointer）與基於紀元（epoch）的回收，兩種在不用鎖的情況下回答什麼時候釋放一個節點才安全？的方法。最後一篇再推進到 RCU，以及這一切為何如此容易出現微妙、無聲錯誤的那個殘酷理由。資料結構是容易的那一半；安全回收才是讓專家都謙卑下來的那一半。