Homework 3
cs550 Operating Systems
5 points
Due Monday, Oct. 20, 2014 at midnight

1. (3 points) Draw a resource allocation graph for the following situations and determine if deadlock exists or not.  Justify your answer using the principles of deadlock.  You may assume that processes will not relinquish their hold on resources until they receive all the resources they have requested.  You may also assume that processes will not be interrupted to release their resources and that multiple processes may not utilize the same resource at the same time.

a) The dining philosophers problem using three philosophers and three chopsticks.

b) There are 4 processes, W, X, Y, and Z. 

There are 3 resources of type I.
There are 2 resources of type II.
There is one resource of type III.
There are 2 resources of type IV.

Process W owns one resource of type I and requests one resource of type II.
Process X owns one resource of type II and requests one resource of type I.
Process Y owns one resource each of type I and III and requests one of type IV.
Process Z owns one resource each of type II and IV and requests one of type III.

c) There are 5 processes, A, B, C, D, and E. 

There are 2 resources of type CPU.
There are 3 resources of type I/O.
There are 4 resources of type Memory.
There are 2 resources of type Network.

Process A owns one resource of type CPU and requests one resource of type I/O.
Process B owns one resource of type I/O and requests one resource of type Memory.
Process C owns one resource each of type CPU and I/O and requests one of type CPU.
Process D owns one resource each of type Memory and Network and requests one of type Memory.
Process E owns one resource each of type I/O and Network and requests one of type Memory.

2. (2 points) Using the banker's algorithm, determine if a safe state can be achieved. Assume each process can complete its work once it receives its maximum claim.

a) (0.5 points) There are four resource types with the total number of system resources expressed as the tuple (2, 3, 2, 1).  There are three processes with current allocations of (0, 1, 0, 1), (1, 1, 0, 0), and (0, 0, 1, 0).  The maximum claim of each process is (2, 1, 0, 1), (1, 3, 0, 0), and (1, 3, 2, 1). 

b) (0.5 points)There are three resource types with the total number of system resources expressed as the tuple (3, 2, 2).  There are three processes with current allocations of (0, 0, 0), (1, 1, 1), and (2, 0, 1).  The maximum claim of each process is (2, 0, 1), (3, 2, 1), and (3, 0, 2).

c) (1 point) There are four resource types with the total number of system resources expressed as the tuple (5, 4, 7, 2).  There are four processes with current allocations of (1, 2, 0, 1), (1, 1, 4, 0), (1, 1, 0, 1), and (0, 0, 2, 0).  The maximum claim of each process is (2, 2, 2, 2), (2, 3, 4, 1), (1, 3, 0, 1), and (1, 3, 2, 1).