Solving Classical Synchronization Problems

The Critical Section Problem

At the core of synchronization is the critical section problem. A critical section is a segment of code where a process or thread accesses shared resources (like a shared variable, a file, or a buffer). The problem is to design a protocol that processes can use to cooperate. A solution must satisfy three requirements:

1. Mutual Exclusion: If a process is executing in its critical section, then no other processes can be executing in their critical sections for the same shared resource. This is the most fundamental requirement.
2. Progress: If no process is in its critical section and some processes wish to enter, the selection of the next process to enter cannot be postponed indefinitely.
3. Bounded Waiting: There must be a limit on the number of times that 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. This prevents starvation of any single process.

Semaphores, which we introduced previously, are a powerful tool for solving this problem. A semaphore is an integer variable that is accessed only through two atomic operations: wait() and signal().

• wait(S) or down(S):

  wait(S) {
      while (S <= 0)
          ; // busy wait
      S--;
  }
  

• signal(S) or up(S):

  signal(S) {
      S++;
  }
  

In practice, the busy waiting is replaced by putting the process in a waiting queue. We'll use two types:

• Counting Semaphore: The value can range over an unrestricted domain.
• Binary Semaphore (or Mutex): The value can only be 0 or 1. It's primarily used to provide mutual exclusion.

The Producer-Consumer Problem

This is a classic synchronization problem that models any situation where one entity is generating work and another is processing it, with a limited buffer in between. Imagine a web server producing log entries and a separate process consuming them to write to a database.

The Setup:

• A producer process generates items and places them into a shared buffer.
• A consumer process removes items from the buffer and consumes them.
• The buffer is of a fixed size, say n.

The Constraints:

1. The producer must wait if the buffer is full.
2. The consumer must wait if the buffer is empty.
3. Only one process can access the buffer at a time (mutual exclusion).

To solve this, we use three semaphores:

• A binary semaphore mutex for mutual exclusion, initialized to 1.
• A counting semaphore full to count the number of full slots in the buffer, initialized to 0.
• A counting semaphore empty to count the number of empty slots, initialized to n.

The following video from Gate Smashers provides an excellent walkthrough of this solution. It demonstrates how the semaphore values change and how they prevent incorrect behavior, even with preemption.

Let's codify the logic you just saw.

Producer Process Code:

while (true) {
    // produce an item
    
    wait(empty);      // Decrement empty count. If 0, wait.
    wait(mutex);      // Enter critical section.
    
    // add the item to the buffer
    
    signal(mutex);    // Exit critical section.
    signal(full);       // Increment full count.
}

Consumer Process Code:

while (true) {
    wait(full);       // Decrement full count. If 0, wait.
    wait(mutex);      // Enter critical section.
    
    // remove an item from the buffer
    
    signal(mutex);    // Exit critical section.
    signal(empty);      // Increment empty count.
    
    // consume the item
}

A classic GATE question trap: What happens if the producer's wait calls are swapped?
wait(mutex);
wait(empty);

Consider this scenario: The buffer is full (empty = 0). The producer executes wait(mutex), acquiring the lock and entering its critical section. Then, it executes wait(empty). Since the buffer is full, it gets blocked and goes to sleep. However, it is still holding the mutex! The consumer, which could have emptied the buffer, is now stuck waiting at its own wait(mutex) call. Neither process can proceed. This is a classic deadlock. The order of semaphore operations is critical.

The Readers-Writers Problem

This problem models access to a shared resource like a database, where multiple processes can read simultaneously, but a writer needs exclusive access.

The Setup:

• A shared resource (e.g., a file or data object).
• Reader processes, which only read the resource.
• Writer processes, which can modify the resource.

The Constraints:

1. Multiple readers can access the resource at the same time.
2. Only one writer can access the resource at any given time.
3. If a writer is accessing the resource, no reader can access it.

This requires a more intricate solution. We need to allow the first reader in to lock out writers, but subsequent readers should not be blocked. Only when the last reader leaves should the resource be unlocked for a potential writer.

We use two semaphores and a counter:

• A binary semaphore db (for "database") to control access. It provides mutual exclusion for writers and is also used by the first/last reader. Initialized to 1.
• A binary semaphore mutex to protect the read_count variable. Initialized to 1.
• An integer read_count to track how many readers are currently active. Initialized to 0.

The following video explains this solution, which gives priority to readers, by walking through every possible interaction.

Here is the pseudo-code for the solution you just saw.

Writer Process Code:

while (true) {
    wait(db);
    
    // perform writing
    
    signal(db);
}

Reader Process Code:

while (true) {
    wait(mutex);         // Lock to protect read_count
    read_count++;
    if (read_count == 1) {
        wait(db);        // If first reader, lock the database from writers
    }
    signal(mutex);       // Unlock for other readers
    
    // perform reading
    
    wait(mutex);         // Lock to protect read_count
    read_count--;
    if (read_count == 0) {
        signal(db);      // If last reader, unlock database for writers
    }
    signal(mutex);       // Unlock
}

This specific solution gives priority to readers. If readers are constantly arriving, a writer might be starved (never get a chance to write). Variants of this problem exist to provide writer priority or prevent starvation, but this is the classic version you must know for GATE.

Monitors: A Higher-Level Approach

Using semaphores correctly can be difficult. A single misplaced wait or signal can lead to deadlocks or race conditions. Monitors are a higher-level language construct designed to make synchronization easier and less error-prone.

A monitor is essentially a class or module that encapsulates:

• Shared private data.
• Public procedures that operate on that data.
• Implicit Mutual Exclusion: Only one thread can be active (executing a procedure) inside the monitor at any given time. The compiler enforces this automatically.

To handle more complex synchronization (like waiting for a buffer to become non-empty), monitors use condition variables. A condition variable has two main operations:

• c.wait(): The calling thread is suspended and placed on a queue for condition c. It also releases the monitor lock, allowing another thread to enter.
• c.signal(): If any threads are waiting on condition c, one of them is resumed. If no thread is waiting, the signal has no effect.

Here is a sketch of how the Producer-Consumer problem would be solved with a monitor:

monitor ProducerConsumer {
    private:
        // buffer and associated counters
        condition not_full, not_empty;

    public:
        procedure produce(item) {
            if (buffer is full) {
                not_full.wait();
            }
            // add item to buffer
            not_empty.signal();
        }

        procedure consume() {
            if (buffer is empty) {
                not_empty.wait();
            }
            // remove item from buffer
            not_full.signal();
            // return item
        }
}

Notice how much cleaner this is. There are no explicit mutex locks. The logic is focused on the conditions (not_full, not_empty) rather than the low-level locking mechanism.

Conclusion

In this lesson, we tackled the crucial topic of process synchronization. You now have the tools to analyze and solve complex concurrency problems, a skill frequently tested in GATE.

Our key takeaways are:

• Synchronization is necessary to prevent race conditions when processes share data.
• The Producer-Consumer Problem can be solved using three semaphores: mutex for mutual exclusion, and full and empty to manage buffer state.
• The Readers-Writers Problem (with reader-priority) is solved using a read_count variable protected by a mutex, and a db semaphore to control exclusive access for writers.
• Monitors provide a higher-level, safer abstraction for synchronization by bundling shared data with procedures and handling mutual exclusion automatically through condition variables.

We briefly mentioned that incorrect semaphore usage can lead to deadlock. This is a severe problem where two or more processes are stuck in a state of permanent waiting, each holding a resource the other needs. Our next lesson will be dedicated entirely to this topic. We will formally define deadlock, identify the four conditions necessary for it to occur, and explore methods for preventing, avoiding, and detecting it.