Operating System – Module II Notes – Part 2 Process Synchronization, Deadlock

PROCESS SYNCHRONIZATION

COOPERATING PROCESS
 A cooperating process is one that can affect other processes executing in the system or that may be affected
by other processes executing in the system.
 Cooperating processes can either directly share both code and data ( using threads ) or may be allowed to
share data only through files or messages.
 Concurrent access to shared data may result in data inconsistency. Therefore OS must provide a means of
synchronization among processes to maintain the consistency of data.

RACE CONDITION
 Several processes access and manipulate the same data concurrently and the outcome of the execution
depends on the particular order in which the shared data is accessed by the processes is called a race
condition.
 Consider two cooperating processes P1 & P2 shown in below table:
Process P1 Process P2
Read balance Read Balance
Balance = Balance + 1000 Balance = Balance - 400

 Suppose balance is initially 5000. Then after execution of P1 & P2 , it should be 5600. To achieve this
result, processes should execute in order, either P1 followed by P2 or P2 followed by P1.
 One possible interleaving sequence of P1 & P2 which may cause inconsistent result is shown below:

Process P1 Process P2 Balance

Read Balance 5000
Read Balance 5000
Balance = Balance + 1000 6000
Balance = Balance – 400 4600

 To guard against the race condition above, we need to ensure that only one process at a time can manipulate
the critical data ( shared data ). In other words, we need to ensure mutual exclusion

CRITICAL SECTION
 The portion of the code of a process in which it accesses or changes the shared data in known as its critical
section ( or critical region )
 OS has to ensure that the execution of critical sections by the cooperating processes is mutually exclusive
i.e. no two processes are allowed to execute their critical sections simultaneously.

CRITICAL SECTION PROBLEM

 The critical-section problem is to design a protocol that the processes can use to cooperate.
 The general structure of a typical process Pi is shown in figure :
Page 1 of 12
Operating System – Module II Notes – Part 2 Process Synchronization, Deadlock

 Each process must request permission to enter its critical section and signal the entrance by setting the
values of some variables. The section of code implementing this request is the entry section.
 After executing the critical section, the process again sets some variables to signal the exit from the critical
section. The portion in which the process does this is called exit section.
 The remaining code is the remainder section.

A solution to the critical-section problem must satisfy the following three requirements:
1. Mutual exclusion:- This condition states that no two cooperating processes can enter into their critical
sections at the same time. i.e. the access to critical section must be mutually exclusive. If process P; is
executing in its critical section, then no other processes can be executing in their critical sections until P1
finishes with it
.
2. Progress:- If no process is executing in its critical section and some processes wish to enter their critical
sections, then only those processes that are not executing in their remainder sections can participate in the
decision on which will enter its critical section next, and this selection cannot be postponed indefinitely (
decision should be made in a finite amount of time ). A process that has exited from its critical section
cannot prevent other waiting processes from entering the critical sections.

3. Bounded waiting:- There exists an upper bound, or 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 the permission is granted. A process wishing to enter its critical section cannot be delayed
indefinitely.

TWO SOLUTIONS FOR CRITICAL SECTION PROBLEM

1) Peterson’s Algorithm ( Two process solution )
2) Solution using Semaphore ( Multiple process solution )

Perterson’s algorithm
 It is a simple algorithm to solve the critical section problem for two processes P0 & P1
 P0 & P1 share the following variables
int turn; boolean flag[2];

 The general structure of code segment for process P0 is as follows :

Page 2 of 12
Operating System – Module II Notes – Part 2 Process Synchronization, Deadlock

do
{
flag[0] = TRUE;
turn = 1
while ( flag[1] && turn == 1 )  Entry Section
doNothing() ;
/* critical section */
flag[0] = FALSE;  Exit Section
/* Remainder section code */
}
while(1);

 The general structure of code segment for process P1 is as follows :

do
{
flag[1] = TRUE;
turn = 0
while ( flag[0] && turn == 0 )  Entry Section
doNothing() ;
/* critical section */
flag[1] = FALSE;  Exit Section
/* Remainder section code */
}
while(1);

 When any one of the processes ,say P0 , wishes to enter its critical section, it sets flag[0] to true and turn to
other number, say 1
It then verifies two conditions:
1) Whether flag[1] is true
2) Whether turn equals 1
If any of these conditions is false, the process P0 enters its critical section.

 If both processes wish to enter critical section, both flags will be set to true. The variable turn will decide
which process enters its critical section.

 This algorithm satisfies all the three requirements ( mutual exclusion, progress & bounded waiting )
needed for a solution of critical section problem

