Resources

Examples of computer resources:

  • Printers
  • Tape drivers
  • Tables in databases.

Processes need access to resources in a reasonable order.

  • Preemptable resources can be taken away from a process with no ill effects.
  • Non-preemptable resource will cause the process to fail when taken away.

Formal Definition of Deadlock

A set of proceses is deadlocked if each process in the set is waiting for an event that only another process in the set can cause.

Conditions for Deadlock

  • Mutual exclusion condition.
    • Each resource assigned to 1 process or is available.
  • Hold and wait condition.
    • Process holding resources can request additional resources.
  • No preemption condition.
    • Previously granted resoucre cannot be forcibly taken away.
  • Circular wait condition.
    • Must be a circular chain of 2 or more processes.
    • Each is waiting for resource held by next member of the chain.

Deadlock Prevention

Must attack one of the four deadlock conditions.

Attacking Mutual Exclusion

Not viable - some resources are intrinsically not shareable.

Attacking Hold and Wait

  • Require process to request resources before starting and then let it run to completion.
    • Process never has to wait for what it needs.
  • Problems:
    • May not know required resources at start of run.
      • => Not always possible.
    • Ties up resources other processes could be using.
      • E.g. A process reads data from an input tape for an hour. No other process can use it in the meantime.

Attacking No-Preemption

  • Forcibly take away resources from a process.
  • Clearly not viable:
    • Can’t stop a printing job halfway through.

Attacking Circular Wait

  • *Order acquisition of resources such that deadlocks cannot happen.
  • Resource allocation graph must be acyclic.

Deadlock Detection and Recovery

Instead of preventing deadlocks, detect when a system is deadlock and recover from it.

Detection With One Resource of Each Type

  • Circles are processes.
  • Squares are resources.
  • Process <- Resource means process holds resource.
  • Process -> Resource means process requesting resource.

Deadlock found when there is a cycle in the graph.

Detection With Multiple Resource of Each Type

Algorithm:

  1. Lock for an unmarked process Pi, for which the i-th row of R is less than or equal to A.
  2. If found, add the i-th row of C to A, and mark Pi. Repeat from step 1.
  3. If no such process exists, terminate.

Recovery:

  • Recovery through preemption.
  • Recovery through rollback.
  • Recovery through killing processes.

Deadlock Avoidance

Avoid deadlocks ahead of time.

  • Requires maximum number of each resource required.

Resource Trajectory

  • Horizontal axis represents number of instructions executed by process A.
  • Vertical axis represents number of instructions executed by process B.
  • Process A requests a printer at I1 and releases the printer at I3.
  • Shaded regions indicate both processes having some resource.
    • Mutual exclusion makes it impossible enter these regions.

If a trajectory has no choice but to enter the shaded boxes, then it is deadlocked.

  • The box bounded by I1-I2 and I5-I6 is unsafe.

Trajectories must be chosen to completely avoid unsafe regions.

  • B is requesting the plotter at t. The system must not grant it and instead suspend B to avoid deadlocks.

Safe and Unsafe States

A state is safe if:

  • The system is not deadlocked.
  • There exists a scheduling order that results in every process running to completion, even if they all request their maximum resources immediately.

Note:

  • Unsafe states are not necessarily deadlocked.
    • With a lucky sequence, all processes may complete.
    • However, we cannot guarantee that they will complete.
  • Safe states guarantee we will eventually complete all processes.