{"title":"Lock-Free Data Structures","description":"","content":"Lock-free data structures are built for one goal: **high concurrency without locking**. Instead of using `synchronized` blocks or mutexes to protect shared state, they rely on atomic CPU instructions (like compare-and-swap) to coordinate updates safely.\n\nIn this chapter, we apply the CAS and atomic operations from the previous chapters to build real data structures: a lock-free stack (Treiber stack) and the famous Michael-Scott queue that powers Java's ConcurrentLinkedQueue.\n\n---\n\n## What are Lock-Free Data Structures?\n\nThink of a checkout line at a grocery store. With a single checkout counter (mutex), if the cashier takes a break, everyone waits. With self-checkout stations (lock-free), even if one station malfunctions, other customers continue checking out. The system makes progress regardless of individual delays.\n\nA lock-free data structure guarantees that if multiple threads are operating on it, at least one thread will complete its operation in a finite number of steps, regardless of the state of other threads. This is a progress guarantee about the system as a whole, not about individual operations.\n\n\n```mermaid\nflowchart LR\n subgraph \"Lock-Based\"\n A[Thread 1
holds lock]:::red\n B[Thread 2
waiting]:::orange\n C[Thread 3
waiting]:::orange\n D[Thread 4
waiting]:::orange\n A --> B --> C --> D\n end\n\n subgraph \"Lock-Free\"\n E[Thread 1
retry]:::yellow\n F[Thread 2
succeeds]:::green\n G[Thread 3
retry]:::yellow\n H[Thread 4
succeeds]:::green\n end\n\n classDef red fill:#ff8787,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef yellow fill:#ffd43b,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\nThe diagram contrasts the two approaches. In lock-based structures, one thread's delay cascades to all others. In lock-free structures, threads that fail their CAS operation retry while others succeed. Even if Thread 1 gets stuck in a retry loop, Thread 2 and Thread 4 complete their operations, so the system progresses.\n\nThe formal definition:\n\n- **Lock-Free:** At least one thread completes its operation in a bounded number of its own steps\n- **Blocking (Lock-Based):** A thread can be delayed indefinitely while waiting for another thread\n\nKey distinction: \"bounded number of its own steps\" means the progress guarantee does not depend on other threads. A thread might retry many times because others are competing, but the retries are its own work, not passive waiting.\n\n---\n\n## Why Lock-Free Matters\n\n### System-Wide Progress\n\nThe primary benefit is fault isolation. If one thread crashes, hangs, or gets suspended:\n\n\n| Scenario | Lock-Based | Lock-Free |\n|----------|-----------|-----------|\n| Thread crash while holding lock | Deadlock (all threads blocked) | Other threads continue |\n| Long GC pause | All waiters delayed | Affected thread retries after pause |\n| Thread preempted indefinitely | Lock held indefinitely | No impact on others |\n\n\nThis matters enormously for long-running services where uptime is critical.\n\n### Latency Characteristics\n\nLock-free structures trade average performance for better worst-case latency:\n\n\n| Metric | Lock-Based | Lock-Free |\n|--------|-----------|-----------|\n| Average operation | Often faster | Often comparable or slightly slower |\n| 99th percentile | Unpredictable spikes | More predictable |\n| 99.99th percentile | Can be very high | Bounded |\n\n\nIn systems where tail latency matters (trading, gaming, real-time communication), lock-free structures shine.\n\n### Real-World Usage\n\nLock-free data structures are not academic curiosities:\n\n- **Java ConcurrentLinkedQueue:** Based on Michael-Scott queue\n- **Java ConcurrentHashMap:** Lock-free read operations\n- **Linux kernel:** Lock-free work queues, RCU (Read-Copy-Update)\n- **Game engines:** Lock-free command buffers between threads\n- **Database engines:** Lock-free buffer pool management\n\n:::info Interview Insight Lock-free data structures are a favorite interview topic for senior roles. Expect questions like: \"Implement a lock-free stack,\" \"Explain the Michael-Scott queue algorithm,\" or \"What's the difference between lock-free and wait-free?\" Understanding the concepts, not just memorizing implementations, is key. :::\n\n---\n\n## Lock-Free Counter\n\nBefore tackling complex data structures, let us start with the simplest lock-free data structure: a counter.\n\n\n```mermaid\nflowchart TD\n START[increment]:::primary --> READ[Read current value]:::secondary\n READ --> CALC[new = current + 1]:::orange\n CALC --> CAS{CAS current → new}\n CAS -->|Success| DONE[Return new value]:::green\n CAS -->|Failure| READ\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef secondary fill:#38d9a9,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\nThe CAS loop pattern from the previous chapters is the foundation. Read the current value, compute the new value, attempt to swap. If another thread modified the counter, retry with the new current value.\n\nimport Tabs from '@theme/Tabs'; import TabItem from '@theme/TabItem';\n\n \n\n\n```java\nimport java.util.concurrent.atomic.AtomicInteger;\n\npublic class LockFreeCounter {\n private final AtomicInteger value = new AtomicInteger(0);\n\n public int increment() {\n while (true) {\n int current = value.get();\n int next = current + 1;\n if (value.compareAndSet(current, next)) {\n return next;\n }\n // CAS failed - another thread incremented\n // Loop continues with fresh read\n }\n }\n\n public int decrement() {\n while (true) {\n int current = value.get();\n int next = current - 1;\n if (value.compareAndSet(current, next)) {\n return next;\n }\n }\n }\n\n public int get() {\n return value.get();\n }\n}\n```\n\n\nThis is lock-free because even if one thread loops forever, other threads can still complete their increments. The `AtomicInteger.incrementAndGet()` method does exactly this internally.\n\n \n\n\n```python\n# Conceptual implementation - Python lacks native CAS\n# In practice, use locks or multiprocessing\n\nimport threading\n\nclass LockFreeCounter:\n \"\"\"\n Simulated lock-free counter using optimistic concurrency.\n True lock-free requires native CAS support.\n \"\"\"\n def __init__(self):\n self._value = 0\n self._lock = threading.Lock() # Used only for CAS simulation\n\n def _compare_and_set(self, expected, new_value):\n \"\"\"Simulated CAS operation.\"\"\"\n with self._lock:\n if self._value == expected:\n self._value = new_value\n return True\n return False\n\n def increment(self):\n while True:\n current = self._value\n next_val = current + 1\n if self._compare_and_set(current, next_val):\n return next_val\n # Retry\n\n def decrement(self):\n while True:\n current = self._value\n next_val = current - 1\n if self._compare_and_set(current, next_val):\n return next_val\n\n def get(self):\n return self._value\n```\n\n\nPython's implementation uses a lock internally to simulate CAS. For true lock-free behavior, you would need C extensions or the `atomics` library.\n\n \n\n\n```cpp\n#include \n\nclass LockFreeCounter {\n std::atomic value{0};\n\npublic:\n int increment() {\n int current = value.load(std::memory_order_relaxed);\n while (!value.compare_exchange_weak(current, current + 1,\n std::memory_order_relaxed)) {\n // current is updated to actual value on failure\n // Loop continues automatically\n }\n return current + 1;\n }\n\n int decrement() {\n int current = value.load(std::memory_order_relaxed);\n while (!value.compare_exchange_weak(current, current - 1,\n std::memory_order_relaxed)) {\n }\n return current - 1;\n }\n\n int get() const {\n return value.load(std::memory_order_relaxed);\n }\n};\n```\n\n\nThe C++ version uses weak CAS and relaxed ordering. Weak CAS is appropriate in loops, and relaxed ordering is fine for an independent counter with no data dependencies.\n\n \n\n\n```csharp\nusing System.Threading;\n\npublic class LockFreeCounter\n{\n private int _value = 0;\n\n public int Increment()\n {\n int current, next;\n do\n {\n current = Volatile.Read(ref _value);\n next = current + 1;\n } while (Interlocked.CompareExchange(ref _value, next, current) != current);\n // current is not updated by CompareExchange in C#\n // Loop continues if CAS returns a different value\n return next;\n }\n\n public int Decrement()\n {\n int current, next;\n do\n {\n current = Volatile.Read(ref _value);\n next = current - 1;\n } while (Interlocked.CompareExchange(ref _value, next, current) != current);\n return next;\n }\n\n public int Get()\n {\n return Volatile.Read(ref _value);\n }\n}\n```\n\n\n**Key Points:**\n\n- Line 12: `Volatile.Read` ensures we see the latest value from memory\n- Line 14: `Interlocked.CompareExchange` returns the original value for comparison\n- Line 14: Unlike C++, the expected variable is NOT updated on failure, so we must re-read\n\n \n\n\n```go\npackage main\n\nimport (\n\t\"sync/atomic\"\n)\n\ntype LockFreeCounter struct {\n\tvalue int64\n}\n\nfunc (c *LockFreeCounter) Increment() int64 {\n\tfor {\n\t\tcurrent := atomic.LoadInt64(&c.value)\n\t\tnext := current + 1\n\t\tif atomic.CompareAndSwapInt64(&c.value, current, next) {\n\t\t\treturn next\n\t\t}\n\t\t// CAS failed - another goroutine incremented\n\t\t// Loop continues with fresh read\n\t}\n}\n\nfunc (c *LockFreeCounter) Decrement() int64 {\n\tfor {\n\t\tcurrent := atomic.LoadInt64(&c.value)\n\t\tnext := current - 1\n\t\tif atomic.CompareAndSwapInt64(&c.value, current, next) {\n\t\t\treturn next\n\t\t}\n\t}\n}\n\nfunc (c *LockFreeCounter) Get() int64 {\n\treturn atomic.LoadInt64(&c.value)\n}\n\n// Go 1.19+ version using atomic.Int64\ntype LockFreeCounterModern struct {\n\tvalue atomic.Int64\n}\n\nfunc (c *LockFreeCounterModern) Increment() int64 {\n\treturn c.value.Add(1)\n}\n\nfunc (c *LockFreeCounterModern) Decrement() int64 {\n\treturn c.value.Add(-1)\n}\n\nfunc (c *LockFreeCounterModern) Get() int64 {\n\treturn c.value.Load()\n}\n```\n\n\n**Key Points:**\n\n- `atomic.CompareAndSwapInt64` returns a boolean (not the original value like C#)\n- Unlike C++, Go does not update the expected variable on failure, so re-read is required\n- Go 1.19+ `atomic.Int64` provides cleaner method-based API\n- `atomic.Add` returns the new value (use for simple increment/decrement)\n\n \n\n---\n\n## Treiber Stack\n\nThe Treiber stack (1986) is the classic lock-free stack implementation. It uses a single atomic pointer to the head node and CAS to update it.\n\n### Structure\n\n\n```mermaid\nflowchart LR\n HEAD[Head
AtomicReference]:::primary --> A[Node A
value: 3]:::purple\n A --> B[Node B
value: 2]:::purple\n B --> C[Node C
value: 1]:::purple\n C --> NULL[null]:::secondary\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef purple fill:#9775fa,stroke:#000,color:#000\n classDef secondary fill:#38d9a9,stroke:#000,color:#000\n```\n\n\nThe stack is a singly-linked list where `head` points to the top element. Each node contains a value and a pointer to the next node. The head is an atomic reference that we modify using CAS.\n\n### Push Operation\n\nTo push a new element:\n\n1. Create a new node with the value\n2. Read the current head\n3. Set the new node's next pointer to the current head\n4. CAS the head from the current value to the new node\n5. If CAS fails, another thread modified the head; go back to step 2\n\n\n```mermaid\nflowchart TD\n subgraph \"Before Push\"\n H1[Head]:::primary --> A1[A]:::purple\n A1 --> B1[B]:::purple\n end\n\n subgraph \"Creating New Node\"\n NEW[New Node X]:::orange\n NEW -.->|next| A2[A]:::purple\n end\n\n subgraph \"After CAS Success\"\n H2[Head]:::primary --> X[X]:::green\n X --> A3[A]:::purple\n A3 --> B2[B]:::purple\n end\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef purple fill:#9775fa,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\nThe diagram shows the push sequence. We create node X, point its `next` to the current head (A), then atomically swing the head from A to X. If another thread pushed between our read and our CAS, the CAS fails, and we retry.\n\n### Pop Operation\n\nTo pop an element:\n\n1. Read the current head\n2. If null, the stack is empty\n3. Read the head's next pointer\n4. CAS the head from the current value to the next pointer\n5. If CAS fails, another thread modified the head; go back to step 1\n6. Return the popped value\n\n\n```mermaid\nflowchart TD\n subgraph \"Before Pop\"\n H1[Head]:::primary --> A1[A]:::purple\n A1 --> B1[B]:::purple\n B1 --> C1[C]:::purple\n end\n\n subgraph \"Reading head.next\"\n H2[Head]:::primary --> A2[A]:::orange\n A2 -.->|next| B2[B]:::purple\n end\n\n subgraph \"After CAS Success\"\n H3[Head]:::primary --> B3[B]:::green\n B3 --> C2[C]:::purple\n POPPED[Return A]:::orange\n end\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef purple fill:#9775fa,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\nWe read the head (A) and its next pointer (B). Then we CAS the head from A to B. If successful, we have \"removed\" A from the stack. If another thread already popped A, our CAS fails and we retry.\n\n### Implementation\n\n \n\n\n```java\nimport java.util.concurrent.atomic.AtomicReference;\n\npublic class TreiberStack {\n private final AtomicReference> head = new AtomicReference<>(null);\n\n private static class Node {\n final T value;\n Node next;\n\n Node(T value) {\n this.value = value;\n }\n }\n\n public void push(T value) {\n Node newNode = new Node<>(value);\n while (true) {\n Node currentHead = head.get();\n newNode.next = currentHead;\n if (head.compareAndSet(currentHead, newNode)) {\n return; // Successfully pushed\n }\n // CAS failed - another thread modified head\n // Loop continues with fresh read\n }\n }\n\n public T pop() {\n while (true) {\n Node currentHead = head.get();\n if (currentHead == null) {\n return null; // Stack is empty\n }\n Node newHead = currentHead.next;\n if (head.compareAndSet(currentHead, newHead)) {\n return currentHead.value; // Successfully popped\n }\n // CAS failed - another thread modified head\n }\n }\n\n public boolean isEmpty() {\n return head.get() == null;\n }\n\n public T peek() {\n Node currentHead = head.get();\n return (currentHead == null) ? null : currentHead.value;\n }\n}\n```\n\n\nThe implementation is straightforward once you understand the CAS loop pattern. The key insight is that both push and pop only modify the head pointer. As long as the CAS on head succeeds, the operation is complete.\n\n \n\n\n```python\nimport threading\nfrom typing import TypeVar, Generic, Optional\n\nT = TypeVar('T')\n\nclass Node(Generic[T]):\n def __init__(self, value: T):\n self.value = value\n self.next: Optional['Node[T]'] = None\n\nclass TreiberStack(Generic[T]):\n \"\"\"\n Conceptual Treiber stack implementation.\n Uses lock for CAS simulation in Python.\n \"\"\"\n def __init__(self):\n self._head: Optional[Node[T]] = None\n self._lock = threading.Lock()\n\n def _compare_and_set_head(self, expected: Optional[Node[T]],\n new_value: Optional[Node[T]]) -> bool:\n with self._lock:\n if self._head is expected:\n self._head = new_value\n return True\n return False\n\n def push(self, value: T) -> None:\n new_node = Node(value)\n while True:\n current_head = self._head\n new_node.next = current_head\n if self._compare_and_set_head(current_head, new_node):\n return\n\n def pop(self) -> Optional[T]:\n while True:\n current_head = self._head\n if current_head is None:\n return None\n new_head = current_head.next\n if self._compare_and_set_head(current_head, new_head):\n return current_head.value\n\n def is_empty(self) -> bool:\n return self._head is None\n\n def peek(self) -> Optional[T]:\n current_head = self._head\n return current_head.value if current_head else None\n```\n\n\n \n\n\n```cpp\n#include \n#include \n\ntemplate\nclass TreiberStack {\n struct Node {\n T value;\n Node* next;\n Node(const T& v) : value(v), next(nullptr) {}\n };\n\n std::atomic head{nullptr};\n\npublic:\n void push(const T& value) {\n Node* newNode = new Node(value);\n Node* currentHead = head.load(std::memory_order_relaxed);\n do {\n newNode->next = currentHead;\n } while (!head.compare_exchange_weak(currentHead, newNode,\n std::memory_order_release,\n std::memory_order_relaxed));\n }\n\n std::optional pop() {\n Node* currentHead = head.load(std::memory_order_acquire);\n while (currentHead != nullptr) {\n Node* newHead = currentHead->next;\n if (head.compare_exchange_weak(currentHead, newHead,\n std::memory_order_acquire,\n std::memory_order_relaxed)) {\n T value = std::move(currentHead->value);\n // Memory reclamation issue: cannot delete currentHead yet!\n // Other threads might still be reading it\n // delete currentHead; // UNSAFE\n return value;\n }\n // currentHead is updated by compare_exchange_weak on failure\n }\n return std::nullopt;\n }\n\n bool isEmpty() const {\n return head.load(std::memory_order_acquire) == nullptr;\n }\n};\n```\n\n\nThe C++ version highlights the memory reclamation problem. After a successful pop, we cannot immediately delete the node because other threads might still be accessing it (the ABA problem territory). Solving this requires hazard pointers, epoch-based reclamation, or smart pointers with atomic operations.\n\n \n\n\n```csharp\nusing System;\nusing System.Threading;\n\npublic class TreiberStack where T : class\n{\n private class Node\n {\n public readonly T Value;\n public Node? Next;\n\n public Node(T value)\n {\n Value = value;\n }\n }\n\n private Node? _head = null;\n\n public void Push(T value)\n {\n var newNode = new Node(value);\n Node? currentHead;\n do\n {\n currentHead = Volatile.Read(ref _head);\n newNode.Next = currentHead;\n } while (Interlocked.CompareExchange(ref _head, newNode, currentHead) != currentHead);\n }\n\n public T? Pop()\n {\n Node? currentHead;\n Node? newHead;\n do\n {\n currentHead = Volatile.Read(ref _head);\n if (currentHead == null)\n {\n return default; // Stack is empty\n }\n newHead = currentHead.Next;\n } while (Interlocked.CompareExchange(ref _head, newHead, currentHead) != currentHead);\n return currentHead.Value;\n }\n\n public bool IsEmpty()\n {\n return Volatile.Read(ref _head) == null;\n }\n\n public T? Peek()\n {\n var currentHead = Volatile.Read(ref _head);\n return currentHead?.Value;\n }\n}\n```\n\n\n**Key Points:**\n\n- Line 4: Constraint `where T : class` needed because `Interlocked.CompareExchange` for references requires reference types\n- Line 25: `Volatile.Read` ensures visibility of the latest head reference\n- Line 27: CAS on reference type atomically swaps the head pointer\n- Memory reclamation is handled by the garbage collector in C#\n\n \n\n\n```go\npackage main\n\nimport (\n\t\"sync/atomic\"\n)\n\ntype Node[T any] struct {\n\tvalue T\n\tnext *Node[T]\n}\n\ntype TreiberStack[T any] struct {\n\thead atomic.Pointer[Node[T]]\n}\n\nfunc NewTreiberStack[T any]() *TreiberStack[T] {\n\treturn &TreiberStack[T]{}\n}\n\nfunc (s *TreiberStack[T]) Push(value T) {\n\tnewNode := &Node[T]{value: value}\n\tfor {\n\t\tcurrentHead := s.head.Load()\n\t\tnewNode.next = currentHead\n\t\tif s.head.CompareAndSwap(currentHead, newNode) {\n\t\t\treturn // Successfully pushed\n\t\t}\n\t\t// CAS failed - another goroutine modified head\n\t\t// Loop continues with fresh read\n\t}\n}\n\nfunc (s *TreiberStack[T]) Pop() (T, bool) {\n\tfor {\n\t\tcurrentHead := s.head.Load()\n\t\tif currentHead == nil {\n\t\t\tvar zero T\n\t\t\treturn zero, false // Stack is empty\n\t\t}\n\t\tnewHead := currentHead.next\n\t\tif s.head.CompareAndSwap(currentHead, newHead) {\n\t\t\treturn currentHead.value, true // Successfully popped\n\t\t}\n\t\t// CAS failed - another goroutine modified head\n\t}\n}\n\nfunc (s *TreiberStack[T]) IsEmpty() bool {\n\treturn s.head.Load() == nil\n}\n\nfunc (s *TreiberStack[T]) Peek() (T, bool) {\n\tcurrentHead := s.head.Load()\n\tif currentHead == nil {\n\t\tvar zero T\n\t\treturn zero, false\n\t}\n\treturn currentHead.value, true\n}\n```\n\n\n**Key Points:**\n\n- Go 1.19+ `atomic.Pointer[T]` provides type-safe atomic pointer operations\n- No need for `unsafe.Pointer` with the generic atomic pointer type\n- Memory reclamation is handled by Go's garbage collector\n- The `(T, bool)` return pattern is idiomatic Go for optional values\n- CAS returns boolean; loop until successful or empty condition\n\n \n\n### ABA Problem in Treiber Stack\n\nThe Treiber stack is vulnerable to the ABA problem when memory is reused. Consider:\n\n1. Thread 1 reads head = A, and A.next = B\n2. Thread 1 is preempted\n3. Thread 2 pops A, pops B, pushes C, pushes A back (same memory address reused)\n4. Thread 1 resumes, sees head = A, CAS succeeds\n5. But now A.next points to something unexpected!\n\nSolution: Use `AtomicStampedReference` in Java or tagged pointers with version numbers.\n\n---\n\n## Michael-Scott Queue\n\nThe Michael-Scott queue (1996) is the most famous lock-free queue algorithm. It is the basis for Java's `ConcurrentLinkedQueue`. Understanding it is essential for any serious concurrent programming work.\n\n### Structure\n\nThe queue uses a dummy node to separate head and tail operations:\n\n\n```mermaid\nflowchart LR\n HEAD[Head]:::primary --> DUMMY[Dummy
sentinel]:::secondary\n DUMMY --> A[Node A]:::purple\n A --> B[Node B]:::purple\n B --> NULL[null]:::secondary\n TAIL[Tail]:::primary --> B\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef secondary fill:#38d9a9,stroke:#000,color:#000\n classDef purple fill:#9775fa,stroke:#000,color:#000\n```\n\n\nKey design decisions:\n\n- **Dummy node:** Separates head/tail contention. Enqueue only touches tail, dequeue only touches head\n- **Head points to dummy (or last dequeued node):** The actual first element is head.next\n- **Tail points to last node (or close to it):** May lag behind due to two-step enqueue\n\n### Why the Dummy Node?\n\nWithout a dummy node, an empty queue would have both head and tail pointing to null. Enqueue and dequeue would both need to handle the empty→non-empty and non-empty→empty transitions, creating contention at both ends. With the dummy, head and tail always point to valid nodes, and the transitions are simpler.\n\n### Enqueue Algorithm\n\nEnqueue is a two-step process:\n\n1. **Step 1:** Link new node to the end of the list (CAS on tail.next)\n2. **Step 2:** Advance tail to point to the new node (CAS on tail)\n\n\n```mermaid\nflowchart TD\n subgraph \"Initial State\"\n H1[Head]:::primary --> D1[Dummy]:::secondary\n D1 --> A1[A]:::purple\n A1 --> NULL1[null]:::secondary\n T1[Tail]:::primary --> A1\n end\n\n subgraph \"Step 1: Link new node\"\n H2[Head]:::primary --> D2[Dummy]:::secondary\n D2 --> A2[A]:::purple\n A2 --> B[New B]:::orange\n B --> NULL2[null]:::secondary\n T2[Tail]:::primary --> A2\n NOTE1[tail.next CAS:
null → B]:::yellow\n end\n\n subgraph \"Step 2: Advance tail\"\n H3[Head]:::primary --> D3[Dummy]:::secondary\n D3 --> A3[A]:::purple\n A3 --> B2[B]:::green\n B2 --> NULL3[null]:::secondary\n T3[Tail]:::primary --> B2\n NOTE2[tail CAS:
A → B]:::yellow\n end\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef secondary fill:#38d9a9,stroke:#000,color:#000\n classDef purple fill:#9775fa,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef yellow fill:#ffd43b,stroke:#000,color:#000\n```\n\n\nThe two-step process creates an important scenario: what if a thread completes Step 1 but not Step 2? The new node is linked, but tail has not moved. This is where \"helping\" comes in: other threads can detect this situation and help advance the tail.\n\n### The Helping Mechanism\n\nWhen a thread tries to enqueue and finds tail.next is not null, it knows another thread is mid-enqueue. Instead of waiting, it helps by trying to advance tail:\n\n\n```shell\nfunction enqueue(value):\n newNode = new Node(value)\n loop:\n tail = this.tail\n next = tail.next\n\n if next == null:\n // Tail is at the actual end\n if CAS(tail.next, null, newNode):\n // Step 1 succeeded, try Step 2\n CAS(this.tail, tail, newNode) // OK if this fails\n return\n else:\n // Tail is lagging - help advance it\n CAS(this.tail, tail, next)\n // Then retry enqueue\n```\n\n\nThe helping mechanism is what makes the algorithm lock-free. Even if the original enqueuer gets stuck between steps, other threads will complete the operation.\n\n### Dequeue Algorithm\n\nDequeue removes the first real element (head.next, not head itself):\n\n\n```shell\nfunction dequeue():\n loop:\n head = this.head\n tail = this.tail\n first = head.next\n\n if head == tail:\n if first == null:\n return EMPTY // Queue is empty\n // Tail is lagging - help advance it\n CAS(this.tail, tail, first)\n else:\n value = first.value\n if CAS(this.head, head, first):\n return value\n```\n\n\nWhen head equals tail, the queue might be empty or tail might be lagging. We check first.next to distinguish. If the queue is truly empty, we return. Otherwise, we help advance tail.\n\n### Complete Implementation\n\n \n\n\n```java\nimport java.util.concurrent.atomic.AtomicReference;\n\npublic class MichaelScottQueue {\n private static class Node {\n final T value;\n final AtomicReference> next;\n\n Node(T value) {\n this.value = value;\n this.next = new AtomicReference<>(null);\n }\n }\n\n private final AtomicReference> head;\n private final AtomicReference> tail;\n\n public MichaelScottQueue() {\n Node dummy = new Node<>(null); // Sentinel node\n head = new AtomicReference<>(dummy);\n tail = new AtomicReference<>(dummy);\n }\n\n public void enqueue(T value) {\n Node newNode = new Node<>(value);\n\n while (true) {\n Node currentTail = tail.get();\n Node tailNext = currentTail.next.get();\n\n // Check if tail is still consistent\n if (currentTail == tail.get()) {\n if (tailNext == null) {\n // Tail is at actual end - try to link new node\n if (currentTail.next.compareAndSet(null, newNode)) {\n // Step 1 succeeded - try to advance tail\n // It's OK if this fails - another thread will help\n tail.compareAndSet(currentTail, newNode);\n return;\n }\n } else {\n // Tail is lagging - help advance it\n tail.compareAndSet(currentTail, tailNext);\n }\n }\n }\n }\n\n public T dequeue() {\n while (true) {\n Node currentHead = head.get();\n Node currentTail = tail.get();\n Node first = currentHead.next.get();\n\n // Check if head is still consistent\n if (currentHead == head.get()) {\n if (currentHead == currentTail) {\n // Head and tail point to same node\n if (first == null) {\n return null; // Queue is empty\n }\n // Tail is lagging - help advance it\n tail.compareAndSet(currentTail, first);\n } else {\n // There's an element to dequeue\n T value = first.value;\n if (head.compareAndSet(currentHead, first)) {\n // Successfully dequeued\n // Note: currentHead (old dummy) can now be GC'd\n return value;\n }\n }\n }\n }\n }\n\n public boolean isEmpty() {\n Node currentHead = head.get();\n Node currentTail = tail.get();\n Node first = currentHead.next.get();\n return (currentHead == currentTail) && (first == null);\n }\n\n public T peek() {\n Node first = head.get().next.get();\n return (first == null) ? null : first.value;\n }\n}\n```\n\n\nThe implementation includes the crucial consistency checks (`if currentTail == tail.get()` and `if currentHead == head.get()`). These checks detect if another thread modified the pointers during our operation, ensuring we do not work with stale data.\n\n \n\n\n```csharp\nusing System;\nusing System.Threading;\n\npublic class MichaelScottQueue where T : class\n{\n private class Node\n {\n public readonly T? Value;\n public Node? Next;\n\n public Node(T? value)\n {\n Value = value;\n Next = null;\n }\n }\n\n private Node _head;\n private Node _tail;\n\n public MichaelScottQueue()\n {\n var dummy = new Node(default); // Sentinel node\n _head = dummy;\n _tail = dummy;\n }\n\n public void Enqueue(T value)\n {\n var newNode = new Node(value);\n\n while (true)\n {\n var currentTail = Volatile.Read(ref _tail);\n var tailNext = Volatile.Read(ref currentTail.Next);\n\n // Check if tail is still consistent\n if (currentTail == Volatile.Read(ref _tail))\n {\n if (tailNext == null)\n {\n // Tail is at actual end - try to link new node\n if (Interlocked.CompareExchange(ref currentTail.Next, newNode, null) == null)\n {\n // Step 1 succeeded - try to advance tail\n // It's OK if this fails - another thread will help\n Interlocked.CompareExchange(ref _tail, newNode, currentTail);\n return;\n }\n }\n else\n {\n // Tail is lagging - help advance it\n Interlocked.CompareExchange(ref _tail, tailNext, currentTail);\n }\n }\n }\n }\n\n public T? Dequeue()\n {\n while (true)\n {\n var currentHead = Volatile.Read(ref _head);\n var currentTail = Volatile.Read(ref _tail);\n var first = Volatile.Read(ref currentHead.Next);\n\n // Check if head is still consistent\n if (currentHead == Volatile.Read(ref _head))\n {\n if (currentHead == currentTail)\n {\n // Head and tail point to same node\n if (first == null)\n {\n return default; // Queue is empty\n }\n // Tail is lagging - help advance it\n Interlocked.CompareExchange(ref _tail, first, currentTail);\n }\n else\n {\n // There's an element to dequeue\n T? value = first!.Value;\n if (Interlocked.CompareExchange(ref _head, first, currentHead) == currentHead)\n {\n // Successfully dequeued\n // Note: currentHead (old dummy) can now be GC'd\n return value;\n }\n }\n }\n }\n }\n\n public bool IsEmpty()\n {\n var currentHead = Volatile.Read(ref _head);\n var currentTail = Volatile.Read(ref _tail);\n var first = Volatile.Read(ref currentHead.Next);\n return (currentHead == currentTail) && (first == null);\n }\n\n public T? Peek()\n {\n var first = Volatile.Read(ref _head).Next;\n return first?.Value;\n }\n}\n```\n\n\n**Key Points:**\n\n- Line 4: Constraint `where T : class` required for `Interlocked.CompareExchange` on references\n- Line 38: Consistency check prevents working with stale pointers\n- Line 43: CAS on `Next` field links the new node\n- Line 47: Helping mechanism advances tail if another thread stalled\n- Memory reclamation is automatic via garbage collection\n\n \n\n\n```go\npackage main\n\nimport (\n\t\"sync/atomic\"\n)\n\ntype QueueNode[T any] struct {\n\tvalue T\n\tnext atomic.Pointer[QueueNode[T]]\n}\n\ntype MichaelScottQueue[T any] struct {\n\thead atomic.Pointer[QueueNode[T]]\n\ttail atomic.Pointer[QueueNode[T]]\n}\n\nfunc NewMichaelScottQueue[T any]() *MichaelScottQueue[T] {\n\tdummy := &QueueNode[T]{} // Sentinel node\n\tq := &MichaelScottQueue[T]{}\n\tq.head.Store(dummy)\n\tq.tail.Store(dummy)\n\treturn q\n}\n\nfunc (q *MichaelScottQueue[T]) Enqueue(value T) {\n\tnewNode := &QueueNode[T]{value: value}\n\n\tfor {\n\t\tcurrentTail := q.tail.Load()\n\t\ttailNext := currentTail.next.Load()\n\n\t\t// Check if tail is still consistent\n\t\tif currentTail == q.tail.Load() {\n\t\t\tif tailNext == nil {\n\t\t\t\t// Tail is at actual end - try to link new node\n\t\t\t\tif currentTail.next.CompareAndSwap(nil, newNode) {\n\t\t\t\t\t// Step 1 succeeded - try to advance tail\n\t\t\t\t\t// It's OK if this fails - another goroutine will help\n\t\t\t\t\tq.tail.CompareAndSwap(currentTail, newNode)\n\t\t\t\t\treturn\n\t\t\t\t}\n\t\t\t} else {\n\t\t\t\t// Tail is lagging - help advance it\n\t\t\t\tq.tail.CompareAndSwap(currentTail, tailNext)\n\t\t\t}\n\t\t}\n\t}\n}\n\nfunc (q *MichaelScottQueue[T]) Dequeue() (T, bool) {\n\tfor {\n\t\tcurrentHead := q.head.Load()\n\t\tcurrentTail := q.tail.Load()\n\t\tfirst := currentHead.next.Load()\n\n\t\t// Check if head is still consistent\n\t\tif currentHead == q.head.Load() {\n\t\t\tif currentHead == currentTail {\n\t\t\t\t// Head and tail point to same node\n\t\t\t\tif first == nil {\n\t\t\t\t\tvar zero T\n\t\t\t\t\treturn zero, false // Queue is empty\n\t\t\t\t}\n\t\t\t\t// Tail is lagging - help advance it\n\t\t\t\tq.tail.CompareAndSwap(currentTail, first)\n\t\t\t} else {\n\t\t\t\t// There's an element to dequeue\n\t\t\t\tvalue := first.value\n\t\t\t\tif q.head.CompareAndSwap(currentHead, first) {\n\t\t\t\t\t// Successfully dequeued\n\t\t\t\t\t// Note: currentHead (old dummy) can now be GC'd\n\t\t\t\t\treturn value, true\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t}\n}\n\nfunc (q *MichaelScottQueue[T]) IsEmpty() bool {\n\tcurrentHead := q.head.Load()\n\tcurrentTail := q.tail.Load()\n\tfirst := currentHead.next.Load()\n\treturn (currentHead == currentTail) && (first == nil)\n}\n\nfunc (q *MichaelScottQueue[T]) Peek() (T, bool) {\n\tfirst := q.head.Load().next.Load()\n\tif first == nil {\n\t\tvar zero T\n\t\treturn zero, false\n\t}\n\treturn first.value, true\n}\n```\n\n\n**Key Points:**\n\n- Go 1.19+ `atomic.Pointer[T]` enables type-safe lock-free data structures\n- The `next` field in `QueueNode` must be an `atomic.Pointer` for CAS operations\n- Consistency checks (`currentTail == q.tail.Load()`) prevent stale pointer issues\n- Helping mechanism advances tail when detecting a lagging tail\n- Memory reclamation handled automatically by Go's garbage collector\n- The `(T, bool)` return pattern is idiomatic Go for optional values\n\n \n\n\n```cpp\n#include \n#include \n\ntemplate\nclass MichaelScottQueue {\n struct Node {\n T value;\n std::atomic next;\n Node() : next(nullptr) {} // For dummy\n Node(const T& v) : value(v), next(nullptr) {}\n };\n\n std::atomic head;\n std::atomic tail;\n\npublic:\n MichaelScottQueue() {\n Node* dummy = new Node();\n head.store(dummy, std::memory_order_relaxed);\n tail.store(dummy, std::memory_order_relaxed);\n }\n\n ~MichaelScottQueue() {\n // Drain queue and delete nodes\n T val;\n while (dequeue().has_value()) {}\n delete head.load(); // Delete dummy\n }\n\n void enqueue(const T& value) {\n Node* newNode = new Node(value);\n\n while (true) {\n Node* currentTail = tail.load(std::memory_order_acquire);\n Node* tailNext = currentTail->next.load(std::memory_order_acquire);\n\n if (currentTail == tail.load(std::memory_order_acquire)) {\n if (tailNext == nullptr) {\n // Try to link new node\n if (currentTail->next.compare_exchange_weak(\n tailNext, newNode,\n std::memory_order_release,\n std::memory_order_relaxed)) {\n // Try to advance tail\n tail.compare_exchange_weak(currentTail, newNode,\n std::memory_order_release,\n std::memory_order_relaxed);\n return;\n }\n } else {\n // Help advance tail\n tail.compare_exchange_weak(currentTail, tailNext,\n std::memory_order_release,\n std::memory_order_relaxed);\n }\n }\n }\n }\n\n std::optional dequeue() {\n while (true) {\n Node* currentHead = head.load(std::memory_order_acquire);\n Node* currentTail = tail.load(std::memory_order_acquire);\n Node* first = currentHead->next.load(std::memory_order_acquire);\n\n if (currentHead == head.load(std::memory_order_acquire)) {\n if (currentHead == currentTail) {\n if (first == nullptr) {\n return std::nullopt; // Empty\n }\n tail.compare_exchange_weak(currentTail, first,\n std::memory_order_release,\n std::memory_order_relaxed);\n } else {\n T value = first->value;\n if (head.compare_exchange_weak(currentHead, first,\n std::memory_order_release,\n std::memory_order_relaxed)) {\n // WARNING: Cannot safely delete currentHead here\n // Need hazard pointers or epoch-based reclamation\n return value;\n }\n }\n }\n }\n }\n};\n```\n\n\n \n\n---\n\n## Linearizability\n\nLock-free data structures must be **linearizable**: each operation appears to take effect instantaneously at some point between its invocation and completion.\n\n### Linearization Points\n\nThe linearization point is the moment when an operation \"takes effect\":\n\n\n| Operation | Linearization Point |\n|-----------|---------------------|\n| Stack push | Successful CAS on head |\n| Stack pop | Successful CAS on head |\n| Queue enqueue | Successful CAS on tail.next (Step 1) |\n| Queue dequeue | Successful CAS on head |\n\n\n\n```mermaid\nsequenceDiagram\n participant T1 as Thread 1\n participant DS as Data Structure\n participant T2 as Thread 2\n\n T1->>DS: push(A) starts\n T1->>DS: Linearization point
(CAS succeeds)\n T1->>DS: push(A) returns\n T2->>DS: pop() starts\n T2->>DS: Linearization point
(CAS succeeds, gets A)\n T2->>DS: pop() returns A\n```\n\n\nThe timeline shows that even though operations take time, they appear to happen instantaneously at their linearization points. Any observer would see a consistent sequential history.\n\n### Why Linearizability Matters\n\nLinearizability lets you reason about concurrent data structures as if operations happened one at a time. This composability is essential: you can use a linearizable queue in a larger system without worrying about internal timing details.\n\n---\n\n## Memory Reclamation Challenge\n\nA major challenge with lock-free structures is: when can we safely free memory?\n\n\n```mermaid\nflowchart TD\n PROBLEM[Thread A reads node X]:::primary --> PREEMPT[Thread A is preempted]:::orange\n PREEMPT --> ANOTHER[Thread B pops X]:::secondary\n ANOTHER --> DELETE[Thread B deletes X]:::red\n DELETE --> RESUME[Thread A resumes]:::orange\n RESUME --> CRASH[Thread A accesses X
CRASH!]:::red\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef secondary fill:#38d9a9,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef red fill:#ff8787,stroke:#000,color:#000\n```\n\n\nThe problem: Thread A holds a pointer to node X. Thread B pops and frees X. Thread A resumes and dereferences a freed pointer.\n\n### Solutions\n\n1. **Garbage Collection (Java):** The GC handles this automatically. Nodes are not freed until no references exist.\n\n1. **Hazard Pointers:** Threads publish pointers they are currently using. Other threads check these \"hazard\" pointers before freeing.\n\n1. **Epoch-Based Reclamation:** Memory is retired to a list. Only freed when all threads have advanced past the retirement epoch.\n\n1. **Reference Counting:** Atomic reference counts track pointer holders. Free when count reaches zero.\n\nFor Java, you do not need to worry about this. For C++, it is a significant complication that often leads developers to use garbage collection libraries or epoch-based schemes.\n\n:::note C# C# benefits from garbage collection just like Java, making lock-free data structures easier to implement. The `Interlocked.CompareExchange` method works with reference types directly, allowing atomic pointer swaps. However, C# has no equivalent to Java's `AtomicStampedReference` for solving the ABA problem. If ABA is a concern, you can use a tuple or struct containing both a reference and a version number, though this requires careful handling. For most applications, the GC's handling of unreachable objects makes ABA much less dangerous than in C++. The `System.Collections.Concurrent` namespace provides production-ready lock-free collections like `ConcurrentQueue` and `ConcurrentStack`. :::\n\n:::note Go Go benefits from garbage collection, making lock-free data structures easier to implement. Go 1.19+ introduced `atomic.Pointer[T]` which provides type-safe atomic pointer operations without requiring `unsafe.Pointer`. This makes implementing lock-free stacks and queues much cleaner. For the ABA problem, Go does not have a built-in equivalent to Java's `AtomicStampedReference`. You can implement a similar pattern by packing a version number into a struct and using `atomic.Pointer` on the struct, or by using `atomic.Uint64` to pack pointer+version together (requires `unsafe`). In practice, Go's GC makes ABA much less dangerous since memory is not reused until all references are gone. For production use, consider using channels for most concurrent communication patterns, and reserve lock-free structures for performance-critical paths where channel overhead is unacceptable. :::\n\n---\n\n## Common Mistakes\n\n### Mistake 1: Not Retrying on CAS Failure\n\n\n```java\n// BAD: Single attempt, may lose operations\npublic void brokenPush(T value) {\n Node newNode = new Node<>(value);\n Node currentHead = head.get();\n newNode.next = currentHead;\n head.compareAndSet(currentHead, newNode); // Ignores failure!\n}\n```\n\n\n**Fix:** Always use a CAS loop.\n\n### Mistake 2: Reading Stale Pointers\n\n\n```java\n// BAD: Using cached values after modification\npublic T brokenPop() {\n Node currentHead = head.get();\n // ... time passes, other threads modify ...\n Node next = currentHead.next.get();\n // currentHead might no longer be the head!\n head.compareAndSet(currentHead, next); // May corrupt the stack\n return currentHead.value;\n}\n```\n\n\n**Fix:** Re-read and validate before critical operations.\n\n### Mistake 3: Ignoring ABA in Pop\n\n\n```java\n// BAD: Vulnerable to ABA\npublic T abaVulnerablePop() {\n while (true) {\n Node currentHead = head.get();\n if (currentHead == null) return null;\n Node next = currentHead.next;\n // ABA: currentHead could be recycled with different next!\n if (head.compareAndSet(currentHead, next)) {\n return currentHead.value;\n }\n }\n}\n```\n\n\n**Fix:** Use stamped references or hazard pointers.\n\n---\n\n## Performance Considerations\n\n### Lock-Free vs Lock-Based\n\n\n| Threads | Lock-Free Queue | Lock-Based Queue |\n|---------|-----------------|------------------|\n| 1 | ~50 ns/op | ~30 ns/op |\n| 4 | ~100 ns/op | ~200 ns/op |\n| 8 | ~200 ns/op | ~500 ns/op |\n| 16 | ~400 ns/op | ~1-2 μs/op |\n| 64 | ~800 ns/op | ~5-10 μs/op |\n\n\nLock-free wins at higher contention but has more overhead at low contention.\n\n### When to Use Lock-Free\n\n- Latency-sensitive applications (trading, gaming)\n- High contention scenarios\n- When you cannot afford to have a stuck thread block others\n- Real-time systems with bounded response time requirements\n\n### When to Use Locks\n\n- Low contention scenarios\n- Complex invariants across multiple variables\n- When simplicity matters more than performance\n- When memory reclamation is a concern (in non-GC languages)\n\n---\n\n## Interview Questions and Answers\n\n**Q1: Implement a lock-free stack and explain the algorithm.**\n\nThe Treiber stack uses an atomic reference to the head node. Push creates a new node, sets its next to current head, then CAS the head from current to new node. Pop reads head and head.next, then CAS head from current to next. Both operations retry on CAS failure.\n\nThe key insight is that all modifications go through a single atomic pointer (head). CAS ensures only one thread wins any given update. Failed threads retry with fresh values. This is lock-free because competing threads do not block each other, they just retry.\n\nThe implementation must handle the empty case (pop returns null when head is null) and the ABA problem (in languages without GC, use stamped references).\n\n---\n\n**Q2: What makes a data structure lock-free vs wait-free?**\n\nLock-free guarantees system-wide progress: at least one thread completes in bounded steps. Individual threads may retry indefinitely under contention, but the system keeps moving.\n\nWait-free provides stronger per-thread guarantees: every thread completes in bounded steps, regardless of contention. No thread can starve.\n\nMost practical lock-free structures (Treiber stack, Michael-Scott queue) are lock-free but not wait-free. A thread that keeps losing CAS races could theoretically spin forever, though this is rare in practice. Wait-free algorithms exist but are typically more complex and slower.\n\n---\n\n**Q3: Explain the Michael-Scott queue algorithm and why it uses a dummy node.**\n\nThe Michael-Scott queue uses head and tail pointers with a dummy sentinel node. Enqueue is two steps: link new node to tail.next, then advance tail. Dequeue swings head to head.next.\n\nThe dummy node separates head and tail operations. Without it, enqueue and dequeue would contend when the queue becomes empty or has one element. With the dummy, an empty queue has head and tail pointing to the dummy, and enqueue/dequeue touch different pointers in the common case.\n\nThe algorithm includes a \"helping\" mechanism: if a thread finds tail.next is not null, it helps advance tail before proceeding. This ensures the two-step enqueue completes even if the original thread stalls.\n\n---\n\n**Q4: How do you handle memory reclamation in lock-free structures in C++?**\n\nMemory reclamation is the biggest challenge for lock-free C++. You cannot immediately free a popped node because other threads might still hold pointers to it.\n\nSolutions include: hazard pointers (threads publish currently-accessed pointers; safe to free only when not hazardous), epoch-based reclamation (nodes are retired to a per-epoch list and freed when all threads advance epochs), and reference counting (atomic counters track holders). Each has trade-offs in complexity and overhead.\n\nIn practice, many teams use GC'd languages for lock-free structures, or specialized memory reclamation libraries like libcds or Folly's hazard pointer implementation.\n\n---\n\n**Q5: What is linearizability and why does it matter for lock-free structures?**\n\nLinearizability means each operation appears to happen instantaneously at some point during its execution (the linearization point). Even though operations take time, observers see a consistent sequential history.\n\nFor lock-free structures, linearizability ensures composability: you can reason about the data structure without worrying about internal timing. If push linearizes at the successful CAS and pop linearizes at its CAS, any sequence of pushes and pops can be mapped to a sequential history.\n\nThe alternative (serializability) is weaker and allows more counterintuitive behaviors. Linearizability is the gold standard for concurrent data structures.\n\n---\n\n## Summary\n\n### Key Takeaways\n\n- Lock-free structures guarantee system progress regardless of individual thread behavior\n- The Treiber stack uses CAS on a single head pointer for both push and pop\n- The Michael-Scott queue uses a dummy node to separate head/tail contention and a helping mechanism for the two-step enqueue\n- Linearizability ensures operations appear instantaneous at their linearization points\n- Memory reclamation is the hard problem in C++ (solved by GC in Java)\n- Lock-free wins at high contention but has overhead at low contention\n\n### Quick Reference\n\n\n| Structure | Head | Tail | Push/Enqueue | Pop/Dequeue |\n|-----------|------|------|--------------|-------------|\n| Treiber Stack | AtomicRef | N/A | CAS head | CAS head |\n| M-S Queue | AtomicRef | AtomicRef | CAS tail.next, CAS tail | CAS head |\n\n\n### What's Next\n\nLock-free guarantees that someone makes progress. But what if we need every thread to complete in bounded time? The next chapter covers wait-free algorithms, which provide the strongest progress guarantee: every operation completes in a bounded number of steps, regardless of contention.\n\n---\n\n## References\n\n- Treiber, R. K. \"Systems Programming: Coping with Parallelism\" - IBM Almaden Research Center, 1986\n- Michael, M. & Scott, M. \"Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms\" - PODC 1996\n- Herlihy, M. & Shavit, N. \"The Art of Multiprocessor Programming\" - Chapters 10-11 on lock-free data structures\n- Java ConcurrentLinkedQueue source - [https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/concurrent/ConcurrentLinkedQueue.java](https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/concurrent/ConcurrentLinkedQueue.java)\n- Michael, M. \"Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects\" - IEEE TPDS 2004","pageType":"concurrency-interview"}

Lock-Free Data Structures

Ashish Pratap Singh

Get Premium