how to distinguish between read and write locks?

10 views
Skip to first unread message

Rudi Wiener

unread,
May 28, 2001, 1:05:15 PM5/28/01
to
Is there a way to distinguish between a read-lock and a write-lock of a
resource? I'd like to have read-access to a resource from several threads
simultaneously while only one single thread may write at once (while no
other reads). The behavioiur would be identical with read-/write-locks in
databases.

Thanks for any hints
Rudi

David Schwartz

unread,
May 28, 2001, 3:20:25 PM5/28/01
to

Rudi Wiener wrote:

> Is there a way to distinguish between a read-lock and a write-lock of a
> resource?

I don't understand the question, what do you mean by 'distinguish'?

> I'd like to have read-access to a resource from several threads
> simultaneously while only one single thread may write at once (while no
> other reads). The behavioiur would be identical with read-/write-locks in
> databases.

Okay, so code that.

DS

Rudi Wiener

unread,
May 29, 2001, 1:13:06 PM5/29/01
to
> > Is there a way to distinguish between a read-lock and a write-lock of a
> > resource?
>
> I don't understand the question, what do you mean by 'distinguish'?

As far as I know I can (using a mutex) lock a resource completely or not at
all. I wonder whether there is a way to lock a resource completely, not at
all _and_ for read access only. Multiple threads should be able to access
the resource in read-mode simultaneously, but accessing the resource in
write-mode (e.g. modify a global variable) should be only possible if there
are no locks at all (not even read-locks).

I have not found a way to achieve this.

Regards
Rudi

Arnold Hendriks

unread,
May 29, 2001, 5:19:51 PM5/29/01
to
Rudi Wiener <nojunk...@wiener.at> wrote:
> the resource in read-mode simultaneously, but accessing the resource in
> write-mode (e.g. modify a global variable) should be only possible if there
> are no locks at all (not even read-locks).

> I have not found a way to achieve this.

In some pthreads there is a readwrite mutex that does exactly that.
And the source code to both Win32 and pthread implementations for
readwrite mutexes can be found in several places on the web.

--
Arnold Hendriks <a.hen...@b-lex.com>
B-Lex Information Technologies, http://www.b-lex.com/

Dave Butenhof

unread,
May 30, 2001, 7:44:07 AM5/30/01
to
Rudi Wiener wrote:

The UNIX 98 standard (and the forthcoming POSIX 1003.1-2001 standard) includes
POSIX read-write lock interfaces. You'll find these interfaces implemented (at
least) on AIX 4.3.x, Solaris 8, Tru64 UNIX 5.0, and any moderately recent
version of Linux. Earlier versions of Solaris and Tru64 UNIX also provided
different nonstandard interfaces for read-write locks.

