UNIT 3

INTER-PROCESS COMMUNICATION,
SYNCHRONIZATION AND
DEADLOCKS
CONCURRENCY AND PARALLELISM

• Concurrency
• Parallelism
• Principles of concurrency: interleaving , overlapping
• Problems in uniprocessor and multi processor systems
CONCURRENT ACCESS TO SHARED DATA

• Concurrent access to shared data may result in data

inconsistency (e.g., due to race conditions)

• Maintaining data consistency requires mechanisms to

ensure the orderly execution of cooperating processes
OPERATING SYSTEM CONCERNS

• Keep track of various process

• PCB
• Resources allocation
• processor time, memory, files, IO devices
• Process should not interfere each other data and resources
• Speed of process and output produced should not affect meaning interaction of processes must be
handled carefully
• Process Interaction
PROCESS INTERACTION

• Processes unaware of each other

• Processes indirectly aware of each other
• Processes directly aware of each other
The critical section problem is used to design a protocol followed by a group of processes,
so that when one process has entered its critical section, no other process is allowed to
execute in its critical section.

The critical section refers to the segment of code where processes access shared resources,
such as common variables and files, and perform write operations on them. Since processes
execute concurrently, any process can be interrupted mid-execution. In the case of shared
resources, partial execution of processes can lead to data inconsistencies.

When two processes access and manipulate the shared resource concurrently, and the
resulting execution outcome depends on the order in which processes access the resource;
this is called a race condition.

Race conditions lead to inconsistent states of data. Therefore, we need a synchronization

protocol that allows processes to cooperate while manipulating shared resources, which
essentially is the critical section problem.
 INTER-PROCESS COMMUNICATION
(IPC)
• 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.
• Process synchronization problem mainly arises in the case of Cooperative process because resources are shared
in Cooperative processes.
• There are certain reasons due to which cooperative environment is created:
• Information sharing
• Computation speedup
• Modularity
• Convenience
 INTER-PROCESS COMMUNICATION
(IPC)
• Mechanism followed by cooperating processes to communicate with each other is
called as Inter-process Communication (IPC)
• IPC allows processes to exchange data and information
• There are two fundamental models which allow Inter-process Communication :
• Shared memory: In this model, sharing region is established. From this sharing
region, cooperating processes exchange data or information. They can read and
write data from and to this region
• Message passing: allows multiple processes to read and write data to the
message queue without being connected to each other. Messages are stored on
the queue until their recipient retrieves them.
INTER-PROCESS COMMUNICATION
MODELS

Shared memory is the memory that Both the processes P1 and P2 can
can be simultaneously accessed by access the message queue and
multiple processes. This is done so store and retrieve data.
that the processes can
communicate with each other
SHARED MEMORY MODEL

• Shared memory systems allow processes to share data or information using

shared memory region. Shared memory region resides in the address space
of the process creating the shared memory segment.
• Other processes which need to share this shared region should connect
their address space with the segment of the memory region
• Generally, operating system tries to avoid one process accessing memory of
another process. Shared memory concept is used when two or more
processes are ready to avoid this restriction. They can then read and write
the data to and from shared memory area
• Processes need to ensure that they don’t write at the same location at a
time.
 MESSAGE PASSING MODEL
• In Message passing model, processes can pass the messages to each other without
sharing of their address space. This type of communication is mainly used in
distributed environment (where processes reside on different computers
connected by the network)
• The best example to illustrate message passing system is the chat which takes place
on the World Wide Web, where multiple users chat from different locations.
They exchange messages from different nodes/locations
• Two facilities: send and receive are used to exchange the messages
• Messages sent by the processes are of either fixed or variable size. System level
implementation is straightforward if the messages sent are of the fixed length and it
is complicated for variable length messages
SHARED MEMORY

• Common address space for processes are in same machine

• The shared memory code to be written explicitly by the application programmer
• Provides maximum speed of communication
• Processes should not be writing to the same location simultaneously
MESSAGE PASSING

It is used for communication

It is used in distributed environment
It facilitates mechanism for communication and synchronization of actions , so no separate
code required
It implements through system calls so time consuming process
Message passing is useful for sharing small amounts of data so that conflicts need not occur
In message passing the communication is slower when compared to shared memory
technique
PRODUCER CONSUMER PROBLEM

