Implement a Mutual-Exclusion Lock Without Built-In Locks

Implement a lock: a mutual-exclusion primitive with `lock()` and `unlock()`. You may not call any existing lock, mutex, semaphore, monitor or condition variable from the language or a library; the point is to build one. After the implementation, expect fundamentals questions about what your lock relies on in the hardware and the operating system. ```text Lock() lock() -> None # returns once the calling thread holds the lock unlock() -> None # releases the lock; only the holder calls it ``` ```hint The race in check-then-take Consider what goes wrong if two threads both see the lock as free before either marks it as taken, and what would make checking and taking a single indivisible step. ``` ```hint What waiters do with their time Once the lock is correct, think about what a waiting thread does with its CPU while the holder is running, or while the holder has been descheduled. ``` ### Constraints and Clarifications - At most one thread may hold the lock at any time. - If the lock is free and threads are trying to take it, one of them must eventually succeed. - Writes made inside one critical section must be visible to the next thread that acquires the lock. ### Clarifying Questions - Which atomic operations may I assume: compare-and-swap, test-and-set, fetch-and-add, or only ordinary loads and stores? - Is the number of threads fixed and known (for example, exactly two), or arbitrary? - Should waiting threads spin or sleep? If they sleep, may I use a low-level operating-system wait and wake facility, as long as it is not itself a lock? - Must the lock be fair (first come, first served)? Must it be reentrant? - Which language and memory model? ### What a Strong Answer Covers - An acquire built on one atomic read-modify-write, and why a separate load and store are racy - Memory ordering: acquire semantics on `lock()` and release semantics on `unlock()`, against both compiler and CPU reordering - Spinning strategy and its costs: cache-line traffic, backoff, a descheduled holder - Sleeping waiters handed to the operating system without lost wakeups - Properties: mutual exclusion, progress, fairness or starvation, reentrancy, unlock by a non-owner - A software-only algorithm when no atomic read-modify-write exists, and its memory-model caveats ### Follow-up Questions - Make the lock first come, first served. What does that cost when many cores contend? - Make it reentrant, so that the holder can call `lock()` again without deadlocking itself. - Make waiting threads sleep instead of spin. How do you avoid a wakeup that is lost between deciding to sleep and actually sleeping? - Without atomic read-modify-write instructions, how can two threads still achieve mutual exclusion, and why does that algorithm fail on modern processors without extra fences?