1:59 AM Posted In 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


Deadlock Detection

3:54 AM Posted In Edit This 0 Comments »
„ Allow system to enter deadlock state

„ Detection algorithm

„ Recovery scheme

Deadlock Recovery

3:47 AM Posted In Edit This 1 Comment »
Recovery from Deadlock

• Recovery through preemption

– take a resource from some other process

– depends on nature of the resource

• Recovery through rollback

– checkpoint a process state periodically

– rollback a process to its checkpoint state if it is found deadlocked

• Recovery through killing processes

– kill one or more of the processes in the deadlock cycle

– the other processes get its resources

• In which order should we choose process to kill?

Deadlock Prevention

3:46 AM Posted In Edit This 0 Comments »
Attacking the Mutual Exclusion Condition:

• Some devices (such as printer) can be spooled

– only the printer daemon uses printer resource

– thus deadlock for printer eliminated

• Not all devices can be spooledRestrain the ways requests can be made to break one of the four necessary conditions for deadlocks.

Methods for Handling Deadlocks

3:45 AM Posted In Edit This 0 Comments »
• Ignore the problem and pretend that deadlocks would never occur

• Ensure that the system will never enter a deadlock state (prevention or avoidance)

• Allow the system to enter a deadlock state and then detect/recover

Deadlock Characterization

3:37 AM Posted In Edit This 2 Comments »

Deadlock CharacterizationDeadlock can arise if four conditions hold simultaneously:
• Mutual exclusion: only one process at a time can use a resource
• Hold and wait: a process holding at least one resource is waiting to acquire additional resources held by other processes
• No preemption: a resource can be released only voluntarily by the process holding it, after that process has completed its task
• Circular wait: there exists a set {P0, P1, …, Pn, P0} of waiting processes such that
– P0 is waiting for a resource that is held by P1,
– P1 is waiting for a resource that is held by P2,
– …,
– Pn–1 is waiting for a resource that is held by Pn,
– and Pn is waiting for a resource that is held by P0.