Solutions and comments for Homework 3 (CS 414)

Exercise 1

The point of this problem is to recognize the difference between the techniques used to guarantee safety in the two algorithms. The priority-ordered algorithm guarantees safety by restricting the order in which resources may be requested. The banker's algorithm guarantees safety by only granting resource requests when the resulting resource allocation graph is reducible.

The simplest solution is to set all of the maximum values to 3 and let P1 and P2 each request one unit of any resources. The priority-ordered algorithm will grant both requests immediately because each process is requesting only one unit of one resource and 3 units are available. But the banker's algorithm will force P2 to wait, because if both requests were granted, the system would not be in a safe state; if both processes required their maximums to be able to finish, then neither process could finish.

Some students tried setting a maximum value above 3. This is illegal, since it would put the system in an unsafe state at the beginning and not grant any allocation requests.

Other students assumed that when a process i requests any units of resource j, the banker's algorithm actually allocates Max[i,j] units of the resource. This is incorrect. If Max=[3 3 3; 2 2 2; 1 1 1], P1 requests 1 unit of R1, and P2 requests 2 units of R2, the banker's algorithm *will* grant both requests immediately, since the resulting resource allocation graph is still reducible (with reduction sequence P2, P1, P3). But if instead P1 requests 2 units of R1 and P2 requests 1 unit of R2, the banker's algorithm will force P2 to wait; if it were granted, it's possible that neither P1 or P2 could complete without an additional R1 that wouldn't be available.

Exercise 2

Notes:

1. This solution has only one “signal” per function, so it is well defined for each of the 2 definitions in pg. 183.

2. Comments in the code are REQUIRED, especially since people are using variable names like a,b,n,m or similar; points are taken out if the code is not commented clearly.

type shower = monitor

const SHOWERSIZE : integer = 3; // number of showers in the room

var showeringMen, // number of men in the room

showeringWomen, // number of women in the room

waitingMen, // number of waiting men

waitingWomen : // number of waiting women

integer;

var queuMen, // male queue

queueWomen : // women queue

condition;

// note that waitingMen is the length of the queue associated with

// the condition variable queueMales

procedure entry maleIn()

begin

// wait if

if waitingWomen > 0 or // women are already waiting or

showeringWomen > 0 or // women are showering or

showeringMen = SHOWERSIZE // there is no room in the shower

begin

// increment the men waiting counter

waitingMen := waitingMen + 1;

// wait in the queue until signaled

queueMen.wait();

// decrement the men waiting counter

waitingMen := waitingMen - 1;

end;

// increment the showering men counter

showeringMen := showeringMen + 1;

// check if there is room, and let another man in

if showeringMen < SHOWERSIZE

queueMen.signal();

end;

procedure entry maleOut()

begin

// decrement the showering men counter

showeringMen := showeringMen - 1;

// check if there is any women in line waiting

if waitingWomen > 0

begin

// check if the shower is empty before letting women in

if showeringMen = 0

// let the next women in

// she will let others in if there is room

queueWomen.signal();

end;

// Since no women are waiting, let the next men in

else

// signal the waiting men queue

queueMen.signal();

end;

// Same procedures for women, but changing women for men

// in the variables names

// initialization

begin

// noone is taking a shower

showeringMen := 0;

showeringWomen := 0;

// noone is waiting

waitingMen := 0;

waitingWomen := 0;

end;

end;

Exercise 3

Part (a) of the problem was really easy and most of the people got it correct. The simplest solution that one could give is that there is only one resource R_x (with one instance only) and Max[i,x]=Max[j,x]=1. So Avail[x]=1 and if P_i request and gets R_x then it becomes Avail[x]=0 and therefore P_j will have to wait until P_i releases the resource.

Another solution that could be given is that we could have such a case because the safety property is violated. If we assume that we only have those two processes and that Max[i,x]=Max[j,x]=Avail[x]=k, then if i gets even 1 instance of R_x, then Avail[x]=k-1 and thus if j wants to get a single instance of resource x it will have to wait, because if that request were granted then safety would be violated (Avail[x]=k-2 and Max[i,x]=Max[j,x]=k-1 so there wouldn’t potentially be enough resources for any of the two processes to finish).

