本文將介紹鎖無關(guān)數(shù)據(jù)結(jié)構(gòu)" title="數(shù)據(jù)結(jié)構(gòu)">數(shù)據(jù)結(jié)構(gòu)的應(yīng)用及其相關(guān)概念，并在 Java 環(huán)境下利用 JDK 1.5 提供的一組類進(jìn)行鎖無關(guān)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)，從而避免基于鎖的數(shù)據(jù)結(jié)構(gòu)可能引發(fā)的同步問題" title="同步問題">同步問題，以改善程序的可靠性。

介紹

??? 通常在一個(gè)多線程環(huán)境下，我們需要共享某些數(shù)據(jù)，但為了避免競爭條件引致數(shù)據(jù)出現(xiàn)不一致的情況，某些代碼段需要變成原子操作去執(zhí)行。這時(shí)，我們便需要利用各種同步機(jī)制如互斥（Mutex）去為這些代碼段加鎖，讓某一線程可以獨(dú)占共享數(shù)據(jù)，避免競爭條件，確保數(shù)據(jù)一致性。但可惜的是，這屬于阻塞性同步，所有其他線程唯一可以做的就是等待。基于鎖（Lock based）的多線程設(shè)計(jì)更可能引發(fā)死鎖" title="死鎖">死鎖、優(yōu)先級(jí)倒置、饑餓等情況，令到一些線程無法繼續(xù)其進(jìn)度。

??? 鎖無關(guān)（Lock free）算法，顧名思義，即不牽涉鎖的使用。這類算法可以在不使用鎖的情況下同步各個(gè)線程。對比基于鎖的多線程設(shè)計(jì)，鎖無關(guān)算法有以下優(yōu)勢：

• 對死鎖、優(yōu)先級(jí)倒置等問題免疫：它屬于非阻塞性同步，因?yàn)樗皇褂面i來協(xié)調(diào)各個(gè)線程，所以對死鎖、優(yōu)先級(jí)倒置等由鎖引起的問題免疫；
• 保證程序的整體進(jìn)度：由于鎖無關(guān)算法避免了死鎖等情況出現(xiàn)，所以它能確保線程是在運(yùn)行當(dāng)中，從而確保程序的整體進(jìn)度；
• 性能理想：因?yàn)椴簧婕笆褂面i，所以在普遍的負(fù)載環(huán)境下，使用鎖無關(guān)算法可以得到理想的性能提升。

??? 自 JDK 1.5 推出之后，當(dāng)中的 java.util.concurrent.atomic 的一組類為實(shí)現(xiàn)鎖無關(guān)算法提供了重要的基礎(chǔ)。本文介紹如何將鎖無關(guān)算法應(yīng)用到基本的數(shù)據(jù)結(jié)構(gòu)中，去避免競爭條件，允許多個(gè)線程同時(shí)存取和使用集合中的共享數(shù)據(jù)。如果一個(gè)數(shù)據(jù)結(jié)構(gòu)本身并非是線程安全的，一旦在多線程環(huán)境下使用這個(gè)數(shù)據(jù)結(jié)構(gòu)，必須施加某種同步機(jī)制，否則很可能會(huì)出現(xiàn)競爭條件。我們即將設(shè)計(jì)的鎖無關(guān)數(shù)據(jù)結(jié)構(gòu)是線程安全的，所以使用時(shí)無需再編寫額外代碼去確保競爭條件不會(huì)出現(xiàn)。

數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)

??? 本文會(huì)由淺入深，先提出鎖無關(guān)棧（Stack）的實(shí)現(xiàn)方法，為讀者提供必須的基礎(chǔ)知識(shí)，棧是一個(gè)先入后出（Last in first out）的基本數(shù)據(jù)結(jié)構(gòu)。當(dāng)讀者掌握必要的技術(shù)之后，我們便會(huì)著手設(shè)計(jì)相對復(fù)雜的鏈表" title="鏈表">鏈表（Linked List）數(shù)據(jù)結(jié)構(gòu)，鏈表是很多其他數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)組成部分。不過，對比起棧，鏈表可以面對更棘手的線程同步問題。

