Process Synchronization

5.1​ Introduction
5.2​ Critical section problem
5.3​ Semaphores –
-​Concept
-​Implementation
-​Deadlock & Starvation
-​Types of Semaphores
5.4​ Classical Problems of synchronization –
-Bounded buffer problem
-​Readers & writers problem
Dining Philosophers problem

Process Synchronization in OS (Operating System)

When two or more process cooperates with each other, their order of execution must be
preserved otherwise there can be conflicts in their execution and inappropriate outputs can be
produced.
A cooperative process is the one which can affect the execution of other process or can be
affected by the execution of other process. Such processes need to be synchronized so that
their order of execution can be guaranteed.
The procedure involved in preserving the appropriate order of execution of cooperative
processes is known as Process Synchronization. There are various synchronization
mechanisms that are used to synchronize the processes.
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.
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.
Critical Section Problem in OS (Operating System)
Critical Section is the part of a program which tries to access shared resources. That resource
may be any resource in a computer like a memory location, Data structure, CPU or any IO
device.
The critical section cannot be executed by more than one process at the same time; operating
system faces the difficulties in allowing and disallowing the processes from entering the
critical section.
The critical section problem is used to design a set of protocols which can ensure that the
Race condition among the processes will never arise.
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.

Semaphores
The Semaphore is just a normal integer. The Semaphore cannot be negative. The least value
for a Semaphore is zero (0). The Maximum value of a Semaphore can be anything. The
Semaphores usually have two operations. The two operations have the capability to decide
the values of the semaphores.

The two Semaphore Operations are:

1.​ Wait ( )
2.​ Signal ( )
1.​ Wait Semaphore Operation
The Wait Operation is used for deciding the condition for the process to enter the critical state
or wait for execution of process. Here, the wait operation has many different names. The
different names are:
1.​ Sleep Operation
2.​ Down Operation
3.​ Decrease Operation
4.​ P Function (most important alias name for wait operation)
1.​ The Wait Operation works on the basis of Semaphore or Mutex Value.
Here, if the Semaphore value is greater than zero or positive then the Process can enter the
Critical Section Area.
If the Semaphore value is equal to zero then the Process has to wait for the Process to exit the
Critical Section Area.
This function is only present until the process enters the critical state. If the Processes enters
the critical state, then the P Function or Wait Operation has no job to do.
2) Signal Semaphore Operation
The Signal Semaphore Operation is used to update the value of Semaphore. The Semaphore
value is updated when the new processes are ready to enter the Critical Section.
The Signal Operation is also known as:
1.​ Wake up Operation
2.​ Up Operation
3.​ Increase Operation
4.​ V Function (most important alias name for signal operation)
Advantages of a Semaphore
●​ Semaphores are machine independent since their implementation and codes are written
in the microkernel's machine independent code area.
●​ They strictly enforce mutual exclusion and let processes enter the crucial part one at a
time (only in the case of binary semaphores).
●​ With the use of semaphores, no resources are lost due to busy waiting since we do not
need any processor time to verify that a condition is met before allowing a process
access to the crucial area.
●​ Semaphores have the very good management of resources
●​ They forbid several processes from entering the crucial area. They are significantly
more effective than other synchronization approaches since mutual exclusion is made
possible in this way.
Disadvantages of a Semaphore
●​ Due to the employment of semaphores, it is possible for high priority processes to
reach the vital area before low priority processes.
●​ Because semaphores are a little complex, it is important to design the wait and signal
actions in a way that avoids deadlocks.
●​ Programming a semaphore is very challenging, and there is a danger that mutual
exclusion won't be achieved.
●​ The wait ( ) and signal ( ) actions must be carried out in the appropriate order to
prevent deadlocks.
 ●​ Types of Semaphores
●​ Here we will discuss the types of Semaphores as follows.
●​ Type-1: General Semaphore
●​ A semaphore whose integer component can take arbitrary non-negative values of S.L.
these is called General Semaphore. They are kind of weak semaphores.
●​ Type-2: Binary Semaphore
●​ A semaphore whose integer component S.L. takes only the values 0 and 1 is called
a binary semaphore. This is also known as “mutex” which stands for mutual exclusion.
●​ Initialization
●​ S <- (0, φ) or S <- (1, φ)
●​ Wait for Operation: It remains Unchanged as above.
●​ Signal Operation: It slightly changes as follows
●​ Type-3: Strong Semaphore
●​ In Strong semaphores, S.L. remains unchanged as in weak semaphores whereas S.V. is
replaced by the queue. Because removal of arbitrary process in a weak semaphore it
may lead to starvation whereas in this case, it remains free from starvation.
●​ Initialization
●​ S <- (0,empty)
●​ Type-4: Busy- Wait for Semaphore
●​ It does not have a component S.L. and Semaphore S is identified only by S.V.
Busy-Wait Semaphore are appropriate in a multi-processor system where the waiting
process has its own processor and is not waste CPU time that could be used for
computation.
●​
Classic Problems of Synchronization :–
1.​ The bounded buffer problem
2.​ The reader writer problem
3.​ The dining philosopher problem

Solving Bound Buffer Problem using the concept of Semaphores

Definition:
The Producer-Consumer problem is another name for Bound Buffer Problem. In this issue,
there are n slots in a buffer, and each slot may hold one data unit. Producer and Consumer are
the two operations that are using the buffer. Both the producer and the consumer attempt to
enter and delete data.
Solution:
Now, we are going to solve the problem faced in the Bound Buffer or Producer Consumer
Problem.
We already know that the duty of the Producer is to enter data in which ever area possible.
The duty of Consumer is to remove the data produced by the Producer or already present data
where ever possible.

2) Solving Readers - Writers Problem using Semaphore

Definition: In Readers - Writers Problems there are two Actors for the problem. They are
Reader and Writer. The Reader - Writer Problem tries to access or change the value of the
Shared Variable. Due, to this parallel execution of accessing and changing operation data
faults take place. Due, to this expected outputs are not the actual outputs of the problem. This
is the problem of Readers - Writers
The duties of Readers and Writers are different from each other.
The Reader duty is to read the value of the Shared Variable.
The Writer duty is to change the value of the Shared Variable.
Required Data
First of all let us consider there is Critical Section which contains a shared variable. Let us
consider that there are two processes. The first process is the one which always tries to access
the shared variable. The second process is the one which always tries to change the value of
the variable.
Solution
Now, let us understand the solution to the Readers and Writers Problem using
Now, our task is to perform the operations of both Readers and Writers using Semaphores
without any possibility of occurrence of Deadlock.
3) Dining Philosopher's Problem using the concept of Semaphores
Definition:
The dining philosopher's dilemma, also known as the classical synchronization issue, has five
philosophers seated around a circular table who must alternate between thinking and eating.
At the center of the table sits a bowl of noodles and five chopsticks, one for each of the
philosophers. A philosopher must use both their right and left chopsticks in order to eat. A
philosopher can only eat if both of their right and left chopsticks are within reach. If the
philosopher's left and right chopsticks are not immediately available, the philosopher sets
down one of the chopsticks (either the left or right) and resumes pondering.
The Dining Philosopher is a classic synchronization problem because it illustrates a broad
class of concurrency control problems.