Using Semaphore ( Multiple process solution)

 In its simplest form, Semaphore can be considered as an integer variable. Other than initialization, only two
operations, namely wait and signal can be performed on it.

 Pseudo code for wait and signal is as follows :


Wait(S) Signal(S)

Page 3 of 12
Operating System – Module II Notes – Part 2 Process Synchronization, Deadlock

{ {
While ( S<=0) S++;
Do nothing(); }
S--;
}
The solution to critical section problem for N processes is implemented by allowing the processes to
share a semaphore S, which is initialized to 1. The general structure of process, say Pi , is as follows :

do
{
Wait(S);  Entry Section
/* critical section */
Signal(S);  Exit Section
/* Remainder section code */
}
while(1);

 The Semaphore used before is a counting semaphore, the integer value of which is not limited.
 There is another type of semaphore, known as binary semaphore, the integer value of which ranges
between 0 and 1 only.

DEADLOCK
 In a multiprogramming environment, several processes may compete for a finite number of resources. If the
resources requested by a process are not available at that time, the process enters a waiting state.
Sometimes, a waiting process is never again able to change state, because the resources it has requested are
held by other waiting processes. This situation is called a deadlock.
 In other words, when two processes are waiting endlessly for resources held by each other, the situation is
referred to as deadlock
NECESSARY CONDITIONS FOR A DEADLOCK
A deadlock situation can arise if the following four conditions hold simultaneously in a system
1. Mutual exclusion:- Only one process can acquire a given resource at any point of time. Any other process
requesting for that resource has to wait until the earlier process releases it.
2. Hold and wait:- A process is holding a resource allocated to it and waiting to acquire additional resources
that are currently being held by other processes.
3. No preemption: Resources cannot be preempted by the system; that is, a resource allocated to a process can
be released only voluntarily by the process holding it, after that process has completed its task.
4. Circular wait:- A set {P0, P1, ..., Pn} of waiting processes must exist such that P0 is waiting for a resource
held by P1, P1 is waiting for a resource held by P2, ..., Pn−1 is waiting for a resource held by Pn, and Pn is
waiting for a resource held by P0. ( Each process is waiting for a resource held by its successor process in a
chain of processes )

RESOURCE ALLOCATION GRAPH ( RAG )

Page 4 of 12
Operating System – Module II Notes – Part 2 Process Synchronization, Deadlock
 Deadlocks can be described more precisely in terms of a directed graph called a system resource-allocation
graph.
 This graph consists of a set of vertices V and a set of edges E.
 The set of vertices V is partitioned into two different types of nodes:
o P = {P1, P2, ...,Pn}, the set consisting of all the active processes in the system,
o R = {R1, R2, ..., Rm}, the set consisting of all resource types in the system.
 A directed edge from process Pi to resource type Rj is denoted by Pi → Rj ;it signifies that process Pi has
requested an instance of resource type Rj and is currently waiting for that resource. A directed edge Pi → Rj
is called a request edge

 A directed edge from resource type Rj to process Pi is denoted by Rj → Pi ; it signifies that an instance of
resource type Rj has been allocated to process Pi . A directed edge Rj → Pi is called an assignment edge.

 In Graph, each process Pi is represented as a circle and each resource type Rj as a rectangle.
 Since resource type Rj may have more than one instance, we represent each such instance as a dot within
the rectangle.

 When process Pi requests an instance of resource type Rj , a request edge is inserted in the resource-
allocation graph. When this request can be fulfilled, the request edge is instantaneously transformed to an
assignment edge.
 When the process no longer needs access to the resource, it releases the resource. As a result, the assignment
edge is deleted.
Example : The resource-allocation graph shown in Figure depicts the following situation.

 The sets P, R, and E:

o P = {P1, P2, P3}
o R = {R1, R2, R3, R4}
o E = {P1 → R1, P2 → R3, R1 → P2, R2 → P2, R2 → P1, R3 → P3}
 Resource instances:
o One instance of resource type R1

Page 5 of 12
Operating System – Module II Notes – Part 2 Process Synchronization, Deadlock
o Two instances of resource type R2
o One instance of resource type R3
o Three instances of resource type R4
 Process states:
o Process P1 holds an instance of resource type R2 and waits for an instance of resource type R1.
o Process P2 holds an instance of R1 and an instance of R2 and waits for an instance of R3.
o Process P3 is holding an instance of R3.
 If the graph contains no cycles, then no process in the system is deadlocked.
 If the graph does contain a cycle, then a deadlock may exist.

 If each resource type has exactly one instance, then a cycle implies that a deadlock has occurred. Each
