Preface: For any questions or answers involving the use of a
monitor, assume the monitor is of the "signal and continue"
type (the signalling process continues in the monitor).  Further
assume that processes woken using signal() have priority for
re-entry into the monitor, and thus can assume that a signalled
condition is true.  If the second assumption does not hold, 
the code below can be modified to recheck the condition upon
being awakened.



6.3

Busy waiting refers to a process using the CPU to continuously check 
for a condition (a lock unlocking, and I/O device being ready).  The
alternative is to block by waiting on some queue and be notified
when the condition is achieved.  However, this queue must be a shared
data structure, which in itself must be synchronized.  Since we
can't recurse indefinitely, this implies that busy waiting can be
minimized, but must exist.



6.8

You can modify the basic definition of a semaphore to make it a
counting semaphore.  Simply initialize it with the value N rather
than 1.  Now the first N attempts to open a connection will succeed,
but the N+1st will block.  We will always maintain N open
connections.



6.10

wait(S) {
  while (TestAndSet(S->guard)) // no-op;
  S->value--;
  if (S->value < 0) {
    Add to S->list;
    S->guard = false;
    block();
  } else {
    S->guard = false;
  }
}

signal(S) {
  while (TestAndSet(S->guard)) // no-op;
  S->value++;
  if (S->value <= 0) {
    remove a process P from S->list;
    wakeup(P);
  } 
  S->guard = false;
}

This solution minimizes busy-waiting, where busy-waiting
only exists for contention over the semaphore's critical
section, which is access to the semaphore's data structures.
See 6.3 for why we need this.

Many people forgot to release the TestAndSet lock before
calling block().  This is not good, obviously, since no
one will be able to obtain the lock to call signal().



6.11

Here's a solution using semaphores.  Note that it requires 
the use of counting semaphores, where multiple calls to signal()
allow multiple wait() calls to succeed.  The semaphores defined
at the start of 6.5 suffice.


semaphore customer_waiting(0) // Initialize in LOCKED state
semaphore haircut_done(0)     // Initialize in LOCKED state
semaphore wait_room_mutex(1)  // Initialize in UNLOCKED state
int num_waiting = 0;

barber() {
  while (1) {
    // wait for customers
    customer_waiting->wait();

    // put someone in the seat
    wait_room_mutex->wait();
    num_waiting--;
    wait_room_mutex->signal();

    // cut hair
    haircut_done->signal();
  }
}

customer() {
  wait_room_mutex->wait();
  if (num_waiting < N) {
    // take a seat
    num_waiting++;
    customer_waiting->signal();
    wait_room_mutex->signal();
    haircut_done->wait();
  } else {
    // leave, we're full
    wait_room_mutex->signal();
  }
}



6.13

Assume we have some queue data structure
with the functions:

enqueue(): add an element to the end of the queue
dequeue(): remove the element at the start of the queue
length(): return the number of elements in the queue

and that N is the size of the bound.

