Transcript deadlock

Chapter 5 Process Management
CIS106
Microcomputer Operating Systems
Gina Rue
CIS Faculty
Ivy Tech State College Northwest Region 01
Introduction Process Management
• Problems are caused when many
processes compete for relatively few
resources & the system is unable to
service all the processes of the system
– A lack of process synchronization can result
in two extreme conditions
• deadlock
• starvation
See Illustration p.99
2
Process Management Deadlock
– In early OSs, deadlock was known as “deadly
embrace”
– begins when two or more jobs requests a
resource
– jobs are put on hold, each waiting for vital
resources to become available, jobs come to
a standstill
3
Process Management Deadlock
– Deadlock is complete if the rest of the
system comes to a standstill as well
– Usually can’t be resolved by the OS and
requires intervention
• operators/users terminate job
– Deadlock described as a narrow staircase in
a building
– Starvation is an extreme case of indefinite
postponement
4
Deadlock
• More serious than indefinite
postponement or starvation
– affects more than one job
– affects resources of the entire system
– were more infrequent in early batch
systems
– became more prevalent with growing use
of interactive systems
See Fig. 5.1 p. 101
5
Seven Cases of Deadlock
Deadlock usually occurs when nonsharable, non-preemptable
resources, such as files, printers are
allocated jobs that eventually
require--the resources that have
been locked by other jobs
• also with resources such as tape drives, disks,
& databases
6
Seven Cases of Deadlock
A Deadlock can occur with
• File Requests - if jobs are allowed to request
and hold files for the duration of their
execution
• Databases - if two processes access and lock
records in a database. Note: Locking & Race
• Device Allocation - use of a group of
dedicated devices, tape drive
• Multiple Device Allocation - can happen when
several processes request, & hold two devices
while other processes act in a similar manor
7
Seven Cases of Deadlock
(con’t.)
A Deadlock can occur with
• Spooling - where a disk, between the device
(printer) and CPU, accepts output from
several users (network) and acts as a
temporary storage area for all output until the
printer is ready to accept it
• Disk Sharing - two processes to be accessing
different areas of the same disk causing
competing processes that send conflicting
commands
• Network - congested or has large % of its I/O
buffer space full if no protocol controls flow of
8
traffic
Conditions For Deadlock
• Deadlock is proceeded by the
simultaneous occurrence of 4
conditions the OS can recognize
– mutual exclusion
– resource holding
– no preemption
– circular wait
9
Conditions For Deadlock
Stairway example:
– mutual exclusion, the act of allowing only
one person (or process) to have access to a
step (or resource)
– resource holding, two people met on the
stairs & each waited for the other to retreat
– no preemption, each step is dedicated to the
climber (or descender) as long as needed
– circular wait, each person (or process)
involved is waiting for another to release the
step (or resource)
10
Modeling Deadlocks
Directed Graphs
• Holt (1972)
• two kinds of symbols
– processes represented by circles
– resources represented by squares
• solid lines
– from a resource to a process means that the
process is holding that resource
– from a process to a resource means that the
process is waiting for that resource
• arrows
– direction indicates the flow
See Fig. 5.7 - 10 p.108-110
11
Strategies for Handling Deadlocks
Requests & releases are received in an
unpredictable order, which makes it
difficult to design a foolproof preventive
policy.
• An OS uses 1 of 3 strategies to deal with
deadlocks:
– Prevent one user of the 4 conditions from
occurring
– Avoid deadlock if it becomes probable
– Detect the deadlock when it occurs &
recover from it gracefully 12
Strategies for Handling Deadlocks
• Deadlock recovery strategies require that
at least one victim, an expendable job,
when removed from the system, will free
the system. Victim selection should have
the least effect on the system:
– Priority of the job
– CPU time used by the job
– The number of jobs
13
Starvation
The result of conservative allocation of
resources where a single job is prevented
from execution because it is waiting for
resources that never become available
– an algorithm designed to detect starving jobs
can be implemented, which tracks how long
each job has been waiting for resources (this
is the same as aging described in Ch.4)
14
Summary
• Every OS must dynamically allocate a
limited number of resources while
avoiding the 2 extremes of deadlock &
starvation
• Methods of dealing with deadlock
– prevention
– avoidance
– detection
– recovery
15
Summary
• Deadlocks can be prevented by not
allowing the 4 conditions of deadlock to
occur in the system at the same time
– mutual exclusion
– resource holding
– no preemption
– circular wait
By eliminating at least one of the 4 conditions,
a system can be kept deadlock-free
16
Summary
• Prevention algorithms are complex & to
routinely execute them involves high
overhead
• Avoid by identifying safe & unsafe states
• Prepare to detect and recover from
deadlock
– “victim” a job must be terminated before it
finishes execution & must be started again
17