Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Notes › Operating Systems

Process Synchronization — Mutex and Semaphore

When processes or threads share data, the result can depend on the order they run in — a race condition. Synchronization makes sure shared data stays correct.

Race condition example

Two threads run count = count + 1 (read → add → write) at the same time, starting from 5:

T1 reads 5        T2 reads 5
T1 writes 6       T2 writes 6      → final 6, expected 7

The critical section problem

The critical section is the code that touches shared data. A correct solution must give:

  1. Mutual exclusion — at most one process in the critical section.
  2. Progress — if nobody is inside, a waiting process can enter without endless delay.
  3. Bounded waiting — a process can't be overtaken forever (no starvation).
entry section      ← ask permission
  critical section
exit section       ← release
  remainder section

Peterson's solution (2 processes, software only)

// shared: bool flag[2]; int turn;
flag[i] = true;            // I want to enter
turn = j;                  // but you go first if you want
while (flag[j] && turn == j);   // busy wait
/* critical section */
flag[i] = false;

Meets all three conditions — but modern CPUs reorder memory operations, so real systems use hardware instructions (test-and-set, compare-and-swap) instead.

Mutex (lock)

A binary lock with an owner: only the thread that locked it can unlock it.

pthread_mutex_lock(&m);
count++;                   // critical section
pthread_mutex_unlock(&m);

Semaphore

An integer S changed only by two atomic operations:

Type Initial value Use
Binary semaphore 1 mutual exclusion (like a lock)
Counting semaphore N N identical resources (N printers, a pool of N connections)

Mutex vs semaphore

Mutex Semaphore
Value locked / unlocked integer
Ownership yes — the locker unlocks no — any thread can signal
Purpose mutual exclusion mutual exclusion and signalling / counting
Example protect a shared counter limit 3 threads to a resource; producer tells consumer "item ready"

Classic problems

Producer–consumer (bounded buffer of size N)

semaphores: mutex = 1, empty = N, full = 0
producer: wait(empty); wait(mutex); add item; signal(mutex); signal(full);
consumer: wait(full);  wait(mutex); take item; signal(mutex); signal(empty);

Doing wait(mutex) before wait(empty) can deadlock — order matters.

Readers–writers: many readers may read together, a writer needs exclusive access. A simple solution can starve writers.

Dining philosophers: 5 philosophers, 5 forks; each needs two forks. If all pick up the left fork first → deadlock. Fixes: one philosopher picks the right fork first, allow only 4 to sit, or pick both forks atomically.

Monitors and condition variables

A monitor (Java synchronized, C++ std::mutex + std::condition_variable) bundles the lock with the data; condition variables let a thread wait() until another signal()s that a condition changed.

Busy waiting vs blocking

Interview one-liners

More Operating Systems notes