DEADLOCK PREVENTION, DETECTION AND AVOIDANCE

INTRODUCTION

           In a multiprogramming environment, several processes may compete for a finite number of resources. A process requests resources; if the resources are not available at that time, the process enters a waiting state. Sometimes, a waiting process is never again able to change state, because the resources it has requested are held by other waiting processes. This situation is called a deadlock. 

           Deadlock is a critical concept in the field of operating systems, particularly in the context of concurrent and multi-threaded environments. It occurs when two or more processes (or threads) are unable to proceed because each is waiting for the other to release a resource or complete a task, resulting in a standstill where none of the processes can make progress. 

           To understand deadlock better, let's look at the four necessary conditions for deadlock to occur, often referred to as the "deadlock conditions" or "Coffman conditions": 

1. Mutual Exclusion: At least one resource must be held in a non-shareable mode, meaning only one process can use it at a time. When a process holds a resource, no other process can access it until it is released. 

2. Hold and Wait: A process must be holding at least one resource while waiting to acquire additional resources that are currently held by other processes. 

3. No Preemption: Resources cannot be forcibly taken away from processes; they can only be released voluntarily by the process holding them. 

4. Circular Wait: A circular chain of two or more processes exists, where each process is waiting for a resource that is held by another process in the chain. 

           When all four conditions are met simultaneously, a deadlock situation arises. This can lead to a system becoming unresponsive, and the only way to recover from a deadlock is to abort one or more processes, releasing the resources they were holding. However, deciding which process to abort can be challenging and may lead to data loss or undesirable consequences. 

           Deadlock avoidance, detection, and recovery are essential techniques used by operating systems to handle or prevent deadlocks from causing system failures. Prevention involves ensuring that at least one of the deadlock conditions is never satisfied. Detection involves periodically examining the state of the system to identify potential deadlocks, while recovery involves taking corrective actions once a deadlock is detected. Handling deadlocks effectively is crucial to ensure the stability and reliability of modern operating systems, especially in scenarios where multiple processes are competing for shared resources.

RESOURCE - ALLOCATION GRAPH

           In operating systems, a resource allocation graph is a graphical representation used to model and analyze the allocation of resources among different processes and the relationships between them. It is a critical tool for understanding resource allocation and detecting potential deadlocks in the system. A resource allocation graph consists of two types of nodes: 

1. Process Nodes: Each process in the system is represented by a process node. It indicates the processes that are currently running or requesting resources. 

2. Resource Nodes: Each resource in the system is represented by a resource node. It indicates the instances of resources available in the system.

Edges in the graph represent the relationships between processes and resources: 

    1. Request Edge: If a process is requesting a resource, there is a directed edge from the process node to the resource node. This indicates that the process is waiting for that resource to become available. 

    2. Assignment Edge: If a resource is allocated to a process, there is a directed edge from the resource node to the process node. This indicates that the process currently holds that resource. A resource allocation graph may evolve over time as processes request and release resources. 

Here are some key points to consider in analyzing the graph: 

    1. Deadlock Detection: A deadlock occurs when there is a cycle in the resource allocation graph. In other words, there is a circular chain of processes waiting for resources that are held by other processes. Detecting such cycles in the graph helps to identify potential deadlocks. 

    2. Deadlock Resolution: Once a deadlock is detected, operating systems can resolve it by employing various deadlock handling strategies, such as resource preemption, process termination, or resource timeout.  

    3. Safe State: If there is no deadlock in the system, it is said to be in a "safe state" where all processes can complete their execution successfully. A state is considered safe if there exists a sequence of process execution that avoids deadlock. 

    4. Resource Allocation Policies: The resource allocation graph can also be used to evaluate the efficiency and effectiveness of resource allocation policies. For example, it can help determine if a resource allocation policy may lead to potential deadlocks under certain conditions. 

           Overall, the resource allocation graph is a valuable tool for understanding the dynamic behavior of resource allocation and identifying potential issues like deadlocks in operating systems. 

