Operating Systems Lecture 6a
Operating Systems
Lecture 6a
Dr Ronald Grau School of Engineering and Informatics Spring term 2018
Previously
Process Synchronisation
Critical Section problem
Synchronisation primitives:
Mutex, Semaphore, Monitor, Condition Variable, . . .
Transactional Memory
Message Passing
1
Recap: Synchronisation primitives
Which synchronisation primitive would you use?
1. Public transport rules
No more than the max. amount of people allowed enter a bus.
2. Commissioning warehouse
Always put the same number of items in every box.
3. Paying the parking fine
Customers get served individually in the order of their arrival.
4. Occupied!
Only a single person can enter the bathroom at a time.
5. Taking everyone onboard
A ship will only depart once all crew are back from land leave.
6. Putting the cart before the horse
Before you can peel an egg you need to boil it first.
2
Today
Deadlocks
Deadlock conditions
Methods of handling deadlocks
3
Recap: Resources 4
Related operations
Request: The process requests the resource. If the request cannot be granted
immediately (for example, if the resource is being used by another process), then
the requesting process must wait until it can acquire the resource.
Use: The process can operate on the resource (for example, if the resource is a
printer, the process can print on the printer).
Release: The process releases the resource.
Synchronisation and Priority Scheduling 5
Scenario
Low-priority process L acquires resource R
L is preempted by long-running medium-priority process M
High-priority process H wants to acquire R, but is blocked
H has to wait until M finishes before L can release R
Problem: Priority inversion
Higher priority process has to wait
because lower priority process holds
the resource it wants to access
Solution: Priority inheritance protocol
Temporarily raise the priority of L to the
maximum priority of all processes
accessing the same resource
Avoids priority inversion
Dining Philosophers Problem (Dijkstra 1965) 6
Rules
The philosophers can either think or eat
Each philosopher needs two chopsticks to eat
They can pick up chopsticks from the left and
the right as they become available
How can we make sure they keep thinking
and eating in turn, and no-one starves?
Deadlocks 7
A set of processes is deadlocked if each process in the set is waiting for
an event that only another process in the set can cause.
Necessary and sufficient conditions:
Mutual exclusion: Each resource is either currently assigned to exactly one process
or is available.
Hold-and-wait: Processes currently holding resources that were granted earlier can
request new resources.
No-preemption: Resources previously granted cannot be forcibly taken away from
a process. They must be explicitly released by the process holding them.
Circular wait: There must be a circular list of two or more processes, each of which is
waiting for a resource held by the next member of the chain.
How do deal with deadlocks? 8
Unfortunately, there is no general solution.
Deadlock prevention:
Design the system so that at least one of the four conditions never arises.
Deadlock avoidance:
Do not approve resource requests that might lead to a deadlock (Safety).
Deadlock detection:
Always approve resource requests if resources are available.
Periodically check whether there is a deadlock.
If there is a deadlock, perform deadlock recovery.
Deadlock Prevention – Mutual Exclusion 9
System designed such that one of the four conditions never occurs
Can we build a system with shared resource access
not requiring mutual exclusion?
General precautions:
Make any data resources read-only where there is no need for modification
Acquire only those resources that are really needed
No, it is always necessary to prevent race conditions
Deadlock Prevention – H&W and NP 10
Hold-and-wait
Acquire all resources at once, i.e. block until all resources are available
No-preemption
(a) Process releases resources when it fails to acquire a resource, and re-tries later
(b) Resource request forces another process to release a resource
+ Process can execute once all required resources are held
– Long delays
– Bad resource utilisation
– Advance knowledge needed about the resources required
Only possible if the state of the resource can be saved and restored
Deadlock Prevention – Circular wait 11
Enforce linear ordering of requests to resource types Ri
e.g. O(disk drive) = 5, O(printer) = 12
Process has to acquire all resources of type Ri at once
After having acquired Ri it can only request resources of type Rj where O( Rj ) > O( Ri )
Does this prevent deadlocks?
Assuming circular wait condition holds: Each process Pi of processes P0 … Pn-1
waits for resource Ri held by process R(i+1)mod n
Our ordering ensures that for each i we have O( Ri ) < O(R(i+1)mod n)
This would mean O( R0 ) < ... < O( Rn-1 ) < O( R0 )
Impossible circular wait condition does not hold
Yes
However, there can be inefficiencies if ordering is poorly chosen
Deadlock Avoidance 12
Do not approve resource requests that might lead to a deadlock
When do we know that the system
is in a state that might lead to a deadlock?
Deadlock example with two processes:
P1 P2
… …
acquire B acquire A
… …
acquire A release A
… …
release B acquire B
… …
release A release B
… …
Resource Trajectories 13
Resource Trajectories 14
Safe and unsafe system states 15
Deadlock or unavoidable-deadlock state
The system is deadlocked or it will be
deadlocked on all trajectories.
Unreachable state
No trajectory can reach such a state,
e.g. because of mutual exclusion.
Safe state:
All possible trajectories starting in a safe state
are guaranteed to be deadlock-free
Unsafe state:
Existing trajectories starting in unsafe state
that lead to deadlock
Depends on scheduler
Banker's Algorithm 16
An algorithm for avoiding deadlocks
There are Available[j] instances of each resource type Rj
Each process Pi declares the maximum of instances
Maximum[i][j] of each resource type Rj required
Allocation[i][j] is the number of instances of resource type Rj held by process Pi
Allocation
R0 R1 R2
P0 0 1 0
P1 2 0 0
P2 3 0 2
P3 2 1 1
P4 0 0 2
Maximum
R0 R1 R2
P0 7 5 3
P1 3 2 2
P2 9 0 2
P3 2 2 2
P4 4 3 3
Available
R0 R1 R2
3 3 2
Banker's Algorithm 17
An algorithm for avoiding deadlocks
Need[i][j] = Maximum[i][j] - Allocation[i][j]
Allocation
R0 R1 R2
P0 0 1 0
P1 2 0 0
P2 3 0 2
P3 2 1 1
P4 0 0 2
Maximum
R0 R1 R2
P0 7 5 3
P1 3 2 2
P2 9 0 2
P3 2 2 2
P4 4 3 3
Need
R0 R1 R2
P0 7 4 3
P1 1 2 2
P2 6 0 0
P3 0 1 1
P4 4 3 1
= -
Banker's Algorithm – Checking Safety 18
1. Work := Available
Finish[i] := false for i = 0 … n-1
2. Find an index i such that Finish[i] = false ^ Need[i] <= Work
If no such i exists, go to step 4.
3. Work := Work + Allocation[i]
Finish[i] := true
Go to step 2.
4. If Finish[i] = true for all i , then the system is in a safe state.
Component-wise ordering on vectors:
X <= Y if for all i : X[i] <= Y[i]
Banker's Algorithm 19
Allocation
R0 R1 R2
P0 0 1 0
P1 2 0 0
P2 3 0 2
P3 2 1 1
P4 0 0 2
Need
R0 R1 R2
P0 7 4 3
P1 1 2 2
P2 6 0 0
P3 0 1 1
P4 4 3 1
Work
R0 R1 R2
3 3 2
Finish
P0 false
P1 false
P2 false
P3 false
P4 false
Is there are process that can finish with the resources available (Work)?
Banker's Algorithm 20
Allocation
R0 R1 R2
P0 0 1 0
P1 2 0 0
P2 3 0 2
P3 2 1 1
P4 0 0 2
Need
R0 R1 R2
P0 7 4 3
P1 1 2 2
P2 6 0 0
P3 0 1 1
P4 4 3 1
Work
R0 R1 R2
3 3 2
Finish
P0 false
P1 false
P2 false
P3 false
P4 false
Yes, P1
Banker's Algorithm 21
Allocation
R0 R1 R2
P0 0 1 0
P1 0 0 0
P2 3 0 2
P3 2 1 1
P4 0 0 2
Need
R0 R1 R2
P0 7 4 3
P1 0 0 0
P2 6 0 0
P3 0 1 1
P4 4 3 1
Work
R0 R1 R2
5 3 2
Finish
P0 false
P1 true
P2 false
P3 false
P4 false
Finish the process and then release all resources previously allocated to P1 , i.e.
add previous allocation (2,0,0) to Work and set Finish = true
Banker's Algorithm 22
Allocation
R0 R1 R2
P0 0 1 0
P1 0 0 0
P2 3 0 2
P3 2 1 1
P4 0 0 2
Need
R0 R1 R2
P0 7 4 3
P1 0 0 0
P2 6 0 0
P3 0 1 1
P4 4 3 1
Work
R0 R1 R2
5 3 2
Finish
P0 false
P1 true
P2 false
P3 false
P4 false
Banker's Algorithm 23
Allocation
R0 R1 R2
P0 0 1 0
P1 0 0 0
P2 3 0 2
P3 0 0 0
P4 0 0 2
Need
R0 R1 R2
P0 7 4 3
P1 0 0 0
P2 6 0 0
P3 0 0 0
P4 4 3 1
Work
R0 R1 R2
7 4 3
Finish
P0 false
P1 true
P2 false
P3 true
P4 false
Banker's Algorithm 24
Allocation
R0 R1 R2
P0 0 1 0
P1 0 0 0
P2 3 0 2
P3 0 0 0
P4 0 0 2
Need
R0 R1 R2
P0 7 4 3
P1 0 0 0
P2 6 0 0
P3 0 0 0
P4 4 3 1
Work
R0 R1 R2
7 4 3
Finish
P0 false
P1 true
P2 false
P3 true
P4 false
Banker's Algorithm 25
Allocation
R0 R1 R2
P0 0 0 0
P1 0 0 0
P2 3 0 2
P3 0 0 0
P4 0 0 2
Need
R0 R1 R2
P0 0 0 0
P1 0 0 0
P2 6 0 0
P3 0 0 0
P4 4 3 1
Work
R0 R1 R2
7 5 3
Finish
P0 true
P1 true
P2 false
P3 true
P4 false
Banker's Algorithm 26
Allocation
R0 R1 R2
P0 0 0 0
P1 0 0 0
P2 3 0 2
P3 0 0 0
P4 0 0 2
Need
R0 R1 R2
P0 0 0 0
P1 0 0 0
P2 6 0 0
P3 0 0 0
P4 4 3 1
Work
R0 R1 R2
7 5 3
Finish
P0 true
P1 true
P2 false
P3 true
P4 false
Banker's Algorithm 27
Safe!
Allocation
R0 R1 R2
P0 0 0 0
P1 0 0 0
P2 0 0 0
P3 0 0 0
P4 0 0 0
Need
R0 R1 R2
P0 0 0 0
P1 0 0 0
P2 0 0 0
P3 0 0 0
P4 0 0 0
Work
R0 R1 R2
10 5 7
Finish
P0 true
P1 true
P2 true
P3 true
P4 true
Banker's Algorithm – Checking requests 28
Request[i] for process Pi
1. If Request[i] <= Need[i], go to step 2.
Otherwise, error (maximum exceeded).
2. If Request[i] <= Available, go to step 3.
Otherwise, Pi must wait (resources not available).
3. Pretend to fulll request:
Available := Available - Request[i]
Allocation[i] := Allocation[i] + Request[i]
Need[i] := Need[i] - Request[i]
Approve request if resulting state is safe.
Otherwise, restore state and Pi has to wait.
Banker's Algorithm – Checking requests 29
Assume request (1 0 2) by P1
Allocation
R0 R1 R2
P0 0 1 0
P1 2 0 0
P2 3 0 2
P3 2 1 1
P4 0 0 2
Need
R0 R1 R2
P0 7 4 3
P1 1 2 2
P2 6 0 0
P3 0 1 1
P4 4 3 1
Available
R0 R1 R2
3 3 2
Banker's Algorithm – Checking requests 30
Assume request (1 0 2) by P1
Allocation
R0 R1 R2
P0 0 1 0
P1 2 0 0
P2 3 0 2
P3 2 1 1
P4 0 0 2
Need
R0 R1 R2
P0 7 4 3
P1 1 2 2
P2 6 0 0
P3 0 1 1
P4 4 3 1
Allocation
R0 R1 R2
P0 0 1 0
P1 3 0 2
P2 3 0 2
P3 2 1 1
P4 0 0 2
Need
R0 R1 R2
P0 7 4 3
P1 0 2 0
P2 6 0 0
P3 0 1 1
P4 4 3 1
Request can be served
Available
R0 R1 R2
2 3 0
Available
R0 R1 R2
3 3 2
Banker's Algorithm – Checking requests 31
Assume request (3 3 0) by P4
Assume request (0 2 0) by P0
Allocation
R0 R1 R2
P0 0 1 0
P1 3 0 2
P2 3 0 2
P3 2 1 1
P4 0 0 2
Need
R0 R1 R2
P0 7 4 3
P1 0 2 0
P2 6 0 0
P3 0 1 1
P4 4 3 1
Available
R0 R1 R2
2 3 0
Request cannot be granted (insufficient resources)
Request cannot be granted (would result in unsafe state)
Summary
Deadlocks
Deadlock conditions:
Mutual exclusion
Hold-and-wait
No preemption
Circular wait
Methods for handling deadlocks
Deadlock prevention
Deadlock avoidance
Deadlock detection and recovery (next lecture)
32
Read
Tanenbaum & Bos., Modern Operating Systems
Chapter 6
Silberschatz et al., Operating System Concepts
Chapter 7
33
Next Lecture
Introduction
Operating System Architectures
Processes
Threads - Programming
Process Scheduling - Evaluation
Process Synchronisation
34
Deadlocks (continued)
Memory Management
File Systems
Input / Output
Security and Virtualisation