monitor bounded_buffer {
  queue buffer(N);
  cond waiting_on_portion;
  cond waiting_on_space;

  void produce (portion val) {
    if (buffer->length() >= N) {
      waiting_on_space.wait();
    }
    buffer->enqueue(val);
    waiting_on_portion.signal();
  }

  portion consume (void) {
    if (buffer->length() == 0) {
      waiting_on_portion.wait();
    }
    val = buffer->dequeue();
    waiting_on_space.signal();
    return val;
}



6.19

6.19 and 6.22 are essentially the same problem, couched in slightly 
different terminology.  In both cases, when a particular "event" 
occurs (file close, clock ticks), we must wake up one OR MORE processes.

The problem is we have N processes blocked, and we want to wake
up K of them, where 1 <= K <= N.  A condition variable with
signal() and broadcast() defined only allows you to wake up
1`or N processes, not anywhere between.  Regardless, many of you
used a single condition variable.

Let's take the case where you call signal() in the event function,
waking one person up.  In the alarm clock case, this just plain
doesn't work.  What if two people set the alarm for the same
time?  They won't both wake up.  It could actually be worse than
that.  Say it's tick 5 and you have two people wanting to be woken
up now, and one at tick 7.  What if you wake up the tick 7 guy?
He'll just get up and go back to sleep, but you'll have woken
nobody at tick 5.

The file case somewhat works with signal().  It's true that everyone
will get a chance to open the file.  But it violates the spirit
of the problem.  Suppose the file has N = 10, and process 10 comes
along and opens it.  Then processes 1, 2, 3, and 4 come along and
try to open it, blocking because the the file is full.  So far,
so good.  Now process 10 closes it.  If you used signal(), one 
person wake up (say 2).  But nobody else can get woken until 2
closes the file, even though 1, 2, 3, and 4 can all access the
file at the same time (1+2+3+4 = 10).

OK, so signal() doesn't work.  I think some of you may have 
misinterpreted what it does, and thought it had the functionality
of broadcast(), where everyone gets woken up.  Does this work?
Well, yes.  In the alarm clock case, at every tick we wake 
everyone up and, presuming they check whether it's really time
to wake up or not, the ones whose time is up wake up and the
others go back to sleep.  In the file system case, everyone
wakes up and essentially re-competes to open the file.  Well,
it works, but it's basically busy waiting, right?  Especially in
the case of the alarm clock, we now have a bunch of processes
asking--at every tick--whether it's time to wake up.  Not
so good.

Again, what we really want to do is wake up K (1 <= K <= N) people,
which just can't be done with a single condition variable (edit:
see the section on priority conditions in the book.  They could
work).  What you want is one condition variable per process.
This let's us selectively wake up individual processes.  More 
importantly, we can now wake up exactly K of them.

Which K do we choose?  In the alarm clock case, it's the K people
who wanted to be woken on the current tick.  In the file case,
it's some K processes whose sum of IDs is l.e. the space left
in the file.  We might want to maximize K; that is, open the
most processes that can fit in the open space.  It can be shown
that K is maximized when we take, in order, the processes with the
smallest IDs until we exhaust the free space (the "greedy" algorithm).

In both cases, we get the right functionality when we store
each process, with associated condition variable, in sorted order
on some key.  In the alarm case, store them in order of wakeup
time.  Then the K processes you want to wake up will always
be the first K elements of the list.  In the file case, store
them in order of process ID, and keep adding the process at
the head of the list until the space is used up.

So, let's assume we have a data structure sorted_list, with the
following methods:

void insert(int val, condition c): Insert, in sorted order (by val)

(int, condition) head(void): return the value and condition at the
  head of the list (the integer is NULL if the list is empty)

void remove(void): remove the element at the head of the list



Then, 6.19 is:

monitor shared_file {
  int sum_of_processes;
  sorted_list list_of_processes;

  function open(int process_id) {
    if (sum_of_processes + process_id > N) {
      c = new condition;
      list_of_processes->insert(process_id, c);
      c->wait();
    }
    sum_of_processes += process_id;
    grant access;
  }

  function close(int process_id) {
    int temp_sum = sum_of_processes;

    for ( (val, c) = list_of_processes->head(); 
          val != NULL; 
          (val, c) = list_of_processes->head() )
    {
      if (temp_sum + val->process_id > N) {
        break;
      } else {
        temp_sum += val->process_id;
        c->signal();
        list_of_processes->remove();
      }
    }
  }
}



6.22

monitor alarm_clock {
  int virtual_time = 0;
  linked_list list_of_timers;
  
  function wake_me(int num_ticks) {
    c = new condition;
    list_of_timers->insert(virtual_time + num_ticks, c);
    c->wait();
  }

  function tick() {
    virtual_time++;
    for ( (val, c) = list_of_timers->head(); 
          val != NULL && val == virtual_time; 
          (val, c) = list_of_timers->head() )
    {
      c->signal();
      list_of_timers->remove();
    }
  }
}