METHODS FOR HANDLING THE DEADLOCK

           Handling deadlocks in operating systems involves employing various strategies to prevent or resolve deadlock situations. Some common methods for dealing with deadlocks are: 

1. Deadlock Prevention:

• Resource Allocation Order: One way to prevent deadlocks is by defining a specific order in which resources must be allocated. This can prevent circular wait conditions that lead to deadlocks. 
• Resource Limitation: Limiting the maximum number of resources a process can hold at any given time can reduce the likelihood of deadlocks. 

2. Deadlock Avoidance: 

• Safe State Check: The operating system can employ algorithms like the Banker's algorithm to check if a state is safe before allocating resources to a process. If the state is not safe, the resource allocation is deferred until it becomes safe.
• Resource Request Check: Before allocating resources to a process, the operating system can predict if the allocation will potentially lead to a deadlock. If so, the allocation is postponed or denied. 

3. Deadlock Detection and Recovery: 

• Resource Allocation Graph: As mentioned earlier, the resource allocation graph can be used to detect deadlocks in the system. Once a deadlock is detected, appropriate actions can be taken to resolve it. 
• Timeout Mechanisms: A timeout can be set on resource requests. If a process cannot acquire the required resources within a specified time, it releases all its allocated resources and restarts execution from the beginning. 

4. Resource Preemption: 

• If a process holding certain resources is waiting indefinitely for additional resources held by other processes, the operating system can preempt the resources from the waiting process and allocate them to the waiting process, thereby breaking the potential deadlock. 

5. Process Termination: 

• In situations where deadlock resolution is difficult or not feasible, the operating system can choose to terminate one or more processes to release the resources they are holding. The terminated processes can be restarted later to continue their tasks.

           It's essential to note that each deadlock handling method comes with its advantages and disadvantages. Deadlock prevention and avoidance methods are proactive but may lead to underutilization of resources. On the other hand, deadlock detection and recovery strategies are reactive and incur overhead for deadlock detection routines. The choice of method depends on the system's requirements, resource utilization, and the criticality of the application being executed.

DETECTING THE DEADLOCK

           Detecting deadlocks in operating systems can be accomplished using various techniques. One of the commonly used methods is the resource allocation graph, as mentioned earlier. Here's a step-by-step guide to detecting deadlocks using the resource allocation graph: 

1. Resource Allocation Graph (RAG) Construction: 

• Identify all the processes and resources in the system.
• Represent each process as a node in the graph.
• Represent each resource as a node in the graph. 
• Add directed edges (arcs) between the process nodes and resource nodes to indicate resource requests and allocations. 

 2. Deadlock Detection Algorithm: 

• Run a deadlock detection algorithm periodically or whenever there is a significant change in resource allocation. 
• One such algorithm is the cycle detection algorithm, which checks if there is a cycle in the resource allocation graph. 
• Another commonly used algorithm is the Banker's algorithm, which checks for the safe sequence to allocate resources and detects if a deadlock exists. 

 3. Cycle Detection Algorithm: 

• Perform a depth-first search (DFS) on the resource allocation graph. 
• Start the DFS from each unmarked process node. 
• While performing the DFS, mark the visited process nodes and follow the arcs (edges) to traverse the graph. 
• If you encounter a marked process node during the DFS, it indicates the presence of a cycle, and thus, a deadlock. 

4. Banker's Algorithm (for Deadlock Avoidance and Detection): 

• The Banker's algorithm is used to check if the system is in a safe state, i.e., no deadlock exists. 
• It simulates resource allocation and deallocation to determine if a safe sequence can be found to complete all processes. 
• If a safe sequence is found, the system is in a safe state, and there is no deadlock. 
• If a safe sequence cannot be found, it indicates that the system is in an unsafe state, and deadlock is possible. 

 5. Deadlock Reporting and Handling: 

