How to go about. On read/write locks

[Piet van Oostrum]

>>>>> Carl Banks <pavlovevidence at gmail.com> (CB) wrote:

>CB> On Apr 6, 2:23 pm, "Diez B. Roggisch" <de... at nospam.web.de> wrote:
>>> > This is a classical synchronization problem with a classical solution:
>>> > You treat the readers as a group, and the writers individually. So you
>>> > have a write lock that each writer has to acquire and release, but it is
>>> > acquired only by the first reader and released by the last one.
>>> > Therefore you need a counter of the number of readers, and manipulations
>>> > of this counter must be protected by another lock.
>>> 
>>> I was going to suggest a similar approach but refused to because of a
>>> problem I see with your code as well - if the readers are reading very
>>> fast (the OP didn't state what his actual application is, so it might
>>> not be a consumer-producer scheme which I don't think a dict would be
>>> the natural choice anyway) they can block the writer from writing
>>> alltogether.

>CB> You could implement some kind of fair ordering where whoever requests
>CB> a lock first is guaranteed to get it first, but I can't think of a way
>CB> to do that without requiring all readers to acquire two locks.

The original implementation (with writers starvation) comes from [1].
They also describe a solution where witers have priority, but it needs 5
semaphores and 2 counters (one for writers and one for readers). It can
cause starvation for readers, however. For the OP this wouldn't be a
problem because writers are rare in his situation.

However, I found a solution [2] with just one additional counter for the
number of writers and no additional semaphores. The manipulations of the
writers counter are also protected by the same mutex. This solution is
fair for both readers and writers. Translated in Python this would be:

#------------------------------------------------------------------------
from threading import Lock

mutex = Lock()
writelock = Lock()
numreaders = 0
numwriters = 0
#------------------------------------------------------------------------
# Reader code:

mutex.acquire()
if numwriters > 0 or numreaders == 0:
   mutex.release()
   writelock.acquire()
   mutex.acquire()
numreaders += 1
mutex.release()

## critical section for reader

mutex.acquire()
numreaders -= 1
if numreaders == 0:
    writelock.release()
mutex.release()
#------------------------------------------------------------------------
# Writer code:

mutex.acquire()
numwriters += 1
mutex.release()
writelock.acquire()

## critical section for writer

mutex.acquire()
numwriters -= 1
mutex.release()
writelock.release()
#------------------------------------------------------------------------

I am going to put this in a class, with a context manager so that it can
be use with the 'with' statement like the normal locks.

I also found a solution with no additional counters but an additional
semaphore, but I found it only in lecture notes [3,4]; I couldn't find any
scientific publications about it. So I don't know for sure if it is
correct, fair etc.

[1] P. J. Courtois , F. Heymans , D. L. Parnas, Concurrent control with
    “readers” and “writers”, Communications of the ACM, v.14 n.10,
    p.667-668, Oct. 1971
[2] Jalal Kawash, Process Synchronization with Readers and Writers
    Revisited Journal of Computing and Information Technology - CIT 13,
    2005, 1, 43–51
[3] http://pages.cs.wisc.edu/~haryadi/537/slides/lec18-semaphores.ppt
[4] http://vorlon.case.edu/~jrh23/338/HW3.pdf
-- 
Piet van Oostrum <piet at cs.uu.nl>
URL: http://pietvanoostrum.com [PGP 8DAE142BE17999C4]
Private email: piet at vanoostrum.org