Operating System

• V is partitioned into to 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 resource types in the system.

-request edge-directed edge P1 [] Rj

-assignment edge-directed edge Rj[]Pi

_Process

_Resource typeb with 4 instances

_Pi requests instance of Rj

_Pi is holding an instance of Rj

• if graph contains no cycle => 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.

(0)A Resource Allocation Graph

_This RAG shows a cycle of 3 processes and 4 resource types.

(0) Resource Allocation Graph with deadlock.

-First P1 have a request to R1.The instance of R1 has been hold by P2. This process then sends request to R3 , and P3 is holding its instance. When P3 sends request to R2, which consists of 2 instances. One instance holds by P2 while the other one holds by P1. There exist the deadlock when the instances of two different resource type are been holds by one Process(P2) at the same time.

(0) Resource allocation graph with a cycle but no deadlock

- The graph contains a cycle. Each processes holds an instance of the resource. First, P1 sends request to R1, which contains 2 instances. P2 and P3 are holding these instances . Then, P3 sends request to R2 which also contains 2 instances and each of these are holds by P4 and P1.

• Recovery through preemption

• Recovery through rollback

• Recovery through killing processes

• Process Termination
• Abort all deadlocked processes:
  -Fast
  -A lot of process work is lost.
• Abort one deadlocked process at a time and check for deadlocks again:
  -More work to resolve a deadlock.
  -Better in terms of process work.
  -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

(0) deadlock detection

Often neither deadlock avoidance nor deadlock prevention may be used. Instead deadlock detection and process restart are used by employing an algorithm that tracks resource allocation and process states, and rolls back and restarts one or more of the processes in order to remove the deadlock. Detecting a deadlock that has already occurred is easily possible since the resources that each process has locked and/or currently requested are known to the resource scheduler or OS.

Detecting the possibility of a deadlock before it occurs is much more difficult and is, in fact, generally undecidable, because the halting problem can be rephrased as a deadlock scenario. However, in specific environments, using specific means of locking resources, deadlock detection may be decidable. In the general case, it is not possible to distinguish between algorithms that are merely waiting for a very unlikely set of circumstances to occur and algorithms that will never finish because of deadlock.

Deadlock detection attempts to find and resolve actual deadlocks. These strategies rely on a Wait-For-Graph (WFG) that in some schemes is explicitly built and analyzed for cycles. In the WFG, the nodes represent processes and the edges represent the blockages or dependencies. Thus, if process A is waiting for a resource held by process B, there is an edge in the WFG from the node for process A to the node for process B.

In the AND model (resource model), a cycle in the graph indicates a deadlock. In the OR model, a cycle may not mean a deadlock since any of a set of requested resources may unblock the process. A knot in the WFG is needed to declare a deadlock. A knot exists when all nodes that can be reached from some node in a directed graph can also reach that node.

In a centralized system, a WFG can be constructed fairly easily. The WFG can be checked for cycles periodically or every time a process is blocked, thus potentially adding a new edge to the WFG. When a cycle is found, a victim is selected and aborted.

(0)Deadlock Prevention

Restrain the ways requests can be made to break one of the four necessary conditions for deadlocks

• We try to ensure that one of the four necessary conditions cannot hold, then we can prevent it
• Mutual Exclusion:
  -If it is shareable resource, then we can break the mutual exclusion (such as: Read-only file)
  -If it is not a shareable resource, then mutual exclusion must hold (such as: Printer)
• 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 spooled

• Hold and wait: two methods
  1. Require process to request and be allocated all its resources before it begins execution.
  2. allow process to request resources only when the process has none.

• NO preemption:

• If a process that is holding some resources requests
  another resource that cannot be immediately to
  allocated it, then all resources currently being held are
  released.
• Preempted resources are added to the list of resources
  for which the process is waiting.
  Process will be restarted only when it can regain its old
  resources, as well as the new ones that it is requesting.
  
• Attacking the No Preemption Condition:
• Preemption– when a process is holding some resources and waiting for others, its resources may be preempted to be used by others
• Problem– Many resources may not allow preemption; i.e., preemption will cause process to fail

• Attacking the Circular Wait Condition:

• impose a total order of all resource types; and require that all processes request resources in the same order

(0) Methods for handling deadlock

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

1. Ignore the problem and pretend that deadlocks would never occur
2. Ensure that the system will never enter a deadlock state (prevention or avoidance)
3. Allow the system to enter a deadlock state and then detect/recover

(0)deadlock characterization

Deadlock can arise if four conditions hold simultaneously:

1.Mutual Exclusion

• only one process at a time can use a resource.
• If another process requests that resource, the requesting process must be delayed until the resource has been released
  

• there exists a set {P0, P1, …, P0} of waiting processes such that
  P0 is waiting for a resource that is held by P1,
  P1is waiting for a resource that is held by P2, …, Pn–1is waiting for a resource that is held by Pn, and P0is waiting for a resource that is held by P0.