• Once a deadlock is detected, the operating system can take appropriate actions based on the chosen deadlock handling strategy. 
• This may involve resource preemption, process termination, or other methods to resolve the deadlock and restore the system to a functional state. 

           It's important to note that detecting deadlocks comes with some overhead, as the deadlock detection algorithm needs to be executed periodically or reactively. Therefore, the frequency and impact of deadlock detection routines should be carefully balanced to ensure system performance and responsiveness. 

 EXAMPLE: BANKER‟S ALGORITHM 

           The Banker's algorithm is a resource allocation and deadlock avoidance algorithm that can also be used for deadlock detection. It is used in systems where multiple processes compete for a finite set of resources. The algorithm keeps track of the available resources, the maximum resources each process may need, and the currently allocated resources. 

Here's how the Banker's algorithm works for deadlock detection: 

a. Resource Allocation Data Structures:

The system maintains several data structures:  

• Available: An array indicating the number of available instances of each resource type. 
• Max: A 2D array representing the maximum number of each resource type that each process may need. 
• Allocation: A 2D array representing the number of each resource type currently allocated to each process. 

b. Work and Finish Vectors: 

The algorithm also maintains two additional arrays: 

• Work: An array initially set to the same values as the Available array. It represents the number of available resources after considering the current allocations.
• Finish: A boolean array initially set to false, representing the finish state of each process. 

c. Safe Sequence Determination (Deadlock Avoidance): 

• Before a resource request is granted to a process, the Banker's algorithm checks if the system is in a safe state. A safe state means that there is at least one sequence in which all processes can complete their execution without getting stuck in a deadlock. 
• The algorithm simulates resource allocation and deallocation to check for a safe sequence using the following steps: a. initially, find an index i such that Finish[i] is false, and Need[i] (the maximum needed resources - currently allocated resources for process i) is less than or equal to Work. b. If such an index i is found, add the Allocation[i] to the Work array and mark the process as finished (Finish[i] = true). c. Repeat steps a and b until no such index i is found, or all processes are marked as finished (Finish[i] is true for all i). d. If all processes are marked as finished, the system is in a safe state, and the requested resource can be granted. If not, the system is in an unsafe state, and the resource request is denied to avoid potential deadlock.

d. Deadlock Detection:

• If the Banker's algorithm finds that the system is in an unsafe state while granting a resource request, it indicates that a deadlock may occur if the request is allowed.
• In this case, the system can choose to use other deadlock detection algorithms, such as cycle detection in the resource allocation graph, to confirm the presence of a deadlock.

           The Banker's algorithm is a useful tool for detecting potential deadlocks in a system and making informed decisions about resource allocation to avoid deadlock situations.

PREVENTING THE DEADLOCK

           Preventing deadlocks in operating systems involves implementing strategies and policies during system design and resource allocation to ensure that deadlocks cannot occur. Here are some effective methods for preventing deadlocks: 

1. Resource Allocation Order: 

• Define a global ordering of resources and require processes to request resources in a specific order. 
• This approach prevents circular waits, as processes can only request resources in a way that respects the predefined order.

2. Resource Limitation: 

• Set a limit on the maximum number of resources each process can hold simultaneously. 
• By limiting the number of resources that a process can have, the chances of deadlocks are reduced.

3. Two-Phase Locking: 

• In concurrent systems, use the two-phase locking protocol to ensure that processes acquire and release locks on resources in a coordinated manner. 
• This method helps prevent deadlocks caused by multiple processes competing for the same resources. 

4. Transaction Serialization: 

• In database management systems, use transaction serialization techniques to ensure that concurrent transactions do not interfere with each other, reducing the risk of deadlocks. 

5. Spooling: 

• Implement spooling, where processes use an intermediate storage area (spool) for holding data or results before using a shared resource. 
• Spooling reduces the contention for shared resources and minimizes the chances of deadlocks. 

6. Timeouts and Resource Reclamation: 

• Set timeouts for resource requests, and if a process cannot acquire the required resources within a specified time, release all its allocated resources and retry later. 
• Reclaim unused or idle resources from processes to avoid resource wastage and increase the availability of resources. 

7. Resource Request Protocol: 

• Implement a resource request protocol where processes explicitly declare their resource needs and release resources they no longer require.
• This helps in efficient resource management and reduces the chances of deadlocks. 

8. Deadlock Detection and Recovery: 

