CS 414 Fall 1999: Homework 3

Due in Class Thursday, October 7.

1. A system contains three processes, P₁, P₂, and P₃ and three categories of resources R₁, R₂, and R₃. There are 3 units available for each of the resources. Give values for Max[i,j] and a sequence of requests (e.g. “Process P₁ requests 2 units of R₃”) such that a priority-ordered resource allocation algorithm would grant all the requests immediately, but a Banker’s algorithm would require at least one request to wait.

Notes: The value of Max[i,j] is needed for the Banker’s algorithm, not the priority-ordered resource algorithm. For the priority ordered algorithm, assume that the priority order is just the index order: R₁ < R₂ < R₃ where < denotes “must be requested before”.

2. On homework 2, problem 4, we developed a semaphore-based solution to the unisex bathroom problem. Develop a monitor solution to the same problem, but with one additional restriction: now the bathroom only has room for 3 people at a time (who should all be of the same sex). Here are the rules to implement:

a) Only one sex at a time

b) No more than 3 people at a time

c) M men and W women, M>0 and W>0, N=M+W processes in all.

d) If men are inside and women are waiting, women get in next (a maximum of 3)

e) If women are inside and men are waiting, men get in next (a maximum of 3)

f) Within the group of men, once men are next allowed in, the man waiting longest is the next one in, and similarly for the women.

3. Consider the Banker’s deadlock avoidance algorithm.

a) Can a situation arise where once process P_i receives even a single unit of a single resources, the banker won’t allow process P_j to run (won’t grant a single request by P_j) until process P_i has terminated? Explain, illustrating with an example if your answer is “yes”, or giving a proof if your answer is “no”.

b) Suppose that the Banker’s algorithm is evaluating requests for resources by all five processes in a system, and that it decides to grant a request for k units of R_x by process P₃. When testing for safety, suppose it sets Finished[i] to “true” in this order: P₃, P₂, P₁, P₄, P₅. Under what conditions does this mean that P₃ will actually finish execution and terminate before P₅ is able to finish executing?

Express your answer “mathematically” as a formula over the variables used by the algorithm: Max[i,j], Avail[j], Need[i,j], Alloc[i,j].

Note: In class we didn’t need a way to express pending requests but if you need to do so for this problem, say that Req[i] = (x,k) means that process P_i requests k units of resource R_x, denoted Req[i].res and Req[i].units.