Implement a Semaphore Using Futex

Topic Overview

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.

Your Task

Model a counting semaphore built on a futex, the way glibc builds one. sem_wait first tries a fast path in user space (an atomic decrement when the value is positive). Only when the value is 0 does it make the futex_wait(&value, 0) system call. The kernel re-checks that the value is still 0 before it puts the thread to sleep, which is what prevents lost wakeups. sem_post increments the value and calls futex_wake(1) only if somebody is asleep. The input is an explicit interleaving of thread operations, so you can replay exactly the races that make this design necessary.

Input

cCopy
Loading…

Threads are created by name on first use.

Rules

A thread that is preparing, asleep or woken cannot wait, trywait or post, and prints T: busy (...) or T: busy, cannot post. futex on a thread that is not preparing prints T: nothing to do (not preparing futex_wait), run on a thread that is not woken prints T: not woken, and an unknown operation prints T: unknown operation X.

Output

cCopy
Loading…

The busy messages are (asleep in futex_wait), (woken, must run first) and (preparing futex_wait). state lists sleepers in queue order and the other groups in order of first appearance. The statistics line is always printed last. A successful trywait prints T: trywait succeeded, value N and counts as a fast-path acquisition.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Keep the user-space value and the kernel's sleep queue separate. Only futex and post touch the queue, and only futex performs the compare.
2. A woken thread must re-check the value. Being woken is only a hint, not a guarantee that the value is still available.

Hidden tests cover several sleepers woken in FIFO order, stolen wakeups, the lost-wakeup window where a post lands between wait and futex, trywait both ways, busy threads, futex/run at the wrong time, and unknown operations.