• Although prevention is the ideal approach, incorporating deadlock detection mechanisms is still valuable.
• Detection mechanisms can be used to periodically check for deadlocks and take appropriate actions to resolve them if they occur. 

           It's essential to carefully design the system and resource allocation mechanisms with deadlock prevention in mind. Prevention techniques may slightly impact system performance and resource utilization, but they are generally preferred over deadlock resolution strategies, which often involve higher overhead and can lead to process termination or resource preemption.

DEADLOCK AVOIDANCE 

           Deadlock avoidance is a different concept and involves making resource allocation decisions in a way that guarantees the system will never enter a deadlock state. The primary goal of deadlock avoidance is to allocate resources safely to processes to prevent any possibility of a deadlock. One of the well-known techniques for deadlock avoidance is the "Resource Allocation Graph" (RAG) and "Deadlock Avoidance Algorithm." Here's how deadlock avoidance works using these methods:

 

1. Resource Allocation Graph (RAG): 

• The RAG is a graphical representation of the resources and processes in the system, similar to the one used for deadlock detection.
• The graph consists of process nodes, resource nodes, request edges (representing resource requests), and assignment edges (representing resource allocations). 

 2. Deadlock Avoidance Algorithm:

• The deadlock avoidance algorithm continually analyzes the resource allocation graph and makes decisions on resource allocation based on certain criteria to ensure deadlock avoidance. 

3. Safe State:

• The algorithm maintains the concept of a "safe state," which is a state where there exists a sequence of resource allocations that allows all processes to complete successfully without encountering a deadlock.
• If the system is in a safe state, resource allocations can proceed.
• If the system is not in a safe state, the algorithm avoids further resource allocations until a safe state is achievable. 

4. Resource Allocation Decisions: 

• Before allocating resources to a process, the algorithm predicts the potential effects of the allocation on the system's state. 
• If the allocation will lead to an unsafe state (risking a deadlock), the allocation is postponed until it is safe to proceed. 
• If the allocation will maintain or lead to a safe state, the resources are allocated to the requesting process. 

5. Process Prioritization: 

• The deadlock avoidance algorithm may prioritize processes based on factors such as the number of resources they currently hold, their maximum resource needs, and their priority levels to make optimal resource allocation decisions. 

            It's important to note that deadlock avoidance requires more sophisticated and dynamic decision-making than deadlock prevention. The advantage of deadlock avoidance is that it allows for more flexible resource allocation, but it also comes with more computational overhead and complexity. Implementing an efficient and effective deadlock avoidance algorithm requires a thorough understanding of the system's resource demands and characteristics.

DEADLOCK RECOVERY 

            Deadlock recovery is the process of resolving a deadlock after it has occurred in an operating system. When a deadlock is detected or suspected, the system takes appropriate actions to break the deadlock and restore normal functioning. There are several methods for deadlock recovery, each with its advantages and disadvantages. Here are some common deadlock recovery strategies: 

1. Process Termination: 

• One of the simplest deadlock recovery methods is to terminate one or more processes involved in the deadlock.
• The terminated processes release their held resources, allowing the remaining processes to continue execution and preventing further deadlocks.
• The operating system can choose which process(es) to terminate based on certain criteria such as priority or resource usage. 

2. Resource Preemption:

• In resource preemption, the operating system forcibly takes resources from one or more processes to break the deadlock.
• The preempted resources are then allocated to other waiting processes.
• Preemption can be either partial or complete, depending on the severity of the deadlock and the criticality of the processes involved. 

3. Rollback and Restart:

• In some systems, the state of the entire system can be check pointed periodically. 
• When a deadlock is detected, the system can roll back to a previously saved checkpoint and restart the processes from that point, avoiding the conditions that led to the deadlock. 

4. Process Prioritization: 

• The operating system can prioritize certain processes over others based on their importance or criticality.
• In case of a deadlock, the higher-priority processes are allowed to continue, while lower-priority processes might be terminated or preempted to break the deadlock.

5. Transaction Abort and Restart:

