分析Java非阻塞算法Lock-Free的實現(xiàn)

更新時間：2021年06月01日 13:02:38 作者：flydean

非阻塞算法一般會使用CAS來協(xié)調線程的操作。雖然非阻塞算法有諸多優(yōu)點，但是在實現(xiàn)上要比基于鎖的算法更加繁瑣和負責。本文將會介紹兩個是用非阻塞算法實現(xiàn)的數(shù)據(jù)結構。

非阻塞的棧

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

我們先構建Node數(shù)據(jù)結構：

public class Node<E> {
    public final E item;
    public Node<E> next;

    public Node(E item){
        this.item=item;
    }
}

這個Node保存了內(nèi)存item和它的下一個節(jié)點next。

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

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方法來說，我們需要執(zhí)行兩步操作：1. 在尾部插入新的節(jié)點。2.將尾部指針指向最新的節(jié)點。

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

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

我們看下具體的代碼實現(xiàn)：

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) {
                //有其他的線程已經(jīng)插入了一個節(jié)點，但是還沒有將tail指向最新的節(jié)點
                tail.compareAndSet(currentTail, tailNext);
            }else{
                //沒有其他的線程插入節(jié)點，那么做兩件事情：1. 插入新節(jié)點，2.將tail指向最新的節(jié)點
                if(currentTail.next.compareAndSet(null, newNode)){
                    tail.compareAndSet(currentTail, newNode);
                }
            }
        }
    }
    }
}

以上就是分析Java非阻塞算法Lock-Free的實現(xiàn)的詳細內(nèi)容，更多關于Java非阻塞算法Lock-Free的實現(xiàn)的資料請關注腳本之家其它相關文章！

您可能感興趣的文章: