To Understand Process Synchronization

Introduction

A process is fundamentally an instance of running software, its execution necessitating a prescribed sequence. It serves as an entity that embodies the basic unit of work to be executed within any system.
Processes can be classified into two categories:

  1. Independent Process: These are processes whose task is not dependent on any other processes.
  2. Cooperating Process: These processes rely on one another, collaborating to accomplish a shared objective within the operating system.
types of process
Fig. 1 Types of Process

Process Synchronization

When two or more processes collaborate, it is imperative that their execution order be maintained. Failure to do so may result in conflicts, leading to erroneous or unintended outputs.
A cooperative process is one that can influence the execution of other processes or be influenced by them. Such processes must be synchronized to ensure that their execution order remains consistent and orderly.
The method by which the correct sequence of execution is preserved among cooperating processes is referred to as Process Synchronization. To achieve this, various synchronization mechanisms are employed, ensuring that processes execute in a regulated and predictable manner.
Classical Problems of Synchronization:

  • Dining Philosopher's Problem
  • Producer-Consumer Problem
  • Bounded-buffer Problem
  • Readers-Writers Problem

How Process Synchronization Works:

Process synchronization ensures the orderly and controlled execution of processes, preventing conflicts and race conditions when multiple processes access shared resources or critical sections of code. The main objective is to guarantee that processes interact with shared resources in a way that preserves data integrity and avoids unpredictable behavior. Below are the key mechanisms and concepts that underpin process synchronization:

  1. Mutual Exclusion: It ensures that only one process can access a critical section at a time, preventing multiple processes from simultaneously modifying shared resources, which could lead to data corruption. Achieving mutual exclusion is crucial, and several Synchronization mechanisms are designed to enforce it. These include:
    • Semaphores: Semaphores are integer variables used to control access to shared resources. They act as counters, allowing processes to signal one another. When a process wishes to enter a critical section, it must check the semaphore, and if the semaphore indicates that another process is already inside, the process will wait. Semaphores manage synchronization by ensuring only one process enters the critical section at a time.
    • Condition Variables: Condition variables are used in conjunction with mutexes. They allow processes to wait for specific conditions to be met before proceeding. Condition variables are effective in scenarios where a process should pause its execution until a certain condition is true.
    • Monitors: Monitors are a higher-level Synchronization construct that encapsulates both data and procedures into a single unit. They provide a structured approach to Synchronization, making it easier to manage concurrent access to shared resources.
    • Spinlocks: Spinlocks are simple locks that repeatedly check for availability until they can acquire the lock. They are efficient when the expected wait time is brief and are often used in low-level Operating System code.
  2. Critical Sections: A critical section is a segment of code that accesses shared resources or data structures that must be protected from concurrent access. Process Synchronization mechanisms ensure that only one process or thread can execute a critical section at a time.
  3. Deadlock Avoidance: Process Synchronization also addresses the issue of deadlocks, which occur when processes are stuck and unable to proceed because they are waiting for resources held by others. Techniques like deadlock detection and prevention algorithms are used to ensure that deadlocks are minimized or resolved when they occur.
  4. Orderly Execution: Process Synchronization establishes a sequence of execution for processes, allowing them to interact with shared resources in a controlled and orderly manner. This ensures that processes do not interfere with each other's tasks and maintains the predictability of their execution.

Semaphores

Semaphores are synchronization tools used in operating systems to control access to shared resources by multiple processes. They help prevent race conditions and ensure data consistency and integrity.

Types of Semaphores

  1. Binary Semaphore (Mutex):
    • Has only two values: 0 and 1.
    • Used to ensure mutual exclusion, allowing only one process to access the critical section at a time.
  2. Counting Semaphore:
    • Can have a value greater than one.
    • Controls access to a resource that has a limited number of instances, allowing multiple processes to access the resource concurrently up to a specified limit.

Semaphore Operations:

  1. Wait Operation (P):
    • If the semaphore's value is greater than 0, it is decremented by 1, and the process proceeds.
    • If the semaphore's value is 0, the process is blocked until the value becomes greater than 0.
  2. Signal Operation (V):
    • Increments the semaphore's value by 1.
    • If there are any processes waiting, one of them is unblocked.
dining-philosopher-problem
Fig. 2 Working of Semaphore

A. Dining Philosopher's Problem

The Dining Philosopher's Problem is a classical synchronization dilemma that involves 'K' philosophers seated around a circular table. The philosophers alternate between thinking and eating. At the center of the table is a bowl of noodles, accompanied by 'K' chopsticks (or forks), one for each philosopher.

dining-philosopher-problem
Fig. 3 Dining Philosopher's Problem Representation

