12/04/2022, 09:25 Exam/Deadlock – COMP3231/COMP9201/COMP3891/COMP9283
1. Deadlock
1. What is deadlock? What is starvation? How do
they differ from each other?
Copyright By PowCoder代写 加微信 powcoder
2. What are the four conditions required for
deadlock to occur?
3. Describe four general strategies for dealing with
deadlocks.
4. For single unit resources, we can model resource
allocation and requests as a directed graph connecting processes and resources. Given such a graph, what is involved in deadlock detection.
5. Is the following system of four processes with 2 resources deadlocked?
6. Assuming the operating system detects the system is deadlocked, what can the operating system do to recover from deadlock?
7. What must the banker’s algorithm know, in order to prevent deadlock?
8. Describe the general strategy behind deadlock prevention, and give an example of a practical deadlock prevention method.
What is deadlock? What is starvation? How do they differ from each other?
Deadlock is the state of a set of threads where all threads in the set are blocked waiting for another thread in the set to release a resource, and a required resource can only be released by a thread in the blocked set. The set remains blocked forever.
Example with a set size of 2 {1,2}: Thread 1 needs the resource A and B to proceed, it holds A. Thread 2 needs resource A and B to proceed, it holds B. Both are blocking on the resource they need and cannot release what they are holding.
Starvation is the phenomenon where the allocation of resources is ‘unfair’, and a process never gets the resources it requests because when the resources are available, they always granted to something else.
For example, a scheduler that always runs the shortest task next may never schedule a task that takes a long time.
In deadlock, processes halt because they cannot proceed and the resources are never released. In starvation, the system overall makes progress using (and reusing) the resources, but particular processes consistently miss out on being granted their resource request.
What are the four conditions required for deadlock to occur?
1. Mutual exclusion: Only one thread can use a resource at a time
2. Hold and wait: A resource can be held, then blocking whilst waiting for more resources 3. No preemption: Resources cannot be forcibly taken away from process holding it
https://wiki.cse.unsw.edu.au/cs3231cgi/Exam/Deadlock
12/04/2022, 09:25 Exam/Deadlock – COMP3231/COMP9201/COMP3891/COMP9283
4. Circular wait: A circular chain of 2 or more processes, each of which are waiting for a resource held by the next member in the chain.
Describe four general strategies for dealing with deadlocks.
1. Ignore it Easy
Especially if the other strategies are very costly, and deadlock is rare
2. Detect and recover
Can cause livelock Detection:
Search for directed cycles in a dependency graph (only possible if there is one copy of each resource)
Use an existence/available/allocation/request matrix
Preemption: steal the resource from another process. Negates preemption condition.
Rollback: periodically save checkpoints and restart at a checkpoint when deadlocked.
Kill a process: essentially steals resources from one process. Need to choose a process that can be safely restarted. Negates preemption condition.
3. Deadlock avoidance: check if a resource allocation will cause deadlock before allocating the resource.
Only allow progression of programs into ‘safe states’, where there is at least one way to complete all processes.
Impractical because we need to know the maximum amount of each resource a process can request before allocating any resources.
4. Deadlock prevention: negate one of the 4 requirements of deadlock.
Negate no preemption: steal resources from other processes. Impractical. Negate mutual exclusion: allow more than one process to hold one resource. Impractical.
Negate hold and wait: threads drop any resources they hold if they cannot get all of the resources they require for progress. This can cause livelock.
Negate circular wait: all processes acquire resources in the same order. Most practical alternative.
For single unit resources, we can model resource allocation and requests as a directed graph connecting processes and resources. Given such a graph, what is involved in deadlock detection.
Deadlock detection can be done by finding directed cycles in the graph.
Is the following system of four processes with 2 resources deadlocked?
Current allocation matrix
https://wiki.cse.unsw.edu.au/cs3231cgi/Exam/Deadlock
12/04/2022, 09:25 Exam/Deadlock – COMP3231/COMP9201/COMP3891/COMP9283
Current request matrix
Availability Vector 1 4
Give 1 2 to P1: Current allocation matrix
Current request matrix
Availability 0 2
P1 finishes, releases 2 5. Current allocation matrix
Current request matrix
Availability 2 7
Give 1 7 to P3: Current allocation matrix
Current request matrix
Availability 1 0
P3 finishes, releases 2 9: Current allocation matrix
P2 4 1 P4 2 0
https://wiki.cse.unsw.edu.au/cs3231cgi/Exam/Deadlock
12/04/2022, 09:25 Exam/Deadlock – COMP3231/COMP9201/COMP3891/COMP9283
Current request matrix
P2 4 3 P4 5 1
Availability 3 9
Now there is no possible request that can be fulfilled, so it is deadlocked.
If the availability vector is as below, is the system above still deadlocked? 2 3 Scenario 2: Current allocation matrix
Current request matrix
Availability Vector 2 3
Give 1 2 to P1: Current allocation matrix
Current request matrix
Availability Vector 1 1
P1 finishes, releases 2 5: Current allocation matrix
Current request matrix
Availability Vector 3 6
Now there is nothing satisfyable. Deadlocked
https://wiki.cse.unsw.edu.au/cs3231cgi/Exam/Deadlock
12/04/2022, 09:25 Exam/Deadlock – COMP3231/COMP9201/COMP3891/COMP9283
Scenario 3: Is the system deadlocked if the availability is 2 4 Current allocation matrix
Current request matrix
Availability Vector 2 4
Give 1 2 to P1 Current allocation matrix
Current request matrix
Availability Vector 1 2
P1 ends, releasing 2 5 Current allocation matrix
Current request matrix
Availability Vector 3 7
Run P3 (releases 1 2): Current allocation matrix
Current request matrix
P2 4 1 P4 2 0
P2 4 3 P4 5 1
https://wiki.cse.unsw.edu.au/cs3231cgi/Exam/Deadlock
12/04/2022, 09:25 Exam/Deadlock – COMP3231/COMP9201/COMP3891/COMP9283
Availability Vector 4 9
Run P2 (releases 4 1): Current allocation matrix
Current request matrix
Availability Vector 8 10
Then P4 can run. System isn’t deadlocked. General approach:
a) look for a process whose requests <= the availability. We know we can then satisfy the requirements for this process, so we assume it gets its resources required and terminates. Thus, we can
b) release all resources *currently allocated* to that process, and add then to the pool.
c) repeat for all processes. If you eventually reach a point where you cannot do this, and there are still processes remaining, the system is deadlocked. If you release them all, you are safe.
Assuming the operating system detects the system is deadlocked, what can the operating system do to recover from deadlock?
Preemption: steal the resource from another process. Negates preemption condition. Rollback: periodically save checkpoints and restart at a checkpoint when deadlocked. Kill a process: essentially steals resources from one process. Need to choose a process that can be safely restarted. Negates preemption condition.
What must the banker's algorithm know, in order to prevent deadlock?
The bankers algorithm must know the maximum resource requirements of all processes.
We assume that the banker can keep track of resource availability and usage, and the process that receives their requested resources will eventually finish and release them.
Describe the general strategy behind deadlock prevention, and give an example of a practical deadlock prevention method.
Deadlock prevention is removing the possibility of deadlock by negating one of the 4 conditions of deadlock. For example, you can negate circular wait by ensuring all processes acquire resources in the same order.
Note: avoiding deadlock via careful allocation (e.g. banker's algorithm) is avoidance, not prevention.
https://wiki.cse.unsw.edu.au/cs3231cgi/Exam/Deadlock
12/04/2022, 09:25 Exam/Deadlock - COMP3231/COMP9201/COMP3891/COMP9283
Exam/Deadlock (last edited 2019-05-11 17:25:26 by LauraChambers)
https://wiki.cse.unsw.edu.au/cs3231cgi/Exam/Deadlock
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com