title: Sleeping Barber algorithm (with multiple barbers)
body: <p>The <strong><a href="http://en.wikipedia.org/wiki/Sleeping_barbers_problem" rel="nofollow noreferrer">Sleeping Barber Problem</a></strong> is a classical synchronization problem that many of you may be familiar with or at least heard of. </p>
  
  <p>It's based on the premise that a barber <em>(a thread)</em> sleeps when there are no customers <em>(each customer is a thread)</em> in the waiting room <em>(which is a semaphore)</em>. If there is someone, he cuts his hair (symbolizing some processing) and the costumer leaves. If, then, there is no one in the waiting room, the barber goes to sleep. When another customer arrives, he then must wake up the barber.</p>
  
  <hr>
  
  <p>I have made a implementation of this using the following basic-idea </p>
  
  <p><sub>(although the actual code is in <code>C</code>, I wrote the following <strong>pseudo-code</strong> without much care for the syntax for sake of problem-understading, only using <code>sem_wait</code> and <code>sem_post</code><strong><sup>1</sup></strong> for smoother reading)</sub></p>
  
  <pre><code>Semaphore Customers = 0;
  Semaphore Barber = 0;
  Mutex accessSeats = 1;
  int NumberOfFreeSeats = N; 
  
  Barber {
      while(1) {
          sem_wait(Customers); // waits for a customer (sleeps)
          sem_wait(accessSeats); // mutex to protect the number of available seats
          NumberOfFreeSeats++; // a chair gets free
          sem_post(Barber); // bring customer for haircut
          sem_post(accessSeats); // release the mutex on the chair
          // barber is cutting hair
      }
  }
  
  Customer {
      while(1) {
          sem_wait(accessSeats); // protects seats so only 1 thread tries to sit in a chair if that's the case
          if(NumberOfFreeSeats &gt; 0) {
              NumberOfFreeSeats--; // sitting down
              sem_post(Customers); // notify the barber
              sem_post(accessSeats); // release the lock
              sem_wait(Barber); // wait in the waiting room if barber is busy
              // customer is having hair cut
          } else {
              sem_post(accessSeats); // release the lock
              // customer leaves
          }
     }
  }
  </code></pre>
  
  <p>However, now that I'll implement this problem with multiple barbers, my head got stuck. I went on Wikipedia to see if I could find something about it, but the only thing that I found there was this</p>
  
  <blockquote>
    <p><em>A multiple sleeping barbers problem has the additional complexity of coordinating several barbers among the waiting customers.</em></p>
  </blockquote>
  
  <p>and I couldn't figure this out by myself <strong><sup>2</sup></strong>. </p>
  
  <p><strong>What changes would I have to do in my code? Where would I need an extra semaphore here?</strong></p>
  
  <p><sup>1</sup><sub><code>sem_wait()</code> locks the semaphore. <code>sem_post()</code> unlocks it </sub><br>
  <sup>2</sup><sub>Disclaimer: Although I have asked this in <a href="https://softwareengineering.stackexchange.com/questions/213101/sleeping-barber-problem-with-multiple-barbers">programmers.stackexchange</a> aswell, I did not have reached a desired answer and my question still persists.</sub></p>