Process synchronization and

deadlocks

Unit 3

VGKhetade
 Introduction
• A cooperating process is one that can affect or be affected by other
processes executing in the system.

• Cooperating processes can either directly share a logical address space (that
is, both code and data) or be allowed to share data only through files or
messages.

• processes can execute concurrently or in parallel.

• one process may only partially complete execution before another process is
scheduled.

• In fact, a process may be interrupted at any point in its instruction stream,

and the processing core may be assigned to execute instructions of another VGKhetade
process.
• Process Synchronization means sharing system resources by processes in a
such a way that, Concurrent access to shared data is handled thereby
minimizing the chance of inconsistent data.

• Process Synchronization was introduced to handle problems that arise while

multiple process executions.

• On the basis of synchronization, processes are categorized as one of the

following two types:

• Independent Process : Execution of one process does not affects the

execution of other processes.
• Cooperative Process : Execution of one process affects the execution of
other processes. VGKhetade
 Critical Section Problem
• We begin our consideration of process synchronization by discussing the so
called critical-section problem.

• Consider a system consisting of n processes {P0, P1, ..., Pn−1}.

• Each process has a segment of code, called a critical section, in which the
process may be changing common variables, updating a table, writing a file,
and so on.

• The important feature of the system is that, when one process is executing in
its critical section, no other process is allowed to execute in its critical
section.
• That is, no two processes are executing in their critical sections at the same
time. VGKhetade
• The critical-section problem is to design a protocol that the processes
can use to cooperate.

• Each process must request permission to enter its critical section.

• The section of code implementing this request is the entry section.

• The critical section may be followed by an exit section.

• The remaining code is the remainder section.

VGKhetade
Fig. General structure of a typical process Pi .
VGKhetade
• A solution to the critical-section problem must satisfy the following three
requirements:

• Mutual exclusion. If process Pi is executing in its critical section, then no other

processes can be executing in their critical sections.

• 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 deciding which will enter its critical section next.

• Bounded waiting. After a process makes a request for getting into its critical section,
there is a limit for how many other processes can get into their critical section, before
this process's request is granted. So after the limit is reached, system must grant the
process permission to get into its critical section..

VGKhetade
 Peterson’s Solution
• A classic software-based solution to the critical-section problem known as Peterson’s
solution.

• Peterson’s solution is restricted to two processes that alternate execution between

their critical sections and remainder sections.

• The processes are numbered P0 and P1. For convenience, when presenting Pi , we use Pj
to denote the other process; that is, j equals 1 − i.
• In Peterson’s solution, we have two shared variables:
• Boolean flag[i] :used to indicate if a process is ready to enter its critical section
• int turn : indicates whose turn it is to enter its critical section

VGKhetade
• The variable turn indicates whose turn it is to enter its critical section.

• That is, if turn == i, then process Pi is allowed to execute in its critical section.

• The flag array is used to indicate if a process is ready to enter its critical section.

• For example, if flag[i] is true, this value indicates that Pi is ready to enter its critical
section.

VGKhetade
Peterson solution

VGKhetade
• 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 blocks
other processes from entering the critical section.

• Bounded Waiting is preserved as every process gets a fair chance.

• Disadvantages of Peterson’s Solution

• It involves Busy waiting
• It is limited to 2 processes. VGKhetade
 Semaphores
• Semaphore is nothing but a synchronization tool with the help of which we can ensure
that the critical section can be accessed by the processes in a mutually exclusible.
• A semaphore S is an integer variable that, apart from initialization, is accessed only
through two standard atomic operations: wait() and signal().
• The wait() operation was originally termed P (from the Dutch proberen, “to test”);
signal() was originally called V (from verhogen, “to increment”).

• The definition of wait() is as follows:

wait(S) {
while (S <=0) ; // busy wait
S--;
}

• The definition of signal() is as follows:

signal(S) {
S++;
} VGKhetade
• Semaphore is a simply a variable. This variable is used to solve
critical section problem and to achieve process synchronization in
the multi processing environment.