• In database systems, transactions involved in a deadlock can be aborted and then restarted from the beginning.
• By restarting the transactions, they can potentially proceed differently and avoid the conditions that caused the deadlock. 

6. Resource Manager Intervention:

• In distributed systems or systems with multiple resource managers, deadlock recovery may involve intervention from the resource managers.
• Resource managers may collectively analyze the deadlock and resolve it by releasing or reallocating resources across the system. 

             It's important to note that deadlock recovery is a reactive approach and typically involves overhead and potential loss of progress. The choice of deadlock recovery strategy depends on the system's requirements, the criticality of the processes involved, and the potential impact on data integrity and system performance. Prevention and avoidance methods are generally preferred over recovery to minimize the occurrence of deadlocks and avoid the need for drastic actions to resolve them. 

Deadlocks: 

             A process requests resources; if the resources are not available at that time, the process enters a waiting state. Sometimes a waiting process is never again able to change state, because the resources it has requested are held by other waiting processes. This situation is called a deadlock. 

System model: 

             A system consists of a finite number of resources to be distributed among a number of competing processes. The resources are partitioned into several types, each consisting of some number of identical instances. A process may utilize a resource in only the following sequence: 

      1. Request: The process requests the resource. If the request cannot be granted immediately (for example, if the resource is being used by another process), then the requesting process must wait until it can acquire the resource. 

      2. Use: The process can operate on the resource (for example, if the resource is a printer, the process can print on the printer). 

      3. Release: The process releases the resource. 

Deadlock Characterization: 

              A deadlock situation can arise if the following four conditions hold simultaneously in a system: 

       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. 

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

       3. No preemption: Resources cannot be preempted; that is, 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, …, Pn} 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 Pn is waiting for a resource that is held by P0. 

Deadlock Example: 

 /* thread one runs in this function */ 

void *do_work_one(void *param) 

{ 

   pthread_mutex_lock(&first_mutex);

   pthread_mutex_lock(&second_mutex);

   /** * Do some work */ 

   pthread_mutex_unlock(&second_mutex);

   pthread_mutex_unlock(&first_mutex);

   pthread_exit(0);

}

/* thread two runs in this function */

void *do_work_two(void *param)

{ 

   pthread_mutex_lock(&second_mutex);

   pthread_mutex_lock(&first_mutex);

   /** * Do some work */

   pthread_mutex_unlock(&first_mutex);

   pthread_mutex_unlock(&second_mutex);

   pthread_exit(0);

}

Resource-Allocation Graph:

Deadlocks can be described more precisely in terms of a directed graph called a system resource-allocation graph. 

This graph consists of 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 in the system 

R = {R1, R2, …, Rm}, the set consisting of all resource types in the system 

request edge – directed edge Pi → Rj 

assignment edge – directed edge Rj → Pi  

Pictorial Representations:

Example of a Resource Allocation Graph:

The sets P, R, and E: ◦ P = {P1, P2, P3}

◦ R = {R1, R2, R3, R4}

◦ E = {P1 → R1, P2 → R3, R1 → P2, R2 → P2, R2 → P1, R3 → P3}

Resource instances:

• One instance of resource type R1
• Two instances of resource type R2
• One instance of resource type R3
• Three instances of resource type R4 

Process states:

• Process P1 is holding an instance of resource type R2 and is waiting for an instance of resource type R1.
• Process P2 is holding an instance of R1 and an instance of R2 and is waiting for an instance of R3.
• Process P3 is holding an instance of R3. 

Resource Allocation Graph With A Deadlock:

At this point, two minimal cycles exist in the system: 

          P1 → R1 → P2 → R3 → P3 → R2 → P1 

          P2 → R3 → P3 → R2 → P2 

Graph With A Cycle But No Deadlock:

             However, there is no deadlock. Observe that process P4 may release its instance of resource type R2. That resource can then be allocated to P3, breaking the cycle. 

             In summary, if a resource-allocation graph does not have a cycle, then the system is not in a deadlocked state. If there is a cycle, then the system may or may not be in a deadlocked state. This observation is important when we deal with the deadlock problem. 