??? 在開始設(shè)計(jì)之前，我們需要理解一個(gè)十分重要的原語" title="原語">原語 Compare-and-swap (CAS) ，Herlihy 證明了 CAS 是實(shí)現(xiàn)鎖無關(guān)數(shù)據(jù)結(jié)構(gòu)的通用原語， CAS 可以原子地比較一個(gè)內(nèi)存位置的內(nèi)容及一個(gè)期望值，如果兩者相同，則用一個(gè)指定值取替這個(gè)內(nèi)存位罝里的內(nèi)容，并且提供結(jié)果指示這個(gè)操作是否成功。很多現(xiàn)代的處理器已經(jīng)提供了 CAS 的硬件實(shí)現(xiàn)，例如在 x86 架構(gòu)下的 CMPXCHG8 指令。而在 Java 下，位于 java.util.concurrent.atomic 內(nèi)的 AtomicReference 類亦提供了 CAS 原語的實(shí)現(xiàn)，并且有很多其他的擴(kuò)展功能。 CAS 操作將會(huì)是稍后實(shí)現(xiàn)的鎖無關(guān)數(shù)據(jù)算法無可缺少的指令。

棧

??? 棧能以數(shù)組或者鏈表作為底下的儲(chǔ)存結(jié)構(gòu)，雖然采取鏈表為基礎(chǔ)的實(shí)現(xiàn)方式會(huì)占用多一點(diǎn)空間去儲(chǔ)存代表元素的節(jié)點(diǎn)，但卻可避免處理數(shù)組溢出的問題。故此我們將以鏈表作為棧的基礎(chǔ)。

??? 首先，我們分析一下一個(gè)非線程安全的版本。為了清楚表達(dá)和集中于文章的主題，代碼沒有包含對異常及不正當(dāng)操作的處理，讀者請留意。它的代碼如下：

                
 class Node { 
    Node next; 
    T value; 
    
    public Node(T value, Node next) { 
        this.next = next; 
        this.value = value; 
    } 
 } 

 public class Stack { 
    Node top; 
    
    public void push(T value) { 
        Node newTop = new Node(value, top); 
        top = newTop; 
    } 
    
    public T pop() { 
        Node node = top; 
        top = top.next; 
        return node.value; 
    } 
    
    public T peek() { 
        return top.value; 
    } 
 } 

??? 數(shù)據(jù)成員 top 儲(chǔ)存著棧頂?shù)墓?jié)點(diǎn)，它的類型為 Node ，這是因?yàn)槲覀兊臈Ｊ腔阪湵淼摹?Node 代表一個(gè)節(jié)點(diǎn)，它有兩個(gè)數(shù)據(jù)成員， value 儲(chǔ)存著入棧的元素，而 next 儲(chǔ)存下一個(gè)節(jié)點(diǎn)。這個(gè)類有三個(gè)方法，分別是 push 、 pop 和 peek ，它們是基本的棧操作。除了 peek 方法是線程安全之外，其余兩個(gè)方法在多線程環(huán)境之下都有可能引發(fā)競爭條件。

push 方法

??? 讓我們先考慮一下 push 方法，它能將一個(gè)元素入棧。調(diào)用 push 時(shí)，它首先建立一個(gè)新的節(jié)點(diǎn)，并將 value 數(shù)據(jù)成員設(shè)定為傳入的參數(shù)，而 next 數(shù)據(jù)成員則被賦值為當(dāng)前的棧頂。然后它把 top 數(shù)據(jù)成員設(shè)定成新建立的節(jié)點(diǎn)。假設(shè)有兩個(gè)線程 A 和 B 同時(shí)調(diào)用 push 方法，線程 A 獲取當(dāng)前棧頂?shù)墓?jié)點(diǎn)去建立新的節(jié)點(diǎn)（ push 方法代碼第一行），但由于時(shí)間片用完，線程 A 暫時(shí)掛起。此時(shí)，線程 B 獲取當(dāng)前棧頂?shù)墓?jié)點(diǎn)去建立新的節(jié)點(diǎn)，并把 top 設(shè)定成新建立的節(jié)點(diǎn)（ push 方法代碼第二行）。然后，線程 A 恢復(fù)執(zhí)行，更新棧頂。當(dāng)線程 B 對 push 的調(diào)用完成后，線程 A 原本獲得的棧頂已經(jīng)「過期」，因?yàn)榫€程 B 用新的節(jié)點(diǎn)取代了原本的棧頂。