• Wait() :-- it is called when a process wants to access a resource. (

when the semaphore variable is negative, the process wait is
blocked.

• Signal():-- is called when a process is done using a resource.

VGKhetade
 Implementation of mutual exclusion

• The definition of wait() is as follows:

wait(S) {
while (S <=0) ; // busy wait
S--;
}

• The definition of signal() is as follows:

signal(S) {
S++;
}

VGKhetade
• Let there be two processes P1 and P2 and a semaphore s is initialized as
s

1.
• Now if suppose P1 enters in its critical section then the value of
semaphore s becomes 0.
• Now if P2 wants to enter its critical section then it will wait until s > 0,
this can only happen when P1 finishes its critical section and calls V
operation on semaphore s.
• This way mutual exclusion is achieved.

VGKhetade
Types of semaphores
s

VGKhetade
Classis problems of synchronizations
1] Bounded buffer problem

VGKhetade
Solution to bounded buffer problem using semaphore

VGKhetade
s

VGKhetade
 s

VGKhetade
s

VGKhetade
s

VGKhetade
System Model
• A system consists of a finite number of resources to be distributed
among a number of competing processes.
• The resources may be partitioned into several types (or classes), each
consisting of some number of identical instances.
• CPU cycles, files, and I/O devices (such as printers and DVD drives) are
examples of resource types.

VGKhetade
Deadlocks
• In a multiprogramming environment, several processes may compete
for a finite number of resources.
• A process requests resources; if the resources 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.

VGKhetade
Deadlock characterization
• In a deadlock, processes never finish executing, and system resources
are tied up, preventing other jobs from starting.
• A deadlock situation can arise if the following four conditions hold
simultaneously in a system:

VGKhetade
 Resource-Allocation Graph
• 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:

• P = {P1, P2, ..., Pn}, the set consisting of all the active processes in the system, and 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
VGKhetade
• 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 Pi → Rj is called a request edge;
• A directed edge Rj → Pi is called an assignment edge.
• Pictorially, each process Pi is represented as a circle and each resource type Rj is represented as a
rectangle.
• Since resource type Rj may have more than one instance, each such instance is represented as a dot
within the rectangle.

VGKhetade
• Resource allocation graph

VGKhetade
VGKhetade
• Given the definition of a resource-allocation graph, it can be shown that, 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.

• If the cycle involves only a set of resource types, each of which has only a single instance,
then a deadlock has occurred

VGKhetade
VGKhetade
VGKhetade
 Methods for Handling Deadlocks
• we can deal with the deadlock problem in one of three ways:

• We can use a protocol to prevent or avoid deadlocks, ensuring that the system will
never enter a deadlocked state.
• We can allow the system to enter a deadlocked state, detect it, and recover.
• We can ignore the problem altogether and pretend that deadlocks never occur in the
system.
• To ensure that deadlocks never occur, the system can use either a deadlock
prevention or a deadlock-avoidance scheme.
• Deadlock prevention algorithms ensure that at least one of the necessary conditions
(Mutual exclusion, hold and wait, no preemption and circular wait) does not hold
true.
• Deadlock avoidance requires that the operating system be given additional
information in advance concerning which resources a process will request and useVGKhetade
during its lifetime
 Deadlock Avoidance
• An alternative method for avoiding deadlocks is to require additional
information about how resources are to be requested.
• For example, in a system with one tape drive and one printer, the system
might need to know that process P will request first the tape drive and
then the printer before releasing both resources, whereas process Q will
request first the printer and then the tape drive.
• Here the operating system should have a prior knowledge regarding the
resources currently available, the resources currently allocated to each
process, and the future requests and releases of each process.

VGKhetade
 Safe State
• The resource allocation state is defined by the number of available and allocated resources
and the maximum demands of the processes.
• A state is safe if the system can allocate resources to each process(up to its maximum) in some
order and still avoid a deadlock.

• More formally, a system is in a safe state only if there exists a safe sequence.

• If Pi resource needs 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

• A safe state is not a deadlocked state.

• Conversely, a deadlocked state is an unsafe state.
VGKhetade
• Not all unsafe states are deadlocks, however An unsafe state may lead to a deadlock
• As long as the state is safe, the operating system can avoid unsafe (and deadlocked)
states.

