Creating a Lock-Free Queue Using Atomic Variables

Lock-Free Queue Using Atomic Variables

Welcome back! In this lesson, we’ll reinforce your understanding of lock-free programming by building a practical example: a lock-free queue . This example highlights how to use atomic variables and operations to create high-performance, thread-safe systems without relying on traditional locks.

What You’ll Learn

By the end of this lesson, you will: Implement a lock-free queue using atomic variables. Reinforce your knowledge of atomic operations and compare-and-swap (CAS). Appreciate the benefits of lock-free structures, such as improved concurrency and reduced contention. This lesson will put your lock-free programming skills into practice with a concrete example.

Lock-Free Programming Recap

We’ve previously covered atomic variables and CAS (compare-and-swap) operations, which are key to lock-free programming. Using atomic variables, we can avoid the blocking and delays caused by locks, allowing threads to work independently without the risk of race conditions. Lock-free programming provides performance benefits in scenarios with high concurrency, as it reduces overhead caused by threads competing for locks. In this lesson, we’ll explore how these concepts apply to implementing a lock-free queue .

Building a Lock-Free Queue: Key Components

To build our lock-free queue, we’ll first implement a Node class, which represents each element in the queue. This class uses AtomicReference to point to the next node in the queue. Java import java.util.concurrent.atomic.AtomicReference; public class Node<T> {final T value; final AtomicReference<Node<T>> next; Node(T value) {this.value = value; this.next = new AtomicReference<>(null);}} In the Node class: value stores the actual data for each node. next is an AtomicReference to the next node in the queue. By using an atomic reference, we ensure thread safety when updating this pointer, allowing multiple threads to enqueue or dequeue elements concurrently without corrupting the queue structure. Next, we’ll define the queue itself. We need a head and tail pointer to track the front and back of the queue. Both will be initialized to point to a dummy node, which simplifies the management of edge cases (like an empty queue). Java import java.util.concurrent.atomic.AtomicReference; public class LockFreeQueue<T> {private final AtomicReference<Node<T>> head, tail; public LockFreeQueue() {Node<T> dummy = new Node<>(null); head = new AtomicReference<>(dummy); tail = new AtomicReference<>(dummy);}} Here: head : points to the front of the queue. tail : points to the back of the queue. Both pointers are initialized to a dummy node to simplify enqueueing and dequeuing operations.

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Enqueue Operation

To add an element to the queue, we’ll create a new Node and append it to the end of the queue using atomic operations. Let’s break down the enqueue operation step by step:

Java

public void enqueue(T value) {
    Node<T> newNode = new Node<>(value);
    while (true) {
        Node<T> last = tail.get(); // Get the current tail of the queue
        Node<T> next = last.next.get(); // Get the next node after the tail

public void enqueue(T value) {
    Node<T> newNode = new Node<>(value);
    while (true) {
        Node<T> last = tail.get(); // Get the current tail of the queue
        Node<T> next = last.next.get(); // Get the next node after the tail

last: the current tail node.
next: the node after the tail. This will be null if the tail is the actual end of the queue.

If next is null, it means the tail is in the correct place, and we can try to append our new node.

Java

        if (next == null) {
            // Try to link the new node to the tail's next position
            if (last.next.compareAndSet(null, newNode)) {
                // Successfully linked the new node
                tail.compareAndSet(last, newNode); // Update tail to point to the new node
                return;
            }
        } else {
            // If next is not null, the tail is outdated, so update it
            tail.compareAndSet(last, next);
        }
    }
}

        if (next == null) {
            // Try to link the new node to the tail's next position
            if (last.next.compareAndSet(null, newNode)) {
                // Successfully linked the new node
                tail.compareAndSet(last, newNode); // Update tail to point to the new node
                return;
            }
        } else {
            // If next is not null, the tail is outdated, so update it
            tail.compareAndSet(last, next);
        }
    }
}

This loop ensures that the tail is updated correctly and that the new node is added safely:

If next == null, we attempt to link the new node to the end of the queue using compareAndSet. If successful, we update the tail to point to the new node.
If next != null, it means another thread already added a node to the queue, so we update the tail and try again.

Dequeue Operation

Removing an element from the queue involves updating the head pointer to skip over the node being dequeued. This also uses atomic operations to maintain thread safety.

Java

public T dequeue() {
    while (true) {
        Node<T> first = head.get(); // Get the current head of the queue
        Node<T> last = tail.get();   // Get the current tail of the queue
        Node<T> next = first.next.get(); // Get the next node after the head

        if (first == head.get()) {   // Ensure the head hasn't changed
            if (first == last) {     // Check if the queue is empty
                if (next == null) {
                    return null; // Queue is empty
                }
                // Tail is outdated, try to update it
                tail.compareAndSet(last, next);
            } else {
                T value = next.value; // Get the value to dequeue
                if (head.compareAndSet(first, next)) {
                    return value; // Successfully dequeued
                }
            }
        }
    }
}

public T dequeue() {
    while (true) {
        Node<T> first = head.get(); // Get the current head of the queue
        Node<T> last = tail.get();   // Get the current tail of the queue
        Node<T> next = first.next.get(); // Get the next node after the head

        if (first == head.get()) {   // Ensure the head hasn't changed
            if (first == last) {     // Check if the queue is empty
                if (next == null) {
                    return null; // Queue is empty
                }
                // Tail is outdated, try to update it
                tail.compareAndSet(last, next);
            } else {
                T value = next.value; // Get the value to dequeue
                if (head.compareAndSet(first, next)) {
                    return value; // Successfully dequeued
                }
            }
        }
    }
}

In the dequeue method:

We retrieve the first (head), last (tail), and next node pointers.
If first == last and next == null, it means the queue is empty.
If first != last, we retrieve the next node’s value, update the head pointer using compareAndSet, and return the value.

Here’s the updated Practical Implementation: Testing the Queue section, with each method as its own snippet:

Lock-Free Queue Using Atomic Variables

What You’ll Learn

Lock-Free Programming Recap

Building a Lock-Free Queue: Key Components

Join the 1M+ learners on CodeSignal

Enqueue Operation

Dequeue Operation

Practical Implementation: Testing the Queue

Consumer Thread

Starting Threads and Joining

Why Lock-Free Queues Matter