Problem 1

More precisely, let P be the sequence of values produced by p, let A be the sequence of values consumed by c1 and let B be the sequence of values consumed by c2. Let Pa and P.b be the sequence of a and of b values in P respectively. Then, for some value of max (which is the number of buffers),

• A is a prefix of P.a.
• B is a prefix of P.b.
• |P| - |A| £ max.
• |P| - |B| £ max.
• Each produced value is eventually consumed.

monitor Split {
  private:
    int in = 0, outA = 0, outB = 0;
    int inA = 0, inB = 0;
    int max;
    int *av, *bv;
    // Invariant 0 <= inA <= max && 0 <= inB <= max
    condition canPut;  // inA < max && inB < max
    condition canGetA; // inA > 0
    condition canGetB; // inB > 0
  public:
    Split(int i) { max = i; av = new int[max]; bv = new int[max]; };

    entry void Put(int a, int b) {
      if (inA == max || inB == max) canPut.wait();
      av[in] = a;
      bv[in] = b;
      in = (in + 1) % max;
      inA++;
      canGetA.signal();
      inB++;
      canGetB.signal();
      };

    entry int GetA(void) {
      int v;
      if (inA == 0) canGetA.wait();
      v = av[outA];
      outA = (outA + 1) % max;
      inA--;
      if (inB < max) canPut.signal();
      return v;
      };

    entry int GetB(void) {
      int v;
      if (inB == 0) canGetB.wait();
      v = bv[outB];
      outB = (outB + 1) % max;
      inB--;
      if (inA < max) canPut.signal();
      return v;
      };
  };

Problem 2

This solution uses an urgent queue for the threads that have been notified (you could instead have them wait on the monitor lock). Note that the value ccount and ucount are updated only by the thread that (implicitly) has the monitor lock. It is import to do this, since otherwise there could be two threads that simultaneously update the variable. This would be a problem since increment is not generally an atomic operation.

1. Instantiate the following structure for each monitor:


struct mon {
  semaphore lock = 1;
  semaphore csem = 0, usem = 0;
  int ccount = 0, ucount = 0;
  };
 

2. Wrap each invocation of an entry procedure as follows (where m is the struct for the monitor):


P(m.lock);
entry procedure invocation
if (m.ucount == 0) V(m.lock);  // release monitor lock
else V(m.usem);  // pass monitor lock to urgent process
 

3. Implement wait() as follows:


m.ccount++;
if (m.ucount == 0) V(m.lock);  // release monitor lock
else V(m.usem);  // pass monitor lock to urgent process
P(m.csem);
P(m.usem);  // reacquire monitor lock
m.ucount--;
 

4. Implement notify() as follows:


if (m.ccount > 0) {
  m.ccount--;
  m.ucount++;
  V(m.csem);
 

5. Implement notifyAll() as follows:


while (m.ccount > 0) {
  m.ccount--;
  m.ucount++;
  V(m.csem);
  }

Problem 3

• Annabelle needs to use the dictionary and a thesaurus to write her paper;
• Bertrand needs a thesaurus and a coffee cup to write his paper;
• Chloe needs a dictionary and a thesaurus to write her paper;
• Dag needs two coffee cups to write his paper (he likes to have a cup of regular and a cup of decaf at the same time to keep himself in balance).

• Annabelle has a thesaurus and need the dictionary.
• Bertrand has a thesaurus and a coffee cup.
• Chloe has the dictionary and needs a thesaurus.
• Dag has a coffee cup and needs another coffee cup.

1. Is the system deadlocked in this state? Explain using a resouce allocation graph.


The resource allocation graph, shown below, can be fully reduced. Betrand is not blocked. Erasing the edges incident on Bertrand unblocks Chloe and Dag. Erasing their edges unblocks Annabelle.


2. Is this state reachable if the four people allocated and released their resources using the Banker's algorithm? Explain.


Yes. The resource allocation graph is also the maximum claims graph. Since it can be fully reduced, the state is attainable using the Banker's algorithm.