ℹ️ Select 'Choose Exercise', or randomize 'Next Random Exercise' in selected language.

Choose Exercise:
Timer 00:00
WPM --
Score --
Acc --
Correct chars --

Simple Concurrent Lock-Free Queue Push

C++

Goal -- WPM

Ready
Exercise Algorithm Area
1struct Node {

2int data;

3Node* next;

4};

5

6class LockFreeQueue {

7private:

8Node* head;

9Node* tail;

10

11public:

12LockFreeQueue() {

13Node* dummy = new Node{0, nullptr};

14head = dummy;

15tail = dummy;

16}

17

18~LockFreeQueue() {

19while (head != nullptr) {

20Node* temp = head;

21head = head->next;

22delete temp;

23}

24}

25

26void push(int value) {

27Node* newNode = new Node{value, nullptr};

28Node* currentTail = tail;

29

30// Ensure tail->next is null before attempting to link

31if (currentTail->next == nullptr) {

32// Atomically update tail->next and then tail

33// This is a simplified ABA-safe approach for demonstration

34// A real implementation would use compare-and-swap on tail

35currentTail->next = newNode;

36tail = newNode;

37} else {

38// If tail->next is not null, another thread might be updating tail.

39// Re-evaluate tail and try again.

40// In a real scenario, this would involve CAS loop.

41push(value); // Retry

42}

43}

44

45// Other methods like pop would go here

46};
Algorithm description viewbox

Simple Concurrent Lock-Free Queue Push

Algorithm description:

This code implements the `push` operation for a basic lock-free queue. It allows multiple threads to add elements to the queue concurrently without using traditional locks. This is crucial for high-performance multithreaded applications where contention on locks can be a bottleneck.

Algorithm explanation:

The `push` operation aims to add a new node to the end of the queue. It first creates a new node and then attempts to link it to the current tail. The core challenge in lock-free programming is managing concurrent updates to shared data structures like `tail`. This simplified implementation uses a basic retry mechanism if the `tail->next` is not null, indicating a potential race condition. A robust lock-free queue would typically employ atomic compare-and-swap (CAS) operations to ensure thread-safe updates to `tail` and prevent ABA problems. The time complexity for `push` in a well-implemented lock-free queue is typically amortized O(1), and the space complexity is O(N) where N is the number of elements in the queue.

Pseudocode:

function push(value):
  create newNode with value and next = null
  get currentTail = tail
  if currentTail.next is null:
    set currentTail.next = newNode
    set tail = newNode
  else:
    // Potential race, retry
    push(value)