Process A        Process B
    int Y;           int Z;
    wait(S);         wait(S);
A1: Y = X*2;     B1: Z = X+1;
A2: X = Y;       B2: X = Z;
    signal(S);       signal(S);

S is set to 1 before either process begins execution and, as before, X is set to 5.

Now, how many different values of X are possible after both processes finish executing? The semaphore S ensures that, once begun, the statements from either process execute without interrupts. So now the possible ways in which statements from A and B can be interleaved are:

A1 A2 B1 B2: X = 11
B1 B2 A1 A2: X = 12

Process A         Process B
    int Y;            int Z;
A1: Y = X*2;      B1: wait(T);
A2: X = Y;        B2: Z = X+1;
    signal(T);        X = Z;

T is set to 0 before either process begins execution and, as before, X is set to 5.

Now, how many different values of X are possible after both processes finish executing? The semaphore T ensures that all the statements from A finish execution before B begins. So now there is only one way in which statements from A and B can be interleaved:

A1 A2 B1 B2: X = 11

• Attempt to grab any fork on the table until you are successful (if there are many forks grab the closest one).
• Attempt to grab any knife on the table until you are succesful (if there are many forks grab the closest one).
• Eat
• Return the knife.
• Return the fork.

• Flip a coin to decide if you are going to first try for a fork or a knife.
• Attempt to grab your choice until you are successful
(if there are many of that utensil grab the closest one).
• Attempt to grab the other type of utensil until you are successful (if there are many of that utensil grab the closest one).
• Eat
• Return the knife.
• Return the fork.

Single semaphore shared among all ggates: OK -- SLOW -- BAD

Semaphore for each tube: OK -- SLOW -- BAD

Semaphore for each ggate: OK -- SLOW -- BAD Single semaphore shared among all ggates: SLOW
Semaphore for each tube: OK
Semaphore for each ggate: BAD Gerbitrail management decides to invest heavily in the revolutionary technology which promises to wipe out the gerbilock threat forever. They hire noted computer expert Nickles Worth to evaluate their ggate approach and suggest improvements. Nickles looks at the simple demonstration above, involving only 2 gerbils and a single tube, and immediately objects. "You are enforcing non-essential constraints on the behavior of these two gerbils", he exclaims.

What non-essential constraint is imposed by the ggate solution involving only 2 gerbils and one tube? Give a specific scenario. Since only 1 gerbil is allowed in the tube at a time, both gerbils can't go through the tube simultaneously in the same direction even though that would work out okay. Nickles proposes that a new synchronization mechanism, the gerbiphore, be defined to handle the management of Gerbitrail tubes. His proposal involves the implementation of a gerbiphore as a C data structure, and the allocation of a single gerbiphore to each tube in a Gerbitrail cage configuration.

Nickles's proposed implementation is:

semaphore mutex=1;

struct gerbiphore {          /* definition of "gerbiphore" structure*/
 int dir;                    /* Direction: 0 means unspecified. */
 int count;                  /* Number of Gerbils in tube */
} A, B, ...;                 /* one gerbiphore for each tube */

int Fwd=1, Bkwd=2;           /* Direction codes for tube travel */

/* genter(g, dir) called with gerbiphore pointer g and direction dir
   whenever a gerbil wants to enter the tube attached to g
   in direction dir */

genter(struct gerbiphore *g, int dir) {
 loop:
   wait(mutex);
   if (g->dir == 0)
     g->dir = dir;    /* If g->dir unassigned, grab it! */
   if (g->dir == dir) {
     g->count = 1 + g->count;   /* One more gerbil in tube. */
     *********;                 /* MISSING LINE! */
     return;
   }
   signal(mutex);
   goto loop;
}

/* gleave(g, dir) is called whenever a gerbil leaves the tube
   attached to gerbiphore g in direction dir. */

gleave(struct gerbiphore *g, int dir) {
   wait(mutex);
   g->count = g->count - 1;
   if (g->count == 0) g->dir = 0;
   signal(mutex);
}

Unfortunately a blotch of red wine obscures one line of Nickles's code. The team of stain analysts hired to decode the blotch eventually respond with a sizable bill and the report that "it appears to be Ch. Petrus, 1981". Again, your services are needed.

