Katkat
Back

Implement a Mutual-Exclusion Lock Without Built-In Locks

AppleSoftware Engineer · Onsite
HardSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

Implement a mutual-exclusion lock without any built-in lock, mutex or semaphore, relying only on atomic operations. Tests atomic read-modify-write, memory ordering, spinning versus sleeping waiters, fairness, reentrancy, and software-only mutual exclusion when atomic instructions are unavailable.

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.

Lock()
lock() -> None # returns once the calling thread holds the lock
unlock() -> None # releases the lock; only the holder calls it

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?

Hints

Hint 1

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 2

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.

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?