• Compiler Assembler
• Server Client
• Web Server (allows HTML files to run and images)
• These are consumed by the client web browser requesting the resources
 PRODUCER-CONSUMER PROBLEM

• Paradigm for cooperating processes, producer process produces information that is

consumed by a consumer process.

• E.g A compiler may produce assembly code and that would be consumed by an assembler. An
assembler produces object modules which are consumed by loader.
Shared memory can be used to solve the P-C problem.

For that purpose a buffer of items can be used which can be placed in the shared
memory.
P-C must be synchronized.
Two types of buffers can be used:
unbounded-buffer places no practical limit on the size of the buffer so consumer
has to wait if buffer is empty.
bounded-buffer assumes that there is a fixed buffer size so consumer has to wait if
buffer is empty and producer has to wait if buffer is full.
CONSUMER PRODUCER
• int count = 0;
• void consumer (void)
• void producer (void)
• { int itemc;
• { int itemp;
• while(true)
• while(true)
• {
• {
• while(count= =0);
• while(count= = n);
• itemc = buffer [out];
• buffer [in]=itemp;
• out = (out+1) % n;
• in = (in +1) % n;
• count = count – 1
• count = count + 1
• } }
• } }
 Solving Critical Section Problem

The critical section problem needs a solution to synchronize the different

processes. The solution to the critical section problem must satisfy the following
conditions −

• Mutual Exclusion: Mutual exclusion implies that only one process can be inside
the critical section at any time. If any other processes require the critical section,
they must wait until it is free.

• Progress: Progress means that if a process is not using the critical section, then
it should not stop any other process from accessing it. In other words, any process
can enter a critical section if it is free.

• Bounded Waiting: Bounded waiting means that each process must have a
limited waiting time. It should not wait endlessly to access the critical section.
• No Assumption related to hardware or speed
CRITICAL SECTION AND MUTUAL EXCLUSION

Source: [Link]
General Structure of a typical process

Ref. Book by Galvin

SOLUTION TO CRITICAL SECTION PROBLEM

• Synchronization :
• Lock variable

• Hardware Synchronization ( Interrupts)

• Peterson’s Solution
• Semaphores
 • Lock variable

do{ 1. while (Lock==1); // entry code

2. Lock = 1
acquire lock
3. CS
CS 4. Lock = 0 // exit code
release lock
}

Analyse if mutual exclusion is guaranteed or not

Mutual exclusion is not guaranteed so what is the solution to the problem
MUTUAL EXCLUSION WITH TEST AND SET

• do • boolean TestAndSet(boolean *target)

• { while(TestAndSet(&Lock)) ; // do nothing • {
• // critical section • boolean rv=*target;
• lock=FALSE; • *target = TRUE;
• //remainder section • return rv;
• } while (TRUE); • }
•
Getting help from hardware

Because of interrupts, CPU makes switching from one process to another. When interrupts
are disabled, CPU switching will not happen
In lock variable mechanism, sometimes Process reads the old value of
lock variable and enters the critical section. Due to this reason, more than
one process might get into critical section. The solution is to use TAS or
TSL Mechanism
PETERSON’S SOLUTION
• It Is a classic software-based solution for Critical Section problem.
• 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.
• Peterson’s solution requires the two processes to share two variables:
• int turn;
• Boolean flag[2] Initially: flag[0]=flag[1]= false (because initially no one is
interested in entering the CS)
• The variable turn indicates which of the two processes is allowed to enter its
critical section first. 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 the critical section.
flag[i] = true implies that process Pi is ready to enter critical section!
To enter the critical section, process Pi first sets flag [i] to be true and then sets turn to
the value j, thereby asserting that if the other process wishes to enter the critical section,
it can do so.
PERTERSON’S ALGORITHM IN PROCESS
SYNCHRONIZATION
• Problem: The producer consumer problem (or bounded buffer problem) describes
two processes, the producer and the consumer, which share a common, fixed-size
buffer used as a queue. Producer produce an item and put it into buffer. If buffer is
already full then producer will have to wait for an empty block in buffer. Consumer
consume an item from buffer. If buffer is already empty then consumer will have to
wait for an item in buffer. Implement Peterson’s Algorithm for the two processes using
shared memory such that there is mutual exclusion between them. The solution
should be free from synchronization problems.
PETERSON’S ALGORITHM –
Explanation of Peterson’s algorithm –

