title: Race condition while trying to use "Readers Writer Lock"
body: <p>I'm working on a project using <code>pthreads</code> and i made my own implementation of <strong>Readers Writer Lock</strong> which has the following methods:</p>
  
  <ul>
  <li>Lock for reader (several can read simultaneously)</li>
  <li>Lock for writer (only one can write)</li>
  <li>Unlock (for both reader/writer)</li>
  </ul>
  
  <p>I've tested it and it works well, my problem is more logical,
  in my program i want several threads to do some testing on numbers in a specific range, and if a number was found that answers my criteria i want them to add them to a shared resource which is an array.</p>
  
  <p>If the number is already found by another thread and exists in the array, continue searching.</p>
  
  <p>Here is a pseudo code for my algorithm:</p>
  
  <pre><code>X = lowest number to search, X' = highest number to search,
  func = the test for the number, ARR = the array shared between the threads, 
  RWL_R = Lock for reader, RWL_W Lock for writer, RWL_U = Unlock.
  
  
  FOR each NUM from X to X' DO:
      IF func(NUM) = true DO:
          FOR each cell of ARR DO:
              RWL_R // lock for reader since i'm reading from ARR
              IF ARR[cell] contains NUM DO:
                  RWL_U // unlock since no longer reading from ARR
                  skip to the next iteration of the first FOR loop
              ENDIF
          END FOR
  
          RWL_U // unlock since no longer reading from ARR
          ////// PROBLEM HERE ////////
          RWL_W // lock to write to array since for loop ended without finding the same NUM
  
          ARR[cell] &lt;- NUM
          RWL_U // unlock since finished writing into array
      END IF
  END FOR
  </code></pre>
  
  <p>As you can see the logic is fine since that little line i marked with the ugly caps "PROBLEM HERE". inside that little gap between the reader unlock and the writer lock a race condition might (and does) occur.</p>
  
  <p>So i have 2 possible results:</p>
  
  <ol>
  <li><p>(The Good)</p>
  
  <ul>
  <li>Thread_A find number N, locks the array for reading.</li>
  <li>Thread_B finds the same number N, waiting to check the array but it's currently locked by Thread_A.</li>
  <li>Thread_A finishes going through the array and the number N is not there, unlocks the lock and locks it again as writer, adding N to the array, unlocks the lock and finishes his job.</li>
  <li>Thread_B can now check the array, number N is there so it skips to number N2 and the rest works hot it's supposed to.</li>
  </ul></li>
  <li><p>(The bad)</p>
  
  <ul>
  <li>Thread_A find number N, locks the array for reading.</li>
  <li>Thread_B finds the same number N, waiting to check the array but it's currently locked by Thread_A.</li>
  <li>Thread_A finishes going through the array and the number N is not there, unlocks the lock.</li>
  <li>Thread_B takes over the lock and locking it as reader, checking the array and number N is still not there (Thread_A haven't added it yet).</li>
  <li><p>Thread_B unlocks the lock.</p></li>
  <li><p>Either Thread_A or Thread_B now locks the lock for writing, adding number N, unlocking the lock and finishes.</p></li>
  <li>The thread that waited now locks the lock, adds the same number N, unlocks and finishes.</li>
  </ul></li>
  </ol>
  
  <p>So i'm now trying to find the best logical way to fix the issue, i can only think about locking as a writer when checking the array and not unlocking it until finishing writing, or to create a method that switches "atomically" from reader lock to writer lock, but that's kind of "Cheating" and not using the "<strong>Readers Writer Lock</strong>" mechanism as it's supposed to be used.</p>
  
  <p>What's a better logical way to use it here?</p>