title: Reusable Barrier Algorithm
body: <p>I'm looking into the Reusable Barrier algorithm from the book <em>&quot;The Little Book Of Semaphores&quot;</em> (archived <a href="https://web.archive.org/web/20120731141936/http://greenteapress.com/semaphores/downey08semaphores.pdf" rel="nofollow noreferrer">here</a>). </p>
  <p>The puzzle is on page 31 (Basic Synchronization Patterns/Reusable Barrier), and I have come up with a 'solution' (or not) which differs from the solution from the book (a two-phase barrier).</p>
  <p>This is my 'code' for each thread:</p>
  <pre><code># n = 4; threads running
  # semaphore = n max., initialized to 0
  # mutex, unowned.
  
  start:
      mutex.wait()
          counter = counter + 1
          if counter = n:
              semaphore.signal(4) # add 4 at once
              counter = 0
      mutex.release()
      semaphore.wait()
          # critical section
      semaphore.release()
  goto start
  </code></pre>
  <p>This does seem to work, I've even inserted different sleep timers into different sections of the threads, and they still wait for all the threads to come before continuing each and every loop. Am I missing something? Is there a condition that this will fail?</p>
  <p>I've implemented this using the Windows library <a href="https://docs.microsoft.com/windows/win32/sync/semaphore-objects" rel="nofollow noreferrer">Semaphore</a> and <a href="https://docs.microsoft.com/windows/win32/sync/mutex-objects" rel="nofollow noreferrer">Mutex</a> functions.</p>
  <h2>Update:</h2>
  <p>Thank you to <strong>starblue</strong> for the <a href="https://stackoverflow.com/a/5049959/8112776">answer</a>. Turns out that if for whatever reason a thread is slow between <code>mutex.release()</code> and <code>semaphore.wait()</code> any of the threads that arrive to <code>semaphore.wait()</code> after a full loop will be able to go through again, since there will be one of the <code>N</code> unused signals left.</p>
  <p>And having put a <code>Sleep</code> command for thread number 3, I got <a href="http://pastebin.com/raw.php?i=FfXcCMZ3" rel="nofollow noreferrer">this</a> result  where one can see that thread 3 missed a turn the first time, with thread 1 having done 2 turns, and then catching up on the second turn (which was in fact its 1st turn).</p>
  <p>Thanks again to everyone for the input.</p>