process involved in the cycle is deadlocked. In this case, a cycle in the graph is both a necessary and a
sufficient condition for the existence of deadlock.

 If each resource type has several instances, then a cycle does not necessarily imply that a deadlock has
occurred. In this case, a cycle in the graph is a necessary but not a sufficient condition for the existence of
deadlock.
METHODS FOR HANDLING DEADLOCKS
A deadlock can be handled in four different ways :
1. Deadlock Prevention ( Prevent the deadlock from occurring )
2. Deadlock avoidance ( Adopt methods for avoiding deadlock )
3. Deadlock Detection & Recovery ( Allow the deadlock to occur, detect it and recover from it
4. Ignore the deadlock

 Protocols are used to prevent or avoid deadlocks which ensure the safe state of the system
 We can allow the system to enter a deadlocked state, then use algorithms for detection & recovery.
 We can ignore the problem altogether and pretend that deadlocks never occur in the system. This solution is
the one used by most operating systems, including Linux and Windows. It is then up to the application
developer to write programs that handle deadlocks.

Deadlock Prevention
 For a deadlock to occur, each of the four necessary conditions must hold. By ensuring that at least one of
these conditions cannot hold, we can prevent the occurrence of a deadlock.

1. Eliminating Mutual Exclusion

o The resources can be of two types
 Sharable resources
 Non-sharable resources
o In order to prevent deadlock in the system, the deadlock prevention methods ensure that mutual
exclusion property hold only on non-sharable resources.

Page 6 of 12
Operating System – Module II Notes – Part 2 Process Synchronization, Deadlock
o Sharable resources do not require mutually exclusive access and thus cannot be involved in a
deadlock.
o For example, a read only file ( sharable resource ) can be accessed by any number of processes at a
time. A non sharable resource , printer, cannot be accessed by several processes simultaneously.
o In general , we cannot prevent deadlocks by denying the mutual exclusion conditions because some
resources are implicitly non sharable.
2. Eliminating Hold and Wait
o Two protocols are used to ensure this
 First protocol suggests that , don’t allow any process to request for a resource until it
releases the resources already held by it, which is impractical as process may require the
resources simultaneously
 Another way to prevent hold and wait condition is to allocate all the required resources
before starting execution of the process, that also impractical always because knowing the
resource requirements in advance may not be possible
 Disadvantage
 Low resource utilization
 Starvation.
3. Eliminating No Preemption
o To ensure that no preemption condition does not hold, two protocols can be used :
 First protocol suggests that, if a process that is holding some resources requests another
resource that cannot be immediately allocated to it, then all resources currently being held
are released. Preempted resources are added to the list of resources for which the process is
waiting. Process will be restarted only when it can regain its old resources, as well as the
new ones that it is requesting.
 Second protocol suggest that, If a process requests some resources, it is allocated as per the
availability of resources. If the requested resource is held by another waiting process, then
that resource is preempted and allocated to the requested process. If the requested resource
is not available and not held by a waiting process, the process has to wait until the resource
become available.
4. Eliminating Circular Wait
o The circular wait condition is eliminated by assigning a priority number to each available resource
and a process can request resources only in increasing order.
o If the priority number of a requested resource is less than that of the currently held resources, all the
resources with greater number must be released first, before acquiring the new resource.
o Suppose a function F:R->N defines priority numbers to resources. A process Pi request a resource
Ri. Ri is allocated to Pi if and only if F(Ri) > F(Rj) where Rj is the resource already held by Pi.
o Example: Suppose , a set of resources have the following numbers :
 F(tape drive)= 10
 F(disk) = 12
 F(printer)=15

Page 7 of 12
Operating System – Module II Notes – Part 2 Process Synchronization, Deadlock
o A process can request a disk and then a printer. But the process cannot request a tape drive after
disk because F(tape drive) < F(disk)
DEADLOCK AVOIDANCE
 Preventing deadlock by eliminating any one of the four conditions results in the inefficient use of the
resources. Instead of preventing, it can be avoided by never allowing allocation of a resource to a process if
it leads to a deadlock.
 The deadlock-avoidance algorithm dynamically examines the resource-allocation state to ensure that there
can never be a circular-wait condition.
 Resource-allocation state is defined by the number of available resources, allocated resources, and the
maximum need of resources by the processes. The state can be either safe or unsafe
 Safe State
o A state is safe if the system can allocate resources to each process in some order without causing
deadlock.
o A system is in safe state only if there is a safe sequence.
o A safe sequence is a sequence of process execution such that each and every process execute till its
completion
o Sequence <P1, P2, …, Pn> is safe, if for each Pi, the resources that Pi can still request can be
satisfied by currently available resources + resources held by all the Pj, with j<i.
o If resource needs of Pi are not immediately available, then Pi can wait until all Pj have finished.
When Pj is finished, Pi can obtain needed resources, execute, return allocated resources, and
terminate.
 When Pi terminates, Pi+1 can obtain its needed resources, and so on.
o For example,
 The no. of tape drives initially available is 12 nos
 The maximum need & already allocated is shown below :
Allocated Max Need
P0 5 10
P1 2 4
P2 2 9
Already allocated : 9 Nos
Balance Available = ( 12 – 9 ) = 3 Nos ,
2 out of 3 can be allocated to P1
Once , P1 completes its task, 4 tape drives will be released
Now, 5 tape drives are available, It can be allocated to P0.
On completion of P0, 10 tape drives will be released
Now P2, will get all the 7 tape drives required for its execution.

So, the safe sequence is < P1, P0, P2 > , So the system is in safe state.

 If a system is in safe state , no deadlocks. If a system is in unsafe state , there is a possibility of

deadlock.
Page 8 of 12
Operating System – Module II Notes – Part 2 Process Synchronization, Deadlock
 Avoidance ensure that a system will never enter an unsafe state.
 Figure shows Safe, Unsafe and deadlocked state spaces.

Two types of algorithms are used to avoid deadlocks:

1. Resource allocation graph algorithm
2. Banker’s Algorithm
RESOURCE ALLOCATION GRAPH ALGORITHM
 In addition to request edge and assignment edge, a new type of edge is introduced known as claim edge
 A claim edge Pi -> Rj indicates that Pi may request an instance of Rj in future. It is denoted by dashed
line.
 Suppose a process Pi requests a resource Rj. The request can be granted only if, converting the request edge
Pi -> Rj to assignment edge Rj -> Pi does not form a cycle in RAG. If no cycle exists, the allocation will
leave the system in safe state. If a cycle is formed, the system is in unsafe state. Therefore, the process Pi
has to wait until the request to be granted.
 Pi Rj ( Claim edge ) - may request in future
 Pi Rj ( Request Edge ) - Requesting
 Pi Rj ( Assignment Edge ) - allocating
 A claim edge is converted to request edge, when Pi request for Rj. When Rj is allocated to Pi, the request
edge will be converted to assignment edge.
 Example : Figure shows a sample RAG for deadlock avoidance

 R1 is allocated to P1. P1 may request R2. P2 requested for R1. P2 may request R2 in future.
 When P2 request R2, the graph will become as shown below : ( draw by yourself )
 If R2 is available, it can be allocated to P2. ( request becomes assignment as show below )

Page 9 of 12
Operating System – Module II Notes – Part 2 Process Synchronization, Deadlock
 If P1 request for R2, a deadlock will occur. RAG algorithm checks whether the allocation will form cycle or
not before converting claim edge to request edge.
BANKER’S ALGORITHM ( SAFETY ALGORITHM & RESOURCE-REQUEST ALGORITHM )
This algorithm uses the following data structures
1. Available Vector: A vector of size q to store available resources
2. Max Matrix : A matrix M of order p x q to store information about maximum number of each resource
type required by each process ( p number of processes )
3. Allocation Matrix: A matrix C of order p x q to store information about the number of resources of each
type allocated to each process.
4. Need Matrix: A matrix R of order p x p – remaining number of resources required by each process
Safety Algorithm ( determine whether or not the system is in safe state)
1. Consider a vector finish of size p ( no. of processes). Initialize finish[i]=false, for i=0, 1, 2, ……, p-1
2. Find an i such that finish[i]=false and Need<=Available, that is resources required by this process is less
than the resources available. If no such process exists, go to step 4.
3. Allocate required resources to i th process and let it finish execution. Set finish[i]=true and add all its
resources to Available vector A , go to step 2
4. If finish[i]=true for all i, then the system is in a safe state
Resource–request algorithm (Determines whether the request by a process can be satisfied or not)
1. If request <= Max, go to step 2. Otherwise, raise an error condition because the process has exceeded its
maximum claim.
2. If request < available, go to step3. Otherwise process has to wait because the resources are not available
3. Allocate the resources and make following changes :
o Available = Available – Request
o Allocation = Allocation + Request
o Need = Need – Request
If the resulting resource allocation state is safe, Process will get its resources and can proceed with execution.
Otherwise process has to wait for Request and old resource allocation state is restored.
Example :
Consider a system with three processes P1, P2 and P3 and three resources X, Y, Z
Initial State of the system
There are 10 instances of resource X, 5 of Y and 7 of Z
 Initial state of the system is given below :

Max Matrix Allocation Need ( Max – Available

Allocation )
X Y Z X Y Z X Y Z X Y Z
P1 7 5 6 P1 0 1 0 P1 7 4 6 5 4 5
P2 5 2 2 P2 2 0 0 P2 3 2 2
P3 9 0 2 P3 3 0 2 P3 6 0 0

Applying Safety algorithm, it can be observed that, there is a safe sequence < P2, P3, P1 >
Page 10 of 12
Operating System – Module II Notes – Part 2 Process Synchronization, Deadlock
DEADLOCK DETECTION
 If a system does not apply either a deadlock-prevention or a deadlock avoidance method, then a deadlock
situation may occur. In such situations, an algorithm must be provided for detecting the occurrence of
deadlock in a system.
DETECTING DEADLOCK IN CASE WE HAVE SINGLE INSTANCE OF EACH RESOURCE TYPE
 A variation of RAG (Resource Allocation Graph) known as Wait-for Graph is used in this situation. Wait-
for graph shows dependency of a process on another process for resource allocation.
 A resource allocation graph involving 5 processes and 5 resources are shown in the figure. The
corresponding wait-for graph is also shown.

 We obtain this graph from the resource-allocation graph by removing the resource nodes and collapsing the
appropriate edges.
 An edge from Pi to Pj in a wait-for graph implies that process Pi is waiting for process Pj to release a
resource that Pi needs.
 An edge Pi → Pj exists in a wait-for graph if and only if the corresponding resource allocation graph
contains two edges Pi → Rq and Rq → Pj for some resource Rq .
 A deadlock exists in the system if and only if the wait-for graph contains a cycle.
 To detect deadlocks, the system needs to maintain the wait for graph and periodically invoke an algorithm
that searches for a cycle in the graph.

DETECTING DEADLOCK IN CASE WE HAVE MULTIPLE INSTANCES OF A RESOURCE TYPE

 When multiple instances of a resource type exist, the wait-for-graph becomes inefficient; another algorithm
which uses certain data structures like Banker’s algorithm is applied.
 Data Structures used :
1. Available : A vector of length m indicates the number of available resources of each type
2. Allocation : An m x n matrix defines the number of resources of each type currently allocated to each
processes
3. Request : An m x n matrix indicates the current request of each process
 Algorithm
1) Let Work and Finish be vectors of length m and n, respectively. Initialize Work = Available. For
i=0,1,…, n-1, if Allocation(i) != 0, then Finish[i]=false, otherwise , Finish[i]=true
2) Find an index i such that both
a. Finish[i]==false
Page 11 of 12
Operating System – Module II Notes – Part 2 Process Synchronization, Deadlock
b. Request(i) <= Work
If no such i exists, go to step 4
3) Work = Work + Allocation(i) ; Finish[i]=true ; Go to step 2
4) If Finish[i] == false for some i, 0<=i<=n , then the system is in deadlocked state. Moreover, if
Finish[i] == false, then Pi is deadlocked.

