argamanza argamanza - 6 months ago 11
Linux Question

Race condition while trying to use "Readers Writer Lock"

I'm working on a project using

pthreads
and i made my own implementation of Readers Writer Lock which has the following methods:


  • Lock for reader (several can read simultaneously)

  • Lock for writer (only one can write)

  • Unlock (for both reader/writer)



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.

If the number is already found by another thread and exists in the array, continue searching.

Here is a pseudo code for my algorithm:

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] <- NUM
RWL_U // unlock since finished writing into array
END IF
END FOR


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.

So i have 2 possible results:


  1. (The Good)


    • Thread_A find number N, locks the array for reading.

    • Thread_B finds the same number N, waiting to check the array but it's currently locked by Thread_A.

    • 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.

    • 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.


  2. (The bad)


    • Thread_A find number N, locks the array for reading.

    • Thread_B finds the same number N, waiting to check the array but it's currently locked by Thread_A.

    • Thread_A finishes going through the array and the number N is not there, unlocks the lock.

    • 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).

    • Thread_B unlocks the lock.

    • Either Thread_A or Thread_B now locks the lock for writing, adding number N, unlocking the lock and finishes.

    • The thread that waited now locks the lock, adds the same number N, unlocks and finishes.




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 "Readers Writer Lock" mechanism as it's supposed to be used.

What's a better logical way to use it here?

Answer

The two options you give are suboptimal in most scenarios, since one prevents multiple readers from checking at the same time (and presumably, after a while, readers are much more common than writers), while the other is impossible; even if you switch "atomically" from reader lock to writer lock, two different readers could both determine a value X is not present, both request an upgrade to write lock, the first one writes X then unlocks, while the second waits its turn then writes X again and you end up violating the uniqueness invariant.

The real answer depends on the common usage patterns:

  1. If writing is more likely to happen than reading in general (concurrent reading is uncommon), then you just drop the reader/writer lock and use a simple mutex. Reader/writer locks often have overhead that isn't worth it if you aren't regularly using concurrent readers, and even if the overhead is trivial (sometimes it is; Windows' SRW Locks used solely in "exclusive" (writer) mode where recursive acquisition isn't needed is as fast or faster than critical sections), if the program logic becomes more complicated, or you need to constantly switch from read to write locks and back, the additional logic and acquisition/release overhead can cost more than just a single lock and unlock with exclusive access.

  2. If you have other frequently used code which reads but never writes, and readers that might need to write are less common and regularly have to write, then use the solution you suggested; keep the reader/writer lock, but have the "might write" code lock for write from the beginning; it eliminates concurrency in the "might write" code path, but "only read" users can operate concurrently.

  3. If reading is much more common than writing (which is the usual use case for something like this if the code provided is the only code that accesses the array; otherwise your array will grow out of control), then perform a double check after "upgrading" to write lock; perform the same scan a second time after upgrading to a write lock to make sure no one grabbed the write lock and added the missing value, then write if the value is still missing. This can be optimized to avoid rescanning if the array only has new values added, with existing values never changing or being deleted. You'd just remember where you left off checking, and scan any new entries added between your original scan and when you acquired the write lock.

The pseudo-code for #3 would look like:

FOR each NUM from X to X' DO:
    IF func(NUM) = true DO:
        RWL_R // lock for reader outside inner loop since repeatedly reading from ARR
        cell = 0
        WHILE cell < ARR.length DO:
            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
            cell += 1
        END WHILE

        RWL_U // unlock since no longer reading from ARR
        RWL_W // lock to write to array since for loop ended without finding the same NUM
        // NEW!!! Check newly added cells
        WHILE cell < ARR.length DO:
            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
            cell += 1
        END WHILE
        // If we got here, not in newly added cells either, so add to end
        ARR[cell] <- NUM
        RWL_U // unlock since finished writing into array
    END IF
END FOR
Comments