Re: why does rwlock prefer readers by default?

[OndÅej BÃlka <neleai at seznam dot cz>]

On Wed, May 07, 2014 at 10:09:05PM +0200, Torvald Riegel wrote:
> On Wed, 2014-05-07 at 14:51 -0400, Rich Felker wrote:
> > On Wed, May 07, 2014 at 12:33:51PM +0200, Torvald Riegel wrote:
> > > POSIX makes it an implementation-defined choice whether readers or
> > > writers are preferred.  Our current implementation's default is that
> > > readers are to be preferred.  I couldn't find the rationale for this;
> > > does anybody know what it was?
> > > 
> > > Otherwise, if this was an arbitrary choice, what do you all think the
> > > default should be?  Can we change it?  Should we change it to preferring
> > > writers?
> > 
> > As far as I know, there is no way to prefer writers but allow
> > recursive locking by readers (which the standard requires be allowed)
> > without unbounded memory usage (to track which threads already own a
> > read lock). The problem is that you can't distinguish a new reader
> > from an existing reader performing a recurive lock and thus you have
> > to allow both, even if a writer is waiting. Please correct me if I'm
> > wrong on this.
> 
> Yes you need space to track which readers have acquired which rwlock.
> At some number of recursive/rwlocks, there will be a runtime overhead.
> 
> Irrespective of that, there's another case where we can prefer readers
> or writers, as I've described elsewhere in the thread.

That means that you need a malloc/mmap from some size which complicates
implementation. With readers we let kernel handle that.

A argument that you need unbounded memory usage is misleading as this is
bounded by number of threads and contention of many readers/writers is bigger
issue than allocating few extra bytes.

Also you only need to prefer writers with high probability. A simple
idea is add a thread local counter that counts number of read locks of
all rwlock. When you are reader and there is pending writer then you first
check counter and yield when it is zero. This works as long as thread
does not use two rwlocks simultaneously. To detect these you use bloom
filter: split counter to 8 8-bit counters, for each rwlock randomly generate 
mask which counters it uses and check if all these counters are zero then yield.
There is techical problem that if a counter reaches 255 we could not
decrease/increase it but it should not happen in practice.