Assignment: Deadlock
Table of Contents
Please upload your solutions to the following problems as a single PDF document to Blackboard. Reminder: I've noticed that some people have been using the digital dropbox on Blackboard for assignment submissions – please submit via the assignments section instead!
Resource Allocation Graphs (10 points)
Your solution to each of the following problems will consist of a resource allocation graph consisting of four processes and three resources, each of the latter containing 1 or more resource instances. Processes and resources can be connected with any (legitimate) combination of request or allocation edges. Not all processes and/or resources need to be connected to the graph.
Assume that requests for resource instances that are available are immediately allocated, so request edges will only appear in your diagram for resources that are currently unavailable. A single process cannot request more instances of a given resource than the total (allocated + free) count of that resource.
- Draw a graph wherein all the processes are involved in a single deadlock.
- Draw a graph wherein there are two separate sets of deadlocked processes.
- Draw a graph containing a cycle but no deadlock.
- Draw a graph containing three cycles but no deadlock.
The Banker's Algorithm (10 points)
Consider the following system resource snapshot.
| Allocation | ||||
| A | B | C | D | |
| P0 | 0 | 0 | 1 | 2 |
| P1 | 1 | 0 | 0 | 0 |
| P2 | 1 | 3 | 5 | 4 |
| P3 | 0 | 6 | 3 | 2 |
| P4 | 0 | 0 | 1 | 4 |
| Max | ||||
| A | B | C | D | |
| P0 | 0 | 0 | 1 | 2 |
| P1 | 1 | 7 | 5 | 0 |
| P2 | 2 | 3 | 5 | 6 |
| P3 | 0 | 6 | 5 | 2 |
| P4 | 0 | 6 | 5 | 6 |
| Available | |||
| A | B | C | D |
| 1 | 5 | 2 | 0 |
- What is the content of the Need matrix?
- Give an ordering of processes that demonstrates the system is in a safe state.
- If \(P_1\) were to submit the request vector <0,4,2,0>, should it be approved? Why or why not?
Deadlock Detection (10 points)
Consider the following system resource snapshot – this time without information on the maximum resource requirements of each process.
| Allocated | ||||
| A | B | C | D | |
| P0 | 2 | 1 | 1 | 4 |
| P1 | 0 | 0 | 0 | 0 |
| P2 | 1 | 0 | 1 | 2 |
| P3 | 2 | 1 | 2 | 0 |
| P4 | 0 | 2 | 0 | 0 |
| Requested | ||||
| A | B | C | D | |
| P0 | 1 | 3 | 0 | 2 |
| P1 | 3 | 0 | 2 | 0 |
| P2 | 2 | 0 | 1 | 1 |
| P3 | 0 | 4 | 0 | 1 |
| P4 | 0 | 0 | 0 | 1 |
| Available | |||
| A | B | C | D |
| 0 | 2 | 0 | 2 |
- Is the system currently deadlocked? If so, list the deadlocked processes. If not, list an order in which the processes might complete to avoid deadlock. Show your work.
- If the system were able to partially fulfill resource requests (e.g., one instance of resource 'D' could be allocated to \(P_2\), even if doing so would not fulfill its entire request vector), could you describe a sequence of allocations leading to deadlock? If so, list such a sequence.