ReadyToGo Logo ReadyToGo
Login Sign Up
› Module 4: Process Synchronization › 4.4 Classical Synchronization Problems
M O D U L E

Module 4: Process Synchronization

Critical sections, Peterson's algorithm, semaphores, and classical problems

4.1 The Critical Section Problem

When concurrent cooperating processes or threads share mutable state (memory, global variables, file handles), unsynchronized simultaneous access can produce inconsistent, corrupt outcomes — a flaw known as a race condition. The region of code that accesses shared resources is designated the Critical Section.

Figure 4.1: General Structure of a Process with Critical Section Safeguards Entry Section ← Requests permission to enter critical section Critical Section ← Accesses & mutates shared variables (MUTEX REQUIRED!) Exit Section ← Releases lock, signals other waiting processes Remainder Section ← Unshared local computation loop

Figure 4.1: Every process follows this four-part structure to ensure mutually exclusive access to shared variables.

The Three Mandatory Solution Criteria

A mathematically sound solution to the critical-section problem must satisfy three strict requirements:

  1. Mutual Exclusion: If process $P_i$ is executing in its critical section, no other process can be executing in its critical section on the same shared data.
  2. Progress: If no process is in its critical section and some processes wish to enter, only those processes not executing in their remainder sections can participate in deciding who enters next. This selection cannot be postponed indefinitely (no livelock/deadlock).
  3. Bounded Waiting: There must exist a bound or limit on the number of times other processes are allowed to enter their critical sections after a process has registered a request to enter, before that request is granted (prevents indefinite starvation).

4.2 Peterson's Solution

Peterson's Solution is a classic, software-based synchronization algorithm designed for two concurrent processes ($P_0$ and $P_1$). It brilliantly satisfies Mutual Exclusion, Progress, and Bounded Waiting using only two shared variables without requiring dedicated hardware instructions.

Figure 4.2: Peterson's Solution Architecture for Processes P0 and P1 shared: boolean flag[2] = {F, F}; int turn; Process P0 Code flag[0] = true; // I want to enter turn = 1; // You go first while (flag[1] && turn == 1); // wait << CRITICAL SECTION >> flag[0] = false; Process P1 Code flag[1] = true; // I want to enter turn = 0; // You go first while (flag[0] && turn == 0); // wait << CRITICAL SECTION >> flag[1] = false; Guarantees Mutual Exclusion, Progress, and Bounded Waiting

Figure 4.2: Each process indicates interest via its flag, politely yields turn to the other, and only proceeds when either the other process is uninterested or it is its turn.

Proof of Correctness

  • Mutual Exclusion: For both $P_0$ and $P_1$ to be in their critical sections simultaneously, both flag[0] == true and flag[1] == true must hold, AND turn must be both 0 and 1 at the same instant — a mathematical impossibility.
  • Progress & Bounded Waiting: If $P_1$ is not in its critical section, flag[1] is false, so $P_0$ enters immediately. If both want to enter, the last value assigned to turn determines who waits; once the current process exits and sets its flag to false, the waiting process immediately enters.

4.3 Semaphores

A semaphore $S$ is a protected integer synchronization tool introduced by Edsger Dijkstra. Except for initialization, a semaphore is accessed strictly through two standard atomic, indivisible operations: wait(S) (historically $P(S)$) and signal(S) (historically $V(S)$).

Figure 4.3: Producer-Consumer (Bounded Buffer) Synchronized with Three Semaphores PRODUCER wait(empty); wait(mutex); // add item to buffer signal(mutex); signal(full); BUFFER (Shared, Fixed Size N) Slots: [D1][D2][ ][ ] CONSUMER wait(full); wait(mutex); // remove item from buf signal(mutex); signal(empty); Semaphore mutex = 1 (Mutex); Semaphore empty = N; Semaphore full = 0 wait(S): while(S <= 0); S--; | signal(S): S++;

Figure 4.3: Binary semaphore mutex guards the buffer from simultaneous writes; counting semaphores empty and full track available slots.

Types of Semaphores

  • Binary Semaphore (Mutex): The integer value can only be 0 or 1. Used to guarantee mutual exclusion in critical sections.
  • Counting Semaphore: The integer value can span an unrestricted positive range. Used to coordinate access to a finite pool of identical resource instances (e.g. tracking $N$ empty slots).

4.4 Classical Synchronization Problems

Computer science researchers rely on classic synchronization scenarios to test and benchmark new concurrency, locking, and deadlock-freedom primitives. The three most celebrated are Bounded-Buffer, Readers-Writers, and Dining Philosophers.

Figure 4.4: The Dining Philosophers Problem — Shared Circular Table and 5 Forks Shared Table Phil 0 Phil 1 Phil 2 Phil 3 Phil 4 Fork 0 Fork 1 Fork 2 Fork 3 Fork 4 Asymmetric Solution: Odd philosophers pick left fork first; even pick right fork first to avoid circular deadlock

Figure 4.4: Five philosophers require two adjacent forks to eat. If all simultaneously pick up their left fork, a circular wait deadlock halts the system.

The Three Classical Scenarios

  • Bounded-Buffer (Producer–Consumer) Problem: Producer and consumer share a buffer of size $N$. Producers must block when buffer is full; consumers must block when buffer is empty. Solved with mutex and counting semaphores.
  • Readers–Writers Problem: A database is shared among reader and writer processes. Multiple readers can read simultaneously without interference; writers require exclusive access.
    • First Readers-Writers (Reader Priority): No reader is kept waiting unless a writer has already secured permission. Can cause writer starvation.
    • Second Readers-Writers (Writer Priority): Once a writer is ready, no new readers may start reading. Can cause reader starvation.
  • Dining Philosophers Problem: Models allocation of multiple shared resources among competing processes without deadlock or starvation. Naive symmetric code deadlocks. Standard solutions:
    1. Allow at most 4 philosophers to sit at the table of 5 chairs simultaneously.
    2. An asymmetric approach: Odd philosophers pick up left fork then right; even philosophers pick up right fork then left.
MODULE COMPREHENSIVE QUIZ

Module 4 Final Quiz

Test your understanding across all 4 topics of this module with interview-grade questions, tricky edge cases, and code output predictions.

Take Module 4 Final Quiz →
ReadyToGo · Operating Systems Study Guide
Yukti Mascot