Chapter 7 Deadlocks

Chapter 7: Deadlocks
Operating System Concepts – 8th Edition Silberschatz, Galvin and Gagne ©2009
Chapter 7: Deadlocks
 The Deadlock Problem
 System Model
 Deadlock Characterization
 Methods for Handling Deadlocks
 Deadlock Prevention
 Deadlock Avoidance
 Deadlock Detection
 Recovery from Deadlock
Operating System Concepts – 8th Edition 7.2 Silberschatz, Galvin and Gagne ©2009
Chapter Objectives
 To develop a description of deadlocks, which prevent sets of
concurrent processes from completing their tasks
 To present a number of different methods for preventing or avoiding

deadlocks in a computer system
The Deadlock Problem
 A set of blocked processes each holding a resource and waiting to
acquire a resource held by another process in the set
 Example
 System has 2 disk drives
 P1 and P2 each hold one disk drive and each needs another one
 Example

semaphores A and B, initialized to 1 P0 P1
wait (A); wait(B) wait (B); wait(A)
Bridge Crossing Example
 Traffic only in one direction

 Each section of a bridge can be viewed as a resource
 If a deadlock occurs, it can be resolved if one car backs up
(preempt resources and rollback)
 Several cars may have to be backed up if a deadlock occurs
 Starvation is possible
 Note – Most OSes do not prevent or deal with deadlocks
System Model
 Resource types R1, R2, . . ., Rm

CPU cycles, memory space, I/O devices
 Each resource type Ri has Wi instances.
 Each process utilizes a resource as follows:

 request
 use
 release
Methods for Handling Deadlocks
 Ensure that the system will never enter a deadlock state
 Allow the system to enter a deadlock state and then recover
 Ignore the problem and pretend that deadlocks never occur in the
system; used by most operating systems, including UNIX
Deadlock Prevention
Restrain the ways request can be made

 Mutual Exclusion – not required for sharable resources; must
hold for nonsharable resources
 Hold and Wait – must guarantee that whenever a process

requests a resource, it does not hold any other resources
 Require process to request and be allocated all its resources
before it begins execution, or allow process to request
resources only when the process has none
 Low resource utilization; starvation possible
Deadlock Prevention (Cont.)
 No Preemption –
 If a process that is holding some resources requests another
resource that cannot be immediately allocated to it, then all
resources currently being held are released
 Preempted resources are added to the list of resources for which
the process is waiting
 Process will be restarted only when it can regain its old resources,
as well as the new ones that it is requesting
 Circular Wait – impose a total ordering of all resource types, and

require that each process requests resources in an increasing order of
enumeration
Deadlock Avoidance
Requires that the system has some additional a priori information

available
 Simplest and most useful model requires that each process declare
the maximum number of resources of each type that it may need
 The deadlock-avoidance algorithm dynamically examines the

resource-allocation state to ensure that there can never be a
circular-wait condition
 Resource-allocation state is defined by the number of available and

allocated resources, and the maximum demands of the processes
Safe State
 When a process requests an available resource, system must decide
if immediate allocation leaves the system in a safe state
 System is in safe state if there exists a sequence <P1, P2, …, Pn> of

ALL the processes is the systems such that for each P i, the
resources that Pi can still request can be satisfied by currently
available resources + resources held by all the Pj, with j < I
 That is:
 If Pi resource needs are not immediately available, then Pi can
wait until all Pj have finished
 When Pj is finished, Pi can obtain needed resources, execute,
return allocated resources, and terminate
 When Pi terminates, Pi +1 can obtain its needed resources, and so
on
Basic Facts
 If a system is in 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.
‫سؤالك ق د يفتح آفاق ًا جدي دة لم‬
‫ أو يط رق أبواب ًا مغلق ة لم‬.. ‫ُتْس َبر‬
‫تأمالت_حياة‬# .. ‫ُتفتح‬
13
Operating Systems

Chapter 7 Deadlocks

Uploaded by

Copyright:

Available Formats

Chapter 7 Deadlocks

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Chapter 7 Deadlocks

Uploaded by

Copyright:

Available Formats

Chapter 7: Deadlocks

 To present a number of different methods for preventing or avoiding

 Traffic only in one direction

 Resource types R1, R2, . . ., Rm

 Each resource type Ri has Wi instances.

 Each process utilizes a resource as follows:

 Ensure that the system will never enter a deadlock state

 Allow the system to enter a deadlock state and then recover

Restrain the ways request can be made

 Hold and Wait – must guarantee that whenever a process

 Circular Wait – impose a total ordering of all resource types, and

Requires that the system has some additional a priori information

 The deadlock-avoidance algorithm dynamically examines the

 Resource-allocation state is defined by the number of available and

 System is in safe state if there exists a sequence <P1, P2, …, Pn> of

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

You might also like