Java 下实现锁无关数据结构--转载
介紹
通常在一個(gè)多線程環(huán)境下，我們需要共享某些數(shù)據(jù)，但為了避免競(jìng)爭(zhēng)條件引致數(shù)據(jù)出現(xiàn)不一致的情況，某些代碼段需要變成原子操作去執(zhí)行。這時(shí)，我們便需要利用各種同步機(jī)制如互斥（Mutex）去為這些代碼段加鎖，讓某一線程可以獨(dú)占共享數(shù)據(jù)，避免競(jìng)爭(zhēng)條件，確保數(shù)據(jù)一致性。但可惜的是，這屬于阻塞性同步，所有其他線程唯一可以做的就是等待。基于鎖（Lock based）的多線程設(shè)計(jì)更可能引發(fā)死鎖、優(yōu)先級(jí)倒置、饑餓等情況，令到一些線程無(wú)法繼續(xù)其進(jìn)度。
鎖無(wú)關(guān)（Lock free）算法，顧名思義，即不牽涉鎖的使用。這類(lèi)算法可以在不使用鎖的情況下同步各個(gè)線程。對(duì)比基于鎖的多線程設(shè)計(jì)，鎖無(wú)關(guān)算法有以下優(yōu)勢(shì)：
- 對(duì)死鎖、優(yōu)先級(jí)倒置等問(wèn)題免疫：它屬于非阻塞性同步，因?yàn)樗皇褂面i來(lái)協(xié)調(diào)各個(gè)線程，所以對(duì)死鎖、優(yōu)先級(jí)倒置等由鎖引起的問(wèn)題免疫；
- 保證程序的整體進(jìn)度：由于鎖無(wú)關(guān)算法避免了死鎖等情況出現(xiàn)，所以它能確保線程是在運(yùn)行當(dāng)中，從而確保程序的整體進(jìn)度；
- 性能理想：因?yàn)椴簧婕笆褂面i，所以在普遍的負(fù)載環(huán)境下，使用鎖無(wú)關(guān)算法可以得到理想的性能提升。
自 JDK 1.5 推出之后，當(dāng)中的?java.util.concurrent.atomic?的一組類(lèi)為實(shí)現(xiàn)鎖無(wú)關(guān)算法提供了重要的基礎(chǔ)。本文介紹如何將鎖無(wú)關(guān)算法應(yīng)用到基本的數(shù)據(jù)結(jié)構(gòu)中，去避免競(jìng)爭(zhēng)條件，允許多個(gè)線程同時(shí)存取和使用集合中的共享數(shù)據(jù)。如果一個(gè)數(shù)據(jù)結(jié)構(gòu)本身并非是線程安全的，一旦在多線程環(huán)境下使用這個(gè)數(shù)據(jù)結(jié)構(gòu)，必須施加某種同步機(jī)制，否則很可能會(huì)出現(xiàn)競(jìng)爭(zhēng)條件。我們即將設(shè)計(jì)的鎖無(wú)關(guān)數(shù)據(jù)結(jié)構(gòu)是線程安全的，所以使用時(shí)無(wú)需再編寫(xiě)額外代碼去確保競(jìng)爭(zhēng)條件不會(huì)出現(xiàn)。
數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)
本文會(huì)由淺入深，先提出鎖無(wú)關(guān)棧（Stack）的實(shí)現(xiàn)方法，為讀者提供必須的基礎(chǔ)知識(shí)，棧是一個(gè)先入后出（Last in first out）的基本數(shù)據(jù)結(jié)構(gòu)。當(dāng)讀者掌握必要的技術(shù)之后，我們便會(huì)著手設(shè)計(jì)相對(duì)復(fù)雜的鏈表（Linked List）數(shù)據(jù)結(jié)構(gòu)，鏈表是很多其他數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)組成部分。不過(guò)，對(duì)比起棧，鏈表可以面對(duì)更棘手的線程同步問(wèn)題。
在開(kāi)始設(shè)計(jì)之前，我們需要理解一個(gè)十分重要的原語(yǔ)?Compare-and-swap (CAS)?，Herlihy 證明了?CAS?是實(shí)現(xiàn)鎖無(wú)關(guān)數(shù)據(jù)結(jié)構(gòu)的通用原語(yǔ)，?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<V>?類(lèi)亦提供了?CAS?原語(yǔ)的實(shí)現(xiàn)，并且有很多其他的擴(kuò)展功能。?CAS?操作將會(huì)是稍后實(shí)現(xiàn)的鎖無(wú)關(guān)數(shù)據(jù)算法無(wú)可缺少的指令。
棧
棧能以數(shù)組或者鏈表作為底下的儲(chǔ)存結(jié)構(gòu)，雖然采取鏈表為基礎(chǔ)的實(shí)現(xiàn)方式會(huì)占用多一點(diǎn)空間去儲(chǔ)存代表元素的節(jié)點(diǎn)，但卻可避免處理數(shù)組溢出的問(wèn)題。故此我們將以鏈表作為棧的基礎(chǔ)。
首先，我們分析一下一個(gè)非線程安全的版本。為了清楚表達(dá)和集中于文章的主題，代碼沒(méi)有包含對(duì)異常及不正當(dāng)操作的處理，讀者請(qǐng)留意。它的代碼如下：
清單 1. 非線程安全的棧實(shí)現(xiàn)
class Node<T> { Node<T> next; T value; public Node(T value, Node<T> next) { this.next = next; this.value = value; } } public class Stack<T> { Node<T> top; public void push(T value) { Node<T> newTop = new Node<T>(value, top); top = newTop; } public T pop() { Node<T> node = top; top = top.next; return node.value; } public T peek() { return top.value; } }數(shù)據(jù)成員?top?儲(chǔ)存著棧頂?shù)墓?jié)點(diǎn)，它的類(lèi)型為?Node<T>?，這是因?yàn)槲覀兊臈Ｊ腔阪湵淼摹?Node<T>?代表一個(gè)節(jié)點(diǎn)，它有兩個(gè)數(shù)據(jù)成員，value?儲(chǔ)存著入棧的元素，而?next?儲(chǔ)存下一個(gè)節(jié)點(diǎn)。這個(gè)類(lèi)有三個(gè)方法，分別是?push?、?pop?和?peek?，它們是基本的棧操作。除了?peek?方法是線程安全之外，其余兩個(gè)方法在多線程環(huán)境之下都有可能引發(fā)競(jìng)爭(zhēng)條件。
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 對(duì)?push?的調(diào)用完成后，線程 A 原本獲得的棧頂已經(jīng)「過(guò)期」，因?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ì)引起競(jìng)爭(zhēng)條件。當(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ì)引起同步問(wèn)題。
peek 方法
而?peek?方法只是簡(jiǎn)單地返回當(dāng)前位于棧頂?shù)脑?#xff0c;這個(gè)方法是線程安全的，沒(méi)有同步問(wèn)題要解決。
在 Java 要解決?push?和?pop?方法的同步問(wèn)題，可以用?synchronized?這個(gè)關(guān)鍵詞，這是基于鎖的解決方案。現(xiàn)在我們看看鎖無(wú)關(guān)的解決方案，以下是鎖無(wú)關(guān)棧實(shí)現(xiàn)的代碼：
清單 2. 鎖無(wú)關(guān)的棧實(shí)現(xiàn)
import java.util.concurrent.atomic.*; class Node<T> { Node<T> next; T value; public Node(T value, Node<T> next) { this.next = next; this.value = value; } } public class Stack<T> { AtomicReference<Node<T>> top = new AtomicReference<Node<T>>(); public void push(T value) { boolean sucessful = false; while (!sucessful) { Node<T> oldTop = top.get(); Node<T> newTop = new Node<T>(value, oldTop); sucessful = top.compareAndSet(oldTop, newTop); }; } public T peek() { return top.get().value; } public T pop() { boolean sucessful = false; Node<T> newTop = null; Node<T> 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?的類(lèi)型由?Node<T>?改為?AtomicReference<Node<T>>?，AtomicReference<V>?這個(gè)類(lèi)可以對(duì)?top?數(shù)據(jù)成員施加?CAS?操作，亦即是可以允許?top?原子地和一個(gè)期望值比較，兩者相同的話便用一個(gè)指定值取代。從上文可知，我們需要解決遇到棧頂「過(guò)期」的問(wèn)題。
push 方法
現(xiàn)在我們先分析新的?push?方法如何處理這個(gè)問(wèn)題，確保競(jìng)爭(zhēng)條件不會(huì)出現(xiàn)。在?while?循環(huán)中，通過(guò)在?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?持有的棧頂并未「過(guò)期」，亦即未被其他線程變更。假如沒(méi)有過(guò)期，則用?newTop?去更新?top?，使之成為新的棧頂，并返回?boolean?值?true?。否則，?compareAndSet?方法便返回false?，并且令到循環(huán)繼續(xù)執(zhí)行，直至成功。因?yàn)?compareAndSet?是原子操作，所以可以保證數(shù)據(jù)一致。
pop 方法
pop?方法把棧頂?shù)脑貜棾?#xff0c;它的實(shí)現(xiàn)方式和?push?方法十分類(lèi)同。在?while?循環(huán)內(nèi)，?compareAndSet?檢查棧頂有沒(méi)有被其他線程改變，數(shù)據(jù)一致的話便更新?top?數(shù)據(jù)成員并把原本棧頂彈出。如果失敗，便重新嘗試，直至成功。
push?和?pop?都沒(méi)有使用任何鎖，所以全部線程都不用停下來(lái)等待。
鏈表
棧是一個(gè)相當(dāng)簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，要解決的同步問(wèn)題亦比較直接和容易。但很多環(huán)境下，棧并不能滿(mǎn)足我們的需求。我們將介紹鏈表，它有更廣泛的應(yīng)用范圍。為了保持簡(jiǎn)潔，這個(gè)鏈表所提供的方法較少。以下是鏈表的非線程安全版本：
清單 3. 非線程安全的鏈表實(shí)現(xiàn)
class Node<T> { Node<T> next; T value; public Node(T value, Node<T> next) { this.value = value; this.next = next; } } class LinkedList<T> { Node<T> head; public LinkedList() { head = new Node<T>(null, null); } public void addFirst(T value) { addAfter(head.value, value); } public boolean addAfter(T after, T value) { for (Node<T> node = head; node != null; node = node.next) { if (isEqual(node.value, after)) { Node<T> newNode = new Node<T>(value, node.next); node.next = newNode; return true; } } return false; } public boolean remove(T value) { for (Node<T> 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?是鏈表的頭，它沒(méi)有存儲(chǔ)任何元素，而是直接指向第一個(gè)元素，這可以令稍后的?remove?方法較易實(shí)現(xiàn)。這個(gè)鏈表有三個(gè)公用方法，其中?addAfter?和?remove?比較重要。
addAfter 方法
先考慮一下?addAfter?方法，這個(gè)方法把一個(gè)新元素加入到集合內(nèi)指定元素之后的位置，并返回一個(gè)?boolean?值指示元素有沒(méi)有被加入到集合中，元素沒(méi)有被加入的原因是因?yàn)榧蟽?nèi)沒(mé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?值指示元素有沒(méi)有被移除，返回?false?代表集合中沒(méi)有指定的元素。這個(gè)方法在一個(gè)循環(huán)尋找要移除的元素，并且將左右兩邊的元素重新連接。
在多線程環(huán)境下，如果兩個(gè)線程同時(shí)調(diào)用?addAfter?或?remove?方法，或者一個(gè)線程調(diào)用?addAfter?方法而同一時(shí)間另一個(gè)線程調(diào)用?remove?方法均有機(jī)會(huì)引發(fā)競(jìng)爭(zhēng)條件。
試想像現(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 通過(guò)?next?成員連接起來(lái)時(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í)問(wèn)題出現(xiàn)，剛剛新加入的 A2 節(jié)點(diǎn)遺失了。解決方法是，每一次準(zhǔn)備把 A 元素和新建立的節(jié)點(diǎn)連接時(shí)，檢查 A 節(jié)的?next?有否被其他線程改動(dòng)過(guò)，沒(méi)有改動(dòng)過(guò)才進(jìn)行連接，這是通過(guò)?CAS?操作原子地進(jìn)行的。
addAfter 和 remove 的沖突
同時(shí)間執(zhí)行?addAfter?和?remove?亦有可能引起競(jìng)爭(zhēng)條件。同樣地，現(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)備通過(guò)改變 A 節(jié)點(diǎn)的?next?成員，把 A 和 C 互相連接時(shí)，這個(gè)線程突然被掛起。此時(shí)另一個(gè)線程調(diào)用?addAfter?方法在 B 節(jié)點(diǎn)后插入一個(gè)新的元素 B2 。插入操作完成后，剛才被掛起的線程恢復(fù)執(zhí)行，并且通過(guò)改變?next?成員把 A 和 C 互相連接，完成移除操作。可是，剛剛被加入的 B2 元素則遺失了，因?yàn)?A 節(jié)點(diǎn)跳過(guò)了 B 節(jié)點(diǎn)，直接連接著 C 節(jié)點(diǎn)。故此，我們要有一個(gè)解決方案。 Timothy L. Harris 提供了一個(gè)方法，他把整個(gè)移除過(guò)程分成兩個(gè)步驟，邏輯刪除和物理刪除。邏輯刪除并非真正地移除一個(gè)節(jié)點(diǎn)，而是把要移除的節(jié)點(diǎn)標(biāo)記為已刪除。另一方面，物理刪除則真實(shí)從集合左移除一個(gè)節(jié)點(diǎn)。每次要加入新元素到指定節(jié)點(diǎn)之后，都必先檢查該節(jié)點(diǎn)有沒(méi)有被標(biāo)記為刪除，沒(méi)有的話才把新的節(jié)點(diǎn)連接到集合中。這是通過(guò)?AtomicMarkableReference<V>?類(lèi)中的?compareAndSet?方法原子地進(jìn)行的。
remove 方法
鏈表有可能發(fā)生的沖突比較多，另一個(gè)問(wèn)題便是兩個(gè)線程同時(shí)間執(zhí)行?remove?方法。這個(gè)問(wèn)題和同時(shí)間執(zhí)行?addAfter?有點(diǎn)類(lèi)同。現(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 連接起來(lái)，實(shí)際的移除還未實(shí)行，這時(shí)這個(gè)線程被掛起了。另一個(gè)線程亦調(diào)用?remove?方法移除 C 元素，它解除 B 和 C 的連結(jié)，并把 B 和 D 連接起來(lái)，移除操作完成。之后剛才的線程恢復(fù)運(yùn)行，繼續(xù)執(zhí)行余下的操作，把 A 和 C 連接起來(lái)，這樣之前的移除 C 的操作便受到了破壞。最終鏈表中的元素變成 A-C-D，C 元素沒(méi)有被移除。所以，我們?remove?方法需要確定要移除的元素的?next?有沒(méi)有被改變。例如移除 B 的時(shí)候，檢查 A 的?next?有沒(méi)有被其他線程更動(dòng)，以及有沒(méi)有被標(biāo)記為已經(jīng)邏輯地刪除。這亦是透過(guò)?CAS?操作去完成的。
從上文的各種情況可見(jiàn)，我們必須原子地施加某些檢查機(jī)制，確保數(shù)據(jù)的一致性。我們現(xiàn)在看看解決這些問(wèn)題的鎖無(wú)關(guān)鏈表是如何實(shí)現(xiàn)的，這些代碼應(yīng)該和讀者在算法書(shū)上看到的很不同。以下是它的代碼：
清單 4. 鎖無(wú)關(guān)的鏈表實(shí)現(xiàn)
import java.util.concurrent.atomic.*; class Node<T> { AtomicMarkableReference<Node<T>> next; T value; public Node(T value, Node<T> next) { this.next = new AtomicMarkableReference<Node<T>>(next, false); this.value = value; } } class LinkedList<T> { AtomicMarkableReference<Node<T>> head; public LinkedList() { Node<T> headNode = new Node<T>(null, null); head = new AtomicMarkableReference<Node<T>>(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<T> node = head.getReference(); node != null && !isRemoved(node); node = node.next.getReference()) { if (isEqual(node.value, after) && !node.next.isMarked()) { found = true; Node<T> nextNode = node.next.getReference(); Node<T> newNode = new Node<T>(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<T> 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<T> node) { while (!node.next.attemptMark(node.next.getReference(), true)) { } } boolean physicallyRemove(Node<T> leftNode, Node<T> node) { Node<T> rightNode = node; do { rightNode = rightNode.next.getReference(); } while (rightNode != null && isRemoved(rightNode)); return leftNode.next.compareAndSet(node, rightNode, false, false); } boolean isRemoved(Node<T> node) { return node.next.isMarked(); } boolean isEqual(T arg0, T arg1) { if (arg0 == null) { return arg0 == arg1; } else { return arg0.equals(arg1); } } }和之前不同，?Node?類(lèi)中的?next?成員數(shù)據(jù)屬于?AtomicMarkableReference<V>?類(lèi)，不是?Node<T>?，亦不是?AtomicReference<V>?。這是因?yàn)槲覀儾坏枰?next?成員進(jìn)行?CAS?操作，也需要在 next 中加上標(biāo)記。?AtomicMarkableReference<V>?上的標(biāo)記是以一個(gè)?boolean?表示的。我們會(huì)以設(shè)定它為?true?來(lái)代表一個(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<V>?這類(lèi)型，因?yàn)槲覀円残枰M(jìn)行同樣的操作。
addAfter 方法
首先考慮一下?addAfter?方法，?addAfter?方法的設(shè)計(jì)必須顧慮到兩個(gè)線程同時(shí)間插入及同時(shí)間一個(gè)線程插入和一個(gè)線程移除的沖突。在一個(gè)for?循環(huán)中，它遍歷集合去尋找?after?所位于的節(jié)點(diǎn)，并通過(guò)調(diào)用?getReference()?把?after?的下一個(gè)節(jié)點(diǎn)賦值到?nextNode?變量中。然后，建立一個(gè)新的節(jié)點(diǎn)去容納新加入的元素，它通過(guò)?next?數(shù)據(jù)成員和?nextNode?變量進(jìn)行連接。下一步，在?node?變量上調(diào)用?compareAndSet?。不同之處在于它不但比較兩個(gè)引用是否相同去確保?next?數(shù)據(jù)成員沒(méi)有被其他線程改變過(guò)，它亦會(huì)比較?boolean?標(biāo)記位和期望值是否相同。上文提到，?AtomicMarkableReference<V>?類(lèi)擁有一個(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é)后仍未尋找到指定的元素，?addAfter?方法便會(huì)返回?false?以表示由于集合內(nèi)不存在指定的元素，所以元素?zé)o法被加入到集合中。?compareAndSet?返回?true?便代表元素插入成功，方法便會(huì)返回并結(jié)束。
addFirst 方法
addFirst?方法只是簡(jiǎn)單地調(diào)用?addAfter?方法去把一個(gè)新的元素插入到集合的開(kāi)端。
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<V>?中的attemptMark?來(lái)設(shè)定標(biāo)記位。由于?attemptMark?可能會(huì)失敗，所以要將它放進(jìn)一個(gè)?while?循環(huán)中，經(jīng)過(guò)?attemptMark?設(shè)定標(biāo)記的節(jié)點(diǎn)代表該節(jié)點(diǎn)已被邏輯地刪除。在?physicallyRemove?方法中，它首先檢查鄰近的其他節(jié)點(diǎn)是否都已經(jīng)被標(biāo)記為邏輯刪除，若果已被標(biāo)記則順道物理地移除它們。這是通過(guò)?compareAndSet?完成，?compareAndSet?會(huì)檢查節(jié)點(diǎn)是否已被邏輯地刪除，以及上一個(gè)節(jié)點(diǎn)的?next?成員未被其他線程更改。這樣可以確保兩個(gè)線程同時(shí)調(diào)用?remove?方法，或者分別同時(shí)間調(diào)用?remove?方法和?addAfter?方法的時(shí)候，競(jìng)爭(zhēng)條件不會(huì)發(fā)生。
ABA 問(wèn)題
因?yàn)?CAS?操作比較一個(gè)內(nèi)存位置的內(nèi)容及一個(gè)期望值是否相同，但如果一個(gè)內(nèi)存位置的內(nèi)容由 A 變成 B，再由 B 變成 A，?CAS?仍然會(huì)看作兩者相同。不過(guò)，一些算法因?yàn)樾枨蟮年P(guān)系無(wú)法容忍這種行為。當(dāng)一些內(nèi)存位置被重用的時(shí)候，這個(gè)問(wèn)題便可能會(huì)發(fā)生。在沒(méi)有垃圾回收機(jī)制的環(huán)境下，ABA 問(wèn)題需要一些機(jī)制例如標(biāo)記去解決。但由于 JVM 會(huì)為我們處理內(nèi)存管理的問(wèn)題，故此以上的實(shí)現(xiàn)足以避免 ABA 問(wèn)題的出現(xiàn)。
結(jié)束語(yǔ)
以往很多的鎖無(wú)關(guān)數(shù)據(jù)結(jié)構(gòu)都以 Immutable object 的方式去達(dá)致線程安全，這很像 Java 中的?String?，但因?yàn)樯婕斑^(guò)多的復(fù)制操作，令性能低下。但經(jīng)過(guò)十多年，鎖無(wú)關(guān)數(shù)據(jù)結(jié)構(gòu)已發(fā)展得十分成熟，性能并不遜色于傳統(tǒng)的實(shí)現(xiàn)方式。編寫(xiě)鎖無(wú)關(guān)算法是十分困難的，但因?yàn)閿?shù)據(jù)結(jié)構(gòu)是經(jīng)常被重用的部分，首先把這個(gè)概念應(yīng)用到數(shù)據(jù)結(jié)構(gòu)中，可以輕易讓程序進(jìn)入鎖無(wú)關(guān)的世界，體驗(yàn)它所帶來(lái)的好處。
原文：http://www.ibm.com/developerworks/cn/java/j-lo-lockfree/
轉(zhuǎn)載于:https://www.cnblogs.com/davidwang456/p/4065700.html
總結(jié)
以上是生活随笔為你收集整理的Java 下实现锁无关数据结构--转载的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： Understanding Extens
- 下一篇： 通过扩展RandomAccessFile