Implementation of lock-free algorithm

In the last article we looked at the disadvantages of using locks, and this article will show you how to use non-blocking algorithms. Non-blocking algorithms typically use CAS to coordinate thread operations.

Although the non-blocking algorithm has many advantages, its implementation is more complicated and responsible than the lock-based algorithm.

This article introduces two data structures implemented using non-blocking algorithms.

A non-blocking stack

Let’s start by building several non-blocking stacks using CAS. The stack is the simplest chain structure, which is essentially a linked list, and the root node of the list is the top of the stack.

Let’s start by building the Node data structure:

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

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

This Node holds the memory item and its next Node, Next.

We then build a non-blocking stack where we need to implement the POP and push methods, use an Atomic class to hold a reference to the top node, and call compareAndSet before pop and push to keep the command atomicity. Also, we need constant loops to ensure that updates can be retried in case of thread conflicts.

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(a){
        Node<E> oldNode;
        Node<E> newNode;
        do {
            oldNode = top.get();
            if(oldNode == null) {return null;
            }
            newNode=oldNode.next;
        }while(! top.compareAndSet(oldNode, newNode));returnoldNode.item; }}Copy the code

A non-blocking linked list

Building linked lists is more complex than building stacks. Because we want to keep the head and tail Pointers. In the case of the PUT method, we need to perform two steps: 1. Insert a new node at the end. 2. Point the tail pointer to the latest node.

The best we can do with CAS is ensure that one of the steps is atomic. So what do we do with the combination of steps 1 and 2?

If we think about it a little more carefully, we don’t have to execute 1 and 2 in the same thread. The other threads do exactly that when they detect that a thread has inserted a node without pointing tail at the last node.

Let’s look at the code implementation:

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=newAtomicReference<>(next); }}Copy the code

Start by building a LinkedNode class.

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) {
                // Another thread has inserted a node, but has not yet pointed tail to the latest node
                tail.compareAndSet(currentTail, tailNext);
            }else{
                // If no other thread inserts a node, do two things: 1. Insert a new node, 2. Point tail to the latest node
                if(currentTail.next.compareAndSet(null, newNode)){
                    tail.compareAndSet(currentTail, newNode);
                }
            }
        }
    }
    }
}
Copy the code

Examples of this article can be found at github.com/ddean2009/l…

More can be found at www.flydean.com/java-lock-f…