Process Synchronization in Operating System

On the basis of synchronization, processes are categorized as one of the following two types:
Independent Process: The execution of one process does not affect the execution of other processes.
Cooperative Process: A process that can affect or be affected by other processes executing in the system.
Process synchronization problem arises in the case of Cooperative process also because resources are shared in Cooperative processes.
Processes can communicate with each other through both:
Shared Memory
Message passing

Some Terminologies

Race Condition
A Race Condition typically occurs when two or more threads try to read, write and possibly make the decisions based on the memory that they are accessing concurrently.
It usually happens due to multiple threads accessing a shared resource or executing a common code block.
Race conditions can leave the system vulnerable to security attacks where attackers can tamper with the shared data.
Race conditions can be avoided by proper synchronization between threads. In Java usage of synchronized and volatile keywords helps us achieve the same
Critical Section
The regions of a program that try to access shared resources and may cause race conditions are called critical section.
To avoid race condition among the processes, we need to assure that only one process at a time can execute within the critical section.
Semaphore
Semaphore is simply an integer variable that is shared between threads.
This variable is used to solve the critical section problem and to achieve process synchronization in the multiprocessing environment.
Semaphores are of two types:
- Binary Semaphore –
- This is also known as mutex lock. It can have only two values – 0 and 1. Its value is initialized to 1. It is used to implement the solution of critical section problems with multiple processes.
- Counting Semaphore –
- Its value can range over an unrestricted domain. It is used to control access to a resource that has multiple instances.
Mutex
Mutex is a mutual exclusion object that synchronizes access to a resource.
It is created with a unique name at the start of a program.
The Mutex is a locking mechanism that makes sure only one thread can acquire the Mutex at a time and enter the critical section.
This thread only releases the Mutex when it exits the critical section.
Mutex VS Semaphore
A Mutex is different than a semaphore as it is a locking mechanism while a semaphore is a signalling mechanism.
A binary semaphore can be used as a Mutex but a Mutex can never be used as a semaphore.

Producer - Consumer Problem

The Producer-Consumer problem is a classic synchronization problem in operating systems.
The problem is defined as follows:
There is a fixed-size buffer and a Producer process, and a Consumer process.
The Producer process creates an item and adds it to the shared buffer.
The Consumer process takes items out of the shared buffer and “consumes” them.
Certain conditions must be met by the Producer and the Consumer processes to have consistent data synchronization:
The Producer process must not produce an item if the shared buffer is full.
The Consumer process must not consume an item if the shared buffer is empty.
Access to the shared buffer must be mutually exclusive; this means that at any given instance, only one process should be able to access the shared buffer and make changes to it.
The solution to the Producer-Consumer problem involves three semaphore variables.
semaphore Full
- Tracks the space filled by the Producer process.
- It is initialized with a value of 0 as the buffer will have 0 filled spaces at the beginning.
semaphore Empty
- Tracks the empty space in the buffer. It is initially set to buffer_size as the whole buffer is empty at the beginning.
semaphore mutex
- Used for mutual exclusion so that only one process can access the shared buffer at a time.
Using the signal() and wait() operations on these semaphores, we can arrive at a solution.
Producer Solution:

