Process Synchronization

Why Synchronization?

Cooperating processes that share data can produce wrong results if not synchronized. A classic example: two threads increment a counter concurrently; the final value may be less than expected because the read-modify-write is not atomic.

Race Condition

A race condition occurs when the outcome of concurrent execution depends on the unpredictable interleaving of threads. Synchronization prevents races by ensuring that critical sections execute atomically.

Critical Section Problem

A critical section is a block of code that accesses shared data. A solution must satisfy three properties:

• Mutual exclusion — only one process in the critical section at a time.
• Progress — if no one is in the CS, one of those wanting to enter must be chosen.
• Bounded waiting — a finite number of other processes can enter between a request and grant.

Peterson's Algorithm

A software solution for two processes:

boolean flag[2];
int turn;
// Process i
flag[i] = true;
turn = j;
while (flag[j] && turn == j) ; // busy wait
// critical section
flag[i] = false;

Peterson's algorithm works only if memory reads/writes are sequentially consistent.

Hardware Support

Modern CPUs provide atomic instructions:

• Test-and-set — atomically set a flag and return its old value.
• Compare-and-swap (CAS) — set a value only if it equals an expected value.

These instructions build higher-level primitives.

Semaphores

A semaphore is an integer with two atomic operations:

• wait(S) (P): while (S <= 0) block; S--;
• signal(S) (V): S++; wake a blocked process;

A binary semaphore (0 or 1) acts as a mutex lock. A counting semaphore counts available resources.

semaphore mutex = 1;
// each process
wait(mutex);
// critical section
signal(mutex);

Monitors

A monitor is a higher-level construct: a module whose methods are automatically mutually exclusive. Condition variables inside a monitor support wait() and signal() for finer coordination. Languages like Java use synchronized and wait/notify to implement monitors.

Classic Synchronization Problems

Producer-Consumer (Bounded Buffer)

Producer fills a buffer, consumer empties it. Use three semaphores: mutex, empty (count of empty slots), full (count of filled slots).

Readers-Writers

Many readers can read simultaneously, but a writer needs exclusive access. Variants: first-readers (readers preferred), first-writers (writers preferred, avoid starvation).

Dining Philosophers

Five philosophers sit around a table; each needs two chopsticks to eat. Naive solution causes deadlock (everyone picks the left first). Solutions: allow only four to try at once; ensure odd philosophers pick right first; use a monitor with conditions.

Sleeping Barber

A barber sleeps when there are no customers; customers either get haircut, wait in chairs, or leave if no chairs free. Solved with three semaphores.

Deadlock vs Starvation

Synchronization can cause:

• Deadlock — all processes wait forever.
• Starvation — some processes wait indefinitely while others proceed.
• Priority inversion — a high-priority task waits for a low-priority one holding a lock.

Summary

Process synchronization is central to correct multiprogramming. Semaphores, monitors, and hardware primitives give the tools; the classic problems (producer-consumer, readers-writers, dining philosophers) are templates you will meet in real systems.

Important Questions

1. What is a race condition? Give an example.
2. State the three conditions for a critical-section solution.
3. Explain Peterson's algorithm.
4. Define semaphore. Differentiate binary and counting semaphores.
5. Solve the producer-consumer problem using semaphores.
6. State the readers-writers problem.
7. Explain the dining philosophers problem. How is deadlock avoided?
8. What is a monitor? How does it differ from a semaphore?