Methods for Handling Deadlocks:

• Ensure that the system will never enter a deadlock state:

                  Deadlock prevention

                  Deadlock avoidance 

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

             By ensuring that at least one of these conditions cannot hold, we can prevent the occurrence of a deadlock. 

1. Mutual Exclusion – not required for sharable resources (e.g., read-only files); must hold for non-sharable resources. 

2. Hold and Wait – must guarantee that whenever a process requests a resource, it does not hold any other resources 

             Require 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 allocated to it. 

Two main disadvantages: Low resource utilization; starvation possible 

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

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

For Example, if P1 process is allocated R5 resources, now next time if P1 ask for R4, R3 lesser than R5 such request will not be granted, only request for resources more than R5 will be granted. 

Deadlock Example with Lock Ordering: 

void transaction(Account from, Account to, double amount)

{ 

   mutex lock1, lock2;

   lock1 = get_lock(from);

   lock2 = get_lock(to);

   acquire(lock1);

     acquire(lock2);

       withdraw(from, amount);

       deposit(to, amount);

     release(lock2);

   release(lock1);

} 

Deadlock is possible if two threads simultaneously invoke the transaction() function, transposing different accounts. That is, one thread might invoke transaction(checking account, savings account, 25); and another might invoke transaction(savings account, checking account, 50); 

Deadlock Avoidance: 

             Requires that the system has some additional a priori information available:

• Simplest and most useful model requires that each process declare the maximum number of resources of each type that it may need
• The deadlock-avoidance algorithm dynamically examines the resource-allocation state to ensure that there can never be a circular-wait condition
• Resource-allocation state is defined by the number of available and allocated resources, and the maximum demands of the processes 

 Safe State:

• When a process requests an available resource, system must decide if immediate allocation leaves the system in a safe state
• System is in safe state if there exists a sequence of ALL the processes in the systems such that for each Pi , the resources that Pi can still request can be satisfied by currently available resources + resources held by all the Pj , with j < i
• That is: If Pi resource needs are not immediately available, then Pi can wait until all Pj have finished
• When Pj is finished, Pi can obtain needed resources, execute, return allocated resources, and terminate
• When Pi terminates, Pi +1 can obtain its needed resources, and so on
• If a system is in safe state ⇒ no deadlocks
• If a system is in unsafe state ⇒ possibility of deadlock
• Avoidance ⇒ ensure that a system will never enter an unsafe state.
• Safe, Unsafe, Deadlock State

DEADLOCK AVOIDANCE ALGORITHMS: 

o Single instance of a resource type 

• Use a resource-allocation graph 

o Multiple instances of a resource type 

• Use the banker’s algorithm

Resource-Allocation-Graph Algorithm: 

• In addition to the request and assignment edges, we introduce a new type of edge, called a claim edge. 
• A claim edge Pi → Rj indicates that process Pi may request resource Rj at some time in the future.
• This edge resembles a request edge in direction but is represented in the graph by a dashed line. 
• When process Pi requests resource Rj, the claim edge Pi → Rj is converted to a request edge. 
• Similarly, when a resource Rj is released by Pi, the assignment edge Rj → Pi is reconverted to a claim edge Pi → Rj.
• Note that the resources must be claimed a priori in the system. That is, before process Pi starts executing, all its claim edges must already appear in the resource-allocation graph. 
• We can relax this condition by allowing a claim edge Pi → Rj to be added to the graph only if all the edges associated with process Pi are claim edges.
• Now suppose that process Pi requests resource Rj. The request can be granted only if converting the request edge Pi → Rj to an assignment edge Rj → Pi does not result in the formation of a cycle in the resource-allocation graph.
• We check for safety by using a cycle-detection algorithm. 
• An algorithm for detecting a cycle in this graph requires an order of n^2 operations, where n is the number of processes in the system. 
• If no cycle exists, then the allocation of the resource will leave the system in a safe state.
• If a cycle is found, then the allocation will put the system in an unsafe state. In that case, process Pi will have to wait for its requests to be satisfied. 
• To illustrate this algorithm, we consider the resource-allocation graph

