COMSCI 2101 - PROCESS MANAGEMENT (DEADLOCK)

- Deadlock
- Starvation

A lack of process synchronization can result in two extreme conditions:

Deadlock

A problem where resources needed by some process to finish execution are held by other processes, which, in turn, are waiting for other resources to
become available.

Deadlock

also called deadly embrace

Deadlock

infrequent in batch systems, and more prevalent in interactive
systems.

• Case 1: Deadlocks on File Requests
• Case 2: Deadlocks in Databases
• Case 3: Deadlocks in Dedicated Device Allocation
• Case 4: Deadlocks in Multiple Device Allocation
• Case 5: Deadlocks in Spooling
• Case 6: Deadlocks in a Network
• Case 7: Deadlocks in Disk Sharing

Seven Cases of Deadlock

Case 5: Deadlocks in Spooling

• The spooler accepts output from several users and acts as a
temporary storage area for all output until the printer is ready
to accept it.
• This process is called _______.

- Mutual Exclusion
- Resource Holding
- No Preemption
- Circular Wait

Conditions for Deadlock

Mutual Exclusion

- act of allowing only one person (or process) to have access to a step (a dedicated resource)

Resource Holding

- When two people meet on the stairs and each one holds ground and waits for the other to retreat

No Preemption

- Each step is dedicated to the climber; it is allocated to the holder
for as long as needed.

Circular Wait

- Each person (or process) involved in the impasse is waiting for
another to voluntarily release the step (or resource) so that at
least one will be able to continue on and eventually arrive at the
destination.

• Detection
• Prevention
• Avoidance
• Recovery

Strategies for Handling Deadlocks

Detection

The directed graphs presented earlier in this chapter showed
how the existence of a circular wait indicated a deadlock, so it's
reasonable to conclude that deadlocks can be detected by
building directed resource graphs and looking for cycles.

Prevention

To prevent a deadlock, the operating system must eliminate
one of the four necessary conditions, a task complicated by
the fact that the same condition can't be eliminated
from every resource.

Avoidance

Even if the operating system can't remove one of the conditions
for deadlock, it can avoid one if the system knows ahead of time
the sequence of requests associated with each of the active
processes.

Recovery

• Once a deadlock has been detected, it must be untangled and
the system returned to normal as quickly as possible.

• There are several ______ algorithms, but they all have one feature in common:
They all require at least one victim, an expendable job, which, when removed from the deadlock, will
free the system.

Starvation

• So far we have concentrated on deadlocks, the result of liberal
allocation of resources.
• At the opposite end is ________, the result of conservative
allocation of resources where a single job is prevented from
execution because it's kept waiting for resources that never
become available.