1:59 AM Posted In OS-8 Edit This 5 Comments »
RESOURCE ALLOCATION GRAPH
Resource Allocation Graph
• Deadlock can be described through a resource allocation
graph.
• The RAG consists of a set of vertices P={P1,P2 ,…,P n} of
processes and R={R1,R2,…,Rm} of resources.
• A directed edge from a processes to a resource, Pi->R j, implies
that Pi has requested Rj.
• A directed edge from a resource to a process, Rj->Pi, implies
that Rj has been allocated by Pi.
• If the graph has no cycles, deadlock cannot exist. If the graph
has a cycle, deadlock may exist.
1.How would you know if theres a deadlock base on the resource
allocation graph?
=
Example of a Resource Allocation Graph
-REQUEST: if process Pi has no outstanding request, it can request simultaneously any number (up to multiplicity) of resources R1, R2, ..Rm. The request is represented by adding appropriate requests edges to the RAG of the current state.
-ACQUISITION: if process Pi has outstanding requests and they can all be simultaneously satisfied, then the request edges of these requests are replaced by assignment edges in the RAG of the current state
-RELEASE: if process Pi has no outstanding request then it can release any of the resources it is holding, and remove the corrisponding assignment edges from the RAG of the current state.
-Process
-Resource Type with 4 instances
-Pi requests instance of Rj
-Pi is holding an instance of Rj
Resource Allocation Graph With A Deadlock
• Deadlock Prevention & Avoidance: Ensurethat the system will never enter a deadlockstate
• Deadlock Detection & Recovery: Detect that adeadlock has occurred and recover
• Deadlock Ignorance: Pretend that deadlockswill never occur
Resource Allocation Graph With A Cycle But No Deadlock
Safe, Unsafe , Deadlock State
Basic Facts
-If graph contains no cycles Þ no deadlock.
-If graph contains a cycle Þ
-if only one instance per resource type, then deadlock.
-if several instances per resource type, possibility of deadlock.
Resource-Allocation Graph For Deadlock Avoidance
-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.
-Resource-allocation state is defined by the number of available and allocated resources, and the maximum demands of the processes.
Unsafe State In Resource-Allocation Graph
Traffic Deadlock for Exercise
Resource-Allocation Graph and Wait-for Graph
5 comments:
good
Thanks for the detailed description....
Thanks a lot Joy. I'm actually having an exam on deadlocks tomorrow. Is there any additional explanation on how to identify deadlock situation from the resource allocation graph?
very useful...................THANK YOU
Thanks 4 the instructions, now i understand fully :-)
Post a Comment