title: Readers-writers problem with writer priority
body: <h1>Problem</h1>
  
  <p>In the book "Little Book of Semaphores", p. 71, there is the following problem:</p>
  
  <blockquote>
    <p>Write a solution to the readers-writers problem that gives priority to writers. That is, once a writer arrives, no readers should be allowed to enter until all writers have left the system.</p>
  </blockquote>
  
  <p>I arrived at a solution, but it's a bit different from the one given in the book.</p>
  
  <h1>My solution</h1>
  
  <p><strong>Shared variables</strong>:</p>
  
  <pre><code>readSwitch = Lightswitch()
  writeSwitch = Lightswitch()
  noWriters = Semaphore(1)
  noReaders = Semaphore(1)
  </code></pre>
  
  <p><code>Semaphore(1)</code> means a semaphore initialized to 1, and <code>Lightswitch</code> is defined in the book like this:</p>
  
  <pre><code>class Lightswitch:
    def __init__(self):
      self.counter = 0
      self.mutex = Semaphore(1)
  
    def lock(self, semaphore):
      self.mutex.wait()
      self.counter += 1
      if self.counter == 1:
        semaphore.wait()
      self.mutex.signal()
  
    def unlock(self, semaphore):
      self.mutex.wait()
      self.counter -= 1
      if self.counter == 0:
        semaphore.signal()
      self.mutex.signal()
  </code></pre>
  
  <p><strong>Reader logic</strong>:</p>
  
  <pre><code>noReaders.wait()
  noReaders.signal()
  
  readSwitch.lock(noWriters)
  
  # critical section for readers
  
  readSwitch.unlock(noWriters)
  </code></pre>
  
  <p><strong>Writer logic</strong>:</p>
  
  <pre><code>writeSwitch.lock(noReaders)
  noWriters.wait()
  
  # critical section for writers
  
  writeSwitch.unlock(noReaders)
  noWriters.signal()
  </code></pre>
  
  <h1>Book's solution</h1>
  
  <p><strong>Shared variables</strong>:</p>
  
  <pre><code>readSwitch = Lightswitch()
  writeSwitch = Lightswitch()
  noWriters = Semaphore(1)
  noReaders = Semaphore(1)
  </code></pre>
  
  <p><strong>Reader logic</strong>:</p>
  
  <pre><code>noReaders.wait()
  readSwitch.lock(noWriters)
  noReaders.signal()
  
  # critical section for readers
  
  readSwitch.unlock(noWriters)
  </code></pre>
  
  <p><strong>Writer logic</strong>:</p>
  
  <pre><code>writeSwitch.lock(noReaders)
  noWriters.wait()
  
  # critical section for writers
  
  noWriters.signal()
  writeSwitch.unlock(noReaders)
  </code></pre>
  
  <h1>Questions</h1>
  
  <p>1) In the reader logic, in my solution, <code>noReaders.signal()</code> immediately follows <code>noReaders.wait()</code>. The idea here is that <code>noReaders</code> behaves as a kind of turnstile that allows the readers to pass through it, but is locked by a writer as soon as one arrives.</p>
  
  <p>However, in the book's solution, <code>noReaders.signal()</code> is done after calling <code>readSwitch.lock(noWriters)</code>.</p>
  
  <p>Is there any reason why my ordering would produce an incorrect behavior?</p>
  
  <p>2) In the writer logic, in my solution, <code>writeSwitch.unlock(noReaders)</code> comes before <code>noWriters.signal()</code>. However, the book places them in the reverse order. Is there any reason why my ordering would produce an incorrect behavior?</p>
  
  <h1>Edit: additional question</h1>
  
  <p>I have an additional question. There is something that I am probably misunderstanding about the book's solution. Let's say that the following happens:</p>
  
  <ul>
  <li><p>Reader 1 acquires <code>noReaders</code> (<code>noReaders</code> becomes 0)</p></li>
  <li><p>Reader 2 waits in <code>noReaders</code> (<code>noReaders</code> becomes -1)</p></li>
  <li><p>Writer 1 waits in <code>noReaders</code> (<code>noReaders</code> becomes -2)</p></li>
  <li><p>Reader 3 waits in <code>noReaders</code> (<code>noReaders</code> becomes -3)</p></li>
  <li><p>Reader 4 waits in <code>noReaders</code> (<code>noReaders</code> becomes -4)</p></li>
  <li><p>Reader 1 acquires <code>noWriters</code> (<code>noWriters</code> becomes 0)</p></li>
  <li><p>Reader 1 signals <code>noReaders</code> (<code>noReaders</code> becomes -3; Reader 2 gets unblocked)</p></li>
  <li><p>Reader 2 passes through <code>noWriters</code> lightswitch; signals <code>noReaders</code> (<code>noReaders</code> becomes -2, 
  Reader 3 gets unblocked)</p></li>
  </ul>
  
  <p>In the above situation, it seems that additional readers can keep arriving and entering the critical section although a writer is waiting.</p>
  
  <p>Besides, considering that reader and writer are looping, a reader that finished the critical section could loop around and wait on <code>noReaders</code> again, even if there are writers already waiting.</p>
  
  <p>What am I misunderstanding here?</p>