RESOURCE ALLOCATION GRAPH

RESOURCE ALLOCATION GRAPH (RAG'S) are directed labeled graphs used to represent, from the point of view if DEADLOCKS, the current state of a system.

RESOURCE ALLOCATION GRAPHS:

PROCESS

REQUEST TYPE w/ 4 INSTANCE

Pi REQUEST INSTANCE of Rj

Rj

Pi is HOLDING AN INSTANCE OF Rj

Rj

EXAMPLE of RESOURCE ALLOCATION GRAPH

RESOURCE ALLOCATION GRAPH w/ DEADLOCK

If graph contains a cycle then it has a DEADLOCK

-if only one instance per resource type,then DEADLOCK

-if several instances per resource type, possibly of DEADLOCK

RESOURCE ALLOCATION GRAPH w/ a CYCLE BUT NO DEADLOCK

If graph contains no cycle no DEADLOCK

DEADLOCK CHARACTERIZATION

• 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, …, 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 P0 is waiting for a resource that is held by P0.

METHODS FOR HANDLING DEADLOCKS

• Ensure that the system will never enter a deadlock state.
• Allow the system to enter a deadlock state and then recover.
• Ignore the problem and pretend that deadlocks never occur in the system; used by most operating systems, including UNIX.

DEADLOCK PREVENTION

• deadlock requires the following conditions:

-mutual exclusion:

-resources not sharable

-hold and wait:

-process must be holding one resource while requesting another

-circular wait:

-at least 2 processes must be blocked on each other

• eliminate mutual exclusion:

-not possible in most cases
-spooling makes I/O devices sharable

• eliminate hold-and-wait

-request all resources at once
-release all resources before a new request
-release all resources if current request blocks

• eliminate circular wait

-order all resources: SEQ(Ri) ? SEQ(Rj)
-process must request in ascending order

DEADLOCK DETECTION

• graph reduction

-repeat:

-select unblocked process p
-remove p and all request and allocation edges

• deadlock? graph not completely reducible
• all reduction sequences lead to the same result

DEADLOCK RECOVERY

• process termination

-kill all processes involved in deadlock
-kill one at a time; in what order:

-by priority: consistent with scheduling
-by cost of restart: length of recomputation
-by impact on other processes: CS, producer/cons.

• resource preemption

-direct: temporarily remove resource (e.g. memory)
-indirect: rollback to earlier checkpoint