Peterson’s Algorithm is used to synchronize two processes. It uses two variables,

a bool array flag of size 2 and an int variable turn to accomplish it.

In the solution i represents the Consumer and j represents the Producer. Initially
the flags are false. When a process wants to execute its critical section, it sets its
flag to true and turn as the index of the other process. This means that the
process wants to execute but it will allow the other process to run first. The
process performs busy waiting until the other process has finished its own
critical section.

After this the current process enters its critical section and adds or removes a
random number from the shared buffer. After completing the critical section, it
sets its own flag to false, indication it does not wish to execute anymore.
flag: array [0 1] of boolean

turn : 0,1

begin flag [0] : false repeat for process 1

flag [1]:=false flag [1]=true
repeat for process i,j (i=0, j=1) turn = 0
flag [0]=true while flag [0] and turn =0
turn = 1 do {nothing};
while flag [1] and turn =1
{CS}
do {nothing};
flag [1]: = false
{CS}
{remainder section}
flag [0]: = false

{remainder section}

Prove that this ensures three properties

do {
flag[1]= True
P2 came
turn=2
while (flag[2] && turn = =2); // p2 will flag [1] = false
not enter p1 will
CS
turn = 2
flag [1] =false while (flag [2] && turn ==2) // p2 enters
RS
CS
}
while true
• 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

• It involves Busy waiting
• It is limited to 2 processes.
• Software-based solutions like Peterson's are not guaranteed to work on
modern computer architectures
• Both Peterson's and the TSL solutions solve the mutual exclusion problem.

• However, both of these solutions have the problem of busy waiting. That is, if the
process is not allowed to enter its critical section it sits in a tight loop waiting for a
condition to be met. This is obviously wasteful in terms of CPU usage.
 SOLUTION OF CRITICAL SECTION
PROBLEM USING SEMAPHORES

• Let’s assume that there are

two processes P1 and P2
which want to access the
critical section
do
{
wait(s);
// critical section
signal(s);
//remainder section
} while(T)
 SEMAPHORE

• Semaphore is an integer variable that solves the critical section problem. After
initialization, it can only be accessed and changed by two atomic operations:
• wait() -- decrement, wait/block until semaphore is open. Also called P(), sleep,
or down operation
• signal() – increment, allow another thread to enter. Also called V(), wake-up,
or up operation.

• Both operations are atomic and semaphore(s) is always initialized to one. Here
atomic means that variable on which read, modify and update happens at the
same time/moment with no pre-emption i.e. in-between read, modify and update
no other operation is performed that may change the variable.

• A critical section is surrounded by both operations to implement process

synchronization
DEFINITION OF SEMAPHORE PRIMITIVES
Types of Semaphores

• Binary Semaphores: Binary semaphores are synchronization mechanisms

with integer values varying between zero (0) and one (1). Thus, this category
of semaphore provides a single access unit to a critical section. It means that
only one entity will access the critical section at once.

• Counting Semaphores: Counting semaphores are synchronization

mechanisms with values varying in a range [0,n], where n is a non-negative
integer value greater than one (1). In this way, counting semaphores can
make available several access tokens to a given critical section. So, several
entities can access the critical section at the same time.
BINARY SEMAPHORE
SOLUTION TO THE PRODUCER CONSUMER
PROBLEM
CONSUMER PRODUCER
• void producer (itemp)
• void consumer (void)
• { int itemp;
• { int itemc;
• while(true)
• while(true)
• {
• {down(full);
• down(empty);
• down(s);
• down(s);
• itemc = buffer [out];
• buffer [in]=itemp;
• out = (out+1) % n;
• in = (in +1) % n;
• up(s);
• up(s)
• up(empty)
• up(full)
• } }
• } }
READER WRITER PROBLEM

Many readers can perform reading simultaneously

reading is prohibited while writer is writing
only one writer can perform the writing at a time
reader have non preemptive priority over writer
 READER WRITER PROBLEM SOLUTION
