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.

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.

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.

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
Copy to clipboard
1import java.util.concurrent.atomic.AtomicReference;
2
3public class Node<T> {
4    final T value;
5    final AtomicReference<Node<T>> next;
6
7    Node(T value) {
8        this.value = value;
9        this.next = new AtomicReference<>(null);
10    }
11}

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
Copy to clipboard
1import java.util.concurrent.atomic.AtomicReference;
2
3public class LockFreeQueue<T> {
4    private final AtomicReference<Node<T>> head, tail;
5
6    public LockFreeQueue() {
7        Node<T> dummy = new Node<>(null);
8        head = new AtomicReference<>(dummy);
9        tail = new AtomicReference<>(dummy);
10    }
11}

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.

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
Copy to clipboard
1public void enqueue(T value) {
2    Node<T> newNode = new Node<>(value);
3    while (true) {
4        Node<T> last = tail.get(); // Get the current tail of the queue
5        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
Copy to clipboard
1        if (next == null) {
2            // Try to link the new node to the tail's next position
3            if (last.next.compareAndSet(null, newNode)) {
4                // Successfully linked the new node
5                tail.compareAndSet(last, newNode); // Update tail to point to the new node
6                return;
7            }
8        } else {
9            // If next is not null, the tail is outdated, so update it
10            tail.compareAndSet(last, next);
11        }
12    }
13}

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.

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
Copy to clipboard
1public T dequeue() {
2    while (true) {
3        Node<T> first = head.get(); // Get the current head of the queue
4        Node<T> last = tail.get();   // Get the current tail of the queue
5        Node<T> next = first.next.get(); // Get the next node after the head
6
7        if (first == head.get()) {   // Ensure the head hasn't changed
8            if (first == last) {     // Check if the queue is empty
9                if (next == null) {
10                    return null; // Queue is empty
11                }
12                // Tail is outdated, try to update it
13                tail.compareAndSet(last, next);
14            } else {
15                T value = next.value; // Get the value to dequeue
16                if (head.compareAndSet(first, next)) {
17                    return value; // Successfully dequeued
18                }
19            }
20        }
21    }
22}

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:

Now, let’s see how the queue works in practice by using two threads: one for enqueueing and one for dequeueing.

The producer thread enqueues integers from 0 to 9, simulating production work with a Thread.sleep.

Java
Copy to clipboard
1// Producer thread
2Thread producer = new Thread(() -> {
3    for (int i = 0; i < 10; i++) {
4        queue.enqueue(i);
5        System.out.println("Enqueued: " + i);
6        try {
7            Thread.sleep(50); // Simulate time taken to produce
8        } catch (InterruptedException e) {
9            Thread.currentThread().interrupt();
10        }
11    }
12});

The consumer thread dequeues values, waiting for items to be enqueued if the queue is empty.

Java
Copy to clipboard
1// Consumer thread
2Thread consumer = new Thread(() -> {
3    for (int i = 0; i < 10; i++) {
4        Integer value;
5        while ((value = queue.dequeue()) == null) {
6            Thread.yield(); // Wait for an item to be enqueued
7        }
8        System.out.println("Dequeued: " + value);
9        try {
10            Thread.sleep(70); // Simulate time taken to consume
11        } catch (InterruptedException e) {
12            Thread.currentThread().interrupt();
13        }
14    }
15});

Finally, both threads are started and joined to ensure proper execution.

Java
Copy to clipboard
1producer.start();
2consumer.start();
3
4producer.join();
5consumer.join();

This demonstrates how a lock-free queue can safely handle concurrent operations in a high-performance environment.

Lock-free queues are important because they:

• Improve Performance: By avoiding locks, threads don’t block each other, reducing contention and boosting throughput.
• Enhance Scalability: Lock-free structures allow more threads to operate concurrently, improving system scalability.
• Handle Heavy Loads: They work well under high-load conditions, avoiding the bottlenecks typically caused by locking mechanisms.

Lock-free programming is essential for high-performance applications where efficiency and scalability are critical. Understanding how to build and use lock-free data structures, like queues, equips you to design systems that can handle concurrent access without the overhead of traditional locking mechanisms.

Now that you’ve implemented a lock-free queue, let’s move to the practice section and apply what you've learned!