/------------------[ David.B...@compaq.com ]------------------\
| Compaq Computer Corporation POSIX Thread Architect |
| My book: http://www.awl.com/cseng/titles/0-201-63392-2/ |
\-----[ http://home.earthlink.net/~anneart/family/dave.html ]-----/

Nils Antonsen

unread,
May 31, 2001, 8:49:39 AM5/31/01
to

"Dave Butenhof" <David.B...@compaq.com> schrieb im Newsbeitrag
news:3B14DD07...@compaq.com...

> The UNIX 98 standard (and the forthcoming POSIX 1003.1-2001 standard)
includes
> POSIX read-write lock interfaces. You'll find these interfaces implemented
(at
> least) on AIX 4.3.x, Solaris 8, Tru64 UNIX 5.0, and any moderately recent
> version of Linux. Earlier versions of Solaris and Tru64 UNIX also provided
> different nonstandard interfaces for read-write locks.

I guess these implementations will take care of classic problems like
starvation of the writer, don't they?

I enjoyed the discussion about how to implement condition variables in
Win32. What would the windows implementation of these read-write lock
interfaces look like?

regards Nils

Alexander Terekhov

unread,
May 31, 2001, 11:24:52 AM5/31/01
to
Nils Antonsen wrote:

> I guess these implementations will take care of classic problems like
> starvation of the writer, don't they?

http://www.opengroup.org/onlinepubs/007908799/xsh/pthread_rwlock_rdlock.html

"Implementations are allowed to favour writers over readers to
avoid writer starvation. "

> I enjoyed the discussion about how to implement condition variables in
> Win32. What would the windows implementation of these read-write lock
> interfaces look like?

for example (version w/o condition variables and with
"no read/write preference" policy; pseudo-code):

---------- Algorithm 1a / IMPL_SEM ----------

given:
mtxEntryLock - mutex or CS (or bin.semaphore/auto-reset event)
mtxReadExitLock - mutex or CS (or bin.semaphore/auto-reset event)
semWriteAccessGranted - bin.semaphore (or auto-reset event)
nReadEntryCount - int
nReadExitCount - int
nReadTriedCount - int
nWriteAccessCount - int

rdlock() {

[auto: register int result] // error checking omitted
// code for recursive readlocks
omitted
lock( mtxEntryLock );

if ( INT_MAX == ++nReadEntryCount ) {
lock( mtxReadExitLock );
nReadEntryCount -= nReadExitCount;
nReadExitCount = 0;
unlock( mtxReadExitLock );
}

unlock( mtxEntryLock );

return result;
}

tryrdlock() {

[auto: register int result] // error checking omitted
// code for recursive readlocks
omitted

lock( mtxReadExitLock );

//!!! RACE CONDITION WITH RESPECT TO nWriteAccessCount
//!!! harmless under Win32 (atomic int store/load)
if ( nWriteAccessCount > 0 || // writer holds the rwlock
nReadExitCount < 0 ) { // writer blocked on rwlock
unlock( mtxReadExitLock );
return EBUSY;
}

nReadTriedCount++;

unlock( mtxReadExitLock );

return result;
}

wrlock() {

[auto: register int result] // error checking omitted

lock( mtxEntryLock );

if ( 0 == nWriteAccessCount ) {

lock( mtxReadExitLock );

if ( 0 != nReadExitCount ) {
nReadEntryCount -= nReadExitCount;
nReadExitCount = 0;
}

if ( 0 != nReadTriedCount ) {
nReadEntryCount += nReadTriedCount;
nReadTriedCount = 0;
}

if ( 0 != nReadEntryCount ) {

nReadExitCount = -nReadEntryCount;
nReadEntryCount = 0;
unlock( mtxReadExitLock )
sem_wait( semWriteAccessGranted );

}
else {
nWriteAccessCount = 1;
unlock( mtxReadExitLock )
}

}
else { // recursive write locking
nWriteAccessCount++; // via recursive mtxEntryLock
}
}

trywrlock() {

[auto: register int result] // error checking omitted

if ( EBUSY == trylock( mtxEntryLock ) ) {
return EBUSY;
}

if ( 0 != nWriteAccessCount ) {
unlock( mtxEntryLock );
return EBUSY;
}

lock( mtxReadExitLock );

if ( 0 != nReadExitCount ) {
nReadEntryCount -= nReadExitCount;
nReadExitCount = 0;
}

if ( 0 != nReadTriedCount ) {
nReadEntryCount += nReadTriedCount;
nReadTriedCount = 0;
}

if ( 0 != nReadEntryCount ) {
unlock( mtxReadExitLock );
unlock( mtxEntryLock );
return EBUSY;
}

nWriteAccessCount = 1;

unlock( mtxReadExitLock );

return result;
}

unlock() {

[auto: register int result ] // error checking omitted
[auto: register int bGrantWriteAccess]
// code for recursive readlocks
omitted

if ( 0 == nWriteAccessCount ) {
lock( mtxReadExitLock );
if ( 0 == nReadTriedCount ) {
if ( 0 == ++nReadExitCount ) {
nWriteAccessCount = 1;
bGrantWriteAccess = true;
}
else {
bGrantWriteAccess = false;
}
}
else {
nReadTriedCount--;
bGrantWriteAccess = false;
}
unlock( mtxReadExitLock );
if ( bGrantWriteAccess ) {
sem_post( semWriteAccessGranted );
}
}
else {
nWriteAccessCount--;
unlock( mtxEntryLock );
}
}

regards,
alexander.

David Schwartz

unread,
May 31, 2001, 5:58:55 PM5/31/01
to

Nils Antonsen wrote:

> I guess these implementations will take care of classic problems like
> starvation of the writer, don't they?

Nope. If you have some notion of "fairness" you want enforced, you need
to specifically ensure you have it.

DS

Dave Butenhof

unread,
Jun 1, 2001, 8:26:20 AM6/1/01
to
Nils Antonsen wrote:

> "Dave Butenhof" <David.B...@compaq.com> schrieb im Newsbeitrag
> news:3B14DD07...@compaq.com...
>
> > The UNIX 98 standard (and the forthcoming POSIX 1003.1-2001 standard)
> includes
> > POSIX read-write lock interfaces. You'll find these interfaces implemented
> (at
> > least) on AIX 4.3.x, Solaris 8, Tru64 UNIX 5.0, and any moderately recent
> > version of Linux. Earlier versions of Solaris and Tru64 UNIX also provided
> > different nonstandard interfaces for read-write locks.
>
> I guess these implementations will take care of classic problems like
> starvation of the writer, don't they?

Sure. If they want to. In whatever manner thought best by the designers. (Or in
whatever way the code happened to fall out if they didn't bother to think about
it.)

Even the POSIX standard read-write lock doesn't require any particular
preference between readers and writers. Which (if any) is "right" depends
entirely on the application. Preference for readers often results in improved
throughput, and is frequently better when you have rarely updated data where
the USE of the data is substantially more important than the updates. (For
example, the TIS read-write locks on Tru64 UNIX were developed specifically to
replace a completely broken attempt to do it using a single mutex in the libc
exception support code. It used the construct to manage access to the code
range descriptor list for stack unwinding; or to update it with a newly loaded
or generated code range. Read preference was appropriate, and sufficient.)

Write preference can be better when you don't care principally about
"throughput", or where multiple readers are really relatively rare; and where
operating on stale data is worse than having the readers wait a bit. (Or where
you simply cannot tolerate the possibility of a starving writer wandering the
streets.)

A generally good compromise is a modified FIFO where adjacently queued readers
are batched into a single wakeup; but that still constrains reader concurrency
over read preference and increases data update latency over writer preference.
Like all compromises, the intention is more to keep both sides from being angry
enough to launch retaliatory nukes, rather than to make anyone "happy". It does
avoid total starvation, but at a cost that may well be unacceptable (and
unnecessary) to many applications.

It wouldn't make sense for the standard to mandate any of those strategies.
Partly because none of them is "best" for everyone (or even for ANYone). Partly
because there are probably even better ideas out there that haven't been
developed yet, and it makes no sense to constrain experimentation until and
unless a clear winner is "obvious". (For example, had the standard specified a
strategy, it would have been either reader or writer, not "modified FIFO",
because the latter wasn't in wide use at the time.)

We considered a read-write lock attribute to specify strategy. We decided that
this would be premature. While we've advanced a bit in the intervening time, I
think it would still be premature. Though of course individual implementations
are welcome (and even encouraged) to experiment with such an attribute. If some
set of strategies become relatively common practice, the next update of POSIX
and UNIX (probably 2006) could consider standardizing it.

> I enjoyed the discussion about how to implement condition variables in
> Win32. What would the windows implementation of these read-write lock
> interfaces look like?

Probably already done, somewhere. Go look! I don't even want to THINK about it.
(But then, I feel that way about anything Windows-ish. Everyone, except
possibly Bill Gates, would be better off without Windows.)

Reply all
Reply to author
Forward
0 new messages