~/problems
Problems
Basics first, then the classics, then company-style assessments. Every problem has tests you run right here; multi-level ones unlock as you go. See the roadmap.
Reader-writer and modal locks
Many readers or one writer; fairness so writers don't starve.
Notes
Recognise it when: many readers and occasional writers share data; "shared vs exclusive" modes; lock modes that can coexist (a mode-compatibility matrix).
class RWLock:
def __init__(self):
self.cond = threading.Condition()
self.readers = 0
self.writer = False
self.waiting_writers = 0
def acquire_read(self):
with self.cond:
# Writer preference: new readers wait while a writer is queued.
self.cond.wait_for(lambda: not self.writer and self.waiting_writers == 0)
self.readers += 1
def release_read(self):
with self.cond:
self.readers -= 1
if self.readers == 0:
self.cond.notify_all()
def acquire_write(self):
with self.cond:
self.waiting_writers += 1
self.cond.wait_for(lambda: not self.writer and self.readers == 0)
self.waiting_writers -= 1
self.writer = True
def release_write(self):
with self.cond:
self.writer = False
self.cond.notify_all()
Fairness: reader preference starves writers, and writer preference starves readers. FIFO fairness means a ticket number or a queue of waiters, where each waiter proceeds only when it's at the front and compatible with the current holders.
Gotchas: notify_all after every release, releasing exactly as many times as you acquired, and upgrading a read lock to a write lock deadlocks if two readers try it at once.
3 problems
Concurrency
Locks Mutexes, lock ordering, readers and writers.
Reader-writer and modal locks
- Basics: a simple reader-writer lock basics easy
- Timetable board: writers go first easy
- ModalLock and FairModalLock 3 levels OpenAI hard