Problem 1

integer count = 0;
integer s = initial value;

binsem mutex = 1, block = 0;

void P(semaphore s) {
    Pb(mutex);
    if (s == 0) {
        count = count + 1;
        Vb(mutex);
        Pb(block);
        }
    else {
        s = s - 1;
        Vb(mutex);
        }
    }

void V(semaphore s) {
    Pb(mutex);
    if (count == 0) {
        s = s + 1;
        Vb(mutex);
        }
    else {
        count = count - 1;
        Vb(block);
        Vb(mutex);
        }
    }

This implementation suffers from a liveness problem. Give a behavior that results in s > 0, count = 0 and a process waiting on the semaphore block.

1. Let the semaphore be initially zero; hence count = 0, block = 0, and s = 0.
   
   
2. Have a process p1 start executing P. It will increment count. Stop it after having executed Vb(mutex) but before having executed Pb(block).
   
   
3. Have another process p2 do the same. At this point count = 2, block = 0 and s = 0.
   
   
4. Have a third process execute three V operations. At this point s = 1, block = 1 and count = 0.
   
   
5. Restart p1. It sets block to zero and completes the execution of P.
   
   
6. Restart p2. It finds block equal to zero and so waits on block.

Explain why such a behavior illustrates that the implementation suffers from a liveness problem.

Any sequence of V operations at this point will leave p2 blocked even though according to the properties of general semaphores, it should be unblocked. This violates a liveness property of general semaphores.

Problem 2

1. Modify Lamport's Bakery Algorithm so that a process will be able to enter its critical section even when another process has halted within its critical section.


When Halted(j) is true, a process can treat it as if choosing[j] is 0 and turn[j] is zero:

  int j;
  while (1) {
    choosing[i] = 1;
    turn[i] = max(turn[0], turn[1], ..., turn[n-1]) + 1;
    choosing[i] = 0;
    for (j = 0; j < n; j++)
      if (j != i) {
        while (choosing[j] && ! Halted(j)) ;
        while (! Halted(j) && turn[j] != 0
            && (turn[j], j) < (turn[i], i)) ;
      }
    critical section;
    turn[i] = 0;
    non-critical section;
  }
 

2. Can the predicate Halted(p) be implemented under the assumptions we have made about processes? Explain.


Not without assuming something stronger than the Finite Progress Axiom. So far, we have assumed a process can be unboundedly slow. With this assumpion, a process can determine that another process will take no further steps only by waiting forever.
 

3. In class, a bank transfer was used as an example of the need for mutual exclusion. What problems could occur if your version of the Bakery Algorithm were used to implement mutual exclusion in such a system?


Mutual exclusion can be used to implement critical sections which, in turn, are used to ensure atomic update of sets of variables. And, the atomicity is used to ensure some safety property holds. In the bank transfer example, the safety property (the "critical section invariant") is that the sum of the two accounts remains constant. If a process halts midway, though, then one account will be debited while the other will not be credited, thereby violating the safety property.

Problem 3

• No more than six people may sit at the counter at a time.
• If anyone sitting at the counter is a smoker, then everyone sitting at the counter must be a smoker. Similarly, if anyone sitting at the counter is a non-smoker, then everyone sitting at the counter must be a non-smoker.
• When there is more than one person waiting to sit down, and one is a smoker and another is a non-smoker, then the non-smoker will get a seat before the smoker.

monitor LunchCounter {

private:
    int s = 0;    // number smokers
    int ns = 0;   // number seated non-smokers
    int wns = 0;  // number waiting non-smokers
    // Invariant: 0 <= s <= 6 &&
    //            0 <= ns <= 6 &&
    //            (s == 0 || ns == 0)
    condition NSEnter;   // ns < 6 && s == 0
    condition SEnter;    // s < 6 && ns == 0 && wns == 0

public:

entry void ArriveNonSmoker (void) {
    if (s > 0 || ns == 6) {
        wns = wns + 1;
        wait(NSEnter);
        wns = wns - 1;
        }
    ns = ns + 1;
    if (ns < 6) signal(NSEnter);
    };

entry void LeaveNonSmoker (void) {
    ns = ns - 1;
    signal(NSEnter);
    if (ns == 0 && wns == 0) signal(SEnter);
    };

entry void ArriveSmoker (void) {
    if (ns > 0 || s == 6 || wns > 0) wait(SEnter);
    s = s + 1;
    if (s < 6) signal(SEnter);
    };

entry void LeaveSmoker (void) {
    s = s - 1;
    if (wns == 0) signal(SEnter);
    if (s == 0) signal(NSEnter);
    };

}