線性化（linearizability）與線性化點
/ lin-ee-uh-rize-uh-BIL-i-tee /
當好幾個執行緒同時對一個共享資料結構操作時，它們的操作在真實時間裡彼此重疊，並沒有一個顯而易見的單一順序。那麼，一個並行的堆疊或佇列「正確」究竟是什麼意思？線性化（linearizability）是標準答案：一個並行物件是正確的，是指儘管種種重疊，它的表現恰如每個操作都在它被呼叫到它返回之間的「某個單一瞬間」瞬時生效。它是無鎖資料結構的黃金標準正確性條件。
用線性化點（linearization point）把它說精確。每個操作雖然橫跨一段真實時間，卻被當成在那段區間內的某一瞬間原子地發生——那就是它的線性化點。若你能為每個操作，在它「呼叫到返回」的區間內選一個線性化點，使得按線性化點順序一次一個地執行這些操作，會得到該物件正確的循序版本所產生的結果，那麼這次執行就是可線性化的。實務上線性化點通常是某條特定指令：對 Treiber 堆疊的 push 而言，是那次成功擺動 head 的 CAS；對 SPSC 的 enqueue 而言，是那次發布新 tail 的釋放儲存。在那條指令之前，操作尚未發生；在它之後，操作已原子地發生，沒有任何中間狀態被任何人看見。
它為何如此重要：線性化讓你能把一個並行物件當成一個單純的循序物件來推理，而這是人類唯一能把這些東西裝進腦袋的方式。它也能組合——由個別可線性化的物件構成的系統，具有一致的整體行為。兩個誠實的區別：線性化強於單純的可序列化（serializability）（它額外尊重真實時間順序，所以一個在另一個開始前就完成的操作，必須被排在前面），而且它和進展保證是不同的關切——一個演算法可以是可線性化但阻塞，也可以是無鎖但若你做錯了就不可線性化。正確性與進展是你必須各自獨立滿足的兩條軸。
/* 線性化點是操作「生效」的那單一瞬間。 */ Node *pop(void) { do { old = head; if (!old) return NULL; next = old->next; } while (!CAS(&head, old, next)); /* <-- 線性化點：那次成功的 CAS */ return old; } /* 在成功的 CAS 之前 pop 尚未發生；在它之後，pop 已原子地發生。 */
指出每個操作原子生效的那單一指令，正是你證明一個無鎖結構可線性化的方法。
線性化（正確性）與進展類別（無鎖、等待無關）是獨立的：一個結構可以可線性化卻阻塞，也可以無鎖卻有錯而不可線性化。兩者你都必須分別建立。