Deadlocks

Resources with exclusive access can be used by only one process at a time.

Examples of resources with exclusive access:

printers,

tape drives,

entries in a system internal tables,

records in a data base,

The fact that processes have exclusive access to resources in a system, can leads to a situation called deadlock.

EXAMPLE

  • There are two processes (A and B) in a system and each of these processeswants to record a scanned document on a CD.
  • We may have the following situation:
  1. Process A requests the CD recorder first and then gets it.
  2. Process B requests the scanner first and also gets it.
  3. Now process A is requesting the scanner:but it cannot get it until B releases it.
  4. Process B is requesting the CD recorder:but it cannot get it until A releases it.
  • At this point, both processes are blocked and will remain blocked forever.

Deadlock may also occur in the following situations:

a)in a network system with shared resources

b)in a data base system with record locking.

Preemptable and Nonpreemptable Resources

There are two major types of resources in as system:

preemptableand

nonpreemptable resourcess.

A preemptable resource

is a resource that can be taken away from the process that is holding it with no ill effect.

Example:the memory, the CPU.

A non-preemptable resource

is a resource that cannot be taken away from the process that is holding it without causing the computation to fail.

Example: a printer.

Deadlocks generally involve non-preemptable resources.

How do Processes use Resources?

The sequence of events required to use a resource is as follows:

  1. Request the resource
  2. Use the resource
  3. Release the resource

If a resource is not available when requested, the requesting process is forced to wait as follows:

  • in some O.S. , the process is automatically blocked, and then awakened when it becomes available.
  • in other systems, the request fails with an error message and it is up to the requesting process to wait a little while, and then try again.

How doesa Process make a Request for a Resource?

It is system dependent: For example, using the open system call in some systems.

Definition of Deadlock

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

Conditions for deadlock (page440)

There is a deadlock is a system only if the following four conditions are true:

  1. Mutual exclusion condition.
  2. Hold and wait condition.
  3. No preemption condition.
  4. Circular wait condition.

Deadlock Modeling:

use of resource graphs.Example in page 447

Dealing with deadlocks:

Four strategies

  1. The ostrich algorithm:ignore the problem.
  2. Detection and recovery:let deadlocks occur, detect them and take action to recover from them.
  3. Dynamic avoidance by careful allocation of resources.
  4. Prevention:by structurally negating one of the four required conditions.

Chapter 6 Questions

1

a)When is a process in an asynchronous concurrent system said to be deadlocked?

b)What are the four conditions that must be true for a deadlock to exist?

c) Describe each of the four strategies used for dealing with deadlocks.

2.

Do the following exercises:

14, 15, 21, 26page 466-467.