void Producer(){ while(true){ // Produce an item wait(Empty); wait(mutex); add(); signal(mutex); signal(Full); } }

In the code above, the Producer process waits for the Empty semaphore. This means that the Producer process is kept in busy-waiting if the Empty semaphore value is 0 ,indicating that there are 0 empty spaces available. The Producer will have to wait for the Consumer to consume some items from the buffer and make some space available for itself.
The Producer then waits for the mutex semaphore, which merely ensures that once a thread has entered the critical section of the code, the rest of the threads cannot access it and cause race conditions.
The add() function appends the item to the shared buffer. Once a Producer process reaches this point in the code, it is guaranteed that no other process is accessing the shared buffer concurrently, preventing data inconsistency.
After the Producer process adds the item to the shared buffer, it uses the signal() operation to increase the value of the mutex semaphore by one, thereby allowing any other threads which were busy-waiting in the mutex semaphore to access the critical section.
Lastly, the Producer process uses the signal() operation on the Full semaphore, increasing its value by 1, indicating that an item has been added to the shared buffer and the count for the filled spaces has increased by one.
Consumer Solution:

void Consumer(){ while(true){ wait(Full); wait(mutex); consume(); signal(mutex); signal(Empty) } }

The Consumer waits for the Full semaphore. If the Full semaphore value is 0, it indicates that there are no items to consume, and it must wait for the Producer process to produce an item and add it to the shared buffer for consumption.
As previously mentioned, the mutex semaphore ensures mutually exclusive access to the critical section of the code so that the shared buffer is only accessed by one thread at a time for data synchronization.
Once the Consumer process reaches the critical section of the code, i.e., the consume() function, it executes the function and takes one item from the shared buffer.
After taking an item from the buffer, the Consumer process first uses signal(mutex) to release the mutex semaphore, allowing other threads that may have been busy-waiting in the mutex to access the critical section.
Lastly, the Consumer uses signal(Empty) to increase the value of the Empty semaphore by one, indicating that a free slot has been made in the shared buffer. Any Producer processes that may have been waiting in the Empty semaphore are now allowed to add an item to the shared buffer.

Requirements of Synchronization Mechanisms

In order to synchronize the cooperative processes, our main task is to solve the critical section problem. We need to provide a solution in such a way that the following conditions can be satisfied.
Primary
Mutual Exclusion
- Our solution must provide mutual exclusion. By Mutual Exclusion, we mean that if one process is executing inside critical section then the other process must not enter in the critical section.
Progress
- Progress means that if one process doesn't need to execute into critical section then it should not stop other processes to get into the critical section.
Secondary
Bounded Waiting
- We should be able to predict the waiting time for every process to get into the critical section. The process must not be endlessly waiting for getting into the critical section.
Portability
- Our mechanism must be architectural natural. It means that if our solution is working fine on one architecture then it should also run on the other ones as well.

Lock Variable Mechanism for Process Synchronization

This is the simplest synchronization mechanism. This is a Software Mechanism implemented in User mode.
This is a busy waiting solution which can be used for more than two processes.
In this mechanism, a Lock variable lockis used. Two values of lock can be possible, either 0 or 1.
Lock value 0 means that the critical section is vacant while the lock value 1 means that it is occupied.
A process which wants to get into the critical section first checks the value of the lock variable.
If it is 0 then it sets the value of lock as 1 and enters into the critical section, otherwise it waits.
Every Synchronization mechanism is judged on the basis of four conditions.
Mutual Exclusion
Progress
Bounded Waiting
Portability
The lock variable mechanism doesn't provide Mutual Exclusion in some of the cases.
Let us consider that we have two processes P1 and P2. The process P1 wants to execute its critical section. P1 gets into the entry section. Since the value of lock is 0 hence P1 changes its value from 0 to 1 and enters into the critical section.
Meanwhile, P1 is preempted by the CPU and P2 gets scheduled. Now there is no other process in the critical section and the value of lock variable is 0. P2 also wants to execute its critical section. It enters into the critical section by setting the lock variable to 1.
Now, CPU changes P1's state from waiting to running. P1 is yet to finish its critical section. P1 has already checked the value of lock variable and remembers that its value was 0 when it previously checked it. Hence, it also enters into the critical section without checking the updated value of lock variable.
Now, we got two processes in the critical section. According to the condition of mutual exclusion, morethan one process in the critical section must not be present at the same time. Hence, the lock variable mechanism doesn't guarantee the mutual exclusion.
The problem with the lock variable mechanism is that, at the same time, more than one process can see the vacant tag and more than one process can enter in the critical section. Hence, the lock variable doesn't provide the mutual exclusion that's why it cannot be used in general.

Peterson's Solution to Process Synchronization

Peterson’s Solution is a classical software-based solution to the critical section problem.
It is a busy waiting solution can be implemented for only two processes.
In Peterson’s solution, we have two shared variables:
A boolean Flag[]: A boolean array Flag which is initialized to FALSE. This Flag array represents which process wants to enter into the critical section.
int Turn: A integer variable Turn indicates the process number which is ready to enter into the critical section.
Peterson’s Solution preserves all three conditions:
Mutual Exclusion is assured as only one process can access the critical section at any time.
Progress is also assured, as a process outside the critical section does not block other processes from entering the critical section.
Bounded Waiting is preserved as every process gets a fair chance.
Disadvantages of Peterson's solution are:
The Peterson's solution involves Busy waiting
The solution is also limited to only 2 processes.