Process Synchronization: Critical Section Problem, Semaphores & Monitors

1. What is Process Synchronization & Race Condition?

In a multiprogramming or multiprocessing operating system, multiple Cooperating Processes often execute concurrently and share common data (such as a shared bank database, a shared memory buffer, or a printer).

• What is a Race Condition? When two or more processes access and manipulate the same shared data concurrently, and the final value of the shared data depends on the particular order in which the accesses take place, this bug is called a Race Condition.
• What is Process Synchronization? The coordination and sequencing of concurrent processes by the Operating System so that only one process can modify shared data at a time, preventing Race Conditions and ensuring data consistency.

Simple Real-Life Analogy: Imagine IRCTC Tatkal Train Booking where only 1 Lower Berth seat (availableSeats = 1) is left. Two users (Rahul and Priya) click “Book Now” at the exact same millisecond. Without Process Synchronization, both processes read availableSeats == 1 as true and book the exact same seat for two different passengers!

2. The Critical Section Problem

A Critical Section (CS) is the specific segment of code inside a process where shared resources (shared variables, files, or tables) are accessed and modified.

To prevent a Race Condition, no two processes may be executing inside their Critical Sections at the exact same time!

The 3 Mandatory Requirements for Any Solution to the Critical Section Problem

Any valid synchronization algorithm (like Peterson’s Solution or Semaphores) MUST satisfy all 3 of these conditions:

1. Mutual Exclusion (Mandatory): If Process Pi is currently executing inside its Critical Section, then no other process can be executing in its Critical Section at the same time. (Like a single-person washroom—only 1 person inside at a time!)
2. Progress (No Unnecessary Delay): If no process is currently inside its Critical Section and some processes wish to enter, then only those processes that are waiting in their Entry Section can participate in deciding who enters next, and this decision cannot be postponed indefinitely.
3. Bounded Waiting (No Starvation): There must exist a strict limit (bound) on the number of times other processes are allowed to enter their Critical Sections after a process has made a request to enter its Critical Section and before that request is granted.

3. Semaphores in Operating Systems

Proposed by Dutch computer scientist Edsger W. Dijkstra in 1965, a Semaphore is an integer synchronization variable (S) that is used to solve the Critical Section Problem and coordinate processes.

Once initialized, a Semaphore S can only be accessed through two indivisible (atomic) operations: wait() (originally called P()) and signal() (originally called V()).

The Two Atomic Operations on Semaphore S:

1. wait(S) or P(S) — Used in the Entry Section (Acquiring Lock)

wait(S) {
    while (S <= 0)
        ; // Busy wait (wait until S becomes > 0)
    S--;  // Decrement S by 1 and enter Critical Section
}

2. signal(S) or V(S) — Used in the Exit Section (Releasing Lock)

signal(S) {
    S++;  // Increment S by 1 so a waiting process can enter
}

Two Types of Semaphores: Binary vs Counting Semaphore

Comparison Table: Binary Semaphore vs Counting Semaphore

4. Monitors (High-Level Synchronization Construct)

Why Were Monitors Invented?

While Semaphores are powerful, a small human programming mistake in using them causes catastrophic bugs:

• If a programmer accidentally writes signal(S) before wait(S), two processes enter the Critical Section simultaneously (Mutual Exclusion violated!).
• If a programmer writes wait(S) twice by mistake (wait(S)... wait(S)), the process freezes forever (Deadlock!).

What is a Monitor?

Invented by C.A.R. Hoare, a Monitor is a high-level, object-oriented synchronization construct (like a class) that encapsulates:

1. Shared Variables (Private Data)
2. Procedures / Methods that operate on those variables
3. Initialization Code and Condition Variables (wait() and signal())

• Key Advantage of a Monitor: The compiler automatically guarantees that only ONE process can be active inside the Monitor at any given time! The programmer does not have to manually code mutex locks.

💡 Exam Preparation Tips for DAVV BCA

• Always write the 3 mandatory conditions of the Critical Section Problem: (1) Mutual Exclusion, (2) Progress, and (3) Bounded Waiting.
• In any question on Semaphores, write the 3-line C code for wait(S) (S--) and signal(S) (S++) and include the Binary vs Counting Semaphore comparison table!