Transcript Module 7: Process Synchronization

Operating Systems
Lecture 27
CPU Simulator III
Deadlock
Operating System Concepts
7.1
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
handle_run_term( )
We will determine what needs to be done for this function
in class.
Operating System Concepts
7.2
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
handle_run_block( )
We will determine what needs to be done for this function
in class.
Operating System Concepts
7.3
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
handle_block_ready( )
We will determine what needs to be done for this function
in class.
Operating System Concepts
7.4
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
Files, etc.
 Place all the code for the fcfs simulation in the file"fcfs.cc"
 In driver.cc, you should have an include line:
 #include "fcfs.cc"
 To compile, you can type:
 g++ driver.cc -o sim
 Place all struct definitions and enums in a file "sim.h"
 Include "sim.h" in both driver.cc and fcfs.cc
 You will need to use #ifndef SIM_H, etc. to make sure the
linker doesn't complain.
 Use the following include lines in sim.h:
 #include "nextEvent.h"
 #include "list.h"
 Do not include nextEvent.h or list.h in driver.cc or fcfs.cc
Operating System Concepts
7.5
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
Developing your code
 Write your functions one at a time.
 Debug each function before you start working on the
next.
 Example: Make sure your function to initialize the
Event queue inserts all the appropriate events based
on the process arrival times before you try to right any
of the event handlers.
 Use cout statements and the display( ) function (part
of the NextEventSimulator and the list classes) to
make sure your function is doing the right thing.
Operating System Concepts
7.6
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
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 tape drives.
 P1 and P2 each hold one tape drive and each needs another
one.
 Example
 semaphores A and B, initialized to 1
P0
P1
wait (A);
wait (B);
Operating System Concepts
wait(B)
wait(A)
7.7
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
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.
Operating System Concepts
7.8
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
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
Operating System Concepts
7.9
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
Deadlock Characterization
Deadlock can arise if four conditions hold simultaneously.
 Mutual exclusion: only one process at a time can use a
resource.
 Hold and wait: a process holding at least one resource
is waiting to acquire additional resources held by other
processes.
 No preemption: a resource can be released only
voluntarily by the process holding it, after that process
has completed its task.
 Circular wait: there exists a set {P0, P1, …, Pn} 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, …, Pn–1 is waiting for a resource that is held by
Pn, and Pn is waiting for a resource that is held by P0.
Operating System Concepts
7.10
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
Resource-Allocation Graph
A set of vertices V and a set of edges E.
 V is partitioned into two types:
 P = {P1, P2, …, Pn}, the set consisting of all the processes in
the system.
 R = {R1, R2, …, Rm}, the set consisting of all resource types
in the system.
 request edge – directed edge Pi  Rj
 assignment edge – directed edge Rj  Pi
Operating System Concepts
7.11
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
Resource-Allocation Graph (Cont.)
 Process
 Resource Type with 4 instances
 Pi requests instance of Rj
Pi
Rj
 Pi is holding an instance of Rj
Pi
Rj
Operating System Concepts
7.12
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
Example of a Resource Allocation Graph
Operating System Concepts
7.13
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
Resource Allocation Graph With A Deadlock
Operating System Concepts
7.14
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
Resource Allocation Graph With A Cycle But No Deadlock
Operating System Concepts
7.15
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
Basic Facts
 If graph contains no cycles  no deadlock.
 If graph contains a cycle 
 if only one instance per resource type, then deadlock.
 if several instances per resource type, possibility of
deadlock.
Operating System Concepts
7.16
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
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.
Operating System Concepts
7.17
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005