Deadlock and Distributed Deadlock

Question 1

4 necessary deadlock conditions

Answer 1

mutual exclusion

hold and wait

no preemption

circular wait

Question 2

what is hold and wait

Answer 2

allowing processes to hold previously acquired resources while waiting for additional ones

Question 3

3 deadlock handling strategies

Answer 3

deadlock prevention

deadlock avoidance

deadlock detection/recovery

Question 4

2 types of resources

Answer 4

reusable resources

consumable resources

Question 5

idea of Havender’s linear ordering scheme

Answer 5

• the idea is deadlock prevention by eliminating circular wait
• resources are ordered in some way by id or priority
• processes can only request resources of higher id or priority than they currently have. since resource request are uni-directional, circular-wait is impossible

Question 6

The part of Banker’s algorithm I’m likely to forget

Answer 6

To find available resources sum up each column in “Allocated” and subtract from Total-Max

Max Resources for process = Allocation + Need

When you are checking to see if a request is safe, subtract request value from “Available”. Then look at need matrix to see if any of the processes can be completed (“Available” has greater than or equal to the number of resources of each kind that are needed by that process).

If a process can be completed, subtract the need from “Available”. Then add “Max” to available. Repeat process to determine if all processes can be completed.

if yes = safe
if no = not safe

Question 7

Resource graph semantics

Answer 7

if a process node has a directed edge towards a resource node = request for that resource

edge from resource node to process node = process is holding that resource

Question 8

system model

Answer 8

a set of assumptions to reduce the complexity of deadlock detection

• reusable resources only
• only exclusive access to resources (no concurrent use)
• each resource only has one instance (only one unit of each resource)

Question 9

what is a wait-for graph? (WFG)

Answer 9

a resource graph without the resource nodes for simplicity

P1 –> P2 implies P1 –> R –> P2

Question 10

centralize deadlock control algorithm

Answer 10

• control site maintains WFG of the entire system
• when a site requests or releases a resource it sends a message to the control site.
• each time the control site receives a message it updates the WFG and the inspects it to see if a deadlock is present