pop 方法

??? 至于 pop 方法，它把棧頂?shù)脑貜棾觥?pop 方法把棧頂暫存在一個(gè)本地變量 node ，然后用下一個(gè)節(jié)點(diǎn)去更新棧頂，最后返回變量 node 的 value 數(shù)據(jù)成員。如果兩個(gè)線程同時(shí)調(diào)用這個(gè)方法，可能會(huì)引起競爭條件。當(dāng)一個(gè)線程將當(dāng)前棧頂賦值到變量 node ，并準(zhǔn)備用下一個(gè)節(jié)點(diǎn)更新棧頂時(shí)，這個(gè)線程掛起。另一個(gè)線程亦調(diào)用 pop 方法，完成并返回結(jié)果。剛剛被掛起的線程恢復(fù)執(zhí)行，但由于棧頂被另一個(gè)線程變更了，所以繼續(xù)執(zhí)行的話會(huì)引起同步問題。

peek 方法

????而 peek 方法只是簡單地返回當(dāng)前位于棧頂?shù)脑?，這個(gè)方法是線程安全的，沒有同步問題要解決。

??? 在 Java 要解決 push 和 pop 方法的同步問題，可以用 synchronized 這個(gè)關(guān)鍵詞，這是基于鎖的解決方案?，F(xiàn)在我們看看鎖無關(guān)的解決方案，以下是鎖無關(guān)棧實(shí)現(xiàn)的代碼：

                
 import java.util.concurrent.atomic.*; 

 class Node { 
    Node next; 
    T value; 
    
    public Node(T value, Node next) { 
        this.next = next; 
        this.value = value; 
    } 
 } 

 public class Stack { 
    AtomicReference> top = new AtomicReference>(); 
    
    public void push(T value) { 
        boolean sucessful = false; 
        while (!sucessful) { 
            Node oldTop = top.get(); 
            Node newTop = new Node(value, oldTop); 
            sucessful = top.compareAndSet(oldTop, newTop); 
        }; 
    } 
    
    public T peek() { 
        return top.get().value; 
    } 
    
    public T pop() { 
        boolean sucessful = false; 
        Node newTop = null; 
        Node oldTop = null; 
        while (!sucessful) { 
            oldTop = top.get(); 
            newTop = oldTop.next; 
            sucessful = top.compareAndSet(oldTop, newTop); 
        } 
        return oldTop.value; 
    } 
 } 

??? 這個(gè)新的實(shí)現(xiàn)方式和剛剛的很不同，看似比較復(fù)雜。成員數(shù)據(jù) top 的類型由 Node 改為 AtomicReference> ， AtomicReference 這個(gè)類可以對 top 數(shù)據(jù)成員施加 CAS 操作，亦即是可以允許 top 原子地和一個(gè)期望值比較，兩者相同的話便用一個(gè)指定值取代。從上文可知，我們需要解決遇到棧頂「過期」的問題。

push 方法