In order to eat, each philosopher requires two chopsticks: one on the left and one on the right. A philosopher can only begin eating if both of these chopsticks are available. If, however, either the left or right chopstick is occupied by another philosopher, the philosopher must relinquish their currently held chopstick and return to thinking.

This problem illustrates the challenges of ensuring synchronization among processes that share resources—in this case, the chopsticks—while avoiding deadlock and ensuring that no philosopher is starved. The solution to the problem requires careful coordination of resource acquisition and release to ensure all philosophers can eat without causing conflict or inefficiency.

Code Snippet:

Void Philosopher
{
   while(1)
   {
      take_chopstick[i];
      take_chopstick[(i+1) % 5];
      . .
      . EATING
      . .
      put_chopstick[i];
      put_chopstick[(i+1) % 5];
      . .
      . THINKING
   }
}

Let’s analyze the code:
When Philosopher P0 wants to eat, it enters the Philosopher() function and:

  • Executes take_chopstick[i], which allows P0 to acquire chopstick C0.
  • Next, P0 executes take_chopstick[(i+1) % 5], allowing P0 to acquire chopstick C1, as (0 + 1) % 5 = 1.

Similarly, when Philosopher P1 wants to eat, it enters the Philosopher() function and:

  • Executes take_chopstick[i], which allows P1 to acquire chopstick C1.
  • P1 then executes take_chopstick[(i+1) % 5], which attempts to acquire chopstick C2, as (1 + 1) % 5 = 2.

However, in practice, chopstick C1 is already taken by P0, making it unavailable for P1. This situation creates a race condition, where P1 is unable to acquire both chopsticks, causing the program to behave unpredictably.

Solution:

The solution to the Dining Philosophers Problem can be effectively implemented by utilizing semaphores to represent the chopsticks. Each chopstick is represented by a semaphore, which plays a pivotal role in managing the synchronization between philosophers. The synchronization process relies on two fundamental operations: the Wait and Signal operations.

  • The Wait operation, is executed when a philosopher attempts to pick up a chopstick. This operation ensures that the philosopher waits until the chopstick is available (i.e., the semaphore value is non-zero), at which point the philosopher decrements the semaphore value, signifying that the chopstick is now in use.
  • The Signal operation, is invoked when a philosopher finishes eating and releases a chopstick. This operation increments the semaphore value, indicating that the chopstick is now available for another philosopher to use.

Let's modify the above code of the Dining Philosopher Problem by using semaphore operations wait and signal:

Void Philosopher
{
   while(1)
   {
      Wait(take_chopstickC[i]);
      Wait(take_chopstickC[(i+1) % 5]);
      . .
      . EATING
      . .
       Signal(put_chopstickC[i]);
       Signal(put_chopstickC[(i+1) % 5]);
      . .
      . THINKING
   }
}

In the code above, the first operation executed by philosopher 'i' is a wait operation on take_chopstickC[i] and take_chopstickC[(i+1) % 5]. This signifies that philosopher 'i' is attempting to acquire the chopsticks to their left (C[i]) and right (C[(i+1) % 5]). If both chopsticks are available, the philosopher can proceed by decrementing the semaphore values, indicating that the chopsticks are now in use. Once both chopsticks are acquired, philosopher 'i' enters the eating phase.
Upon finishing the meal, philosopher 'i' performs a signal operation on put_chopstickC[i] and put_chopstickC[(i+1) % 5]. This operation increments the semaphore values, signifying that philosopher 'i' has completed eating and has released both the left and right chopsticks. With the chopsticks now available for other philosophers, philosopher 'i' resumes the thinking phase, awaiting the next opportunity to eat.
By employing these semaphore operations, we ensure that mutual exclusion is maintained, preventing multiple philosophers from simultaneously accessing the same chopstick. This synchronization mechanism effectively addresses the core issues of the Dining Philosophers Problem, namely, preventing race conditions and ensuring orderly execution among competing processes.

Drawback

One significant drawback of the solution is the potential for a deadlock condition. This occurs when all philosophers pick up their left chopstick simultaneously, leading to a situation where none of them can proceed, as they are all indefinitely waiting for the chopstick held by the next philosopher. As a result, deadlock occurs, preventing any philosopher from eating.

