Generate a lock free stack in c#

In .net 4.0 the concurrent datastructures were introduced (System.Collections.Concurrent). This datastructures uses a lockfree algorithm to implement the access control. In this post i will write about implementing a lock free stack. To do so i will first develop an concurrent stack that works with locking, and then i will show what we need to change to make the stack lock free. For the beginning i will show how we can use the ConcurrentStack that is implemented in the System.Collection.Concurrent namespace.

  System.Collections.Concurrent.ConcurrentStack<int> concurrentStack = new
System.Collections.Concurrent.ConcurrentStack<int>();

concurrentStack.Push(1);
concurrentStack.Push(2);

int result = 0;

concurrentStack.TryPop(out result);

Now i will implement this stack with a lock.

public class ConcurrentStack
{
    private class Node
    {
        public Node Next;
        public V Item;
    }

    private Node head;

    public ConcurrentStack()
    {
        head = new Node();
    }

    public void Push(T item)
    {
        Node node = new Node();
        node.Item = item;
        lock (head)
        {
            node.Next = head.Next;
            head.Next = node;
        }
    }

    public bool TryPop(out T result)
    {
        Node node = head.Next;
        if (node == null)
        {
            result = default(T);
            return false;
        }
        lock (head)
        {
            head.Next = node.Next;
            result = node.Item;
            return true;
        }
    }

    public bool TryPeek(out T result)
    {
        Node node = head.Next;
        if (node == null)
        {
            result = default(T);
            return false;
        }
        lock (head)
        {
            node = head.Next;
            result = node.Item;
            while (node.Next != null)
            {
                node = node.Next;
                result = node.Item;
            }
            return true;
        }
    }
}

So if you use this stack from multible threads then the locks in Push and TryPop become the bottle neck. So Microsoft introduced a so called lock free stack implementation. To implement such a lock free stack we need to know which commands produce the problems when accessed from different threads. This commands are:

lock (head)
{
    node.Next = head.Next;
    head.Next = node;
}

in the Push method and

lock (head)
{
    head.Next = node.Next;
    result = node.Item;
    return true;
}

in the TryParse method. So if we have an context switch between this two commandos then that would break the stack because node.Next points to one head element and the next element of another head element points to this node. So the lock prevents this context switch and so the stack is not broken. If we want to implement this without a lock we have to remove the lock and replace it with something else. To implement this i will use the compare and swap algorithm
So here is my implementation of the lock free stack:

public class ConcurrentStack
{
    private class Node
    {
        public Node Next;
        public V Item;
    }

    private Node head;

    public ConcurrentStack()
    {
        head = new Node();
    }

    public void Push(T item)
    {
        Node node = new Node();
        node.Item = item;
        do
        {
            node.Next = head.Next;
        } while (!CompareAndSwap(ref head.Next, node.Next, node));
    }        

    public bool TryPop(out T result)
    {
        Node node;
        do
        {
            node = head.Next;
            if (node == null)
            {
                result = default(T);
                return false;
            }
        } while (!CompareAndSwap(ref head.Next, node, node.Next));
        result = node.Item;
        return true;
    }

    // if headNext is nodeNext 
    // (that was assigned now, that means that no other thread has inserted or removed something,
    // if some thead had assigned something then head.next would not have the same value as node.next) 
    // then node.next is assigned to head.next
    private static bool CompareAndSwapUnsafe(ref Node destination,
      Node currentValue, Node newValue)
    {
        // has to be atomar (that means that there must not be a thread context switch)
        if (destination == currentValue)
        {
            destination = newValue;
            return true;
        }
        return false;
    }

    // here the compare and swap method is implemented thread safe with the Interlocked.CompareExchange method
    // CompareExchange compares one value with another value and if they are the // same a new value is asigned to the // first value. This is an atomic operation // that means that there is no context switch possible.
    private static bool  CompareAndSwap(ref Node destination, Node
      currentValue, Node newValue)
    {
        if (currentValue == Interlocked.CompareExchange<Node>
        (ref destination, newValue, currentValue))
            return true;
        else
            return false;
    }
}

Here we can see that the CompareAndSwap function replaces the lock and if the stack is used from many threads than this implementation is faster than the implementation with the lock because no context switch is necessary. In the CompareAndSwapUnsafe function the principle is shown. The problem is that the compare between the destination and the currentValue and the allocation between destination and newValue has to be atomar. This two steps are atomar executed by the Interlocked.CompareExchange method. So this method guaranteed that the two commandos are executed without a thread context switch. So if you want to implement an other datastructure (e.g. a queue or a list) you can use the simmular method.

Advertisements