What belongs in place of ********* at the line commented "MISSING LINE"? signal(mutex). We have to release the mutual exclusion lock before returning from genter. Ben Bitdiddle has been moonlighting at Gerbitrail Research Laboratories, home of the worlds largest gerbil population. Ben's duties include computer related research and shoveling. He is anxious to impress his boss with his research skills, in the hopes that demonstrating such talent will allow him to spend less of his time with a shovel.

Ben observes that the GRL Gerbitrail cage, housing millions of gerbils and involving tens of millions of tubes, is a little sluggish despite its use of Nickles Worth's fancy gerbiphore implementation. Ben studies the problem, and finds that each gerbil spends a surprisingly large amount of time in genter and gleave calls, despite the fact that tubes are infrequently used due to their large number. Ben suspects some inefficiency in the code. Ben focuses on the gleave code, and collects statistics about which line of code in the gleave definition is taking the most CPU time.

Which line of the (4-line) gleave body do you expect to be the most time consuming? wait(mutex) since that may hang while waiting for other instances of genter or gleave to complete. Identify a class of inessential precedence constraints whose imposition by Nickles's code causes the performance bottleneck observed by Ben. The mutex semaphore implements a global lock, so you can't manipulate more than one 1 semaphore at a time. Briefly sketch a change to Nickles's code which mitigates the performance bottleneck. If we use a separate mutex for each gerbifore than the mutual exclusion each mutex provides will only apply to operations on that gerbifore. Encouraged by his success (due to your help), Ben decides to try more aggressive performance improvements. He edits the code to gleave, eliminating entirely the calls to wait and signal on the mutex semaphore. He then tries the new code on a 2-gerbil, 1-tube cage.

Will Ben's change work on a 2-gerbil, 1-tube cage? Choose the best answer.

1. It still works fine. Nice work, Ben!
2. Gerbilock may be caused by two nearly simultaneous genter calls.
3. Gerbilock may be caused by two nearly simultaneous gleave calls.
4. Gerbilock may be caused by nearly simultaneous gleave and genter calls, followed by another genter call.
5. Gerbilock can't happen, although the system may fail in other ways.

Since tubes are advertised as a general mechanism for communication among a set of Unix processes, it is important that they work reliably when several processes attempt to read and/or write the simultaneously. S. Quire, the ex-lawyer CEO, has been unable to figure out just what the semantics of tubes are under these circumstances. He finally asks you for help.

Describe what will happen if a process writes an empty tube while multiple processes are waiting to read it. How many processes will read the new value? Since RTube_handler() is not interruptible, exactly one process will get the new value. Describe what will happen if multiple processes write different values to a tube at about the same time that another process is doing successive reads from that tube. Will each value be read once? Will at least one value be read, but some may be lost? Will garbage (values other than those written) be read? Since WTube_handler() is not interruptible, no values will be lost. Each value will be read correctly. S. Quire suggests that the interrupt hardware be modified so that timer interupts (which mark the end of the quantum for the currently running process) are allowed to happen in both user and kernel mode. How would this modification change your answer to parts (C) and (D)? If the handlers are interruptible, multiple processes may read the same value or garbage (zero). Multiple processes may write over other values before they are read, but will not be read twice if there is only a single reader. Customers have observed that Unicks seems to favor certain processes under some circumstances. In particular, when one process writes data to a tube while processes A, B, and C are waiting to read it, it is typically the case that the amount of data read by A, B, and C will be dramatically different.

Briefly explain the cause for this phenomenon. If process D writes data and the scheduler calls A, B, C, and D round-robin (in that order), process A has the best chance of having its Rtube call succeed since it runs right after process D has finished calling Wtube. Sketch, in a sentence or two, a plausible strategy for treating the processes more equitably. If processes have numbers, each tube could remember the last process that read it. When a process writes to the tube again, it could reorder scheduling so that the waiting process with the next higher process number is called next. Another approach would be to use a randomized scheduler, but this creates the possibility that some processes will not be run for a long period of time. Nickles Worth, a consultant to Similar Software, claims that tubes can be used to implement mutual exclusion-that is, to guarantee that at most one process is executing code within a critical section at all times. He offers an example template:

int TubeNumber = 37;	/* tube to be used for mutual exclusion */

WTube(TubeNumber,1);	/* one-time-only initialization */

while () {	/* loop with critical section */
   
   	/* LOCK ACCESS */
   
   <critical section>
   
   	/* UNLOCK ACCESS */
   
}

Fill in the LOCK and UNLOCK code above. LOCK: datum=RTube(TubeNumber)
UNLOCK: Wtube(TubeNumber,datum)