To Understand Process Synchronization

Introduction

A process is essentially running software. The execution of any process must occur in a specific order. A process refers to an entity that helps in representing the fundamental unit of work that must be implemented in any system.
There are two types of processes:

  1. Independent Process: These are processes whose task is not dependent on any other processes.
  2. Cooperating Process: These are processes that depend on other processes and work together to achieve a common goal in an operating system.
types of process
Fig. 1 Types of Process

Process Synchronization

When two or more processes cooperate with each other, their order of execution must be preserved. Otherwise, conflicts may arise, leading to inappropriate outputs.
A cooperative process is one that can affect the execution of other processes or be affected by their execution. Such processes need to be synchronized to ensure that their order of execution is maintained.
The procedure for preserving the appropriate order of execution among cooperative processes is known as Process Synchronization. Various synchronization mechanisms are employed to achieve this synchronization and ensure that processes execute in a controlled and predictable manner.
Example of Process Synchronization:

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

How does Process Synchronization work?

It revolves around preventing conflicts and race conditions when processes access shared resources or critical sections of code. To understand how Process Synchronization works in Operating Systems, here are the various mechanisms and concepts that underpin this crucial functionality:

  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.
    Various Synchronization mechanisms are used to enforce mutual exclusion and facilitate Process Synchronization. These include:
    • Semaphores: Semaphores are integer variables that act as counters to control access to shared resources. They can be used to signal between processes, allowing one process to enter a critical section while blocking others.
    • Mutexes or Mutual Exclusion: Mutexes are binary variables that serve as locks. When a process locks a mutex, it signifies that it has access to a critical section. Other processes attempting to lock the same mutex will be blocked until it is released.
    • 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 (P) Operation:
    • 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 (V) Operation:
    • 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

Dining Philosopher's Problem

The dining philosopher's problem is the classical problem of synchronization which says that 'K' philosophers are sitting around a circular table and their job is to think and eat alternatively. A bowl of noodles is placed at the center of the table along with 'K' chopsticks or forks for each of the philosophers. To eat a philosopher needs both their right and a left chopstick. A philosopher can only eat if both immediate left and right chopsticks of the philosopher is available. In case if both immediate left and right chopsticks of the philosopher are not available then the philosopher puts down their (either left or right) chopstick and starts thinking again.


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

Let's understand the Dining Philosophers Problem, we have used fig 3 as a reference to make you understand the problem exactly. The five Philosophers are represented as P0, P1, P2, P3, and P4 and five chopsticks by C0, C1, C2, C3, and C4.


dining-philosopher-problem
Fig. 4 Five Philosopher's sitting around a table

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 will enter the Philosopher() function and execute take_chopstick[i]. This operation allows P0 to hold chopstick C0. Next, P0 executes take_chopstick[(i+1) % 5], which allows P0 to hold chopstick C1, as (0 + 1) % 5 = 1.
Similarly, if Philosopher P1 wants to eat, it will enter the Philosopher() function and execute take_chopstick[i], which allows P1 to hold chopstick C1. Then, P1 executes take_chopstick[(i+1) % 5], which allows P1 to hold chopstick C2, as (1 + 1) % 5 = 2.
But Practically Chopstick C1 is not available as it has already been taken by philosopher P0, hence the above code generates problems and produces race condition.

Solution:

We use a semaphore to represent a chopstick and this truly acts as a solution of the Dining Philosophers Problem. Wait and Signal operations will be used for the solution of the Dining Philosophers Problem, for picking a chopstick wait operation can be executed while for releasing a chopstick signal semaphore can be executed.

Let's modify the above code of the Dining Philosopher Problem by using semaphore operations wait and signal, the desired code looks like

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 is a wait operation on 'take_chopstickC[i]' and 'take_chopstickC[(i+1) % 5]'. This indicates that philosopher 'i' has picked up the chopsticks to their left and right. After acquiring both chopsticks, the philosopher proceeds with the eating function.
Upon completing the meal, philosopher i performs a signal operation on 'put_chopstickC[i]' and 'put_chopstickC[(i+1) % 5]'. This signals that philosopher 'i' has finished eating and has put down both the left and right chopsticks. Subsequently, philosopher i resumes thinking.


Drawback

The drawback is that this solution can lead to a deadlock condition. This situation happens if all the philosophers pick their left chopstick at the same time, which leads to the condition of deadlock and none of the philosophers can eat. To avoid deadlock, some of the solutions are as follows -

  • Maximum number of philosophers on the table should not be more than four, in this case, chopstick C4 will be available for philosopher P3, so P3 will start eating and after the finish of his eating procedure, he will put down his both the chopstick C3 and C4. Now philosopher P2 which was holding chopstick C2 will also have chopstick C3 available, hence similarly, he will put down his chopstick after eating and enable other philosophers to eat.
  • A philosopher at an even position should pick the right chopstick and then the left chopstick while a philosopher at an odd position should pick the left chopstick and then the right chopstick.
  • Only in case if both the chopsticks ( left and right ) are available at the same time, only then a philosopher should be allowed to pick their chopsticks.
  • All the four starting philosophers ( P0, P1, P2, and P3) should pick the left chopstick and then the right chopstick, whereas the last philosopher P4 should pick the right chopstick and then the left chopstick. This will force P4 to hold his right chopstick first since the right chopstick of P4 is C0, which is already held by philosopher P0 and its value is set to 0, i.e C0 is already 0, because of which P4 will get trapped into an infinite loop and chopstick C4 remains vacant. Hence philosopher P3 has both left C3 and right C4 chopstick available, therefore it will start eating and will put down its both chopsticks once finishes and let others eat which removes the problem of deadlock.

Producer-Consumer Problem

The Producer-Consumer problem involves two types of processes, producers and consumers, that share a common, fixed-size buffer. The producers generate data and place it into the buffer, while the consumers remove data from the buffer and process it. The challenge is to ensure that producers do not add data to a full buffer and consumers do not remove data from an empty buffer.

Producer-Consumer problem
Fig. 5 Producer-Consumer Problem

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:
    • Produces an item.
    • Waits on the empty semaphore to ensure there is space in the buffer.
    • Waits on the mutex semaphore to enter the critical section.
    • Adds the item to the buffer.
    • Signals the mutex semaphore to exit the critical section.
    • Signals the full semaphore to indicate a new item has been added.
  2. Consumer Process:
    • Waits on the full semaphore to ensure there is an item in the buffer.
    • Waits on the mutex semaphore to enter the critical section.
    • Removes an item from the buffer.
    • Signals the mutex semaphore to exit the critical section.
    • Signals the empty semaphore to indicate an empty slot is available.
    • Consumes the item.

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.