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.

  1. Draw a graph wherein all the processes are involved in a single deadlock.
  2. Draw a graph wherein there are two separate sets of deadlocked processes.
  3. Draw a graph containing a cycle but no deadlock.
  4. Draw a graph containing three cycles but no deadlock.

The Banker's Algorithm (10 points)

Consider the following system resource snapshot.

Allocation
ABCD
P0 0012
P1 1000
P2 1354
P3 0632
P4 0014
Max
ABCD
P0 0012
P1 1750
P2 2356
P3 0652
P4 0656
Available
ABCD
1520
  1. What is the content of the Need matrix?
  2. Give an ordering of processes that demonstrates the system is in a safe state.
  3. 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
ABCD
P0 2114
P1 0000
P2 1012
P3 2120
P4 0200
Requested
ABCD
P0 1302
P1 3020
P2 2011
P3 0401
P4 0001
Available
ABCD
0202
  1. 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.
  2. 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.