RECOVERY FROM DEADLOCK

When a detection algorithm determines that a deadlock exists, there are two possibilities for recovery:
1) Operator deal with the deadlock manually
2) Let the system recover from deadlock automatically
There are two options for automatic recovery:
1) Process Termination: Simply abort one or more processes to break the circular wait.
2) Preempting the resources: Preempt some resources from one or more of the deadlocked
processes.
1) PROCESS TERMINATION
To eliminate deadlocks by aborting a process, we use one of two methods. In both methods, the system
reclaims all resources allocated to the terminated processes.
1) Abort all deadlocked processes. This method clearly will break the deadlock cycle, but at
great expense. The deadlocked processes may have computed for a long time, and the results of
these partial computations must be discarded and probably will have to be recomputed later.
2) Abort one process at a time until the deadlock cycle is eliminated. This method incurs
considerable overhead, since after each process is aborted, a deadlock-detection algorithm must
be invoked to determine whether any processes are still deadlocked.
Criteria for selecting the process
1) Priority of the process
2) How long the process has computed
3) The number and types of resources the process has used
4) How many more resources the process needs to complete its execution
5) How many processes will need to be terminated
6) Whether the process is interactive or batch

2) PREEMPTING THE RESOURCES

Preempt resources from processes one by one and allocate them to other processes until the circular-
wait condition is eliminated.
Steps involved in this process are:
i. Select a process for preemption : choose process which causes minimum cost to the
system
ii. Rollback of the process : After preempting resources, rollback the process properly to
maintain the consistency of the system
iii. Prevent starvation: Try to avoid the situation of starvation by ensuring that resources will
not always be preempted from the same process.
Page 12 of 12