• int rc=0; • down(mutex)//exit code reader
• semaphore mutex = 1; • rc=rc--1;
• semaphore db=1; • if(rc==o) then
• void Reader(void) //entry code for reader • up(db);
• { • up(mutex)
• while(true)
• process_data
• {
• }}//exit code for reader ends
• down(mutex);
• void write(void) //entry code for writer
• rc=rc+1;
• { while(true)
• if(rc==1) then
• {
• down(db);
• down(db);
• up(mutex)
• {up(db); //exit code for writer
• DB
• }
case1 RW
case2 WR
case3 WW
case 4 RR
DINNING PHILOSOPHERS PROBLEM AND
SOLUTION
• Void philosopher(void)
• { p0

• while(true) f1 f0

• {
• thinking();
p4
• take_fork(i);//it will take left f p1
f4
• take_fork((i+1)%N);// then right f2

• eat(); p3
• put_fork(i);//it will put left f f3
p2
• put_fork((i+1)%N);// put right
• }}
DINNING PHILOSOPHERS PROBLEM AND
SOLUTION
• Void philosopher(void)
• {

• while(true)
• {
• thinking();

• wait(take_fork(Si));//it will take left f

• wait(take_fork(S(i+1)%N));// then right
• eat();

• signal(put_fork(Si));//it will put left f

• signal(put_fork((Si+1)%N));// put right
• }}
P0 S0 S1
P1 S1 S2
P2 S2 S3
P3 S3 S4
P4 S4 S0
SCHEMATIC VIEW OF A MONITOR
WORKING OF MONITOR
MONITOR WITH CONDITION VARIABLES
63
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.

• This results from sharing resources such as memory, devices, files, links.

• Operating systems typically do not provide deadlock-prevention facilities, and it

remains the responsibility of programmers to ensure that they design deadlock-free
programs.
 64
DEADLOCKS Bridge Crossing
7:
Deadloc Example
ks

• Traffic only in one direction.

• Each section of a bridge can be viewed as a resource.
• If a deadlock occurs, it can be resolved if one car backs up (preempt
resources and rollback).
• Several cars may have to be backed up if a deadlock occurs.
• Starvation is possible.
 Deadlock Principles

⮚ A deadlock is a permanent blocking of a set of processes

✔ a deadlock can happen while threads/processes are competing for system resources or
communicating with each other
 SYSTEM MODEL
• A system consists of a finite number of resources (physical or logical) to be distributed among a number of competing processes. The resources are partitioned into
several types, each consisting of some number of identical instances. Memory space, CPU cycles, files, semaphores and I/0 devices (such as printers and DVD
drives) are examples of resource types. If a system has two CPUs, then the resource type CPU has as two instances. Similarly, the resource type printer may have
five instances.

• If a process requests an instance of a resource type, the allocation of any instance of the type will satisfy the request. If it will not, then the instances are not identical,
and the resource type classes have not been defined properly..

• Each process utilizes a resource as follows:

• request
• use
• Release
o The request and release of resources are system calls. Request and release of resources that are not managed by the operating system can be accomplished
through the wait() and signal() operations on semaphores or through acquisition and release of a mutex lock. For each use of a kernel managed resource by a
process or thread, the operating system checks to make sure that the process has requested and has been allocated the resource
o To illustrate a deadlocked state, consider a system with one printer and one DVD drive. Suppose that process P; is holding the DVD and process Pi is holding
the printer. If P; requests the printer and P1 requests the DVD drive, a deadlock occurs. This example illustrates a deadlock involving the different resource type.
o A programmer who is developing multithreaded applications must pay particular attention to this problem. Multithreaded programs are good candidates for
deadlock because multiple threads can compete for shared resources
 67
DEADLOCKS DEADLOCK
7:
Deadloc CHARACTERISATION
ks
NECESSARY CONDITIONS
ALL of these four must happen simultaneously for a deadlock to occur:

Mutual exclusion
At least one resource must be held in a non-sharable mode; that is, only one process at a time can use the resource. If
another process requests that resource, the requesting process must be delayed until the resource has been released.

Hold and Wait

A process holds a resource while waiting to acquire another resource held by other processes.

No Preemption
There is only voluntary release of a resource - nobody else can make a process give up a resource.

Circular Wait
A set { P0 , Pl, ... , P11 } 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.
METHODS FOR HANDLING DEADLOCKS
🞆 Prevention
⚫Ensure that the system will never enter a deadlock state. Prevent any one of the 4
conditions from happening

🞆 Avoidance
⚫Ensure that the system will never enter an unsafe state. Allow all deadlock conditions, but
calculate cycles about to happen and stop dangerous operations.
🞆 Detection
⚫Allow the system to enter a deadlock state and then recover

🞆 Do Nothing
⚫Ignore the problem and let the user or system administrator respond to the problem;
used by most operating systems, including Windows and UNIX
To ensure that deadlocks never occur, the system can either use a deadlock-prevention or a
deadlock-avoidance scheme
 69 DEADLOCKS Deadlock
Prevention
Do not allow one of the four conditions to
occur.

Mutual exclusion:
Must holds for printers and other non-
sharable resources.
Shared entities (read only files) don't
need mutual exclusion (and aren’t
susceptible to deadlock.). A process
never needs to wait for a sharable
resource.
In general, however, we cannot prevent
deadlocks by denying the mutual-
exclusion condition, because some
resources are intrinsically non-sharable.
 70
DEADLOCKS Deadlock
Prevention
No preemption:
• If a process that is holding some
resources requests another
resource that cannot be
immediately allocated to it, then
all resources currently being
held by the process are released
• Preempted resources are added
to the list of resources for which
the process is waiting
• A process will be restarted only
when it can regain its old
resources, as well as the new
ones that it is requesting .
 71

Hold and wait:

⚫We must guarantee that whenever a process requests a resource, it does
not hold any other resources

⚫One protocol that can be used requires each process to request and be
allocated all its resources before it begins execution. We can implement this
provision by requiring that system calls requesting resources for a process
precede all other system calls.

⚫An alternative protocol allows a process to request resources only when it

has none. A process may request some resources and use them. Before it
can request any additional resources, however, it must release all the
resources that it is currently allocated.
⚫Require a process to request and be allocated all its resources before it
begins execution, or allow a process to request resources only when the
process has none
⚫Result: Low resource utilization; starvation possible
 72

CIRCULAR WAIT

TO MAKE SURE THAT

THIS CONDITION
NEVER HOLDS,
IMPOSE A TOTAL
ORDERING OF ALL
RESOURCE TYPES,
AND REQUIRE THAT
EACH PROCESS
REQUESTS
RESOURCES IN AN
INCREASING ORDER
OF ENUMERATION.

.
73
DEADLOCKS Deadlock
Avoidance
If we have prior knowledge of how resources will be requested, it's possible to determine if we are
entering an "unsafe" state.

Possible states are:

Deadlock No forward progress can be made.

Unsafe state A state that may allow deadlock.

Safe state A state is safe if a sequence of processes exist such that there are enough
resources for the first to finish, and as each finishes and releases its
resources there are enough for the next to finish.

The rule is simple: If a request allocation would cause an unsafe state, do not honor that request.

NOTE: All deadlocks are unsafe, but all unsafes are NOT deadlocks.
 DEADLOCKS Deadlock
Avoidance
NOTE: All deadlocks are unsafe, but all unsafe are NOT deadlocks.

If a system is in safe state ⇒ no deadlocks.

A safe state is not a deadlocked state. Conversely, a UNSAFE
deadlocked state is an unsafe state. Not all unsafe states
are deadlocks, however (Figure below). An unsafe state
may lead to a deadlock. As long as the state is safe, the
operating system can avoid unsafe (and deadlocked)
states. In an unsafe state, the operating system cannot
prevent processes from requesting resources in such a way
DEADLOC
SAFE
that a deadlock occurs. The behavior of the processes K
controls unsafe states.

If a system is in unsafe state ⇒ possibility of deadlock

Avoidance ⇒ ensure that a system will never enter an unsafe

state
 SAFE STATE
🞆 When a process requests an available resource, the system must decide if immediate allocation leaves the
system in a safe state
🞆 A state can be called as safe state if system is capable of providing the resources to each and every process up
to its maximum value or as per its requirement. A safe state cant be a deadlock state.
🞆 The deadlock state is known as unsafe state. In unsafe state, system is not able to allocate the different
resources required by the processes.
🞆 A system is in a safe state only if there exists a safe sequence
🞆 A sequence of processes <P1, P2, …, Pn> is a safe sequence for the current allocation state if, for each Pi, the
resource requests that Pi can still make, can be satisfied by currently available resources plus resources held by
all Pj, with j < i.
🞆 That is:
⚫If the 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

If no such sequence exists, then the system state is said to be unsafe.

 AVOIDANCE ALGORITHMS

• For a single instance of a resource type, use a resource-

allocation graph

• For multiple instances of a resource type, use the banker’s

algorithm
 DEADLOCK AVOIDANCE

Requires that the system has some additional a priori information

available.

• Simplest and most useful model requires that each process declare the maximum
number of resources of each type that it may need

• The deadlock-avoidance algorithm dynamically examines the resource-allocation state

to ensure that there can never be a circular-wait condition

• A resource-allocation state is defined by the number of available and allocated

resources, and the maximum demands of the processes
 BANKER’S ALGORITHM
• 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.

• Used when there exists multiple instances of a resource type

• Each process must a priori claim maximum use. 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.
When a process gets all its resources, it must return them in a finite amount of time
80

• Two algorithms are used in bankers algorithm:

• Safety Algorithm:-determines whether the given system is in safe

state or not.

• Resource-Request Algorithm:- Tells whether to assign a new

resource to a process or not.
 DATA STRUCTURES FOR THE BANKER’S
ALGORITHM
Let n = number of processes, and m = number of resources types.

• Available: A vector of length m indicates the number of available resources of each type. If available [j] = k, there are k
instances of resource type Rj available.
• Max: An n X m matrix defines the maximum demand of each process. If Max [i,j] = k, then process Pi may request at most k
instances of resource type Rj.

• Allocation: An n X m matrix defines the number of resources of each type

currently allocated to each process. If Allocation[i,j] = k then Pi is currently allocated k instances of Rj.
• Need: An n X m matrix indicates the remaining resource need of each

process. If Need[i,j] = k, then Pi may need k more instances of Rj to complete its task.
Need [i,j] = Max[i,j] – Allocation [i,j]
SAFETY ALGORITHM
• Let Work and Finish be vectors of length m and n, respectively.
Initialize
• Work := Available
• Finish[i] := false for i = 0,1,2,…,n-1.

• Find an i (i.e. process Pi) such that both:

• Finish[i] = false
• Need_i <= Work
• If no such i exists, go to step 4.

• Work := Work + Allocation_i

• Finish[i] := true
• go to step 2

• If Finish[i] = true for all i, then the system is in a safe state.

• Answer the following questions using Banker’s algorithm
• A) What is the content of the matrix need?
• B) Is the system is in safe state
• If a request from process P1 arrives for(1,0,2)can the request be granted immediately?

