LC

Implement Lock-Free Queue (Michael-Scott Queue)

hard4/8

Fix ABA Problem Using Stamped Reference or Hazard Pointers Implement SPSC Lock-Free Queue (Single Producer Single Consumer)

Language

Compiler

2.0s Limit 256MB

Implementation

Implement Michael-Scott lock-free queue.

Requirements:

Define Node structure with atomic next pointer
Define Queue structure with head and tail
Implement queue_init() with dummy node
Implement enqueue() with CAS loop and helper pattern
Implement dequeue() with consistency checks
Handle empty queue condition
Use proper memory ordering
Test with multiple producers/consumers
Compare with mutex-based implementation
Demonstrate lock-free property

Why This Matters

The Michael-Scott queue from their 1996 PODC paper is the reference algorithm cited by java.util.concurrent.ConcurrentLinkedQueue's own source comments and by Boost.Lockfree, making it the most-implemented lock-free structure in production concurrency libraries. Its helping pattern, where a stalled thread's peers finish its work for it, is the technique that lets it guarantee system-wide progress even when individual threads are descheduled by the OS.

Hints

0 / 3 revealed

Validation Suite

main.c

Workspace 1.0