??? 現(xiàn)在我們先分析新的 push 方法如何處理這個(gè)問題，確保競爭條件不會(huì)出現(xiàn)。在 while 循環(huán)中，通過在 top 數(shù)據(jù)成員調(diào)用 AtomicReference.get() ， oldTop 持有當(dāng)前棧頂節(jié)點(diǎn)，這個(gè)棧頂稍后會(huì)被取替。變量 newTop 則被初始化為新的節(jié)點(diǎn)。最重要的一步， top.compareAndSet(oldTop, newTop) ，它比較 top 和 oldTop 這兩個(gè)引用是否相同，去確保 oldTop 持有的棧頂并未「過期」，亦即未被其他線程變更。假如沒有過期，則用 newTop 去更新 top ，使之成為新的棧頂，并返回 boolean 值 true 。否則， compareAndSet 方法便返回 false ，并且令到循環(huán)繼續(xù)執(zhí)行，直至成功。因?yàn)?compareAndSet 是原子操作，所以可以保證數(shù)據(jù)一致。

pop 方法

??? pop 方法把棧頂?shù)脑貜棾?，它的?shí)現(xiàn)方式和 push 方法十分類同。在 while 循環(huán)內(nèi)， compareAndSet 檢查棧頂有沒有被其他線程改變，數(shù)據(jù)一致的話便更新 top 數(shù)據(jù)成員并把原本棧頂彈出。如果失敗，便重新嘗試，直至成功。

push 和 pop 都沒有使用任何鎖，所以全部線程都不用停下來等待。

鏈表

??? 棧是一個(gè)相當(dāng)簡單的數(shù)據(jù)結(jié)構(gòu)，要解決的同步問題亦比較直接和容易。但很多環(huán)境下，棧并不能滿足我們的需求。我們將介紹鏈表，它有更廣泛的應(yīng)用范圍。為了保持簡潔，這個(gè)鏈表所提供的方法較少。以下是鏈表的非線程安全版本：

                
 class Node { 
    Node next; 
    T value; 
    
    public Node(T value, Node next) { 
        this.value = value; 
        this.next = next; 
    } 
 } 

 class LinkedList { 
    Node head; 
    
    public LinkedList() { 
        head = new Node(null, null); 
    } 
    
    public void addFirst(T value) { 
        addAfter(head.value, value); 
    } 
    
    public boolean addAfter(T after, T value) { 
        for (Node node = head; node != null; node = node.next) { 
            if (isEqual(node.value, after)) { 
                Node newNode = new Node(value, node.next); 
                node.next = newNode; 
                return true; 
            } 
        } 
        return false; 
    } 
    
    public boolean remove(T value) { 
        for (Node node = head; node.next != null; node = node.next) { 
            if (isEqual(node.next.value, value)) { 
                node.next = node.next.next; 
                return true; 
            } 
        } 
        return false; 
    } 
    
    boolean isEqual(T arg0, T arg1) { 
        if (arg0 == null) { 
            return arg0 == arg1; 
        } else { 
            return arg0.equals(arg1); 
        } 
    } 
 } 

??? 數(shù)據(jù)成員 head 是鏈表的頭，它沒有存儲(chǔ)任何元素，而是直接指向第一個(gè)元素，這可以令稍后的 remove 方法較易實(shí)現(xiàn)。這個(gè)鏈表有三個(gè)公用方法，其中 addAfter 和 remove 比較重要。

addAfter 方法

??? 先考慮一下 addAfter 方法，這個(gè)方法把一個(gè)新元素加入到集合內(nèi)指定元素之后的位置，并返回一個(gè) boolean 值指示元素有沒有被加入到集合中，元素沒有被加入的原因是因?yàn)榧蟽?nèi)沒有所指定的元素。它首先在一個(gè) for 循環(huán)中尋找指定元素的節(jié)點(diǎn)，成功發(fā)現(xiàn)指定的節(jié)點(diǎn)后，便建立一個(gè)新節(jié)點(diǎn)。這個(gè)新節(jié)點(diǎn)的 next 數(shù)據(jù)成員連接到指定節(jié)點(diǎn)原本的 next ，指定節(jié)點(diǎn)的 next 則連到新節(jié)點(diǎn)上。另一方面， remove 方法尋找指定元素并從集合中移除，并且返回一個(gè) boolean 值指示元素有沒有被移除，返回 false 代表集合中沒有指定的元素。這個(gè)方法在一個(gè)循環(huán)尋找要移除的元素，并且將左右兩邊的元素重新連接。

