Synchronisation, critical sections and semaphores
45 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)"Two threads increment a counter. What can go wrong, and how do you fix it?" is a standard OS and Python question. The interviewer is checking that you can name the race, the critical section and the right tool.
Race condition example and the critical-section problem
Race condition is a bug where the result depends on the timing of two threads that use the same shared data, and at least one of them writes it.
The program below replays one bad timing by hand: two booking threads both read that one train seat is left, and both book it.
Example 1 · A lost update, step by step
seats = 1 # one seat left on the train
# Two booking threads, A and B, each run: read, check, write.# We replay one bad interleaving by hand.a_read = seatsb_read = seatsif a_read > 0: seats = a_read - 1print("A booked, seats now", seats)if b_read > 0: seats = b_read - 1print("B booked, seats now", seats)print("Tickets sold: 2 for 1 seat")A booked, seats now 0 B booked, seats now 0 Tickets sold: 2 for 1 seat
What this code does
- B read the value before A wrote it, so B's check used a stale value. Both bookings succeed and the seat is sold twice.
- The fix is to make read-check-write one indivisible critical section, so B cannot read until A has finished.
count += 1 looks like one step but is three: load count, add 1, store it back. The GIL lets only one thread run bytecode at a time, but it can switch threads between those steps. If two threads both load 5 before either stores, both store 6 and one increment is lost.
The critical section is the part of code that touches the shared data. The critical-section problem is designing an entry and exit protocol so threads take turns inside it. Race conditions are timing bugs: a program may pass a hundred runs and fail on the hundred-and-first.
Order of execution
A lost update
Two threads run count++ with count = 5. Put the unlucky timing in order.
Mutual exclusion, progress and bounded waiting
Mutual exclusion means at most one process or thread is inside the critical section at any moment; it is the first of the three requirements.
Any correct solution to the critical-section problem must meet three requirements. Peterson's idea for two processes is shown below, followed by a program that gets mutual exclusion with a threading.Lock and, as the other fix, with no shared writes.
# Peterson's solution for two processes i and j (classic textbook idea)flag[i] = True # I want to enterturn = j # but you may go firstwhile flag[j] and turn == j: pass # wait# critical sectionflag[i] = False # exitExample 2 · Fixing a race with a Lock and with no sharing
import threading
locked_count = 0lock = threading.Lock()
def with_lock(): global locked_count for _ in range(100_000): with lock: # entry section locked_count += 1 # critical section: leaving the block is the exit section
def on_its_own(results, slot): mine = 0 # nothing shared is written inside the loop for _ in range(100_000): mine += 1 results[slot] = mine
threads = [threading.Thread(target=with_lock) for _ in range(2)]for t in threads: t.start()for t in threads: t.join()
results = [0, 0]threads = [threading.Thread(target=on_its_own, args=(results, i)) for i in range(2)]for t in threads: t.start()for t in threads: t.join()
print("lock count: ", locked_count)print("own counters: ", sum(results))lock count: 200000 own counters: 200000
What this code does
with lock:gives mutual exclusion: only one thread at a time runslocked_count += 1, so no update is lost and the result is always 200000. The GIL alone would not promise this, because it can switch threads between the load, add and store.- Python has no atomic integer. The other fix is to share nothing: each thread counts in its own variable and the main thread adds the results after
join(). Without either fix, the total can come out below 200000.
The three requirements interviewers ask for by name:
- Mutual exclusion: at most one process is in the critical section at a time.
- Progress: if no one is inside and some want to enter, one of them must be chosen soon; processes not trying to enter cannot block the choice.
- Bounded waiting: after a process asks to enter, there is a limit on how many times others can enter before it.
Hardware helps with atomic instructions such as test-and-set and compare-and-swap; in Python that means threading.Lock, Semaphore and the thread-safe queue.Queue, which the interpreter builds on the operating system's own locks.
Fix the error
Fix the lock
Each snippet fails when it runs. Pick the line that fixes it.
Round 1 of 2
A thread-safe counter that locks on a shared object.
Error
TypeError: 'int' object does not support the context manager protocol
Mutex vs binary vs counting semaphore
Semaphore is an integer changed only by two atomic operations, wait (P) and signal (V); a counting semaphore starts at N and lets up to N threads use a resource.
The program below lets eight students share three lab printers through a counting semaphore, and checks that never more than three print at once.
Example 3 · A counting semaphore for 3 lab printers
import threadingimport time
printers = threading.Semaphore(3) # 3 printersin_use = 0max_seen = 0stats = threading.Lock()
def student(): global in_use, max_seen with printers: # wait (P) on entry, signal (V) on exit with stats: in_use += 1 max_seen = max(max_seen, in_use) time.sleep(0.02) # printing with stats: in_use -= 1
students = [threading.Thread(target=student) for _ in range(8)]for t in students: t.start()for t in students: t.join()
free = 0while printers.acquire(blocking=False): # count the permits left free += 1print("8 students printed")print("Never more than 3 at once:", max_seen <= 3)print("Free printers at the end:", free)8 students printed Never more than 3 at once: True Free printers at the end: 3
What this code does
with printers:is wait on entry (it takes a permit, or blocks when all 3 are taken) and signal on exit (it returns the permit and wakes a waiting thread).- Eight students share three printers, and the check proves the semaphore never let a fourth one in. All 3 permits are back at the end.
wait (also called P or down) decrements the value and blocks if no permit is left; signal (V or up) increments it and wakes a waiting thread. A binary semaphore only takes the values 0 and 1.
A mutex also allows one user at a time, but it has ownership: only the thread that locked it should unlock it. A semaphore has no owner, so one thread can wait while another signals, which suits signalling between threads.
Predict the output
Permits left
Pick what the semaphore code prints.
Round 1 of 2
A semaphore with 2 permits gets one acquire and two releases. How many non-blocking acquires succeed afterwards?
threading.Semaphore (counting) and threading.Lock or RLock (mutex-style locks). The plain Lock does not check who releases it; RLock does.Producer-consumer and readers-writers at a high level
Producer-consumer is the bounded-buffer problem: producers add items to a buffer of size N and consumers remove them, so producers wait when it is full and consumers when it is empty.
Producers put items into a buffer of size N and consumers take them out. The classic solution uses three semaphores, shown below and in the program after it.
Producer: Consumer: wait(empty) wait(full) wait(mutex) wait(mutex) add item to buffer remove item from buffer signal(mutex) signal(mutex) signal(full) signal(empty)Example 4 · Producer-consumer with three semaphores
import threadingfrom collections import deque
SIZE = 2buffer = deque()empty = threading.Semaphore(SIZE) # free slotsfull = threading.Semaphore(0) # filled slotsmutex = threading.Semaphore(1) # protects buffer
def producer(): for order in range(1, 6): empty.acquire() with mutex: buffer.append(order) full.release()
def consumer(): for _ in range(5): full.acquire() with mutex: order = buffer.popleft() empty.release() print("Warehouse packed order", order)
p = threading.Thread(target=producer)c = threading.Thread(target=consumer)p.start()c.start()p.join()c.join()print("Buffer empty at the end:", not buffer)Warehouse packed order 1 Warehouse packed order 2 Warehouse packed order 3 Warehouse packed order 4 Warehouse packed order 5 Buffer empty at the end: True
What this code does
empty.acquire()blocks the producer (a web shop taking orders) when 2 orders are waiting;full.acquire()blocks the consumer (the warehouse) when there are none.- Orders come out in the same order they went in, because only the consumer prints and the buffer is FIFO. The order
wait(empty)thenwait(mutex)matters: reversed, the producer could hold the mutex while waiting for space, and the consumer could never get in. In everyday Python,queue.Queue(maxsize=2)does all of this for you:putwaits when it is full andgetwaits when it is empty. In everyday Python,queue.Queue(maxsize=2)does all of this for you:putwaits when it is full andgetwaits when it is empty.
empty starts at N and counts free slots, full starts at 0 and counts filled slots, and mutex starts at 1 and protects the buffer itself. The order wait(empty) then wait(mutex) matters: reversed, a producer could hold the mutex while waiting for space, and the consumer could never get in.
Readers-writers: many readers may read at the same time, but a writer needs the data alone. The first version favours readers, so writers can starve; the standard library has no readers-writers lock, so you build one from threading.Condition. Dining philosophers is the third classic, used to show deadlock. In everyday Python, queue.Queue(maxsize=N) is the ready-made producer-consumer buffer.
Order of execution
The producer for one item
Put the producer's steps for one item in the safe order.
Interview questions with model answers
Synchronisation questions test whether you can name the problem, the three requirements and the right tool. Expect follow-ups such as "Why can a binary semaphore not always replace a mutex?".
- Must say: a race condition is a timing-dependent result on shared data.
- Must say: the three requirements are mutual exclusion, progress and bounded waiting.
- Must say: wait (P) decrements and may block; signal (V) increments and may wake.
- Must say: a mutex has an owner; a semaphore has none.
Find the bug
Weak spoken answers
Each spoken answer has one wrong sentence. Click it.
Answer to "Mutex vs semaphore?"
Round 1 of 2Next step
Check your understanding
12 quick questions