Understanding Operating Systems Fifth Edition
Chapter 5 Process Management
Learning Objectives
Several causes of system deadlock The difference between preventing and avoiding deadlocks How to detect and recover from deadlocks The concept of process starvation and how to detect and recover from it The concept of a race and how to prevent it The difference between deadlock, starvation, and race
Understanding Operating Systems, Fifth Edition
Deadlock
Resource sharing
Memory management and processor sharing
Many programs competing for limited resources Lack of process synchronization consequences
Deadlock: deadly embrace
Two or more jobs placed in HOLD state Jobs waiting for unavailable vital resource System comes to standstill Resolved via external intervention
Starvation
Infinite postponement of job
Understanding Operating Systems, Fifth Edition 3
Deadlock (continued)
More serious than starvation Affects entire system
Affects more than one job
Not just a few programs
All system resources become unavailable
Example: traffic jam (Figure 5.1) More prevalent in interactive systems Real-time systems
Deadlocks quickly become critical situations
No simple and immediate solution
Understanding Operating Systems, Fifth Edition 4
Deadlock (continued)
Understanding Operating Systems, Fifth Edition
Seven Cases of Deadlock
Nonsharable/nonpreemptable resources
Allocated to jobs requiring same type of resources
Resource types locked by competing jobs
File requests Databases Dedicated device allocation Multiple device allocation Spooling Disk sharing Network
6
Understanding Operating Systems, Fifth Edition
Case 1: Deadlocks on File Requests
Jobs request and hold files for execution duration Example (Figure 5.2)
Two programs (P1, P2) and two files (F1, F2) Deadlock sequence
P1 has access to F1 and also requires F2 P2 has access to F2 and also requires F1
Deadlock remains
Until one program withdrawn or Until one program forcibly removed and file released
Other programs requiring F1 or F2
Put on hold for duration of situation
Understanding Operating Systems, Fifth Edition 7
Case 1: Deadlocks on File Requests (continued)
Understanding Operating Systems, Fifth Edition
Case 2: Deadlocks in Databases
Two processes access and lock database records Locking
Technique
One user locks out all other users Users working with database
Three locking levels
Entire database for duration of request Subsection of database Individual record until request completed
Understanding Operating Systems, Fifth Edition
Case 2: Deadlocks in Databases (continued)
Example: two processes (P1 and P2)
Each needs to update two records (R1 and R2) Deadlock sequence
P1 accesses R1 and locks it P2 accesses R2 and locks it P1 requests R2 but locked by P2 P2 requests R1 but locked by P1
Race between processes
Results when locking not used Causes incorrect final version of data Depends on process execution order
Understanding Operating Systems, Fifth Edition 10
Case 2: Deadlocks in Databases (continued)
Understanding Operating Systems, Fifth Edition
11
Case 3: Deadlocks in Dedicated Device Allocation
Limited number of dedicated devices Example
Two programs (P1, P2)
Need two tape drives each Only two tape drives in system
Deadlock sequence
P1 requests tape drive 1 and gets it P2 requests tape drive 2 and gets it P1 requests tape drive 2 but blocked P2 requests tape drive 1 but blocked
Understanding Operating Systems, Fifth Edition
12
Case 4: Deadlocks in Multiple Device Allocation
Several processes request and hold dedicated devices Example (Figure 5.4)
Three programs (P1, P2, P3) Three dedicated devices (tape drive, printer, plotter) Deadlock sequence
P1 requests and gets tape drive P2 requests and gets printer P3 requests and gets the plotter P1 requests printer but blocked P2 requests plotter but blocked P3 requests tape drive but blocked
13
Understanding Operating Systems, Fifth Edition
Case 4: Deadlocks in Multiple Device Allocation (continued)
Understanding Operating Systems, Fifth Edition
14
Case 5: Deadlocks in Spooling
Virtual device
Dedicated device made sharable Example
Printer: high-speed disk device between printer and CPU
Spooling
Process
Disk accepts output from several users Acts as temporary storage for output Output resides in disk area until printer accepts job data
Understanding Operating Systems, Fifth Edition 15
Case 5: Deadlocks in Spooling (continued)
Deadlock sequence
Printer needs all job output before printing begins
Spooling system fills disk space area No one job has entire print output in spool area Results in partially completed output for all jobs Results in deadlock
Understanding Operating Systems, Fifth Edition
16
Case 6: Deadlocks in a Network
No network protocols controlling network message flow Example (Figure 5.5)
Seven computers on network
Each on different nodes
Direction of arrows
Indicates message flow
Deadlock sequence
All available buffer space fills
Understanding Operating Systems, Fifth Edition
17
Case 6: Deadlocks in a Network (continued)
Understanding Operating Systems, Fifth Edition
18
Case 7: Deadlocks in Disk Sharing
Competing processes send conflicting commands
Scenario: disk access
Example (Figure 5.6)
Two processes Each process waiting for I/O request
One at cylinder 20 and one at cylinder 310
Deadlock sequence
Neither I/O request satisfied Device puts request on hold while attempting to fulfill other request for each request
Livelock results
Understanding Operating Systems, Fifth Edition 19
Case 7: Deadlocks in Disk Sharing (continued)
Understanding Operating Systems, Fifth Edition
20
Conditions for Deadlock
Four conditions simultaneously occurring prior to deadlock or livelock
Mutual exclusion Resource holding No preemption Circular wait
All needed by operating system
Must recognize simultaneous occurrence of four conditions
Resolving deadlock
Removal of one condition
Understanding Operating Systems, Fifth Edition 21
Conditions for Deadlock (continued)
Mutual exclusion
Allowing only one process access to dedicated resource
Resource holding
Holding resource and not releasing it Waiting for other job to retreat
No preemption
Lack of temporary reallocation of resources
Understanding Operating Systems, Fifth Edition
22
Conditions for Deadlock (continued)
Circular wait
Each process involved in impasse
Waiting voluntarily resource release by another so at least one can continue
All four required for deadlock occurrence Deadlock remains until one condition removed
Understanding Operating Systems, Fifth Edition
23
Modeling Deadlocks
Directed graphs
Circles represent processes Squares represent resources Solid arrow from resource to process
Process holding resource
Solid arrow from a process to resource
Process waiting for resource
Arrow direction indicates flow Cycle in graph
Deadlock involving processes and resources
Understanding Operating Systems, Fifth Edition 24
Modeling Deadlocks (continued)
Understanding Operating Systems, Fifth Edition
25
Modeling Deadlocks (continued)
Three graph scenarios to help detect deadlocks
System has three processes (P1, P2, P3) System has three resources (R1, R2, R3)
Scenario one: no deadlock
Resources released before next process request
Scenario two: deadlock
Processes waiting for resource held by another
Scenario three: no deadlock
Resources released before deadlock
Understanding Operating Systems, Fifth Edition
26
Modeling Deadlocks (continued)
No deadlock
Resources released before next process request
Understanding Operating Systems, Fifth Edition
27
Modeling Deadlocks (continued)
Understanding Operating Systems, Fifth Edition
28
Modeling Deadlocks (continued)
Deadlock
Processes waiting for resource held by another
Understanding Operating Systems, Fifth Edition
29
Modeling Deadlocks (continued)
Understanding Operating Systems, Fifth Edition
30
Modeling Deadlocks (continued)
No deadlock
Resources released before deadlock
Understanding Operating Systems, Fifth Edition
31
Modeling Deadlocks (continued)
Understanding Operating Systems, Fifth Edition
32
Modeling Deadlocks (continued)
Another example
Resources of same type Allocated individually or grouped in same process
Graph clusters devices into one entity
Allocated individually or grouped in different process
Graph clusters devices into one entity
Understanding Operating Systems, Fifth Edition
33
Modeling Deadlocks (continued)
Understanding Operating Systems, Fifth Edition
34
Strategies for Handling Deadlocks
Prevention
Prevent occurrence of one condition
Mutual exclusion, resource holding, no preemption, circular wait
Avoidance
Avoid deadlock if it becomes probable
Detection
Detect deadlock when it occurs Recover gracefully
Recovery
Resume system normalcy quickly and gracefully
Understanding Operating Systems, Fifth Edition 35
Strategies for Handling Deadlocks (continued)
Prevention eliminates one of four conditions
Complication: every resource cannot be eliminated from every condition Mutual exclusion
Some resources must allocate exclusively Bypassed if I/O device uses spooling
Resource holding
Bypassed if jobs request every necessary resource at creation time Multiprogramming degree significantly decreased Idle peripheral devices
Understanding Operating Systems, Fifth Edition 36
Strategies for Handling Deadlocks (continued)
Prevention (continued)
No preemption
Bypassed if operating system allowed to deallocate resources from jobs Okay if job state easily saved and restored Not accepted to preempt dedicated I/O device or files during modification
Circular wait
Bypassed if operating system prevents circle formation Use hierarchical ordering scheme Requires jobs to anticipate resource request order Difficult to satisfy all users
37
Understanding Operating Systems, Fifth Edition
Strategies for Handling Deadlocks (continued)
Avoidance: use if condition cannot be removed
System knows ahead of time
Sequence of requests associated with each active process
Dijkstras Bankers Algorithm
Regulates resources allocation to avoid deadlock
No customer granted loan exceeding banks total capital All customers given maximum credit limit No customer allowed to borrow over limit Sum of all loans will not exceed banks total capital
Understanding Operating Systems, Fifth Edition 38
Strategies for Handling Deadlocks (continued)
Understanding Operating Systems, Fifth Edition
39
Strategies for Handling Deadlocks (continued)
Understanding Operating Systems, Fifth Edition
40
Strategies for Handling Deadlocks (continued)
Understanding Operating Systems, Fifth Edition
41
Strategies for Handling Deadlocks (continued)
Understanding Operating Systems, Fifth Edition
42
Strategies for Handling Deadlocks (continued)
Operating systems deadlock avoidance assurances
Never satisfy request if job state moves from safe to unsafe
Identify job with smallest number of remaining resources Number of available resources => number needed for selected job to complete Block request jeopardizing safe state
Understanding Operating Systems, Fifth Edition
43
Strategies for Handling Deadlocks (continued)
Problems with the Bankers Algorithm
Jobs must state maximum number needed resources Requires constant number of total resources for each class Number of jobs must remain fixed Possible high overhead cost incurred Resources not well utilized
Algorithm assumes worst case
Scheduling suffers
Result of poor utilization Jobs kept waiting for resource allocation
Understanding Operating Systems, Fifth Edition 44
Strategies for Handling Deadlocks (continued)
Detection: build directed resource graphs
Look for cycles
Algorithm detecting circularity
Executed whenever appropriate
Detection algorithm
Remove process using current resource and not waiting for one Remove process waiting for one resource class
Not fully allocated
Go back to step 1
Repeat steps 1 and 2 until all connecting lines removed
Understanding Operating Systems, Fifth Edition 45
Strategies for Handling Deadlocks (continued)
Understanding Operating Systems, Fifth Edition
46
Strategies for Handling Deadlocks (continued)
Understanding Operating Systems, Fifth Edition
47
Strategies for Handling Deadlocks (continued)
Recovery
Deadlock untangled once detected System returns to normal quickly
All recovery methods have at least one victim Recovery methods
Terminate every job active in system
Restart jobs from beginning
Terminate only jobs involved in deadlock
Ask users to resubmit jobs
Identify jobs involved in deadlock
Terminate jobs one at a time
Understanding Operating Systems, Fifth Edition 48
Strategies for Handling Deadlocks (continued)
Recovery methods (continued)
Interrupt jobs with record (snapshot) of progress Select nondeadlocked job
Preempt its resources Allocate resources to deadlocked process
Stop new jobs from entering system
Allow nondeadlocked jobs to complete Releases resources when complete No victim
Understanding Operating Systems, Fifth Edition
49
Strategies for Handling Deadlocks (continued)
Factors to consider
Select victim with least-negative effect on the system Most common
Job priority under consideration: high-priority jobs usually untouched CPU time used by job: jobs close to completion usually left alone Number of other jobs affected if job selected as victim Jobs modifying data: usually not selected for termination (a database issue)
Understanding Operating Systems, Fifth Edition
50
Starvation
Job execution prevented
Waiting for resources that never become available Results from conservative resource allocation
Example
The dining philosophers by Dijkstra
Starvation avoidance
Implement algorithm tracking how long each job waiting for resources (aging) Block new jobs until starving jobs satisfied
Understanding Operating Systems, Fifth Edition
51
Starvation (continued)
Understanding Operating Systems, Fifth Edition
52
Starvation (continued)
Understanding Operating Systems, Fifth Edition
53
Summary
Operating system
Dynamically allocates resources Avoids deadlock and starvation
Four methods for dealing with deadlocks
Prevention, avoidance, detection, recovery
Prevention
Remove simultaneous occurrence of one or more conditions System will become deadlock-free Prevention algorithms
Complex algorithms and high execution overhead
Understanding Operating Systems, Fifth Edition 54
Summary (continued)
Avoid deadlocks
Clearly identify safe and unsafe states Keep reserve resources to guarantee job completion Disadvantage
System not fully utilized
No prevention support
System must detect and recover from deadlocks
Detection relies on selection of victim
Understanding Operating Systems, Fifth Edition
55