??? 在多線程環(huán)境下，如果兩個(gè)線程同時(shí)調(diào)用 addAfter 或 remove 方法，或者一個(gè)線程調(diào)用 addAfter 方法而同一時(shí)間另一個(gè)線程調(diào)用 remove 方法均有機(jī)會(huì)引發(fā)競爭條件。

??? 試想像現(xiàn)在鏈表內(nèi)有三個(gè)元素，分別是 A、B 和 C 。如果一個(gè)線程準(zhǔn)備把一個(gè)元素加到 A 之后，它首先確定 A 節(jié)點(diǎn)的位置，然后新建一個(gè)節(jié)點(diǎn) A1，這個(gè)節(jié)點(diǎn)的 value 數(shù)據(jù)成員儲(chǔ)存著新加入的元素，而 next 數(shù)據(jù)成員則儲(chǔ)存著 B 節(jié)點(diǎn)的引用。當(dāng)這個(gè)線程準(zhǔn)備把 A 和 A1 通過 next 成員連接起來時(shí)，此時(shí)線程因?yàn)闀r(shí)間片用完而被掛起。另一個(gè)線程亦準(zhǔn)備在 A 之后加入一個(gè)新元素，它建立 A2 節(jié)點(diǎn)，并解除 A 和 B 原本的連結(jié)，然后依著 A-A2-B 的次序重新連接三個(gè)節(jié)點(diǎn)，操作完成。現(xiàn)在，剛剛被掛起的線程恢復(fù)執(zhí)行，并依著 A-A1-B 的次序去重新連接三個(gè)節(jié)點(diǎn)。這時(shí)問題出現(xiàn)，剛剛新加入的 A2 節(jié)點(diǎn)遺失了。解決方法是，每一次準(zhǔn)備把 A 元素和新建立的節(jié)點(diǎn)連接時(shí)，檢查 A 節(jié)的 next 有否被其他線程改動(dòng)過，沒有改動(dòng)過才進(jìn)行連接，這是通過 CAS 操作原子地進(jìn)行的。

addAfter 和 remove 的沖突

??? 同時(shí)間執(zhí)行 addAfter 和 remove 亦有可能引起競爭條件。同樣地，現(xiàn)在一個(gè)鏈表內(nèi)有三個(gè)元素 A、B 和 C 。當(dāng)一個(gè)線程準(zhǔn)備調(diào)用 remove 方法從這個(gè)集合中移除 B 元素，它首先獲得 A 節(jié)點(diǎn)，然后準(zhǔn)備通過改變 A 節(jié)點(diǎn)的 next 成員，把 A 和 C 互相連接時(shí)，這個(gè)線程突然被掛起。此時(shí)另一個(gè)線程調(diào)用 addAfter 方法在 B 節(jié)點(diǎn)后插入一個(gè)新的元素 B2 。插入操作完成后，剛才被掛起的線程恢復(fù)執(zhí)行，并且通過改變 next 成員把 A 和 C 互相連接，完成移除操作。可是，剛剛被加入的 B2 元素則遺失了，因?yàn)?A 節(jié)點(diǎn)跳過了 B 節(jié)點(diǎn)，直接連接著 C 節(jié)點(diǎn)。故此，我們要有一個(gè)解決方案。 Timothy L. Harris 提供了一個(gè)方法，他把整個(gè)移除過程分成兩個(gè)步驟，邏輯刪除和物理刪除。邏輯刪除并非真正地移除一個(gè)節(jié)點(diǎn)，而是把要移除的節(jié)點(diǎn)標(biāo)記為已刪除。另一方面，物理刪除則真實(shí)從集合左移除一個(gè)節(jié)點(diǎn)。每次要加入新元素到指定節(jié)點(diǎn)之后，都必先檢查該節(jié)點(diǎn)有沒有被標(biāo)記為刪除，沒有的話才把新的節(jié)點(diǎn)連接到集合中。這是通過 AtomicMarkableReference 類中的 compareAndSet 方法原子地進(jìn)行的。

