title: Hints (not answers) on correctness of my sleeping barber and dining philosopher algorithms?
body: <p>I'm in an operating systems course.  We have an exam in two weeks, and I suspect that the dining philosopher and sleeping barber problems (semaphore versions) are in there.  Now, if I wanted to, I could just crack open the textbook and have the answers spoonfed to me, but I would rather actually learn them on my own.  I've spent some time working through the problems and I think I'm getting close, but... I'm not sure.  I don't want to just be told exactly what's wrong with my solutions, but I would like hints. I want to figure out as much as possible by myself.  </p>
  
  <p>So, sleeping barber... In the solution I've worked out I have three binary semaphores: 'w' for the waiting room, 'c' for the barber's chair, and 'x' for exit.  The barber can take care of one customer at a time, when done checks the waiting room for other customers, and if there are none, sleeps, right?    This is what I have worked out for the barber process's code (in kinda a hybrid of C and pseudocode):</p>
  
  <pre><code>while(true)
  {
      P(w);    //Guarantees an entering customer can't check the waiting room before the barber.
      P(c);
      P(x);    //A customer being serviced can't leave until barber is done servicing him.
      while( customersWaiting &gt; 0 )  
      {
          V(c);    //Allow a waiting room customer to sit in barber's chair.
          V(w);    //Allow another customer to enter the waiting room
          service customer
          V(x);    //Allow customer to leave
          P(w);    //Lock waiting room so barber can check it.
      }   
      //No customers
      V(w);   //Allow next entering customer to check waiting room.
      sleep
      V(c);   //Allows new customer service.
      service customer
      V(x);    //Allow customer to leave.
  }
  </code></pre>
  
  <p>I think this is right but I'm not sure.  I feel like the customer who just came in should be handled by the code in the while(customersWaiting > 0) loop, but I can't figure out how to arrange the semaphores to make that work.</p>
  
  <p>The customer, if I understand it, must check to see if the chair is occupied.  If it is, he must see if it is the barber in it.  If it is, me wakes him up, otherwise he sits in the waiting room.  If the waiting room is full, he leaves, right?  Anyway, here's the code I've worked out for the customer process:</p>
  
  <pre><code>P(w);    //Guarantees neither barber nor other customers can check waiting room.
  if (chair is occupied)  //Could you write this as if(c), or would you create a separate flag?
  {    
      if (barber is sleeping)
      {
          wakeup barber
          V(w);    //Now the waiting room can be checked by someone else.
          P(c);    //Sit in barber's chair
          P(x);    //Attempt to exit shop
      }
  }
  else
  {
      if (customersWaiting &lt; amountOfChairs)
      {
          customersWaiting++;
          V(w);    //Now the waiting room can be checked by someone else.
          P(c);    //Sit in barber's chair, when it's available that is.
          P(x);    //Attempt to exit shop
          customersWaiting--;
      }
  }
  exit shop
  </code></pre>
  
  <p>I'm not sure if I'm on the right track here or not... the problem I see is that, when there are no customers, the barber goes to sleep but, he might not be all the way asleep when a new customer arrives, and so the customer will go to the waiting room and wait for him forever.  I've thought of a couple possible ways to solve this...I could have a flag that the barber sets right before he sleeps (using a semaphore to access it), and then the new customer could check that, and sit in a tight loop until the barber is all the way asleep, then wake him up... but that's not exactly the best solution, is it?  I'm so unsure about this... Any hints?  Again I don't want the answer straight up, I want hints.</p>
  
  <p>Now the dining philosophers problem... I'm significantly more confident about this one, but I still want to double check.  In wthe solution I've worked out, I have a binary semaphore 'g' for grabbing a pair of chopsticks, a counting semaphore 'a' for the number of philosophers that may start eating, and one binary semaphore c[0..n-1] for each chopstick.  Basically, half the philosophers (rounded down, of course) may eat at any one time, right? (rounded down, of course) So in my solution, the philsopher after his thinking is done tries to grab a pair of chopsticks chopstick, but only if less than half the philosophers are eating and no one else is trying to grab a chopstick.  I've coded the philosopher's code like this:</p>
  
  <pre><code>while(true)
  {
      think
      P(g);    //Above all, no one else can try to grab a chopstick at the same time as someone else.
      P(a);    //Decrement the amount of philosophers that may start eating.
      P(c[left chopstick's number]);
      take left chopstick
      P(c[right chopstick's number]);
      take right chopstick
      V(g);    //Now someone else may attempt to grab a pair.
      eat
      V(c[left chopstick's number]);
      replace left chopstick
      V(c[right chopstick's number]);
      replace right chopstick
      V(a);
  </code></pre>
  
  <p>The one problem I can see is that, if a philosopher is eating and someone adjacent to him tries to grab a pair of chopsticks, he won't be able to get a full pair and therefore everyone will be frozen until the current eater finishes.  Am I on the right track at all here?</p>
  
  <p>I would greatly appreciate any feedback!</p>
  
  <p>Sincerely,
  RedZone</p>