PID Allocation Max Available

A B C A B C A B C
P0 0 1 0 7 5 3 3 3 2
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
SOLUTION

• Need = Max – Allocation

• Matrix is

A B C
P0 7 4 3
P1 1 2 2
P2 6 0 0
P3 0 1 1
P4 4 3 1
 Allocation Max Available Need
A B C A B C A B C A B C
P0 0 1 0 7 5 3 3 3 2 7 4 3

P1 2 0 0 3 2 2 1 2 2

P2 3 0 2 9 0 2 6 0 0

P3 2 1 1 2 2 2 0 1 1

P4 0 0 2 4 3 3 4 3 1
• To find system in safe state apply safety algorithm

• P0: need<=availability (7,4,3)<=(3,3,2) is false , P0 not executed

• P1: need<=availability (1.2.2)<=(3,3,2) is true , P1 executed

• new availability = availability + allocation = 3,3,2+2,0,0=5,3,2

• P2: need<=availability (6,0,0)<=(5,3,2) is false , P2 not executed

• P3: need<=availability (0,1,1)<=(5,3,2) is True , P3 executed

• new availability = availability + allocation = 5,3,2+2,1,1=7,4,3

• P4: need<=availability (4,3,1)<=(7,4,3) is True , P4 executed

• new availability = availability + allocation = 7,4,3+0,0,2=7,4,5

