Home▸Algorithms & AI▸The Michael-Scott Lock-Free Queue

🔗 The Michael-Scott Lock-Free Queue

Explore how the Michael-Scott algorithm builds a thread-safe FIFO queue from a singly linked list using only atomic compare-and-swap operations, no locks required.

Algorithms & AI3DModerate60 FPS

The simulator visualizes multiple threads racing to enqueue and dequeue nodes on a shared linked list, showing each compare-and-swap attempt, its success or failure, and the moment the tail pointer lags one node behind reality until another thread helps advance it.

🔬 What It Demonstrates

🎮 How to Use

Add threads and trigger enqueue or dequeue operations, then step through execution one atomic instruction at a time to watch the head and tail pointers, the linked list structure, and each compare-and-swap outcome update in real time.

💡 Did You Know?

The tail pointer in a Michael-Scott queue is allowed to be stale by exactly one node at any moment, and every operation is written to detect and repair that staleness opportunistically, which is precisely what lets the algorithm avoid ever needing a lock.

⚙ Under the hood

Explore how the Michael-Scott algorithm builds a thread-safe FIFO queue from a singly linked list using only atomic compare-and-swap operations, no locks required.

concurrencylock-freedata-structuresalgorithmscompare-and-swapmultithreadingqueuescomputer-science

3D · Three.js / WebGL renderer · 60 FPS target · runs fully client-side, no install