CS 162 Assignment 3 Sample Solution

CS 162
Spring 1996

Homework 3 -- sample solution and discussion

1 Laundromat: parallel allocators

  // semaphore 'nfree' initialized to NMACHINES,
  // boolean 'available' array initialized to all TRUE.

  int allocate() //Returns index of available machine.
  {
    P(nfree);    // Wait until a machine is available.
    for (int i=0; i < NMACHINES; i++) {
      if (available[i] == TRUE) {
        available[i] = FALSE;
        return i;
      }
    }
  }

  void release(int machine) // Releases machine.
  {
    available[machine] = TRUE;
    V(nfree);
  }

1.a Explain the error

As the code stands, the semaphore nfree properly tracks the availability of machines. However, in addition to identifying when a machine is available, allocate must identify which machine may be used. The code searches a shared array, and a race-condition allows concurrent searching threads to erroneously find and manipulate the same free element.

1.b Eliminate the error

An immediately apparent solution is to force atomicity on the entire array search, thereby eliminating the race-condition entirely:

  Lock available_mutex("available array mutex");

  int allocate() // Returns index of available machine.
  {
    P(nfree);    // Wait until a machine is available.
    available_mutex.Acquire();  // begin atomic region
    for (int i=0; i < NMACHINES; i++) {
      if (available[i] == TRUE) {
        available[i] = FALSE;
        available_mutex.Release();  // end atomic region
        return i;
      }
    }

    // if we get this far, a bad call V(nfree) has been made somewhere!
    assert(FALSE);
  }

this synchronization is stronger than necessary. As the assert statement above suggests, an important invariant is provided by the nfree semaphore: a search of the available array will not commence unless there is a free machine with which the search can terminate. One can use this result to show that for any n threads concurrently executing the search code in allocate, there are at least n array entries marked TRUE.

Because each searching thread is guaranteed a free entry, there is no need to completely serialize the searches. The only place atomicity is required is in the span while reading and updating an entry within the loop, so that there is not a race-condition in the search termination. An alternate solution:

  Lock available_mutex("available array mutex");

  int allocate() // Returns index of available machine.
  {
    P(nfree);    // Wait until a machine is available.
    for (int i=0; i < NMACHINES; i++) {
      available_mutex.Acquire();   // begin atomic region
      if (available[i] == TRUE) {
        available[i] = FALSE;
        available_mutex.Release(); // exit 1 from atomic region
        return i;
      }
      else {
        available_mutex.Release(); // exit 2 from atomic region
      }
    }
  }

note the need to carefully maintain the lock along all execution paths in the atomic region.

Observe that neither solution is inherently better than the other, but rather that each makes different trade-offs in performance. One must weigh the drawbacks of the first solution's non-interleaved searches against the second solution's more frequent synchronization operations in deciding which solution is most appropriate in a given context.

2 Making water: rendezvous

For every triple of two hReady calls and an oReady call, exactly one call to makeWater should be made. In addition, a call to oReady or hReady should return only after successfully forming such a triple. This is analogous to send/receive pairs with synchronizing ports.

  Semaphore hArrived(0);   // for oxygen threads to wait on
  Semaphore hCanLeave(0);  // for hydrogen threads to wait on
  Semaphore oMutex(1);     // to prevent multiple oxygen threads from 
                           // fighting for hydrogen.

  void hReady() {
    hArrived.V();   // announce arrival

    hCanLeave.P();  // wait until we're allowed to leave
  }

  void oReady() { 
    oMutex.P();     // make sure only one oxygen claims arriving hydrogens
                    // to avoid deadlock.
    hArrived.P();   // wait for a hydrogen thread to arrive
    hArrived.P();   // wait for another hydrogen thread to arrive
    oMutex.V();     // allow another oxygen to start...

    makeWater();    // form water with those two atoms and ourself
                    // this assumes makeWater is thread-safe.

    hCanLeave.V();  // allow a hydrogen thread to leave
    hCanLeave.V();  // allow another hydrogen thread to leave
  }

because the oxygen thread is unique in any water-forming triple, it can most easily perform as the controlling thread for the interaction. Were we to have one of the hydrogen threads direct the interaction and call makeWater, we would have to implement a more elaborate election to assign the asymmetric roles. The mutex is required to make sure one oxygen really controls the show; if more than one started counting hydrogens, we could have deadlock.

However, this solution does not really prevent starvation; depending on the implementation of semaphores used, a call to oReady might block indefinitely at the call to oMutex.P() while threads subsequently calling oReady continually get the mutex first!

The astute reader might notice that this simple fact prevents any semaphore-based solution from preventing starvation: regardless of what queueing policy we try to implement, a general locking scheme cannot be constructed to maintain the shared queue without subverting the entire point of having the queue. In order to queue up, a thread must eventually grab a lock, at which point it might starve. As a special case, it is worth noting that a solution can be found if the total number n of participating threads is known. A sequence of n-1 semaphores can be arranged with decreasing initial counts n-1, ..., 1 such that a FIFO queue is simulated as each thread decrements the semaphores in the same decreasing order (and get blocked at different points in the sequence).

The only way to prevent starvation with semaphores is to proscribe semaphore implementations which do not use a FIFO policy. As long as semaphores behave with FIFO ordering, starvation-free programs can be written (the solution given above is sufficient under this condition).