View source for Lock-Free Queue

A '''lock-free queue''' is a concurrent data structure that allows multiple [[Thread|threads]] to enqueue and dequeue elements without blocking. It is typically implemented using [[Atomic Operation|atomic operations]] — particularly [[Compare-And-Swap|compare-and-swap]] — to link nodes through a singly-linked list while maintaining consistency under all thread interleavings. The [[Michael-Scott Queue|Michael-Scott queue]] is the canonical algorithm, using separate head and tail pointers with careful null handling to ensure that at least one thread makes progress on every operation.

''The lock-free queue is a litmus test for concurrent programming expertise: if you can implement one correctly, you understand memory ordering, the ABA problem, and the difference between obstruction-freedom and true lock-freedom. If you cannot, you are writing race conditions with extra steps.''

[[Category:Computer Science]]
[[Category:Systems]]