我們先使用CAS來構建幾個非阻塞的棧。棧是最簡單的鏈式結構，其本質是一個鏈表，而鏈表的根節點就是棧頂。

我們先構建Node數據結構：

public class Node<E> { public final E item; public Node<E> next; public Node(E item){this.item=item; }}

這個Node保存了內存item和它的下一個節點next。

然后我們構建非阻塞的棧，在該棧中我們需要實現pop和push方法，我們使用一個Atomic類來保存top節點的引用，在pop和push之前調用compareAndSet命令來保證命令的原子性。同時，我們需要不斷的循環，以保證在線程沖突的時候能夠重試更新。

public class ConcurrentStack<E> { AtomicReference<Node<E>> top= new AtomicReference<>(); public void push(E item){Node<E> newNode= new Node<>(item);Node<E> oldNode;do{ oldNode=top.get(); newNode.next= oldNode;}while(!top.compareAndSet(oldNode, newNode)); } public E pop(){Node<E> oldNode;Node<E> newNode;do { oldNode = top.get(); if(oldNode == null){return null; } newNode=oldNode.next;}while(!top.compareAndSet(oldNode, newNode));return oldNode.item; }}非阻塞的鏈表

構建鏈表要比構建棧復雜。因為我們要維持頭尾兩個指針。以put方法來說，我們需要執行兩步操作：1. 在尾部插入新的節點。2.將尾部指針指向最新的節點。

我們使用CAS最多只能保證其中的一步是原子執行。那么對于1和2的組合步驟該怎么處理呢？

我們再仔細考慮考慮，其實1和2并不一定要在同一個線程中執行，其他線程在檢測到有線程插入了節點，但是沒有將tail指向最后的節點時，完全幫忙完成這個操作。

我們看下具體的代碼實現：

public class LinkedNode<E> { public final E item; public final AtomicReference<LinkedNode<E>> next; public LinkedNode(E item, LinkedNode<E> next){this.item=item;this.next=new AtomicReference<>(next); }}

先構建一個LinkedNode類。

public class LinkedQueue<E> { private final LinkedNode<E> nullNode= new LinkedNode<>(null, null); private final AtomicReference<LinkedNode<E>> head= new AtomicReference<>(nullNode); private final AtomicReference<LinkedNode<E>> tail= new AtomicReference<>(nullNode); public boolean put(E item){ LinkedNode<E> newNode = new LinkedNode<>(item, null); while (true){LinkedNode<E> currentTail= tail.get();LinkedNode<E> tailNext= currentTail.next.get();if(currentTail == tail.get()){ if (tailNext != null) {//有其他的線程已經插入了一個節點，但是還沒有將tail指向最新的節點tail.compareAndSet(currentTail, tailNext); }else{//沒有其他的線程插入節點，那么做兩件事情：1. 插入新節點，2.將tail指向最新的節點if(currentTail.next.compareAndSet(null, newNode)){ tail.compareAndSet(currentTail, newNode);} }} } }}

以上就是分析Java非阻塞算法Lock-Free的實現的詳細內容，更多關于Java非阻塞算法Lock-Free的實現的資料請關注好吧啦網其它相關文章！