remove 方法

??? 鏈表有可能發(fā)生的沖突比較多，另一個(gè)問題便是兩個(gè)線程同時(shí)間執(zhí)行 remove 方法。這個(gè)問題和同時(shí)間執(zhí)行 addAfter 有點(diǎn)類同。現(xiàn)在假設(shè)一個(gè)集合內(nèi)有四個(gè)元素 A、B、C 和 D，一個(gè)線程調(diào)用 remove 方法去移除元素 B 。它首先確定了 A 和 C 的位置，然后準(zhǔn)備解除 A 和 B 的連結(jié)，再將 A 和 C 連接起來，實(shí)際的移除還未實(shí)行，這時(shí)這個(gè)線程被掛起了。另一個(gè)線程亦調(diào)用 remove 方法移除 C 元素，它解除 B 和 C 的連結(jié)，并把 B 和 D 連接起來，移除操作完成。之后剛才的線程恢復(fù)運(yùn)行，繼續(xù)執(zhí)行余下的操作，把 A 和 C 連接起來，這樣之前的移除 C 的操作便受到了破壞。最終鏈表中的元素變成 A-C-D，C 元素沒有被移除。所以，我們 remove 方法需要確定要移除的元素的 next 有沒有被改變。例如移除 B 的時(shí)候，檢查 A 的 next 有沒有被其他線程更動(dòng)，以及有沒有被標(biāo)記為已經(jīng)邏輯地刪除。這亦是透過 CAS 操作去完成的。

??? 從上文的各種情況可見，我們必須原子地施加某些檢查機(jī)制，確保數(shù)據(jù)的一致性。我們現(xiàn)在看看解決這些問題的鎖無關(guān)鏈表是如何實(shí)現(xiàn)的，這些代碼應(yīng)該和讀者在算法書上看到的很不同。以下是它的代碼：

                
 import java.util.concurrent.atomic.*; 

 class Node { 
    AtomicMarkableReference> next; 
    T value; 
    
    public Node(T value, Node next) { 
        this.next = new AtomicMarkableReference>(next, false); 
        this.value = value; 
    } 
 } 
    
 class LinkedList { 
    AtomicMarkableReference> head; 

    public LinkedList() { 
        Node headNode = new Node(null, null); 
        head = new AtomicMarkableReference>(headNode, false); 
    } 
    
    public void addFirst(T value) { 
        addAfter(head.getReference().value, value); 
    } 
    
    public boolean addAfter(T after, T value) { 
        boolean sucessful = false; 
        while (!sucessful) { 
            boolean found = false; 
            for (Node node = head.getReference(); node != null && !isRemoved(node); 
            node = node.next.getReference()) { 
                if (isEqual(node.value, after) && !node.next.isMarked()) { 
                    found = true; 
                    Node nextNode = node.next.getReference(); 
                    Node newNode = new Node(value, nextNode); 
                    sucessful = node.next.compareAndSet(nextNode, newNode, false, false); 
                    break; 
                } 
            } 
            if (!found) { 
                return false; 
            } 
        } 
        return true; 
    } 
    
    public boolean remove(T value) { 
        boolean sucessful = false; 
        while (!sucessful) { 
            boolean found = false; 
            for (Node node = head.getReference(), nextNode = node.next.getReference(); 
            nextNode != null; node = nextNode, nextNode = nextNode.next.getReference()) { 
                if (!isRemoved(nextNode) && isEqual(nextNode.value, value)) { 
                    found = true; 
                    logicallyRemove(nextNode); 
                    sucessful = physicallyRemove(node, nextNode); 
                    break; 
                } 
            } 
            if (!found) { 
                return false; 
            } 
        } 
        return true; 
    } 
    
    void logicallyRemove(Node node) { 
        while (!node.next.attemptMark(node.next.getReference(), true)) { } 
    } 
    
    boolean physicallyRemove(Node leftNode, Node node) { 
        Node rightNode = node; 
        do { 
            rightNode = rightNode.next.getReference(); 
        } while (rightNode != null && isRemoved(rightNode)); 
        return leftNode.next.compareAndSet(node, rightNode, false, false); 
    } 
    
    boolean isRemoved(Node node) { 
        return node.next.isMarked(); 
    } 
    
    boolean isEqual(T arg0, T arg1) { 
        if (arg0 == null) { 
            return arg0 == arg1; 
        } else { 
            return arg0.equals(arg1); 
        } 
    } 
 } 

