21. Deadlock Management

Question 1

Deadlock

Answer 1

• The permanent blocking of a set of processes that either compete for system resources or communicate with each other

Question 2

Process-Resource Dependency Graph

Answer 2

• Processes and resources are nodes
• An edge exists from a process to a resource if the process is requesting that resource
• An edge exists from a resource to a process if that process has already acquired the resource
• A deadlock occurs when there is a loop in the graph

Question 3

Necessary and Sufficient Conditions for Deadlock

Answer 3

• Multiple processes sharing multiple resources
• Resources have limited capacity
• Processes may hold some resources while waiting for others
• A closed chain of dependency in the process-resource graph

Question 4

Flaw of Deadlock Prevention

Answer 4

• Change the system so that conditions do not hold
• Not a practical solution

Question 5

Flaw of Deadlock Detection & Recovery

Answer 5

• Detect loops in graph and break them
• Hard to detect a lack of progress and reconstruct the dependency graph

Question 6

Flaw of Deadlock Avoidance

Answer 6

• Do not entire a doomed state in the first place
• Processes may be stalled unnecessarily

Question 7

Banker Algorithm

Answer 7

• Given a request for process i and resource k
• Assume we grant the request
• Recalculate available resources and remaining needs
• Check if the system can finish execution in this configuration

Question 8

Banker Algorithm R(k)

Answer 8

• The total amount of resource R_{k} in the system

Question 9

Banker Algorithm C_{i}(k)

Answer 9

• The total amount of resource R_{k} that process P_{i} will ever need

Question 10

Banker Algorithm A_{i}(k)

Answer 10

• The total amount of resource R_{k} currently allocated to process P_{i}

Question 11

Banker Algorithm V(k)

Answer 11

• The total amount of resource R_{k} currently available
• Equal to the total minus the sum of the current allocation

Question 12

Banker Algorithm N_{i}(k)

Answer 12

• The total amount of resource R_{k} currently needed by process P_{i} to complete its execution

Question 13

Limitations of the Banker Algorithm

Answer 13

• There may exist a state that would not lead to a deadlock that is deemed unsafe by the algorithm
• Deadlocks are still possible if processes declare inexact values of C_{i}(k) or if there are hidden shared resources