• Now Check P0 and P2

• P0: need<=availability (7,4,3)<=(7,4,5) is True , P0 executed

• new availability = availability + allocation =7,4,5+0,1,0=7,5,5

• P2: need<=availability (6,0,0)<=(7,5,5) is True , P2 executed

• new availability = availability + allocation = 7,5,5+0,1,0=10,5,7

• <P1P3P4P0P2>
• Updated Snapshot

Allocation Max Available

A B C A B C A B C
P0 0 1 0 7 5 3 2 3 0
P1 3 0 2 3 2 2
P2 3 0 2 9 0 2
P3 2 1 1 2 2 2
P4 0 0 2 4 3 3
• Updated Snapshot

Allocation Max Available

A B C A B C A B C
P0 0 1 0 7 5 3 2 3 0
P1 3 0 2 3 2 2
P2 3 0 2 9 0 2
P3 2 1 1 2 2 2
P4 0 0 2 4 3 3
89
Consider the matrix below. Use Banker’s algorithm to find out the following:
a) Need Matrix
b) Is system in safe state? If yes then find out the safe sequence

Allocation Max Available

A B C D A B C D A B C D
P0 0 0 1 2 0 0 1 2 1 5 2 0
P1 1 0 0 0 1 7 5 0
P2 1 3 5 4 2 3 5 6
P3 0 6 3 2 0 6 5 2
P4 0 0 1 4 0 6 5 6
 Allocation Max Available Need
