ch8
41 pág.

ch8


DisciplinaSistemas Operacionais I8.352 materiais171.655 seguidores
Pré-visualização2 páginas
Silberschatz, Galvin and Gagne \uf6d920028.1Operating System Concepts
Chapter 8: Deadlocks
\ufffd System Model
\ufffd Deadlock Characterization
\ufffd Methods for Handling Deadlocks
\ufffd Deadlock Prevention
\ufffd Deadlock Avoidance
\ufffd Deadlock Detection
\ufffd Recovery from Deadlock
\ufffd Combined Approach to Deadlock Handling
Silberschatz, Galvin and Gagne \uf6d920028.2Operating System Concepts
The Deadlock Problem
\ufffd A set of blocked processes each holding a resource and
waiting to acquire a resource held by another process in
the set.
\ufffd Example
\u2726 System has 2 tape drives.
\u2726 P1 and P2 each hold one tape drive and each needs another
one.
\ufffd Example
\u2726 semaphores A and B, initialized to 1
 P0 P1
wait (A); wait(B)
wait (B); wait(A)
Silberschatz, Galvin and Gagne \uf6d920028.3Operating System Concepts
Bridge Crossing Example
\ufffd Traffic only in one direction.
\ufffd Each section of a bridge can be viewed as a resource.
\ufffd If a deadlock occurs, it can be resolved if one car backs
up (preempt resources and rollback).
\ufffd Several cars may have to be backed up if a deadlock
occurs.
\ufffd Starvation is possible.
Silberschatz, Galvin and Gagne \uf6d920028.4Operating System Concepts
System Model
\ufffd Resource types R1, R2, . . ., Rm
CPU cycles, memory space, I/O devices
\ufffd Each resource type Ri has Wi instances.
\ufffd Each process utilizes a resource as follows:
\u2726 request
\u2726 use
\u2726 release
Silberschatz, Galvin and Gagne \uf6d920028.5Operating System Concepts
Deadlock Characterization
\ufffd Mutual exclusion: only one process at a time can use a
resource.
\ufffd Hold and wait: a process holding at least one resource
is waiting to acquire additional resources held by other
processes.
\ufffd No preemption: a resource can be released only
voluntarily by the process holding it, after that process
has completed its task.
\ufffd Circular wait: there exists a set {P0, P1, \u2026, P0} of waiting
processes such that P0 is waiting for a resource that is
held by P1, P1 is waiting for a resource that is held by
P2, \u2026, Pn\u20131 is waiting for a resource that is held by
Pn, and P0 is waiting for a resource that is held by P0.
Deadlock can arise if four conditions hold simultaneously.
Silberschatz, Galvin and Gagne \uf6d920028.6Operating System Concepts
Resource-Allocation Graph
\ufffd V is partitioned into two types:
\u2726 P = {P1, P2, \u2026, Pn}, the set consisting of all the processes in
the system.
\u2726 R = {R1, R2, \u2026, Rm}, the set consisting of all resource types
in the system.
\ufffd request edge \u2013 directed edge P1 \u2192 Rj
\ufffd assignment edge \u2013 directed edge Rj \u2192 Pi
A set of vertices V and a set of edges E.
Silberschatz, Galvin and Gagne \uf6d920028.7Operating System Concepts
Resource-Allocation Graph (Cont.)
\ufffd Process
\ufffd Resource Type with 4 instances
\ufffd Pi requests instance of Rj
\ufffd Pi is holding an instance of Rj
Pi
Pi
Rj
Rj
Silberschatz, Galvin and Gagne \uf6d920028.8Operating System Concepts
Example of a Resource Allocation Graph
Silberschatz, Galvin and Gagne \uf6d920028.9Operating System Concepts
Resource Allocation Graph With A Deadlock
Silberschatz, Galvin and Gagne \uf6d920028.10Operating System Concepts
Resource Allocation Graph With A Cycle But No Deadlock
Silberschatz, Galvin and Gagne \uf6d920028.11Operating System Concepts
Basic Facts
\ufffd If graph contains no cycles \ufffd no deadlock.
\ufffd If graph contains a cycle \ufffd
\u2726 if only one instance per resource type, then deadlock.
\u2726 if several instances per resource type, possibility of
deadlock.
Silberschatz, Galvin and Gagne \uf6d920028.12Operating System Concepts
Methods for Handling Deadlocks
\ufffd Ensure that the system will never enter a deadlock state.
\ufffd Allow the system to enter a deadlock state and then
recover.
\ufffd Ignore the problem and pretend that deadlocks never
occur in the system; used by most operating systems,
including UNIX.
Silberschatz, Galvin and Gagne \uf6d920028.13Operating System Concepts
Deadlock Prevention
\ufffd Mutual Exclusion \u2013 not required for sharable resources;
must hold for nonsharable resources.
\ufffd Hold and Wait \u2013 must guarantee that whenever a
process requests a resource, it does not hold any other
resources.
\u2726 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.
\u2726 Low resource utilization; starvation possible.
Restrain the ways request can be made.
Silberschatz, Galvin and Gagne \uf6d920028.14Operating System Concepts
Deadlock Prevention (Cont.)
\ufffd No Preemption \u2013
\u2726 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.
\u2726 Preempted resources are added to the list of resources for
which the process is waiting.
\u2726 Process will be restarted only when it can regain its old
resources, as well as the new ones that it is requesting.
\ufffd Circular Wait \u2013 impose a total ordering of all resource
types, and require that each process requests resources
in an increasing order of enumeration.
Silberschatz, Galvin and Gagne \uf6d920028.15Operating System Concepts
Deadlock Avoidance
\ufffd Simplest and most useful model requires that each
process declare the maximum number of resources of
each type that it may need.
\ufffd The deadlock-avoidance algorithm dynamically examines
the resource-allocation state to ensure that there can
never be a circular-wait condition.
\ufffd Resource-allocation state is defined by the number of
available and allocated resources, and the maximum
demands of the processes.
Requires that the system has some additional a priori information 
available.
Silberschatz, Galvin and Gagne \uf6d920028.16Operating System Concepts
Safe State
\ufffd When a process requests an available resource, system must
decide if immediate allocation leaves the system in a safe state.
\ufffd System is in safe state if there exists a safe sequence of all
processes.
\ufffd Sequence <P1, P2, \u2026, Pn> is safe if for each Pi, the resources
that Pi can still request can be satisfied by currently available
resources + resources held by all the Pj, with j<I.
\u2726 If Pi resource needs are not immediately available, then Pi can wait
until all Pj have finished.
\u2726 When Pj is finished, Pi can obtain needed resources, execute,
return allocated resources, and terminate.
\u2726 When Pi terminates, Pi+1 can obtain its needed resources, and so
on.
Silberschatz, Galvin and Gagne \uf6d920028.17Operating System Concepts
Basic Facts
\ufffd If a system is in safe state \ufffd no deadlocks.
\ufffd If a system is in unsafe state \ufffd possibility of deadlock.
\ufffd Avoidance \ufffd ensure that a system will never enter an
unsafe state.
Silberschatz, Galvin and Gagne \uf6d920028.18Operating System Concepts
Safe, Unsafe , Deadlock State
Silberschatz, Galvin and Gagne \uf6d920028.19Operating System Concepts
Resource-Allocation Graph Algorithm
\ufffd Claim edge Pi \u2192 Rj indicated that process Pj may request
resource Rj; represented by a dashed line.
\ufffd Claim edge converts to request edge when a process
requests a resource.
\ufffd When a resource is released by a process, assignment
edge reconverts to a claim edge.
\ufffd Resources must be claimed a priori in the system.
Silberschatz, Galvin and Gagne \uf6d920028.20Operating System Concepts
Resource-Allocation Graph For Deadlock Avoidance
Silberschatz, Galvin and Gagne \uf6d920028.21Operating System Concepts
Unsafe State In Resource-Allocation Graph
Silberschatz, Galvin and Gagne \uf6d920028.22Operating System Concepts
Banker\u2019s Algorithm
\ufffd Multiple instances.
\ufffd Each process must a priori claim maximum use.
\ufffd When a process requests a resource it may have to wait.
\ufffd When a process gets all its resources it must return them
in a finite amount of time.
Silberschatz, Galvin and Gagne \uf6d920028.23Operating System Concepts
Data Structures for the Banker\u2019s Algorithm
\ufffd Available: Vector of length m. If available [j] = k, there are
k instances of resource type Rj available.
\ufffd Max: n x m matrix. If Max [i,j] = k, then process Pi may
request at most k instances of resource type Rj.
\ufffd Allocation: n x m matrix. If Allocation[i,j] = k then Pi is
currently