KWAS Academy
Learn. Build. Master.
QUICK START:HTMLCSSJavaScriptTypeScriptPythonSQLReactNext.jsNode.jsLinux & UbuntuKotlinSwiftC# / .NETJavaGoRustC++DSASystem DesignDevOpsCybersecurityAI / ML
Advanced 28 min readModule: Module 14: Lock-Free Concurrency Algorithms: Stacks & Queues

Lock-Free Algorithms: Treiber Stack & Michael-Scott Queue

Design wait-free and lock-free concurrent algorithms: Compare-And-Swap (CAS) consensus, lock-free Treiber Stack, the Michael-Scott non-blocking FIFO Queue, and solving the ABA problem with tagged pointers.

What You Will Learn in This Lesson

  • The hierarchy of non-blocking concurrency: Obstruction-Free vs Lock-Free vs Wait-Free
  • Atomic hardware primitives: Compare-And-Swap (CAS) and Fetch-And-Add (FAA)
  • The Michael-Scott Lock-Free Queue algorithm (foundation of Java's ConcurrentLinkedQueue)
  • The ABA Problem and solving it with versioned/tagged atomic pointers

Introduction & Core Concept

Concurrent data structures that rely on mutual exclusion locks (mutexes) suffer from priority inversion, deadlock risks, and high context-switching overhead. Lock-free algorithms guarantee system-wide progress without locks: even if some threads are suspended or delayed by the OS, at least one thread is guaranteed to complete its operation in a bounded number of steps.
WHY DOES THIS MATTER IN THE REAL WORLD?

High-throughput asynchronous runtimes (Tokio, .NET ThreadPool, Go runtime) and financial trading systems rely on lock-free stacks and queues to schedule millions of tasks per second without lock contention.

Syntax & Structure

javascript
while (!CAS(&head, oldHead, newHead)) {
    oldHead = head;
}

Simulating a Lock-Free Michael-Scott Non-Blocking FIFO Queue with Atomic CAS

javascript
javascript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
// Conceptual Lock-Free Michael-Scott Queue Simulation
class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}
 
class LockFreeQueue {
    constructor() {
        // Dummy sentinel node
        const sentinel = new Node(null);
        this.head = sentinel;
        this.tail = sentinel;
    }
 
    // Atomic CAS Simulation Helper
    _cas(obj, field, expected, update) {
        if (obj[field] === expected) {
            obj[field] = update;
            return true;
        }
        return false;
    }
 
    enqueue(val) {
        const newNode = new Node(val);
        while (true) {
            const curTail = this.tail;
            const tailNext = curTail.next;
 
            if (curTail === this.tail) {
                if (tailNext === null) {
                    // Try to link newNode at the end of the list
                    if (this._cas(curTail, 'next', null, newNode)) {
                        // Advance tail to new node (Helpful step)
                        this._cas(this, 'tail', curTail, newNode);
                        return;
                    }
                } else {
                    // Tail was lagging behind; help advance it
                    this._cas(this, 'tail', curTail, tailNext);
                }
            }
        }
    }
 
    dequeue() {
        while (true) {
            const curHead = this.head;
            const curTail = this.tail;
            const headNext = curHead.next;
 
            if (curHead === this.head) {
                if (curHead === curTail) {
                    if (headNext === null) return null; // Queue Empty
                    // Advance lagging tail
                    this._cas(this, 'tail', curTail, headNext);
                } else {
                    const value = headNext.value;
                    if (this._cas(this, 'head', curHead, headNext)) {
                        return value; // Dequeued successfully!
                    }
                }
            }
        }
    }
}
 
const queue = new LockFreeQueue();
queue.enqueue("TASK_101");
queue.enqueue("TASK_102");
console.log("=== Lock-Free Michael-Scott Queue ===");
console.log("Dequeued:", queue.dequeue());
console.log("Dequeued:", queue.dequeue());
console.log("Dequeued (Empty):", queue.dequeue());
console.log("✅ Queue executed without locking or thread suspension!");

Line-by-Line Technical Breakdown

1The ABA Problem: Thread 1 reads pointer A. Thread 2 pops A, frees it, pushes B, and pushes a newly allocated node that happens to share the same physical address A. Thread 1's CAS succeeds even though the list changed. Tagged pointers (storing a 16-bit incrementing counter alongside the pointer) prevent the ABA problem.

Try It Yourself (Interactive Editor)

Modify the code in real-time and click Run to test live browser output and console logs.

Intelligent Code Runner & Live Sandbox[JAVASCRIPT]
JAVASCRIPT SOURCE EDITOR
Interactive Live Code

Common Mistakes & How to Avoid Them

#1: Assuming lock-free algorithms are always faster than mutex locks for low-contention single-threaded workloads.

Under zero contention, simple sequential data structures are faster due to lack of memory barrier instructions. Lock-free shines under concurrent thread contention.

Incorrect / Antipattern
// Using complex CAS retry loops on thread-confined collections
Correct / Professional Solution
// Use lock-free structures specifically when multiple threads contend concurrently

Industry Best Practices & Professional Standards

  • Use tagged/versioned pointers (`AtomicStampedReference` in Java) to eliminate the ABA problem.
  • Use helping mechanisms so lagging threads do not block forward progress of active threads.
  • Rely on battle-tested standard libraries (`ConcurrentLinkedQueue`, `crossbeam::queue`) in production.

Lesson Summary & Core Takeaways

  • Lock-free algorithms guarantee system-wide forward progress using hardware atomic CAS instructions.
  • The Michael-Scott Queue provides high-concurrency FIFO buffering without mutex locks.
  • Tagged pointers and epoch memory reclamation solve the concurrent ABA problem.