• Suppose that P2 requests R2. Although R2 is currently free, we cannot allocate it to P2, since this action will create a cycle in the graph.

 

• A cycle, as mentioned, indicates that the system is in an unsafe state. 
• If P1 requests R2, and P2 requests R1, then a deadlock will occur. 

BANKER'S ALGORITHM:

• For Multiple instances of a resource type, we have to use Banker’s algorithm.
• When a new process enters the system, it must declare the maximum number of instances of each resource type that it may need. This number may not exceed the total number of resources in the system.
• When a user requests a set of resources, the system must determine whether the allocation of these resources will leave the system in a safe state.
• If it will, the resources are allocated; otherwise, the process must wait until some other process releases enough resources.

Data Structures for the Banker‟s Algorithm: 

              Several data structures must be maintained to implement the banker’s algorithm. These data structures encode the state of the resource-allocation system. We need the following data structures, where n is the number of processes in the system and m is the number of resource types:

• Available. A vector of length m indicates the number of available resources of each type. If Available[j] equals k, then k instances of resource type Rj are available.
• Max. An n × m matrix defines the maximum demand of each process. If Max[i][j] equals k, then process Pi may request at most k instances of resource type Rj .
• Allocation. An n × m matrix defines the number of resources of each type currently allocated to each process. If Allocation[i][j] equals k, then process Pi is currently allocated k instances of resource type Rj.
• Need. An n × m matrix indicates the remaining resource need of each process. If Need[i][j] equals k, then process Pi may need k more instances of resource type Rj to complete its task. Note that Need[i][j] equals Max[i][j]− Allocation[i][j].

Safety Algorithm: 

              We can now present the algorithm for finding out whether or not a system is in a safe state. This algorithm can be described as follows:

1. LetWork and Finish be vectors of length m and n, respectively. Initialize Work = Available and Finish[i] = false for i = 0, 1, ..., n − 1. 

2. Find an index i such that both 

        a. Finish[i] == false 

        b. Needi ≤Work 

    If no such i exists, go to step 4. 

3. Work =Work + Allocationi 

    Finish[i] = true 

    Go to step 2. 

4. If Finish[i] == true for all i, then the system is in a safe state. 

This algorithm may require an order of m × n^2 operations to determine whether a state is safe.

Resource-Request Algorithm: 

Let Requesti be the request vector for process Pi . If Requesti [ j] == k, then process Pi wants k instances of resource type Rj . When a request for resources is made by process Pi , the following actions are taken: 

1. If Requesti ≤Needi , go to step 2. Otherwise, raise an error condition, since the process has exceeded its maximum claim. 

2. If Requesti ≤ Available, go to step 3. Otherwise, Pi must wait, since the resources are not available. 

3. Have the system pretend to have allocated the requested resources to process Pi by modifying the state as follows: 

Available = Available–Requesti ; 

Allocationi = Allocationi + Requesti ; 

Needi = Needi –Requesti; 

If the resulting resource-allocation state is safe, the transaction is completed, and process Pi is allocated its resources. However, if the new state is unsafe, then Pi must wait for Requesti , and the old resource-allocation state is restored

Example: 

Considering a system with five processes P0 through P4 and three resources of type A, B, C. Resource type A has 10 instances, B has 5 instances and type C has 7 instances. Suppose at time t0 following snapshot of the system has been taken:

Question1. What will be the content of the Need matrix? 

Need [i, j] = Max [i, j] – Allocation [i, j] 

So, the content of Need Matrix is: 

Question2. Is the system in a safe state? If Yes, then what is the safe sequence? 

Applying the Safety algorithm on the given system,

Question3. What will happen if process P1 requests one additional instance of resource type A and two instances of resource type C?

We must determine whether this new system state is safe. To do so, we again execute Safety algorithm on the above data structures.

Hence the new system state is safe, so we can immediately grant the request for process P1.

 

Deadlock Detection:

              If a system does not employ either a deadlock-prevention or a deadlock avoidance algorithm, then a deadlock situation may occur. In this environment, the system may provide:

