CMSC 412-F98 Exam 1 Solution

Problem 1 Solution

D should wait for B to add the even entries. So introduce a semaphore that B signals after doing its sum; D waits on it before accessing B's sum; the semaphore is initially 0. Similarly between D and C. This leads to the following.

semaphore overB := 0;
semaphore overC := 0;
integer sumB := 0;
integer sumC := 0;

B_code {
 for i := 0 to 9 {
  sumB := sumB + x[2*i];
 };
 V(overB);
}

C_code {
 for i := 0 to 9 {
  sumC := sumC + x[2*i + 1];
 };
 V(overC);
}

D_code {
 P(overB);
 P(overC);
 sum := sumB + sumC;
}

Equivalently, the two sempahores can be combined into one.

semaphore over := 0;
integer sumB := 0;
integer sumC := 0;

B_code {
 for i := 0 to 9 {
  sumB := sumB + x[2*i];
 };
 V(over);
}

C_code {
 for i := 0 to 9 {
  sumC := sumC + x[2*i + 1];
 };
 V(over);
}

D_code {
 P(over);
 P(over);
 sum := sumB + sumC;
}

GRADING: Semaphore(s) declaration (2 pts). Integer declaration (1 pt). B_code loop (1 pt), B_code V op (1 pt), C_code loop (1 pt), C_code V op (1 pt), D_code P ops (2 pt), D_code summation (1 pt).

COMMON MISTAKES: Making B and C wait until D finishes. Using mutex to protect x, so B and C cannot access x concurrently. Redundant semaphores. Allowing D to terminate before B/C starts. Have B and C not processes but functions called by D, thereby reducing to single thread system. Busy waiting. Blatant busy waiting, e.g., no semaphores (-8 pts).

Problem 2 Solution

Before getting a buffer from eQ, need to ensure that eQ is not empty. Exactly as in the bounded-buffer problem, this can be achieved by doing a P on a semaphore that keeps track of the number of items (buffers) in eQ. V should be done on this semaphore whenever a buffer is added to eQ.

No need to worry about an overflow control semaphore (i.e., to avoid putting a buffer on a queue that already has N buffers) because there are only N buffers in circulation.

Need a lock to ensure mutual exclusion on eQ.

Exactly the same considerations hold for fQ.

This leads to following:

sempahore eQcount := N;  // number of buffers in eQ
sempahore fQcount := N;  // number of buffers in fQ
sempahore eQlock := 1;
sempahore fQlock := 1;

B_code {
 repeat
  P(eQcount);
  P(eQlock);
  get buffer from eQ;
  V(eQlock);
  write into buffer;
  P(fQlock);
  put buffer into fQ;
  V(fQlock);
  V(fQcount);
 forever
}
  
C_code {
 repeat
  P(fQcount);
  P(fQlock);
  get buffer from fQ;
  V(fQlock);
  read from buffer;
  P(eQlock);
  put buffer into eQ;
  V(eQlock);
  V(eQcount);
 forever
}

GRADING: Lock semaphores declaration (2 pts). Lock semaphores usage (2 pts). Qcount semaphores declaration (2 pts). Qcount semaphores P ops (2 pts). Qcount semaphores V ops (2 pts).

COMMON MISTAKES: Using one lock for both queues. Doing V on Qcount before putting item in Q. Doing P(Qlock) before P(Qcount); causes deadlock. Busy waiting, using no semaphores (lost lot of points). Busy waiting, using only lock semaphore.

Problem 3 Solution

(a) Claim holds

Proof: Flag[i] is written by Pi and read by Pj (where i=0,1 and j=1-i). Flag[i] is true whenever Pi is in CS.

Whenever P0 enters CS, flag[1]=false and hence P1 is not in CS.

Symmetric argument holds for P1.

GRADING: Correct decision (1 pt). Proof (4 pts). Partial points for sensible proof attempt (even if the decision is incorrect).

COMMON MISTAKES: Needlessly complicating the explanation by attempting to prove "everything" about the algorithm rather than what was asked.

(b) Claim does not hold

Counter-example (an execution that falsifies the claim):

  1. P0 executes NCS, sets flag[0] to true
  2. P1 executes NCS, sets flag[0] to true
  3. P0 executes one iteration of while loop
  4. P1 executes one iteration of while loop
  Repeat steps 3 and 4 forever (preserves weak fairness of P0, P1)

GRADING: Correct decision (1 pt). Counter-example execution (4 pts). Partial points for sensible execution attempt (even if the decision is incorrect).

COMMON MISTAKES: When P0 and P1 are both looping, assuming that P0 eventually sees flag[1]=false because P1 repeatedly clears and sets flag.