Synchronization: Mutex and Semaphores

The Bathroom Lock Problem

Imagine an office with one bathroom. Two colleagues — Alice and Bob — both need to use it at the same time. Without a lock on the door, they walk in simultaneously. Chaos ensues. Embarrassment guaranteed.

Now put a lock on the door. Alice enters, flips the lock. Bob arrives, sees the locked door, and waits outside. Alice finishes, unlocks the door, and Bob enters. Problem solved.

This is exactly what synchronization does for shared data in an operating system. Multiple processes or threads compete for shared resources — a variable, a file, a database record. Without proper locking, they corrupt each other's work. Mutex and semaphores are the locks that bring order to this chaos.

Why Synchronization Exists

Modern operating systems run many processes and threads concurrently. When two threads share data and at least one of them writes, the outcome depends on the precise timing of their execution. This is called a race condition.

Thread A: balance = balance + 100   (reads 1000, adds 100)
Thread B: balance = balance - 50    (reads 1000, subtracts 50)
Final:    balance = 950              (one update is lost!)

The correct result should be 1050. Both threads read the original value before either writes back. One update overwrites the other. This is a race condition — and it is silent, intermittent, and devastating.

The Critical Section Problem

A critical section is any segment of code that accesses shared resources. The critical section problem asks: how do we ensure only one thread executes its critical section at a time?

Three requirements must be satisfied:

Peterson's Solution (Software Approach)

Peterson's Solution is a classic two-process software solution. It uses two variables: flag[] (intent to enter) and turn (whose turn it is).

# Process i wants to enter critical section
flag[i] = True
turn = j                     # yield to the other process
while flag[j] and turn == j: # busy-wait if other wants in and it's their turn
    pass

# --- Critical Section ---

flag[i] = False              # done, release

This satisfies all three requirements for two processes, but it uses busy-waiting (spinning), which wastes CPU cycles. Modern solutions use hardware support or OS primitives.

Mutex: The Binary Lock

A mutex (mutual exclusion lock) is the simplest synchronization primitive. It has two states: locked and unlocked. Only the thread that locked it can unlock it.

Operations:

• acquire() — lock the mutex; block if already locked
• release() — unlock the mutex; wake a waiting thread

import threading

balance = 1000
lock = threading.Lock()

def deposit(amount):
    global balance
    lock.acquire()           # enter critical section
    balance += amount
    lock.release()           # exit critical section

def withdraw(amount):
    global balance
    with lock:               # context manager — auto acquire/release
        balance -= amount

t1 = threading.Thread(target=deposit, args=(100,))
t2 = threading.Thread(target=withdraw, args=(50,))
t1.start(); t2.start()
t1.join(); t2.join()
print(f"Final balance: {balance}")  # Output: Final balance: 1050

The with lock: syntax is preferred — it guarantees release even if an exception occurs.

Semaphore: The Counting Lock

A semaphore is a more powerful synchronization tool. It holds an integer value and supports two atomic operations:

• wait() (also called P() or down()) — decrement; block if value becomes negative
• signal() (also called V() or up()) — increment; wake a blocked thread if any

wait(S):
    S -= 1
    if S < 0: block this process

signal(S):
    S += 1
    if S <= 0: wake a blocked process

Binary Semaphore vs Counting Semaphore

A counting semaphore is useful when you have multiple instances of a resource — for example, a connection pool with 5 database connections.

import threading
import time

# Allow max 3 threads to access a resource simultaneously
semaphore = threading.Semaphore(3)

def access_resource(thread_id):
    semaphore.acquire()
    print(f"Thread {thread_id} accessing resource")
    time.sleep(1)
    print(f"Thread {thread_id} done")
    semaphore.release()

threads = [threading.Thread(target=access_resource, args=(i,)) for i in range(6)]
for t in threads: t.start()
for t in threads: t.join()

# Output (only 3 threads run simultaneously):
# Thread 0 accessing resource
# Thread 1 accessing resource
# Thread 2 accessing resource
# Thread 3 accessing resource  (after one of the first three finishes)
# ...

Classic Synchronization Problems

These three problems are the canonical tests of any synchronization mechanism:

Producer-Consumer Problem

A producer creates data items; a consumer uses them. They share a bounded buffer. The producer must not overfill the buffer; the consumer must not read from an empty buffer.

Solution: Use two semaphores — empty (initially N) tracks empty slots, full (initially 0) tracks filled slots — plus one mutex for buffer access.

Readers-Writers Problem

Multiple readers can read simultaneously, but a writer needs exclusive access. The challenge: prevent starvation of writers when readers continuously arrive.

Solution: Track active readers with a counter protected by a mutex. The first reader locks out writers; the last reader unlocks access for writers.

Dining Philosophers Problem

Five philosophers sit around a table with five chopsticks between them. Each needs two chopsticks to eat. If all grab their left chopstick simultaneously, no one can grab their right — deadlock.

Solution: Limit diners to four simultaneously, or impose a global ordering on chopstick acquisition.

Deadlock from Bad Synchronization

Incorrect use of locks creates deadlock — a state where processes wait for each other forever.

lock_a = threading.Lock()
lock_b = threading.Lock()

def thread1():
    lock_a.acquire()   # holds A
    lock_b.acquire()   # waits for B (held by thread2)

def thread2():
    lock_b.acquire()   # holds B
    lock_a.acquire()   # waits for A (held by thread1)
    # DEADLOCK: both threads wait forever

Prevention: always acquire locks in the same global order across all threads.

Summary

Synchronization is the foundation of correct concurrent programs. Every modern database, web server, and operating system depends on these primitives to protect shared state from corruption.