This is the mail archive of the
mailing list for the glibc project.
Re: why does rwlock prefer readers by default?
- From: OndÅej BÃlka <neleai at seznam dot cz>
- To: Torvald Riegel <triegel at redhat dot com>
- Cc: Rich Felker <dalias at libc dot org>, GLIBC Devel <libc-alpha at sourceware dot org>
- Date: Sat, 24 May 2014 17:26:18 +0200
- Subject: Re: why does rwlock prefer readers by default?
- Authentication-results: sourceware.org; auth=none
- References: <1399458831 dot 32485 dot 12625 dot camel at triegel dot csb> <20140507185121 dot GZ26358 at brightrain dot aerifal dot cx> <1399493345 dot 32485 dot 15258 dot camel at triegel dot csb>
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.