Process Synchronization (Semaphores & Mutex)

The problem: shared data

Threads and processes often share data — a counter, a buffer, a bank balance. Even a tiny statement like count++ is really three machine steps:

register ← count
register ← register + 1
count ← register

If the OS switches between two threads in the middle, both may read the same old value and one update is lost. The result depends on timing — a race condition. Play the race in the 3D model to see it happen.

Critical sections

The code that touches shared data is a critical section. A correct solution must guarantee:

1. Mutual exclusion — at most one process inside at a time.
2. Progress — if nobody is inside, a waiting process can enter.
3. Bounded waiting — no process waits forever.

Tools

Mutex lock

A mutex (mutual exclusion lock) has two operations: lock() and unlock(). Only the thread holding the lock may enter. Others wait.

lock(mutex)
count++              // critical section
unlock(mutex)

Semaphore

A semaphore is an integer counter with two atomic operations (Dijkstra called them P and V):

wait(S):    while S ≤ 0: sleep          signal(S):  S ← S + 1
            S ← S − 1                               wake up one waiting process

• A binary semaphore (0 or 1) works like a mutex.
• A counting semaphore counts available resources — e.g. free slots in a buffer.

The producer–consumer (bounded buffer) problem

A producer puts items into a buffer of N slots; a consumer removes them. We must ensure:

• the producer doesn’t add to a full buffer,
• the consumer doesn’t take from an empty buffer,
• they never modify the buffer at the same time.

Three semaphores solve it:

semaphore empty = N     // free slots
semaphore full  = 0     // filled slots
semaphore mutex = 1     // protects the buffer

producer:                     consumer:
  wait(empty)                   wait(full)
  wait(mutex)                   wait(mutex)
  buffer[in] ← item             item ← buffer[out]
  in ← (in + 1) mod N           out ← (out + 1) mod N
  signal(mutex)                 signal(mutex)
  signal(full)                  signal(empty)

Order matters! If the producer did wait(mutex) before wait(empty) on a full buffer, it would sleep while holding the lock — the consumer could never get in to free a slot. That’s a deadlock.

Code

import threading, time, random

N = 5
buffer = [None] * N
inp = out = 0
empty = threading.Semaphore(N)
full = threading.Semaphore(0)
mutex = threading.Lock()

def producer():
    global inp
    for item in range(10):
        empty.acquire()               # wait(empty)
        with mutex:                   # wait(mutex) ... signal(mutex)
            buffer[inp] = item
            inp = (inp + 1) % N
        full.release()                # signal(full)
        time.sleep(random.random() / 10)

def consumer():
    global out
    for _ in range(10):
        full.acquire()                # wait(full)
        with mutex:
            item = buffer[out]
            out = (out + 1) % N
        empty.release()               # signal(empty)
        print("consumed", item)

t1, t2 = threading.Thread(target=producer), threading.Thread(target=consumer)
t1.start(); t2.start(); t1.join(); t2.join()

Other classic problems

• Readers–writers: many readers may read together, but writers need exclusive access.
• Dining philosophers: five philosophers, five forks — a famous deadlock and starvation puzzle.
• Sleeping barber: customers, a waiting room and one barber.

Common mistakes

• Forgetting to unlock on every path (use with blocks / RAII).
• Taking two locks in different orders in different threads → deadlock.
• Using a mutex where a counting semaphore is needed (or vice versa).