Introduction to Lock-Free Stack

Welcome back to your journey through lock-free programming in C++. Building on the knowledge from our last lesson on memory ordering and atomic operations, we'll now dive into a practical implementation of a lock-free stack. This lesson is a crucial next step in understanding how to create efficient, thread-safe data structures without using traditional locks. By the end of this unit, you'll have a firmer grasp on how to manage concurrency with atomic operations.

In this lesson, you'll learn how to implement a lock-free stack using atomic operation, but before we move on, let's understand why we need lock-free data structures in the first place.

In the previous course we have learned about lock-based data structures, where we use locks to protect shared resources from concurrent access. This approach ensures that only one thread can access the resource at a time, and a logical question arises: why do we need lock-free data structures? The answer lies in the limitations of lock-based approaches. Locks can introduce performance bottlenecks, especially in highly concurrent applications, where contention for locks can lead to thread contention and reduced scalability. Lock-free data structures, on the other hand, allow multiple threads to access shared resources concurrently without blocking each other. This approach can improve performance and scalability in multithreaded applications.

Here are some real-world scenarios where lock-free data structures can be beneficial over lock-based ones:

• High-performance applications requiring low latency and high throughput such as financial trading systems, gaming engines, and real-time analytics platforms.
• Applications with a large number of threads contending for shared resources, where lock contention can lead to performance degradation.
• Applications requiring high scalability to utilize the full potential of modern multicore processors.

Here's a simple example to illustrate the lock-free stack concept:

#include <atomic>
#include <iostream>
#include <memory>
#include <thread>
#include <chrono>

template<typename T>
class LockFreeStack {
private:
    struct Node {
        T data;
        Node* next;
        Node(const T& value) : data(value), next(nullptr) {}
    };

    std::atomic<Node*> head;

public:
    LockFreeStack() : head(nullptr) {}

    void push(const T& value) {
        Node* new_node = new Node(value);
        new_node->next = head.load();

        // Print statement for push operation
        std::cout << "Pushing: " << value << "\n";

        while (!head.compare_exchange_weak(new_node->next, new_node));
    }

    bool pop(T& result) {
        Node* old_head = head.load();

        while (old_head != nullptr &&
               !head.compare_exchange_weak(old_head, old_head->next));

        if (old_head == nullptr) {
            // Print if pop fails
            std::cout << "Pop failed - stack is empty.\n";
            return false;
        }

        // Print statement for pop attempt
        std::cout << "Attempting to pop...\n";
        result = old_head->data;
        delete old_head;

        // Print the popped value
        std::cout << "Popped: " << result << "\n";
        return true;
    }
};

In this example, we've implemented a simple lock-free stack using atomic operations with the following components:

• We define a Node structure to represent each element in the stack. Each node contains a data value and a pointer to the next node. The constructor initializes the node with the given data value and sets the next pointer to nullptr.
• The LockFreeStack class contains a single member variable head of type std::atomic<Node*>. This pointer points to the top of the stack.
• The push method adds a new element to the stack. It creates a new node with the given value, sets its next pointer to the current head of the stack, and then atomically updates the head pointer to point to the new node. The compare_exchange_weak method is used to perform the atomic update.
• The pop method removes the top element from the stack. It loads the current head, then repeatedly attempts to swing head to old_head->next using compare_exchange_weak. If the stack is empty (old_head == nullptr), it returns false. Otherwise, it reads the node’s data, deletes the removed node, and returns true.

Next, let's use the lock-free stack in a multithreaded environment to see how it performs under concurrent access.

void pushItems(LockFreeStack<int>& stack, int start, int end) {
    for (int i = start; i < end; ++i) {
        stack.push(i);
        std::this_thread::sleep_for(std::chrono::milliseconds(50)); // Add delay
    }
}

void popItems(LockFreeStack<int>& stack, int count) {
    int value;
    for (int i = 0; i < count; ++i) {
        stack.pop(value);
        std::this_thread::sleep_for(std::chrono::milliseconds(30)); // Add delay
    }
}

int main() {
    LockFreeStack<int> stack;

    // Create multiple threads for push and pop operations
    std::thread t1(pushItems, std::ref(stack), 1, 10);
    std::thread t2(popItems, std::ref(stack), 7);
    std::thread t3(pushItems, std::ref(stack), 10, 20);
    std::thread t4(popItems, std::ref(stack), 7);

    t1.join();
    t2.join();
    t3.join();
    t4.join();

    return 0;
}

Here we have a simple main function that creates multiple threads to perform push and pop operations on the lock-free stack concurrently. The pushItems function pushes a range of integers onto the stack with a delay of 50 milliseconds between each push operation. The popItems function pops a specified number of items from the stack with a delay of 30 milliseconds between each pop operation.

When you run this code, you'll see the push and pop operations interleaved across multiple threads, demonstrating the lock-free stack's ability to handle concurrent access without blocking. You can experiment with different thread counts, delays, and stack sizes to observe how the lock-free stack behaves under various conditions. Note, that the output may vary depending on the timing of thread execution, and the printed messages might be interleaved, since we are not using any synchronization mechanisms to order the output.