Potential Solutions to Avoid Deadlock:

  1. Limiting the Number of Philosophers: To avoid deadlock, it is suggested that the maximum number of philosophers on the table should be limited to four. In this case, philosopher P3 will be able to acquire chopstick C4, which is free after philosopher P4 has finished eating. This allows philosopher P3 to begin eating, and after finishing, they will release both C3 and C4. As philosopher P3 releases C3, philosopher P2 will be able to acquire it, continuing the cycle and eventually allowing all philosophers to eat.
  2. Even-Odd Picking Strategy: Philosophers at even positions (such as P0, P2) should pick the right chopstick first, followed by the left chopstick, while philosophers at odd positions (such as P1, P3) should pick the left chopstick first, followed by the right chopstick. This strategy helps to prevent all philosophers from attempting to pick up the same chopstick simultaneously, which could lead to deadlock.
  3. Only Allowing Both Chopsticks to Be Available: Philosophers should only be allowed to pick up their chopsticks if both chopsticks are available simultaneously. This would prevent a situation where a philosopher picks one chopstick and waits indefinitely for the second one.
  4. Special Rule for the Last Philosopher (P4): In some variations, the last philosopher, P4, can be treated differently. For example, philosophers P0, P1, P2, and P3 should pick their left chopstick first, followed by the right chopstick, while philosopher P4 should reverse the order, picking the right chopstick first. This forces philosopher P4 to pick up C0 (the right chopstick for P4), which is already held by philosopher P0. This prevents P4 from proceeding immediately, thus preventing the deadlock scenario.
    Philosopher P3 will be able to start eating because both C3 and C4 are available to them. After finishing, P3 releases both chopsticks, enabling other philosophers to eat, thereby breaking the deadlock and ensuring proper execution.

B. Producer-Consumer Problem

The Producer-Consumer Problem is a classic synchronization problem that involves two types of processes: producers and consumers. These processes share a common, fixed-size buffer, and their tasks are interdependent:

  • Producers generate data and place it into the buffer.
  • Consumers remove data from the buffer and process it.

Producer-Consumer problem
Fig. 4 Producer-Consumer Problem Representation

The main challenge in this problem is ensuring that:

  1. Producers do not add data to a full buffer.
  2. Consumers do not attempt to remove data from an empty buffer.

In this scenario, synchronization mechanisms are essential to prevent race conditions, ensure mutual exclusion, and avoid the problems mentioned above. If not properly managed, these issues can lead to deadlocks or data inconsistencies.

Solution

There are typically three semaphores involved in the solution:

  1. Mutex:
    • A binary semaphore to ensure mutual exclusion when accessing the buffer.
    • Ensures that only one process (either producer or consumer) accesses the buffer at a time.
  2. Empty:
    • A counting semaphore to keep track of the number of empty slots in the buffer.
    • Keeps track of the number of empty slots in the buffer. Producers wait on this semaphore before adding an item to the buffer.
  3. Full:
    • A counting semaphore to keep track of the number of filled slots in the buffer.
    • Keeps track of the number of filled slots in the buffer. Consumers wait on this semaphore before removing an item from the buffer.

How It Works

  1. Producer Process:
    1. Produce an Item: The producer generates a new item to be added to the buffer.
    2. Wait on the Empty Semaphore: The producer checks if there is space in the buffer. The empty semaphore is decremented to indicate that space is being reserved. If the buffer is full (i.e., the empty semaphore is zero), the producer will wait until there is space available.
    3. Wait on the Mutex Semaphore: The producer waits for access to the critical section by acquiring the mutex semaphore. This ensures that no other producer or consumer can modify the buffer simultaneously.
    4. Add the Item to the Buffer: Once inside the critical section, the producer adds the item to the buffer.
    5. Signal the Mutex Semaphore: After adding the item, the producer releases the mutex semaphore, allowing other processes (producers or consumers) to access the buffer.
    6. Signal the Full Semaphore: The producer signals the full semaphore, indicating that the buffer now contains one more item. This allows consumers to know that there is data available for consumption.
  2. Consumer Process:
    1. Wait on the Full Semaphore: The consumer waits for the full semaphore to be decremented, ensuring that there is at least one item in the buffer. If the buffer is empty (i.e., the full semaphore is zero), the consumer will wait until an item is produced.
    2. Wait on the Mutex Semaphore: The consumer waits to acquire the mutex semaphore, ensuring that no other process is modifying the buffer while it is accessing the critical section.
    3. Remove an Item from the Buffer: Once inside the critical section, the consumer removes an item from the buffer.
    4. Signal the Mutex Semaphore: After consuming the item, the consumer releases the mutex semaphore, allowing other processes to access the buffer.
    5. Signal the Empty Semaphore: The consumer signals the empty semaphore, indicating that one slot in the buffer is now available for producers to add items.
    6. Consume the Item: Finally, the consumer processes the item, completing the consumption phase.

    Advantages of Process Synchronization

    • Ensures data consistency and integrity.
    • Avoids race conditions.
    • Prevents inconsistent data due to concurrent access.
    • Supports efficient and effective use of shared resources.

    Disadvantages of Process Synchronization

    • Adds overhead to the system.
    • This can lead to performance degradation.
    • Increases the complexity of the system.
    • Can cause deadlock if not implemented properly.