Mastering Process Synchronization: Critical Sections and Semaphores

The Critical Section Problem

In a multi-threaded or multi-process system, shared data can easily become corrupted if multiple processes try to modify it at the same time. This issue is known as a race condition.

To prevent this, we identify the section of code where shared resources are accessed as the Critical Section. The goal is to ensure that only one process executes in its critical section at any given moment.

do {
    [ Entry Section ]   <-- Request permission to enter
        Critical Section   <-- Manipulate shared data
    [ Exit Section ]    <-- Release permission
        Remainder Section  <-- Non-shared code
} while (true);

To be a valid solution, any mechanism managing the critical section must satisfy three strict requirements:

• Mutual Exclusion: If process P_i is executing in its critical section, no other processes can be executing in their critical sections for that same shared resource.
• Progress: If no process is executing in its critical section and some processes want to enter, only those processes not executing in their remainder sections can participate in deciding which process enters next. This selection cannot be postponed indefinitely.
• Bounded Waiting: There must be a limit on the number of times other processes can enter their critical sections after a process has made a request to enter, preventing that process from starving.

Semaphores

A semaphore is a synchronization tool introduced by Edsger Dijkstra. It is essentially an integer variable (S) that, apart from initialization, is accessed only through two standard atomic, indivisible operations: wait() (historically called P) and signal() (historically called V).

Types of Semaphores

• Binary Semaphore: The value of S can range only between 0 and 1. It behaves exactly like a lock (often called a mutex).
• Counting Semaphore: The value of S can range over an unrestricted domain. It is used to control access to a resource with a finite number of identical instances.

Implementation and Definitions

The standard behavior of the operations can be defined as follows:

void wait(Semaphore S) {
    while (S <= 0) 
        ; // Busy wait (in basic spinlocks)
    S--;
}

void signal(Semaphore S) {
    S++;
}

Note on Busy Waiting: The basic implementation above causes "spinning" (wasting CPU cycles). To avoid this, actual operating systems implement semaphores by blocking the process. If a resource isn't available, the process is placed in a waiting queue associated with the semaphore, and the CPU switches to another task. signal() unblocks a waiting process.

Classical Problems of Synchronization

These classic problems are used to test almost any new synchronization scheme or primitive.

1. The Bounded-Buffer (Producer-Consumer) Problem

A producer process produces data items into a buffer of a fixed size (n), and a consumer process removes items from it.

• The Challenge: The producer must not add data when the buffer is full, and the consumer must not remove data when the buffer is empty.
• The Semaphore Solution: Uses three semaphores:
  • mutex (binary semaphore, initialized to 1) to protect the buffer from simultaneous access.
  • empty (counting semaphore, initialized to n) to count empty buffer slots.
  • full (counting semaphore, initialized to 0) to count filled buffer slots.

2. The Readers-Writers Problem

Multiple concurrent processes want to access a shared database. Some only need to read data (Readers), while others need to update data (Writers).

• The Challenge: Multiple readers can read simultaneously without issue. However, if a writer is accessing the data, no other process (reader or writer) should be allowed near it.
• The Semaphore Solution: Uses a binary semaphore rw_mutex (initialized to 1) to ensure mutual exclusion for writers, and a mutex (initialized to 1) to protect the integer tracker read_count, which keeps track of how many readers are currently active.

3. The Dining Philosophers Problem

Five philosophers sit around a circular table with five single chopsticks. A philosopher spends their time thinking and eating. To eat, a philosopher must pick up both their left and right chopsticks.

• The Challenge: If every philosopher picks up their left chopstick simultaneously, they will all wait forever for their right chopstick, resulting in a deadlock.
• The Solutions: Deadlock can be avoided by:
  • Allowing at most four philosophers to sit at the table at once.
  • Allowing a philosopher to pick up chopsticks only if both are available (analyzed within a critical section).
  • Using an asymmetric solution (an odd philosopher picks up the left chopstick first, while an even philosopher picks up the right one first).

Monitors

While semaphores are highly effective, they are low-level primitives. A simple programming mistake—such as swapping a wait() and signal() call or forgetting a signal() entirely—can instantly cause deadlocks or timing errors that are incredibly difficult to debug. To solve this, researchers developed Monitors, a high-level synchronization construct.

Characteristics of a Monitor

• Encapsulation: A monitor is an abstract data type (like a class) that contains private data variables and public procedures.
• Implicit Mutual Exclusion: The monitor ensures that only one process can be active inside the monitor at any given time. You don't need to manually code locks around the procedures; the compiler handles it.

Condition Variables

To allow processes to wait inside a monitor without holding up the entire construct, monitors provide condition variables. A programmer can declare variables of type condition (e.g., condition x, y;). Only two operations can be invoked on a condition variable:

• x.wait(); — The process invoking this operation is suspended and placed in a private queue associated with the condition variable x. It relinquishes its exclusive lock on the monitor so another process can enter.
• x.signal(); — Resumes exactly one process suspended on x.wait(). If no processes are waiting on x, the operation has no effect (unlike semaphores, where a signal always increments the counter).

Signal Semantics

If process P executes x.signal(), and a waiting process Q is resumed, both cannot run inside the monitor simultaneously. Two primary design choices exist:

1. Signal and Wait (Hoare Semantics): P waits until Q either leaves the monitor or waits on another condition.
2. Signal and Continue (Mesa Semantics): Q waits until P either leaves the monitor or blocks on another condition. This is the approach used in most modern programming languages like Java and C#.