Implement Mutex Using Compare-And-Swap (CAS)

Locking Without Kernel Help

A mutex guarantees mutual exclusion around a critical section. User-space locks on Linux often bottom out in a futex, but the fast path is a single atomic compare-and-swap on a locked word. If CAS succeeds, you never enter the kernel.

CAS Mutex Pattern

Typical spin-then-block flow:

• Try lock: CAS(&lock, 0, 1) succeeds if uncontended
• Spin: brief pause loop for short holds
• Park: futex wait if still locked

For example, two threads incrementing a counter without a lock may end at 998 instead of 1000 after 1000 adds; with CAS guarding the increment, the result is exact.

Why This Matters in Production

The lock cmpxchg instruction you use here is the literal foundation of glibc's pthread_mutex_t fast path and every lock-free data structure in Java's java.util.concurrent.atomic package. Getting this wrong is not academic: unsynchronized read-modify-write on a shared counter is the textbook race condition behind real production bugs, from lost e-commerce inventory decrements to double-spend bugs in early cryptocurrency wallet code.

Debugging Checklist

Before you call the implementation done, walk failure modes on purpose. Test empty structures, single-element edge cases, maximum concurrency, and errno paths that must not crash the program. OS code usually fails in production when happy-path tests pass but invariants break under contention or memory pressure.

Implementation Notes

Keep structures small and name fields after kernel counterparts when possible. That lets you read man pages and kernel source side by side while you work. Print observable events during development; remove noisy logs once tests pass reliably.

For This Exercise

You will implement mutex_lock and mutex_unlock using GCC __sync_bool_compare_and_swap or C11 atomics. This exercise requires you to demonstrate the race without the lock, then fix it, mirroring how pthread_mutex documents its fast path.