• An algorithm that examines the state of the system to determine whether a deadlock has occurred
• An algorithm to recover from the deadlock 

Single Instance of Each Resource Type:

• If all resources have only a single instance, then we can define a deadlock detection algorithm that uses a variant of the resource-allocation graph, called a wait-for graph.
• We obtain this graph from the resource-allocation graph by removing the resource nodes and collapsing the appropriate edges. 
• A deadlock exists in the system if and only if the wait-for graph contains a cycle.
• To detect deadlocks, the system needs to maintain the wait-for graph and periodically invoke an algorithm that searches for a cycle in the graph.
• An algorithm to detect a cycle in a graph requires an order of n^2 operations, where n is the number of vertices in the graph
• Nodes are processes
• Pi → Pj if Pi is waiting for Pj

Several Instances of Resource type:

• Available. A vector of lengthmindicates the number of available resources of each type. 
• Allocation. An n × m matrix defines the number of resources of each type currently allocated to each process.
• Request. An n × m matrix indicates the current request of each process. If Request[i][j] equals k, then process Pi is requesting k more instances of resource type Rj . 

Detection Algorithm: 

1. Let Work and Finish be vectors of length m and n, respectively 

   Initialize: 

   (a) Work = Available 

   (b) For i = 1,2, …, n, if Allocationi ≠ 0, then Finish[i] = false; 

        otherwise, Finish[i] = true 

2. Find an index i such that both: 

   (a) Finish[i] == false 

   (b) Requesti  Work 

   If no such i exists, go to step 4  

3. Work = Work + Allocationi 

    Finish[i] = true 

    go to step 2 

4. If Finish[i] == false, for some i, 1 ≤ i ≤ n, then the system is in deadlock state.

Moreover, if Finish[i] == false, then Pi is deadlocked Algorithm requires an order of O(m x n 2 ) operations to detect whether the system is in deadlocked state. 

Example of Detection algorithm:

we consider a system with five processes P0 through P4 and three resource types A, B, and C. Resource type A has seven instances, resource type B has two instances, and resource type C has six instances. Suppose that, at time T0, we have the following resource-allocation state: 

We claim that the system is not in a deadlocked state. Indeed, if we execute our algorithm, we will find that the sequence <P0,P2,P3,P1,P4>  results in Finish[i] == true for all i. 

Suppose now that process P2 makes one additional request for an instance of type C. The Request matrix is modified as follows: 

We claim that the system is now deadlocked. Although we can reclaim the resources held by process P0, the number of available resources is not sufficient to fulfill the requests of the other processes. Thus, a deadlock exists, consisting of processes P1, P2, P3, and P4. 

Detection-Algorithm Usage: 

• When, and how often, to invoke the detection algorithm depends on: 

             How often is a deadlock likely to occur?
             How many processes will be affected by deadlock when it happens?

• If deadlocks occur frequently, then the detection algorithm should be invoked frequently. 
• Resources allocated to deadlocked processes will be idle until the deadlock can be broken. The no of processes involved in deadlock cycle may grow.
• If detection algorithm is invoked arbitrarily, there may be many cycles in the resource graph and so we would not be able to tell which of the many deadlocked processes "caused" the deadlock.

Recovery from Deadlock:

• When a detection algorithm determines that a deadlock exists, several alternatives are available. 
• One possibility is to inform the operator that a deadlock has occurred and to let the operator deal with the deadlock manually.
• Another possibility is to let the system recover from the deadlock automatically. There are two options for breaking a deadlock.
• One is simply to abort one or more processes to break the circular wait. The other is to preempt some resources from one or more of the deadlocked processes. 

Process Termination:

• Abort all deadlocked processes – great expensive
• Abort one process at a time until the deadlock cycle is eliminated (minimum cost)
• In which order should we choose to abort? 

              1. Priority of the process 

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

              3. Resources the process has used 

              4. Resources process needs to complete 

              5. How many processes will need to be terminated 

              6. Is process interactive or batch? 

Recovery from Deadlock: 

• 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