Lock Free Stack Implementation in C#

This method compares destination to currentValue, and if they're equal sets destination to newValue and returns currentValue unchanged.

If they aren't equal it just returns the value of destination.

This is done in an atomic fashion i.e. no other thread can interrupt it.  In carrys out this in atomic fashion becasue its executed at hardware level with a single nstruction CMPXCH instruction.

public class LockFreeStack<T> {
    private volatile StackNode<T> m_head;

private static bool CAS(ref Node<T> destination, Node<T> currentValue, Node<T> newValue)
         currentValue== Interlocked.CompareExchange<Node<T>>(ref destination, newValue, currentValue);

    public void Push(T item) {
        StackNode<T> node = new StackNode<T>(item);
        StackNode<T> head;
        do {
            head = m_head;
            node.m_next = head;
        } while (m_head != head || CAS(ref m_head, node, head) != head);

    public T Pop() {
        StackNode<T> head;
        SpinWait s = new SpinWait();

        while (true) {
            StackNode<T> next;
            do {
                head = m_head;
                if (head == null) goto emptySpin;
                next = head.m_next;
            } while (m_head != head || CAS(ref m_head, next, head) != head);


        return head.m_value;

class StackNode<T> {
    internal T m_value;
    internal StackNode<T> m_next;
    internal StackNode(T val) { m_value = val; }


Popular posts from this blog

ActiveMQ, easy to use open source message oriented middleware (MOM)

Basic Send Message to MQ with Java and IBM MQ JMS

Automated Service Monitoring with F5, Consul and Python F5 SDK