Part (b) on the other hand was much more difficult. What was being asked was for people to try and give a set of formulas (with a small explanation) that would ensure that P₃ runs and terminates before P₅ can do the same, or alternatively to explain formally under what the conditions that event is guaranteed. A substantial percentage of the homeworks turned in had formulas that did not really guarantee this event (e.g. that Avail<Need₅) or they were giving formulas for other events, events that were not asked for by the question (e.g. that Need₃£Avail since P₃ can definitely run with the number of resources available). Most of the homeworks had answers that were covering only a specific case (e.g. that if Max[5,x]>Avail[x]+Alloc[1,x] +Alloc[2,x] +Alloc[4,x] then even if all other processes 1, 2 and 4 can finish then the resources held by 3 are still needed for 5 to run). These were essentially correct, but they were only covering only one or a few of the possible cases under which P₅ waits for P₃, so for answers like that only partial credit was given (the credit was proportional to the number of cases covered and of course was the same for similar answers!).

One way in which it was possible to give an answer (and that was the way people who got 5/5 answered the question) is to consider that the actual requests by the most processes are close to their respective “Need”s. That of course restricts our cases slightly (but since there were no better answers given that translated to full credit). Let’s consider the following cases to be more general: (by Req[i,x] I denote the total request made for resource x by process i – if you want you can change this to Need[i,x] but this is going to restrict the solution)

1. P5 waits for some resource directly from P3 (that is to say 1,2 and 4 can potentially run immediately):

$x such that Req[5,x]>Avail[x]+Sum[i=1,2,4](Alloc[i,x])

or that

if Req[5,x]£Avail[x]+Sum[i=1,2,4](Alloc[i,x]) then Need[5,x]>Avail[x]+Sum[i=1,2,4](Alloc[i,x])

and Need[3,x]>Avail[x]+Sum[i=1,2,4](Alloc[i,x])-Req[5,x]

This means that that either there are not enough resources for P5’s request to be granted or if there are then it is unsafe to do so, because neither P3 or P5 could finish safely in that case!

NOTE: I’m not going to give those equations again in the next cases but assume that similar equations do exist.

2. P5 waits for some resource from process Pa (aÎ{1,2,4}) and Pa waits for some resource from P3 (that is to say 1,2 and 4 except Pa can run potentially immediately):

$y such that Req[5,y]>Avail[y]+Sum[i=1,2,4;i¹a](Alloc[i,y])

and

$x such that Req[a,x]>Avail[x]+Sum[i=1,2,4;i¹a](Alloc[i,x])

3. P5 waits for some resource from process Pa (aÎ{1,2,4}) and Pa waits for some resource from process Pb (bÎ{1,2,4}-{a}) and Pb waits for some resource from P3 (that is to say only one of 1,2 and 4 - the one which is not a or b - can potentially run immediately):

$z such that Req[5,z]>Avail[z]+Sum[i=1,2,4;i¹a,b](Alloc[i,z])

and

$y such that Req[a,y]>Avail[y]+Sum[i=1,2,4;i¹a,b](Alloc[i,y])

and

$x such that Req[b,x]>Avail[x]+Sum[i=1,2,4;i¹a,b](Alloc[i,x])

4. P5 waits for some resource from process Pa (aÎ{1,2,4}) and Pa waits for some resource from process Pb (bÎ{1,2,4}-{a}) and Pb waits for some resource from process Pc (c={1,2,4}-{a,b}) and Pc for some resource from P3 (so all processes except 3 have to wait):

$x,y,z,w such that

Req[5,w]>Avail[w] and Req[a,z]>Avail[z] and Req[b,y]>Avail[y] and Req[c,x]>Avail[x]

So the idea that we need to bear in mind here is that, if a request is small enough, maybe by granting it we will be still in a safe state. Also that in order to cover all the cases we need to consider what can happen if other processes finish up and free up more resources that they were holding; so either we need to make sure that they don’t finish up or that we take into account the resources that they free.

Most students ended up getting either 2 or 3 points for this problem with few getting 0 and even fewer getting 4 or 5 points.