??? 和之前不同， Node 類中的 next 成員數(shù)據(jù)屬于 AtomicMarkableReference 類，不是 Node ，亦不是 AtomicReference 。這是因?yàn)槲覀儾坏枰?next 成員進(jìn)行 CAS 操作，也需要在 next 中加上標(biāo)記。 AtomicMarkableReference 上的標(biāo)記是以一個(gè) boolean 表示的。我們會(huì)以設(shè)定它為 true 來代表一個(gè)節(jié)點(diǎn)已被邏輯刪除， false 則代表這個(gè)節(jié)點(diǎn)未被邏輯刪除。當(dāng)一個(gè)節(jié)點(diǎn)被標(biāo)記為已經(jīng)邏輯地刪除，它的 next 數(shù)據(jù)成員的標(biāo)記位會(huì)被設(shè)定成 boolean 值 true 。另一方面，鏈表中的 head 亦屬 AtomicMarkableReference 這類型，因?yàn)槲覀円残枰M(jìn)行同樣的操作。

addAfter 方法

??? 首先考慮一下 addAfter 方法， addAfter 方法的設(shè)計(jì)必須顧慮到兩個(gè)線程同時(shí)間插入及同時(shí)間一個(gè)線程插入和一個(gè)線程移除的沖突。在一個(gè) for 循環(huán)中，它遍歷集合去尋找 after 所位于的節(jié)點(diǎn)，并通過調(diào)用 getReference() 把 after 的下一個(gè)節(jié)點(diǎn)賦值到 nextNode 變量中。然后，建立一個(gè)新的節(jié)點(diǎn)去容納新加入的元素，它通過 next 數(shù)據(jù)成員和 nextNode 變量進(jìn)行連接。下一步，在 node 變量上調(diào)用 compareAndSet 。不同之處在于它不但比較兩個(gè)引用是否相同去確保 next 數(shù)據(jù)成員沒有被其他線程改變過，它亦會(huì)比較 boolean 標(biāo)記位和期望值是否相同。上文提到，AtomicMarkableReference 類擁有一個(gè)標(biāo)記位，我們利用它去檢查一個(gè)節(jié)點(diǎn)是否已被邏輯地刪除了。如果我們發(fā)現(xiàn)那個(gè)節(jié)點(diǎn)已被 logicallyRemove 方法標(biāo)記為已經(jīng)被邏輯地刪除， compareAndSet 方法便會(huì)失敗，并繼續(xù)循環(huán)尋找下一個(gè)符合的節(jié)點(diǎn)。若果循環(huán)終結(jié)后仍未尋找到指定的元素， a ddAfter 方法便會(huì)返回 false 以表示由于集合內(nèi)不存在指定的元素，所以元素?zé)o法被加入到集合中。 compareAndSet 返回 true 便代表元素插入成功，方法便會(huì)返回并結(jié)束。

addFirst 方法

???addFirst 方法只是簡單地調(diào)用 addAfter 方法去把一個(gè)新的元素插入到集合的開端。

Remove 方法

