~/problems / Locks / Reader-writer and modal locks

ModalLock and FairModalLock

hard 3 levels ~70 min OpenAI

Level 1 ModalLock: shared within a mode, exclusive across modes

A frog splits its day between tasks in the "water" and tasks on "land". Many threads run these tasks. Any number of water tasks may run together, and any number of land tasks may run together, but a water task must never overlap a land task.

Build ModalLock with Python's threading primitives (Lock, Condition, ...):

  • acquire(mode) blocks until the calling thread may hold the lock in mode, then returns.
  • release(mode) gives back one hold in mode.

Rules:

  • An idle lock (no holders) can be taken in any mode.
  • While the lock is held in mode M, another acquire(M) succeeds immediately, even if threads of other modes are waiting. This version does not need to be fair.
  • While it is held in M, an acquire of any other mode blocks.
  • When the last holder releases, the lock becomes idle and the blocked threads must be woken. One mode wins, and every thread waiting for that mode gets in (they don't need to take turns).
  • release(mode) on an idle lock, or in a mode the lock isn't held in, raises RuntimeError.
  • Modes are arbitrary hashable values, not just "water"/"land", but never None.
lock = ModalLock()
# thread A: lock.acquire("water")   -> returns at once
# thread B: lock.acquire("water")   -> returns at once (shared)
# thread C: lock.acquire("land")    -> blocks
# thread A: lock.release("water")   -> C still blocked (B holds water)
# thread B: lock.release("water")   -> C returns, lock is now in "land"

The tests drive worker threads step by step and check who holds the lock after each step, check that different modes never overlap, check that same-mode holders really run at the same time, and join every thread with a timeout (a hang is a failure).

FairModalLock (same file) is for the next levels; leave it as a stub for now.

Level 2 unlocks when level 1 passes.

Level 3 unlocks when level 2 passes.

Topic: Reader-writer and modal locks. Many readers or one writer; fairness so writers don't starve.

0:00
Ctrl ' run · Ctrl ↵ submit
esc