CS414 Prelim 1.  10:15 to 11:25. 

Four problems, 25 points each.  Closed book.

 

Your name: ___________________Your ID : _______________________

 

 

1. Any Ithaca driver soon becomes familiar with our one-lane bridges.  When cars want to cross in both directions, people take turns.  All the cars going one way cross, than all the ones going the other way, and so forth.  Ithaca being a small city, we never have an “infinite” supply of cars, so this works.

One lane bridges have a weight limit.  The bridge can only hold 2 cars at one time.

Assume that cars are processes.  Modify the readers and writers monitor (code is given below to remind you how it looks) into a new monitor with four methods, “go_north_wait,” “go_north_done,” “go_south_wait”, and  “go_south_done.”  A car going north calls go_north_wait when it gets to the bridge, then crosses, then calls “go_north_done”, and similarly for a car heading south.

 

    int rcnt = 0, rwaiting = 0, wcnt = 0, wwaiting = 0;
    condition wantread, wantwrite;

public StartRead()     {         if(wcnt > 0 || wwaiting > 0)         {              ++rwaiting;              wantread.wait();              --rwaiting;         }         rcnt++;         wantread.signal();     }	public StartWrite()     {           if(wcnt == 1 || rcnt > 0)         {               ++ wwaiting;               wantwrite.wait();               --wwaiting;         }         wcnt = 1;     }
public EndRead() {         if(--rcnt == 0)                wantwrite.signal();     }	public EndWrite()     {         wcnt = 0;         if(rwaiting > 0)              wantread.signal();         else              wantwrite.signal();     }

 

 

 

 

 

int scount=0, ncount=0, nwaiting=0, swaiting=0;

condition wantsouth, wantnorth;

public go_north_wait()     {         if((scount > 0)||(ncount==2))         {              ++nwaiting;              wantnorth.wait();              --nwaiting;         }         ncount++;         if(ncount < 2) wantnorth.signal();     }	public go_south_wait()    {         if((ncount > 0)||(scount==2))         {              ++swaiting;              wantsouth.wait();              --swaiting;         }         scount++;         if(scount < 2) wantsouth.signal();     }
public go_north_done()     {         ncount--;         if (nwaiting > 0)             wantnorth.signal();         else if(ncount == 0){             wantsouth.signal();     }	public go_south_done()     {         scount--;         if (swaiting > 0)             wantsouth.signal();         else if(scount == 0){             wantnorth.signal();     }

 

 

 

 

 

 

 

 

 

 

 

 

2.   Below is the Bakery algorithm, using the same code and notation we employed in class.  Recall that (a,x)<(b,y) means “(a < b) or (a=b and x<y)”.   Assume that N=6

 

#define      true                 1

#define      false                0

int number[N], choosing[N];  /* Initially number[i] = 0, choosing[i] = false */

     

Process P_i:

      while (1) {

                      do something else

choosing[i] = true;

number[i] = max(number[0]…number[N-1])+1;

choosing[i] = false;

for(k = 0; k < N; ++k) {

while(choosing[k] ) loop;

while((number[k]!=0)&&((number[k],k) < (number[i],i))) loop;

}

 

Critical Section for Process i

number[i] := 0;

 

}

 

 

Suppose that

a)      process 0 is in the “do something else” code

b)      process 2 enters the critical section, with number[2] = 5

c)      processes 1, 3, 4 and 5 could be anywhere that this code will allow.

 

Now suppose that process 0 finishes the “do something else code” while process 2 is still in the critical section.  The next line that process 0 will execute is “choosing[0] = true;” 

 

Which of the following are possibilities?  Explain, by reference to the code, why each can or cannot occur, explaining the conditions that can cause the scenario to arise, or explaining why no possible execution sequence can cause this to happen.   Don’t worry about numbers overflowing, but do consider possible actions by other processes.

 

Note: You only need to describe one scenario in which the condition described can occur.  Even if there are many other scenarios in which it would not occur, we aren’t concerned about that.  That is, when we say “can” occur, can means that the possibility exists, not that this outcome is certain!  Also, remember that even a very mean, nasty scheduler must still provide certain guarantees.  Your answer can specify a weird scheduling order, such as “only run process 3 during periods when process 2 is choosing a number”, but not schedules that break the rules, like “Wait until process 4 has set choosing[4] to true, but then make it stop and never, ever, run process 4 again.”

 

a)      Process 2 has not yet left the critical section, yet process 0 doesn’t wait when it executes the while loop “while((number[2],2) < (number[0],0)) loop”

 

No, this cannot happen.  If Process 2 is still in the critical section, number[2] = 5.  When Process 0 chooses its number, number[0] must be >= 6.  Thus it will wait in the while loop until Process 2 exits the critical section, setting number[2] to 0.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

b)      Process 2 is able to leave and re-enter the critical section before Process 0 is able to enter it even once.

 