?? remove 方法在一個(gè)循環(huán)內(nèi)尋找要移除元素的前一個(gè)節(jié)點(diǎn)，然后確定這個(gè)節(jié)點(diǎn)未被邏輯地移除。確定后，它首先調(diào)用 logicallyRemove 邏輯地刪除節(jié)點(diǎn)，然后調(diào)用 physicallyRemove 物理地刪除節(jié)點(diǎn)。在 logicallyRemove 中，我們調(diào)用 AtomicMarkableReference 中的 attemptMark 來設(shè)定標(biāo)記位。由于 attemptMark 可能會(huì)失敗，所以要將它放進(jìn)一個(gè) while 循環(huán)中，經(jīng)過 attemptMark 設(shè)定標(biāo)記的節(jié)點(diǎn)代表該節(jié)點(diǎn)已被邏輯地刪除。在 physicallyRemove 方法中，它首先檢查鄰近的其他節(jié)點(diǎn)是否都已經(jīng)被標(biāo)記為邏輯刪除，若果已被標(biāo)記則順道物理地移除它們。這是通過 compareAndSet 完成， compareAndSet 會(huì)檢查節(jié)點(diǎn)是否已被邏輯地刪除，以及上一個(gè)節(jié)點(diǎn)的 next 成員未被其他線程更改。這樣可以確保兩個(gè)線程同時(shí)調(diào)用 remove 方法，或者分別同時(shí)間調(diào)用 remove 方法和 a ddAfter 方法的時(shí)候，競爭條件不會(huì)發(fā)生。

ABA 問題

??? 因?yàn)?CAS 操作比較一個(gè)內(nèi)存位置的內(nèi)容及一個(gè)期望值是否相同，但如果一個(gè)內(nèi)存位置的內(nèi)容由 A 變成 B，再由 B 變成 A， CAS 仍然會(huì)看作兩者相同。不過，一些算法因?yàn)樾枨蟮年P(guān)系無法容忍這種行為。當(dāng)一些內(nèi)存位置被重用的時(shí)候，這個(gè)問題便可能會(huì)發(fā)生。在沒有垃圾回收機(jī)制的環(huán)境下，ABA 問題需要一些機(jī)制例如標(biāo)記去解決。但由于 JVM 會(huì)為我們處理內(nèi)存管理的問題，故此以上的實(shí)現(xiàn)足以避免 ABA 問題的出現(xiàn)。

結(jié)束語

??? 以往很多的鎖無關(guān)數(shù)據(jù)結(jié)構(gòu)都以 Immutable object 的方式去達(dá)致線程安全，這很像 Java 中的 String ，但因?yàn)樯婕斑^多的復(fù)制操作，令性能低下。但經(jīng)過十多年，鎖無關(guān)數(shù)據(jù)結(jié)構(gòu)已發(fā)展得十分成熟，性能并不遜色于傳統(tǒng)的實(shí)現(xiàn)方式。編寫鎖無關(guān)算法是十分困難的，但因?yàn)閿?shù)據(jù)結(jié)構(gòu)是經(jīng)常被重用的部分，首先把這個(gè)概念應(yīng)用到數(shù)據(jù)結(jié)構(gòu)中，可以輕易讓程序進(jìn)入鎖無關(guān)的世界，體驗(yàn)它所帶來的好處。

參考資料

• 查閱“Lock-Free Data Structures”：有關(guān)鎖無關(guān)數(shù)據(jù)結(jié)構(gòu)的詳細(xì)解析，適合初接觸鎖無關(guān)算法的讀者。
  
  
• 查閱“A Pragmatic Implementation of Non-Blocking Linked-Lists”：Timothy L. Harris 有關(guān)使用兩步刪除實(shí)現(xiàn)鎖無關(guān)鏈表的文章。
  
  
• 查閱“LockFree Linked Lists and Skip Lists”：基于 Timothy L. Harris 方式并利用 backlink 實(shí)現(xiàn)更高性能鏈表的文章。
  
  
• 在 Java 多線程與并行編程專題 中找到更多關(guān)于 Java 多線程編程方面的技術(shù)文章和教程。
  
  
• 在 developerWorks Java 技術(shù)專區(qū)上可以找到數(shù)百篇關(guān)于 Java 各個(gè)方面的文章。