Home▸Algorithms & AI▸Michael-Scott Lock-Free Queue (2D)

Michael-Scott Lock-Free Queue (2D)

2D visualization of the Michael-Scott lock-free FIFO queue: watch concurrent threads race compare-and-swap operations on a shared linked list, with real CAS successes, failures and retries — no locks required.

Algorithms & AI2DAdvanced60 FPS📱 Mobile-adapted⇄ 3D version

This 2D companion runs the same real Michael-Scott linked-list queue as the 3D version, drawn as a flat node chain instead of a rotating scene: several colored thread markers hover over the head or tail pointer depending on whether they're enqueueing or dequeueing, each one caching the shared pointer it reads before attempting a compare-and-swap, and flashing red on a genuine CAS failure or green on a genuine commit — with the underlying queue, pointers and retry counter all driven by the actual algorithm rather than a scripted animation.

⚙ Under the hood

2D Michael-Scott lock-free queue lab: real singly-linked-list state, real compare-and-swap emulation per thread, and a live CAS-retry / queue-length readout.

concurrencylock-freedata-structuresalgorithmscompare-and-swapmultithreading

2D · HTML5 Canvas 2D · 60 FPS target · runs fully client-side, no install

What does this simulation show?

It shows the Michael-Scott lock-free FIFO queue algorithm: several threads race to enqueue and dequeue nodes on a shared singly-linked list using only atomic compare-and-swap (CAS) operations, with no locks.

What is a CAS retry?

A compare-and-swap retry happens when a thread's cached copy of the head or tail pointer no longer matches the live shared value because another thread updated it first; the thread must re-read the shared state and try again.

Why does the tail pointer sometimes lag behind the last node?

The Michael-Scott algorithm allows the shared tail pointer to be stale by exactly one node; any thread that notices this helps swing it forward before continuing its own operation, which is what lets the queue avoid ever needing a lock.