(7) Deadlock

Question 1

When is a thread deadlocked?

Answer 1

When it’s waiting for an event to occur that can never occur.

Question 2

What four conditions must be present for a deadlock to be possible?

Answer 2

Mutual exclusion
Hold and wait
No preemption
Circular wait

Question 3

What happens if you have an -irreducible- cycle?

Answer 3

A deadlock occurs

Question 4

When can a graph be reduced by a thread?

Answer 4

If all of that threads requests can be granted meaning that the thread will eventually terminate.

Question 5

What are the (Hold, Havender) Miscellaneous theroems?

Answer 5

There are no deadlocked threads iff the graph is completely reducible
The order of reductions is irrelevant.

Question 6

How would you prevent deadlocks by targeting the Mutual Exclusion requirement?

Answer 6

Don’t require mutual exclusion for shareable (e.g read-only) files; but do for non-shareable resources.

Question 7

How would you prevent deadlocks by targeting the Hold and Wait requirement?

Answer 7

Guarantee that whenever a process requests a resource it does not hold any other resources.

Question 8

How would you prevent deadlocks by targeting the No Preemption requirement?

Answer 8

If a process holding some resources requests another unavailable resource then all resources currently held are released.
Only restart process when it can regain its old resources as well as the newly requested ones.

Question 9

How would you prevent deadlocks by targeting the Circular Wait requirement?

Answer 9

Impose a total ordering of all resource types and requires that each process requests resources in an increasing order of enumeration.

Question 10

What is detect and recover?

Answer 10

Every once in a while check to see if there is a deadlock and if there is then remove it.

Question 11

What is a Safe State?

Answer 11

If there is a sequence of ALL processes in the systems such that for every Pi the resources that Pi can still request can be satisfied by the currently available resources and the resources held by all Pj where j

Question 12

What is the relation between unsafe states and deadlocks?

Answer 12

Deadlocks are a subset of unsafe states.

Question 13

What is deadlock detection?

Answer 13

You allow the system to enter the deadlock state
Run the detection algorithm (waits-for with cycle detection)
Recover