Implementation of non blocking algorithm (lock free)

Implementation of non blocking algorithm (lock free)

In the last article, we talked about the disadvantages of using locks. This article will explain how to use non blocking algorithms. Non blocking algorithms generally use CAS to coordinate the operation of threads.

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

This paper will introduce two data structures implemented by non blocking algorithm.

Non blocking stack

We first use CAS to build several non blocking stacks. Stack is the simplest chain structure. Its essence is a linked list, and the root node of the linked list is the top of the stack.

Let's build the node data structure first:

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

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

This node stores the memory item and its next node next.

Then we build a non blocking stack. In this stack, we need to implement the pop and push methods. We use a Atomic class to save the reference of the top node, and invoke the compareAndSet command before pop and push to ensure the atomicity of the command. At the same time, 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(){
        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;
    }

}

Non blocking linked list

Building a linked list is more complex than building a stack. Because we have to maintain two pointers at the beginning and end. For the put method, we need to perform two steps: 1 Insert a new node at the tail. 2. Point the tail pointer to the latest node.

When we use CAS, we can only guarantee that one step is atomic execution. So what about the combination steps of 1 and 2?

Let's consider it carefully. In fact, 1 and 2 do not have to be executed in the same thread. Other threads completely help complete this operation when they detect that a thread has inserted a node, but do not point the tail to the last node.

Let's look at the specific 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=new AtomicReference<>(next);
    }
}

First build 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) {
                //有其他的线程已经插入了一个节点，但是还没有将tail指向最新的节点
                tail.compareAndSet(currentTail,tailNext);
            }else{
                //没有其他的线程插入节点，那么做两件事情：1. 插入新节点，2.将tail指向最新的节点
                if(currentTail.next.compareAndSet(null,newNode)){
                    tail.compareAndSet(currentTail,newNode);
                }
            }
        }
    }
    }
}

Examples of this article can be referred to https://github.com/ddean2009/learn-java-concurrency/tree/master/nonblock

For more information, please visit http://www.flydean.com/java-lock-free/