graphs

p1 is holding instance of r1..
p1 may request instance of r2
p2 is holding the instance of r2
p2 is requesting instance of r1
there no dead lock becuse there is no cycle..

p2 is requesting instace of r1

p1 is holding the instance of r1

both p1 and p2 may request instance of r2

but there is no deadlock because there is no cycle

P2 and P3 has the instance of R1

P1 and P4 has the instance of R2

P1 and P3 has no interuption on cycle..

there for no deadlock

P1 and P2 is holding a instance of R2 then P1 request instance of R1 but P2 is holding the instance of R1 then P2 request isntance of R3 but P3 is holding the instance of R3 then P3 request instance of R2 but P1 and P2 has the instance of R2..
R4 is undistured

there is deadlock

P1 and P2 is holding a instance of R2 then P1 request instance of R1 but P2 is holding the instance of R1 then P2 request isntance of R3 but P3 is holding the instance of R3..

R4 is undistured

there is deadlock

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 inthe system.


• R = {R1, R2, …, Rm}, the set consisting of all resource typesin the system.

request edge – directed edge P1 → Rj

assignment edge – directed edge Rj → Pi

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 ofdeadlock.
  

Resource-Allocation Graph Algorithm

Claim edge Pi → Rj indicated that process Pj may requestresource Rj; represented by a dashed line.

Claim edge converts to request edge when a processrequests a resource.

When a resource is released by a process, assignmentedge reconverts to a claim edge.

Resources must be claimed a priori in the system.

deadlock handler

There is a certain level of deadlock detection/avoidance built into the record locking facility. This deadlock handling provides the same level of protection granted by the /usr/group standard lockf call. This deadlock detection is only valid for processes that are locking files or records on a single system. Deadlocks can only potentially occur when the system is about to put a record locking system call to sleep. A search is made for constraint loops of processes that would cause the system call to sleep indefinitely. If such a situation is found, the locking system call will fail and set errno to the deadlock error number. If a process wishes to avoid the use of the system's deadlock detection, it should set its locks using F_SETLK instead of F_SETLKW.

deadlock detection

• Allow system to enter deadlock state

• Detection algorithm

• Recovery scheme

1. In the extreme case – every time a request for a resource cannot be granted immediately

• This comes with enormous cost /think about complexity in real systems)

2. Reasonable alternative periodically. But what period to use?

• How long are we willing to wait after it happens to be detected
• How much system resources are we willing to commit to this detection algorithm

deadlock characterezation

Continuous mutual blocking of a “set of threads” eithercompeting for resources or interacting with each other (via synchronization, cooperation or communication)

• Conflicting requests by at least 2 threads

No satisfying solution in all cases

Some standard OSes don‘t bother deadlocks at all (e.gSUN’s OS) arguing that deadlocks will occur scarcely

“a set of processes is in a deadlock state when every process in theset is waiting for an event that can be caused only by another process in the set”, Silberschatz et. al., “Operating Systems Concepts”

There is no efficient solution

deadlock prevention

Progressive deadlock Recovery

• Robin hood approach – de-allocate resources from normal packets and assign to the recovery packet

1. Remove any message from a deadlocked cycle
2. Ensure its progress towards the destination

Regressive deadlock recovery

• De-allocate resources from deadlocked packets
• ypically destroy packets
• Need some recovery mechanism, for example, end-to-end flow control

deadlock prevention

At least 1 necessary condition does not hold

• Mutual Exclusion: not required for sharable resources; must hold for non-sharable resources.
• Hold-and-Wait: can not request new when holding resources.

1. Protocol 1: request all resources before it begins execution
2. Protocol 2: request resources only when the process has none.
3. Low resource utilization; starvation possible.

• No Preemption: preempt resources from processes

1. Protocol 1: If a request can not be satisfied then preempt all resources held and block
2. Protocol 2: Preempt only if resources are needed by another running process
3. Requires resource state to be easily restored

• Circular Wait: Block any request that results in a cycle.

1. Impose a total ordering of all resource types, and require that each process requests resources in an increasing order