Yes, this is possible.  Consider the case in which Process 0 is switched out by the OS before choosing its number.  Then if Process 2 is run until it picks a number, before Process 0 has a chance to run again, Process 2 will have a lower number and thus re-enter the critical section before Process 0 is able to enter it.

 

 

 

 

 

 

 

 

 

 

 

 

c)      Process 1 enters the critical section before process 0 enters it even once. 

 

Yes, this is possible.  Suppose Process 1 has already picked a number when Process 0 picks.  Then Process 1 will enter while Process 0 loops on

                        while((number[1], 1) < (number[0],0))

 

 

 

 

 

 

 

 

 

 

 

d)      When process 0 enters the critical section, it prints number[0].  The value is 1.

 

Yes, this is possible.  Suppose all other processes exit the critical section, setting number[p]=0 before Process 0 has a chance to pick a number.  Then when Process 0 picks, it will get

            number[0] = max(0,0,0…,0)+1;

            Thus number[0]==1 when Process 0 prints in its critical section.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

e)      Process 0 never enters the critical section, although other processes continue to do so.

 

No, this is not possible.  Suppose Process 0 picks number[0]= k.  It then proceeds to wait on each of the other processes.  Eventually each process will choose a number.  So Process 0 will eventually get through

            while(choosing[k])loop;  for each of the other processes.

Then, after each process exits its critical section once (after Process 0 has picked its number), it could try to reenter but would then pick a number k’>k.  Thus Process 0 will no longer wait on

while((number[k]!=0)&&((number[k],k) < (number[i],i))) loop;

for each process.  Process 0 will then be able to enter the critical section.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3.   You are developing a new computer game called “multiplayer scavenger hunt”.  A scavenger hunt is a kind of race to be the first to discover a treasure.  The players are given clues which are puzzles.  When you solve a clue (a puzzle), it tells you where to look for the next clue, and this continues until you get to the final location.

 

The game will maintain an elaborate map of Gotham City, and clues will lead to various places, such as the broom-closet in the editor’s office of the Daily News.  A place may have just one way in and out (like a broom closet), or it may have several (like the editor’s office).  Moreover, any number of people can play concurrently, but some “places” have a limited capacity.  For example, the broom closet is small and only has room for one person.  If Clark is in the broom closet, Lois needs to wait at the door until Clark leaves.   The editor’s office is big and might have room for ten people.  The road out in front probably won’t have any limit at all.

 

Keep in mind that players move from place to place one step at a time, and that the player (not the game) gets to decide what a player will do on the next move.  All the game can do is let them make a move or ask them to wait (“Clark is in the broom closet right now, and you can’t squeeze in, so you’ll need to wait.”), tell them about a place (“I see a pile of dusty papers and a bottle”), etc.  A player may want to revisit rooms many times.

 

1. Explain why multi-player scavenger hunt is at risk of deadlocks by listing the four necessary conditions for deadlock and, for each, indicating how it arises in the game.

 

 

1.      Mutual Exclusion – Only one player can stand on a particular space at a time.  The closet has a maximum capacity of 1 so that only one player can be in it at once.

2.      Hold and Wait – The space that the player is standing on is still being used by the player while the player is waiting to move to a new space.  So if Clark is in the closet, he is holding the closet while he waits for a space to open up in the adjoining room.

3.      Circular Wait – Suppose player 1 is standing in a full room where player 2 wants to go to, and player 1 wants to go into the full room where player 2 is standing.  This is an example of circular wait.  We can imagine n people all standing in a circle waiting to move to the next position clockwise around the circle.

4.      No Preemption – No one can move anyone else from where they are standing.   No one can tell a player to stop waiting.

 

 

2. Suppose that we add a command “scram!”  It takes the player back to the main gates to Gotham City (there is no space limit at the front gate or the streets leading away from it).  A player who is unable to leave a place can then use “scram!” to get out.  Does this eliminate the risk of deadlock?  If your answer is “yes” explain which of the conditions for deadlock is eliminated.  If your answer is “no”, give a small counterexample.   
   
   Yes, the risk of deadlock is eliminated.  The reason is that preemption is now available through the scram command.  A player can preempt himself back to the front gate.

4. Below are two process-wait graphs and two resource wait graphs.   If the graph does not show a deadlock, list the order in which we can fully reduce the graph (e.g. P₄, P₁, ….).  If a deadlock is present, prove this by showing us a fully-reduced but non-trivial component.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

There is no deadlock.  The graph can be reduced, in the following order:  P0, P3, P1, P6, P4, P2, P5

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

This graph cannot be reduced.  The entire graph is a non-trivial component.  The key element causing the deadlock is the cycle consisting of P1, P0, and P5.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

There are several different reduction orders, one of which is :

P2, P5, P3, P0, P6, P1, P4

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Again there are several different reduction orders, one of which is:

                P5, P2, P0, P6, P1, P4, P3