Page 118 - DCAP403_Operating System

Unit 6: Process Synchronization

Here are some important propositions about deadlocks and resource allocation graphs: Notes

1. If a RAG of a state of a system is fully reducible (i.e. it can be reduced to a graph without
any edges using ACQUISITION and RELEASE operations) then that state is not a deadlock
state.

2. If a state is not a deadlock state then its RAG is fully reducible [this holds only if you are
dealing with reusable resources; it is false if you have consumable resources]
3. A cycle in the RAG of a state is a necessary condition for that being a deadlock state
4. A cycle in the RAG of a state is a sufficient condition for that being a deadlock state only in

the case of reusable resources with multiplicity one.

Example: Here is an example of reduction of a RAG:

R1 P2 R1
 P1
P1 P3 P3
R2
R2
R1 
R1
 P1 P3
P3
R2
R2

R1 
P3 
R2

Reduction of a RAG
And here is a deadlock-free system with a loop.

R1

P1 P2
R2

P3

RAG with Loop but no Deadlock

Task A monitor is a software synchronization tool or hardware synchronization tool.

LOVELY PROFESSIONAL UNIVERSITY 111