A B C D A B C D A B C D A B C D
P0 0 0 1 2 0 0 1 2 1 5 2 0 0 0 0 0
✓✓
P1 1 0 0 0 1 7 5 0 0 7 5 0 X
P2 1 3 5 4 2 3 5 6 1 0 0 2 X✓
P3 0 6 3 2 0 6 5 2 0 0 2 0 ✓✓
P4 0 0 1 4 0 6 5 6 0 6 4 2 X✓
2 9 10 12

Total instances A B C D
3 14 12 12

Allocation Max Available Need

A B C D A B C D A B C D A B C D
P0 0 0 1 2 0 0 1 2 1 5 2 0 0 0 0 0
P1 1 0 0 0 1 7 5 0 1 5 3 2 0 7 5 0
P2 1 3 5 4 2 3 5 6 2 8 8 6 1 0 0 2
P3 0 6 3 2 0 6 5 2 2 14 11 8 0 0 2 0
P4 0 0 1 4 0 6 5 6 2 14 12 12 0 6 4 2
Add the resources
2 9 10 12 allocated to P1 to
3 14 12 12
available resources
Safe sequence: <P0, P2, P3, P4, P1>
• To demonstrate the working of banker’s algorithm, consider the following snapshot of
the system at time t0. Processes are numbered P0 to P4. Resources are P=12, Q=9, and
R=6.
• Analyse the sequence<P2, P1, P0, P4, P3> satisfies the safety criteria or not.
•

Allocation Max Available

P Q R P Q R P Q R
P0 3 0 1 5 2 1 1 6 2
P1 0 2 1 3 2 2
P2 2 0 0 3 2 2
P3 2 1 0 7 3 1
P4 4 0 2 5 0 3
DEADLOCK PREVENTION AND AVOIDANCE
Sr Factors Prevention avoidance
No
1 Concept
2 Future
Resource
Request
3 Procedure
4 Information
Required
5 Pre-emption
6 Resource
Request
7 Resource
allocation
8 Example
RESOURCE-ALLOCATION GRAPH ALGORITHM

• Suppose that process Pi requests a resource Rj

• The request can be granted only if converting the request

edge to an assignment edge does not result in the formation
of a cycle in the resource allocation graph
RESOURCE-ALLOCATION GRAPH SCHEME

• Introduce a new kind of edge called a claim edge

• Claim edge Pi Rj indicates that process Pi may request

resource Rj; which is represented by a dashed line

• A claim edge converts to a request edge when a process requests

a resource

• A request edge converts to an assignment edge when the

resource is allocated to the process

• When a resource is released by a process, an assignment edge

reconverts to a claim edge

• Resources must be claimed a priori in the system

 RESOURCE-ALLOCATION GRAPH

A set of vertices V and a set of edges E.

• V is partitioned into two types:

• P = {P1, P2, …, Pn}, the set consisting of all
the processes in the system

• R = {R1, R2, …, Rm}, the set consisting of all

resource types in the system

• request edge – directed edge P1 → Rj

• assignment edge – directed edge Rj → Pi

An arrow from the process to resource indicates the process is requesting the
resource. An arrow from resource to process shows an instance of the resource
has been allocated to the process.

Process is a circle, resource type is square; dots represent number of instance of

resource.
 RESOURCE-ALLOCATION GRAPH WITH
CLAIM EDGES

Assignment
Request
edge
edge

Claim
edge
Claim
edge
 UNSAFE STATE IN RESOURCE-ALLOCATION GRAPH

Assignment
Request
edge
edge

