Implement a Semaphore Using Futex

Counting Access

Semaphores generalize mutexes with a counter: wait() decrements (blocking at zero) and post() increments, potentially waking waiters. Kernel semaphores exist, but Linux user-space pthread primitives often sleep on futexes tied to an int guard variable.

Futex Wait/Wake

Fast path when counter > 0:

• Decrement counter atomically and return
• Slow path: FUTEX_WAIT if zero, FUTEX_WAKE on post

For example, a pool of 4 identical buffers uses a semaphore initialized to 4. Each producer wait() consumes a slot; each consumer post() returns one.

Why This Matters in Production

Linux's futex(2) syscall, introduced in kernel 2.5.7, is the mechanism glibc's sem_t and pthread_mutex_t are built on today precisely because it avoids a syscall on the uncontended fast path, which is why futex-based locks vastly outperform SysV semaphores under light contention. This same primitive underlies Rust's parking_lot and Java's LockSupport.park(), and the spurious-wakeup handling you implement here is required by the futex(2) man page itself.

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 sem_wait and sem_post with syscall(SYS_futex, ...) for blocking. Understanding the futex contract matters because incorrect waiter counts produce lost wakeups that TSan cannot see.