Recovery or Deadlock Recovery

• Abort all deadlock processes and release resource - too drastic - will lead to loss of work
• Abort one process at a time - releasing resources until no deadlock
  How do we determine which process to abort first ? - priority ordering, process which has done least work
• Selectively restart processes from a previous checkpoint i.e. before it claimed any resources
  difficult to achieve - sometimes impossible
• Successively withdraw resources from a process and give to another process until deadlock is broken. How to choose which processes and which resources ?

1. Complex decisions due to the large number of processes present within a system
2. Difficult to automate
3. Use Operator to resolve conflicts - BUT this requires the operator to have skill and understanding of what processes are actually doing

Process Termination:

· Abort all deadlocked processes.

· Abort one process at a time until the deadlock cycle is eliminated.

· In which order should we choose to abort?

 - Priority of the process.

 - How long process has computed, and how much longer to completion.

 - Resources the process has used.

 - Resources process needs to complete.

 - How many processes will need to be terminated.

 - Is process interactive or batch?

Resource Preemption

· Selecting a victim – minimize cost.

· Rollback – return to some safe state, restart process for that state.

· Starvation – same process may always be picked as victim, include

number of rollback in cost factor.

Deadlock Detection

In Operating Systems a special resource-allocation graph algorithm can be used to detect whether there is any deadlock in the system. A resource-allocation graph is a directed graph consisting of two different types of nodes P = P₁, P₂,..., P_n, the set consisting of all active processes in the system, and R = R₁, R₂,..., R_m, the set consisting of all resource types in the system.

A directed edge from process P_i to resource R_j is denoted by P_i R_j and means that process P_i requested an instance resource type R_j, and is currently waiting for that resource. A directed edge from resource type R_j to process P_i, is denoted by R_j P_i and means that an instance of resource type R_j has been allocated to process P_i.

The following figure illustrates a resource-allocation graph where processes are denoted by circles and resources by squares. Notice that if there is a circular wait among the processes, then it implies that a deadlock has occurred.

Given a resource allocation graph in which each resource type has exactly one instance, your job is to determine whether there is a deadlock in the system. In case a deadlock exists, you must also show the sequence of processes and resources involved.

Input

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

We will assume that processes are named by capital letters and resources by small letters, so we limit to 26 the number of processes and/or resources. Therefore, the first line of input consists of three numbers N, M and E, respectively, the number of processes, the number of resources and the number of edges. The edges are given in the following lines as pairs of letters linked by a `-' character. Edges are separated by spaces or newlines.

Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

The output must be `NO' if no deadlock is detected. In case a deadlock is detected, the output must be `YES' followed by the sequence or sequences of circular waits detected, one per line. If more then one sequence is found, they should all be output in increasing order of their length.

Sample Input

1

2 2 4
A-b B-a
a-A b-B

Sample Output

YES
A-b-B-a-A

Deadlock Prevention

No Preemption –

• If a process that is holding some resources requests another resource that cannot be immediately allocated to 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.
  Circular Wait – impose a total ordering of all resource types, and require that each process requests resources in an increasing order of enumeration.

Circular Wait – impose a total ordering of all resource types, and require that each process requests resources in an increasing order of enumeration.

Deadlock prevention - low device utilization and reduced system throughput.
Deadlock avoidance

• Given the complete sequence of requests and releases for each process, we can decide for each request whether or not the process should wait.
  
• For every request, the system
  tconsiders the resources currently available, the resources currently allocated, and the future requests and releases of each process, and
  decides whether the current request can be satisfied or must wait to avoid a possible future deadlock.

1. 
   considers the resources currently available, the resources currently allocated, and the future requests and releases of each process, and
2. 
   decides whether the current avoid a possible future deadlock.
   
   
   
   

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 Characterization


• All four conditions must existsimultaneously for deadlock to occur.
• If we can prevent any one of theconditions, we prevent deadlock

1. Mutual exclusion: only one process at a time can use a resource.

2. Hold and wait: a process holding at least one resource is waiting to acquire additional resources held by other processes.

3. No preemption: a resource can be released only voluntarily by the process holding it, after that process has Completed its task.

4. 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 waiting for a resource that is held by Pn, and P0 is waiting for a resource that is held by P0.Deadlock can arise if four conditions hold simultaneously