Graph Explanation

graph 1

• Graph 1 shows that it has no deadlock because there is no other cycles going on.
• R1 has one instance, R2 has 2 instances, R3 has one instance and R4 has 4 instances.
• P1 is requesting an instance in R1.
• P2 is holding an instance from R1.
• P3 is holding an instnace from R3.
  

graph 2

• Graph 2 shows that it has a deadlock because there is a cycle and process 3 is requisting an instance.
• P1 is requesting an instance in R1.
• P2 is holding an instance from R1.
• P3 is holding an instance from R3.
• P3 is requesting an instance in R2.

graph 3

• Graph 3 shows that there is no deadlock even it has a cycles.
• P1 is requesting an instance in R1.
• P2 is holding an instance from R1.
• P3 is holding an instance from R1.
• P3 is requesting an instance in R2.
• P4 is holding an instance from R2.
• P1 is holding an instance in R2.

graph 4

• Graph 4 shows that:
• P1 is hodling an instance from R1.
• P2 is requesting an instance in R1.
• P1 and P2 may access in or request in R2.

graph 5

• Graph 5 shows that:
• P1 is holding an instance from R1.
• P2 is requesting an instance in R1.
• P1 may access or request an instance in R2.
• P2 is holding an instance from R2.

Resource Allocation Graph

-A set of vertices and set of edge E.

• V is partitioned into two types:

1. P = {P1, P2,...Pn}, the set consisting of all the processes in the system.
2. R = {R1, R2,...Rm}, the set consisting of all the resource types in the system.
   

• request edge - directed edge P1 - Rj
  
• assignment edge - directed edge Rj - Pi

Q: How would you know if there's a deadlock in the reasource allocation graph?

A: You would know if there's a deadlock in the allocation graph if graphs contains a cycle and only if one instnace p[er reource type, then deadlock and only if several intances per resource type, possibility of deadlock.

Deadlock Characterization

Deadlock can arise if four conditions hold simultaneously.

• Mutual exclusion: only one process at a time can use a (non-sharable) 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

• Deadlock Prevention.
  =>Disallow one of the four necessary conditions for deadlock.
  
• Deadlock Avoidance.
  =>Do not grant a resource request if this allocation have the potential to lead to a deadlock.
  
• Deadlock Detection.
  =>Always grant resource request when possible. Periodically check for deadlocks. If a deadlock exists, recover from it.
  
• Ignore the problem...
  =>Makes sense if the likelihood is very low.

Deadlock Recovery

• Process Termination
  =>Abort all deadlocked processes:
  1.)Fast
  2.)A lot of process work is lost.
  =>Abort one deadlocked process at a time and check for deadlocks again:
  1.)More work to resolve a deadlock.
  2.)Better in terms of process work.
  3.)What is a good order to abort processes?
  
• Resource Preemption
  =>what is a good way to select a victim
  =>How can we rollback and then recover from preemption?
  =>How can we protect from starvation

What can the system do if it discovers a deadlock?

Deadlock Prevention

Eliminate one of the four conditions:

• Mutual Exclusion:
  =>Well, if we need it then we need it.
• Hold and Wait:
  =>Require a process to request and be allocated all its resources before it begins execution, or allow process to request resources only when the process has none.
  =>May lead to low resource utilization.
  =>Starvation is a problem - a process may be held for a long time waiting for all its required resources.
  =>If it needs additional resources, it releases all of the currently held resources and then requests all of those it needs (the application needs to be aware of all of the required resources).

Deadlock Detection

• The system may enter a deadlock state.
• The system needs:
  1.)An algorithm that periodically determines whether a deadlock has occurred in the system.
  2.)A procedure to recover from a deadlock.
• Two algorithms:
  1.)One instance per resource type.
  2.)Multiple instances per resource type.