• Basic fact:----

• If a system is in safe state  no deadlocks

• If a system is in unsafe state  possibility of deadlock

• Avoidance  ensure that a system will never enter an unsafe state.

VGKhetade
 example
• we consider a system with twelve magnetic tape drives and three processes:
• P0, P1, and P2.
• Process P0 requires ten tape drives
• process P1 may need as many as four tape drives
• process P2 may need up to nine tape drives.

• Suppose that, at time t0, process P0 is holding five tape drives

• Process P1 is holding two tape drives
• process P2 is holding two tape drives(Thus, there are three free tape drives.)

VGKhetade
• At time t0, the system is in a safe state.

• The sequence <P1, P0, P2> satisfies the safety condition.

• Process P1 can immediately be allocated all its tape drives and then return them (the system
will then have five available tape drives);
• then process P0 can get all its tape drives and return them (the system will then have ten
available tape drives); and finally process P2 can get all its tape drives and return them (the
system will then have all twelve tape drives available)
• A system can go from a safe state to an unsafe state……….

• Suppose that, at time t1, process P2 requests and is allocated one more tape drive.

• The system is no longer in a safe state. At this point, only process P1 can be allocated all its
tape drives.

VGKhetade
• When it returns them, the system will have only four available tape drives.

• Since process P0 is allocated five tape drives but has a maximum of ten, it may request
five more tape drives.

• If it does so, it will have to wait, because they are unavailable.

• Similarly, process P2 may request six additional tape drives and have to wait, resulting in
a deadlock.

VGKhetade
Banker’s Algorithm
• The resource-allocation-graph algorithm is not applicable to a
resource allocation system with multiple instances of each resource
type.
• The banker’s algorithm is applicable to a resource allocation system
with multiple instances of each resource type.
• The name was chosen because the algorithm could be used in a
banking system to ensure that the bank never allocated its available
cash in such a way that it could no longer satisfy the needs of all its
customers.

VGKhetade
 s

• When a new process enters the system, it must declare the

maximum number of instances of each resource type that it may
need. This number may not exceed the total number of resources in
the system.
• When a user requests a set of resources, the system must determine
whether the allocation of these resources will leave the system in a
safe state.
• If it will, the resources are allocated; otherwise, the process must
wait until some other process releases enough resources.

VGKhetade
• Bankers’s Algorithm is resource allocation and deadlock avoidance algorithm which test all
the request made by processes for resources, it check for safe state, if after granting
request system remains in the safe state it allows the request and if their is no safe state it
don’t allow the request made by the process.

• Inputs to Banker’s Algorithm

1. Max need of resources by each process.
2. Currently allocated resources by each process.
3. Max free available resources in the system.

• Request will only be granted under below condition.

1. If request made by process is less than equal to max need to that process.
• 2. If request made by process is less than equal to freely available resource in the system.

VGKhetade
VGKhetade
Problem 1
• Consider a system with 5 processes P0, P1, P2, P3 and [Link] are 3
types of resources A, B and C. There are 10 instances of A, 5 instances
of B and 7 instances of C. At time T0, the following snapshot of the
system has been taken. Using Bankers algorithm, determine system is
in safe state or unsafe state.

Process Allocation Max

A B C A B C

P0 0 1 0 7 5 3
P1 2 0 0 3 2 2
P2 3 0 2 9 0 2
P3 2 1 1 2 2 2
P4 0 0 2 4 3 3
VGKhetade
Problem1 solution

VGKhetade
s

VGKhetade
Problem 2
• Consider a system with 5 processes P0, P1, P2, P3 and [Link] are 3
types of resources A, B and C. There are 10 instances of A, 5 instances
of B and 7 instances of C. At time T0, the following snapshot of the
system has been taken. Using Bankers algorithm, determine system is
in safe state or unsafe state.

Process Allocation Max

A B C A B C

P0 0 1 0 7 5 3
P1 2 0 0 3 2 2
P2 3 0 2 9 0 2
P3 2 1 1 4 2 2
P4 0 0 2 5 3 3

VGKhetade
VGKhetade
Recovery from Deadlock

VGKhetade