Assignment
edge
Claim
edge
98
DEADLOCKS RESOURCE
ALLOCATION GRAPH
🞆 If the graph contains no cycles, then no process is deadlocked.
🞆 If there is a cycle, then:
a) If resource types have multiple instances, then deadlock MAY exist.
b) If each resource type has 1 instance, then deadlock has occurred.

R3 Assigned to P3

Resource allocation graph

P2 Requests P3
99
DEADLOCKS RESOURCE
ALLOCATION GRAPH

Resource allocation graph

Resource allocation graph with a cycle but no deadlock.
with a deadlock.
RELATIONSHIP OF CYCLES TO DEADLOCKS

• If a resource allocation graph contains no cycles ⇒ no deadlock

• If a resource allocation graph contains a cycle and if only one instance exists per
resource type ⇒ deadlock

• If a resource allocation graph contains a cycle and and if several instances exists per
resource type ⇒ possibility of deadlock
Solve the following multi-instance resource allocation graph and
generate a safe state.
 Deadlock Detection
If a system does not employ either a deadlock-prevention or a deadlock avoidance algorithm, then a deadlock
situation may occur. In this environment, the system may provide:
• An algorithm that examines the state of the system to determine whether a deadlock has occurred
• An algorithm to recover from the deadlock
We elaborate on these two requirements as they pertain to systems with only a single instance of each
resource type, as well as to systems with several instances of each resource type

SINGLE INSTANCE OF A RESOURCE TYPE

● If all resources have only a single instance, then we can define a deadlock detection algorithm that uses
a variant of the resource-allocation graph, called a wait-for graph.
● Wait-for graph == remove the resource nodes from the usual graph and collapse 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. An algorithm to detect a cycle in a graph requires an order of nxn operations, where n is the
number of vertices in the graph.
 103

7:
Deadloc
ks
104
DEADLOCKS Deadlock Detection

SEVERAL INSTANCES OF A RESOURCE TYPE

If multiple instances of resources are there and there is a cycle in wait-for graph then deadlock may or
may not be there

The algorithm employs several time-varying data structures that are similar to those used in the banker's
algorithm:

Available - A vector of length m indicates the number of available resources of each type
Allocation – An n x m matrix defines the number of resources of each type currently allocated to each
process.
Request - An n x m matrix indicates the current request of each process. If Request[i][j] equals k, then
process Pi is requesting k more instances of resource type Rj.
105
DEADLOCKS Deadlock Detection

1. Let work and finish be vectors of length m and n respectively. Initialize

work[] = available[]. For i = 0,1,2,...n-1, if allocation[i] != 0 then // For all
n processes
finish[i] = false; otherwise, finish[i] = true;

2. Find an i process such that:

finish[i] == false and request[i] <= work

If no such i exists, go to step 4.

3. work = work + allocation[i]

finish[i] = true
goto step 2

4. if finish[i] == false for some i, then the system is in deadlock state.

If finish[i] == false, then process P[i] is deadlocked.
 DEADLOCKS Deadlock Recovery
When a detection algorithm determines that a deadlock exists, several alternatives are available. One
possibility is to inform the operator that a deadlock has occurred and to let the operator deal with the
deadlock manually. Another possibility is to let the system recover from the deadlock automatically. There
are two options for breaking a deadlock One is simply to abort one or more processes to break the circular
wait. The other is to preempt some resources from one or more of the deadlocked processes.
PROCESS TERMINATION:

∙ Abort all deadlocked processes-- this is expensive. 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
∙ Abort one process at a time until the deadlock cycle is eliminated ( time consuming ).
∙ Select which process to terminate based on priority, time executed, time to completion, needs for
completion, or depth of rollback
∙ In general, it's easier to preempt the resource, than to terminate the process.

RESOURCE PREEMPTION:
To eliminate deadlocks using resource preemption, preempt some resources from processes and give these
resources to other processes until the deadlock cycle is broken. If preemption is required to deal with
deadlocks, then three issues need to be addressed:

∙ Selecting a victim. Which resources and which processes are to be preempted? As in process
termination, we must determine the order of preemption to minimize cost.
∙ Rollback the preempted process to some safe state and restart it from that state. Since, in general, it is
difficult to determine what a safe state is, the simplest solution is a total rollback: abort the process and then
restart it.
∙ Starvation -Ensure that a process can be picked as a victim" only a (small) finite number of times. The most
common solution is to include the number of rollbacks in the cost factor.