Introduction to Lock-free Queue | CodeSignal Learn

Introduction to Lock-free Queue | CodeSignal Learn

Introduction to Lock-free Queue

Welcome back to our journey through lock-free programming in C++ . In the last lesson, you learned about implementing a lock-free stack. Now, we're progressing to another essential data structure: the queue. This lesson will focus on implementing a thread-safe lock-free queue, building upon the foundation of atomic operations explored in the previous lessons. By the end of this unit, you'll be equipped with the skills to implement a robust, efficient queue that operates without traditional locking mechanisms.

What You'll Learn

In this lesson, you'll learn how to build a lock-free queue using atomic operations to handle concurrency efficiently. The following code example is a sneak peek into what you'll be creating: C++#include <atomic> #include <iostream> #include <thread> #include <memory> #include <chrono> template<typename T> class LockFreeQueue { private: struct Node { T data; std::atomic<Node*> next; Node(const T& value) : data(value), next(nullptr) {} }; std::atomic<Node*> head; std::atomic<Node*> tail; public: LockFreeQueue() { Node* dummy = new Node(T{}); // Dummy node to simplify push/pop logic head.store(dummy); tail.store(dummy); } ~LockFreeQueue() { while (Node* old_head = head.load()) { // Cleanup all nodes head.store(old_head->next); delete old_head; } } void push(const T& value) { Node* new_node = new Node(value); Node* old_tail; while (true) { old_tail = tail.load(); Node* tail_next = old_tail->next; if (old_tail == tail.load()) { // Check if tail hasn't changed if (tail_next == nullptr) { // Tail is truly the last node if (old_tail->next.compare_exchange_weak(tail_next, new_node)) { break; // Successfully added the new node } } else { // Tail is lagging; advance it tail.compare_exchange_weak(old_tail, tail_next); } } } // Move tail to the new node tail.compare_exchange_weak(old_tail, new_node); std::cout << "Pushed: " << value << "\n"; } bool pop(T& result) { Node* old_head; while (true) { old_head = head.load(); Node* old_tail = tail.load(); Node* head_next = old_head->next; if (old_head == head.load()) { // Consistency check if (old_head == old_tail) { // Queue might be empty if (head_next == nullptr) { // Queue is empty std::cout << "Pop failed - queue is empty.\n"; return false; } tail.compare_exchange_weak(old_tail, head_next); // Advance tail } else { // Queue is not empty if (head.compare_exchange_weak(old_head, head_next)) { result = head_next->data; delete old_head; // Free the old dummy head node std::cout << "Popped: " << result << "\n"; return true; } } } } } }; Let's break down the implementation step by step: Node Structure: The queue is implemented using a linked list of nodes, where each node contains the data and an atomic pointer to the next node. The constructor initializes the node with the provided data and a null pointer for the next node. Head and Tail Pointers: The queue maintains two atomic pointers, head and tail, representing the front and back of the queue, respectively. Both pointers are initially set to a dummy node to simplify the logic. Push Operation: The push method adds a new node to the queue. It first creates a new node with the provided value and then attempts to add it to the queue. The method uses a loop to handle concurrent updates to the tail pointer and ensures that the new node is correctly linked to the queue. Pop Operation: The pop method removes and returns the front node from the queue. It also uses a loop to handle concurrent updates to the head and tail pointers. The method checks for empty and non-empty queue conditions and updates the pointers accordingly. Cleanup: The destructor cleans up the queue by deleting all nodes, starting from the head. Let's now see how to use this lock-free queue in a multithreaded environment: C++void pushItems(LockFreeQueue<int>& queue, int start, int end) { for (int i = start; i < end; ++i) { queue.push(i); std::this_thread::sleep_for(std::chrono::milliseconds(50)); // Delay for interleaving } } void popItems(LockFreeQueue<int>& queue, int count) { int value; for (int i = 0; i < count; ++i) { queue.pop(value); std::this_thread::sleep_for(std::chrono::milliseconds(30)); // Delay for interleaving } } int main() { LockFreeQueue<int> queue; // Create threads to push and pop concurrently std::thread t1(pushItems, std::ref(queue), 1, 6); std::thread t2(popItems, std::ref(queue), 3); std::thread t3(pushItems, std::ref(queue), 6, 11); std::thread t4(popItems, std::ref(queue), 5); t1.join(); t2.join(); t3.join(); t4.join(); return 0; } In this example, we create a lock-free queue of integers and spawn multiple threads to push and pop items concurrently. The pushItems and popItems functions simulate the enqueue and dequeue operations, respectively, with a delay to introduce interleaving. The main function creates threads to perform these operations and waits for them to complete before exiting. Note, that the output may vary due to the interleaving of operations and the printed messages may be mixed up, since we don't use any synchronization for the output.

Sign up

Join the 1M+ learners on CodeSignal

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