Operating Systems Lecture 6a
Dr Ronald Grau School of Engineering and Informatics Spring term 2018
Previously 1 Process Synchronisation
Critical Section problem
Synchronisation primitives:
Mutex, Semaphore, Monitor, Condition Variable, . . . Transactional Memory
Message Passing
Recap: Synchronisation primitives 2 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.
Today 3 Deadlocks
Deadlock conditions
Methods of handling deadlocks
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?
No, it is always necessary to prevent race conditions
General precautions:
Make any data resources read-only where there is no need for modification Acquire only those resources that are really needed
Deadlock Prevention – H&W and NP 10 Hold-and-wait
Acquire all resources at once, i.e. block until all resources are available
+ Process can execute once all required resources are held – Long delays
– Bad resource utilisation
– Advance knowledge needed about the resources required
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
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 )
Yes
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
However, there can be inefficiencies if ordering is poorly chosen
Does this prevent deadlocks?
Assuming circular wait condition holds: Each process Pi of processes P0 ... Pn-1
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
Available
R0
R1
R2
3
3
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
Allocation
R0
R1
R2
P0
0
1
0
P1
2
0
0
P2
3
0
2
P3
2
1
1
P4
0
0
2
Banker's Algorithm
17
An algorithm for avoiding deadlocks
Need[i][j] = Maximum[i][j] - Allocation[i][j]
Need
R0
R1
R2
P0
7
4
3
P1
1
2
2
P2
6
0
0
P3
0
1
1
P4
4
3
1
Maximum
R0
R1
R2
P0
7
5
3
P1
3
2
2
P2
9
0
2
P3
2
2
2
P4
4
3
3
Allocation
R0
R1
R2
P0
0
1
0
P1
2
0
0
P2
3
0
2
P3
2
1
1
P4
0
0
2
=
-
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 ifforalli: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
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
Assume request (1 0 2) by P1
Banker's Algorithm – Checking requests 30
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
Assume request (1 0 2) by P1
Request can be served
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
Banker's Algorithm – Checking requests 31
Allocation
R0
R1
R2
P0
0
1
0
P1
3
0
2
P2
3
0
2
P3
2
1
1
P4
0
0
2
Available
R0
R1
R2
2
3
0
Need
R0
R1
R2
P0
7
4
3
P1
0
2
0
P2
6
0
0
P3
0
1
1
P4
4
3
1
Assume request (3 3 0) by P4
Request cannot be granted (insufficient resources)
Assume request (0 2 0) by P0
Request cannot be granted (would result in unsafe state)
Summary 32 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)
Read 33 Tanenbaum & Bos., Modern Operating Systems
Chapter 6
Silberschatz et al., Operating System Concepts Chapter 7
Next Lecture
34
Introduction
Operating System Architectures Processes
Threads - Programming
Process Scheduling - Evaluation Process Synchronisation
Deadlocks (continued) Memory Management File Systems
Input / Output
Security and Virtualisation