Deadlocks & Livelocks

Question 1

Deadlock arises only if what four conditions hold simultaneously?

Answer 1

1. Mutual exclusion
2. Hold and Wait
3. No pre-emption
4. Circular wait

Question 2

What is Mutual Exclusion (mutex) 3 points?

Answer 2

There are resources requiring mutual exclusion
* At least one resource held in a non-sharable state
* i.e. Only one process at a time can access the resource
* A requesting process must be delayed until the resource
has been released

Question 3

What is Hold and Wait?

Answer 3

• A process is currently holding (at least one) mutex
  resource
• And is waiting to acquire (at least one) more that is being
  held by another process

Question 4

What is No Pre-emption?

Answer 4

• Resources cannot be pre-empted
• Resources can only be released voluntarily by the the
  process holding it.
• After it has completed its task

Question 5

What is Circular Wait?

Answer 5

There exists a chain of processes P1,P2 “, … P3 such that
P1 is waiting for a mutex resource being held by P2.
* P2 for one held by P3
*P2$ for one held by Pn
* Pn for one held by P1

Question 6

Options for Handling Deadlocks 3 points

Answer 6

1. Ensure the system will never enter a deadlock state
2. Allow deadlock states, but enable recovery
3. Ignore the problem and pretend they never occur

Question 7

Deadlock Prevention

Answer 7

1. Mutex:
2. Hold & Wait:
   * Could remove by guaranteeing that when a process requests a
   resource, it does not hold others
   * Required process allocated all its resources before execution
3. No pre-emption:
   * Could remove: Example – if a process requests a resource but is not
   immediately allocated, it must release all other resources
4. Circular wait:
   * Could ensure it doesn’t arise: Impose ordering on resource types,
   and processes must request them strictly by this order

Question 8

What to avoid Deadlock?

Answer 8

• Prevention ensures cannot exist though limiting
  conditions
• Avoidance considers resources requirements prior to
  allocation

Question 9

What is a safe sate?

Answer 9

When a process requests an available resource, the
system must decide if immediate allocation leaves the
system in a safe state

Question 10

System is in a safe state if, for processes , P1,P2 “, … P3 what
conditions hold:

Answer 10

• If Pi resource needs are not immediately available, then Pi can wait
  until all Pj(j < i) have finished
• When Pj” is finished, Pi can obtain needed resources, execute, and return
  allocated resources, and terminate
• When Pi terminates, P i+1 can obtain its needed resources, and so on.

Question 11

Safe State and Deadlock Avoidance

Answer 11

• If a system is in a 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

Question 12

How to recover from a Deadlock?

Answer 12

• Two main alternatives:
  Process termination
• Abort all processes?
• Abort individual processes until deadlock eliminated

Resource pre-emption
* Which process?
* How to rollback?
* Can cause starvation

Question 13

Alternative apporach to recovering from a Deadlock?

Answer 13

• Ignore Deadlocks!