Boost logo

Boost :

From: Alexander Terekhov (terekhov_at_[hidden])
Date: 2004-07-06 04:02:11


Howard Hinnant wrote:

Read this thread:

http://groups.google.com/groups?threadm=ijnd7a.3pb.ln%40tux.localdomain
(Subject: upgradeable lock)

I've quoted below a few bits.

> read_lock to write_lock promotion is not atomic.

Butenhof:

IF one allows only one "upgradeable reader", (UR) as a special type of
access (as he suggested), you certainly could make the guarantee. You can
allow the single UR concurrent access with any number of readers. When the
UR requests upgrade, it releases its read access and in effect becomes the
HEAD of the writer queue. Once all readers have released (there's still no
chance that the data could have been modified from the state last observed
by the UR), the waiting UR must be immediately granted write access and
scheduled to run.

Normally, one is better off making a RW lock behave like normal POSIX
mutexes, where awakened waiters compete equally with running threads for
access. (Rather than forced "FIFO" ownership that, like Ada rendezvous,
causes completely wasted context switches.) In this case, though, we can't
do that because the UR would lose atomicity. That's a BIG inefficiency.
You'd really be better off breaking the atomicity guarantee and requiring
the UR to re-evaluate the data after it gains write access. In which case
you can allow multiple upgradeable readers. However it also means there's
no longer any point to allowing upgrade... you might as well just release
the read lock and contend normally for a write lock. Which is precisely why
"upgrade" isn't in POSIX.

>
> Once that is understood, the programmer can just deal with it. Trying
> to encapsulate this bit of reality only serves to obfuscate the
> necessary logic.

Me:

[...] how about the following "extensions":

a) ability for a reader to request a write-upgrade with an
   indication whether it ended up being "atomic" or not.

b) upgrade operation could either result in a "write"
   ownership always or (optionally) in "read-again ;-)",
   if it ended up being non-atomic.

c) ability for a writer to query whether some
   upgrades are pending -- that would allow some
   extra "optimizations" (basically he could then
   keep track of updated/invalidated stuff, to allow
   *conditional* re-calcs for non-atomic upgraders),
   I think.

Butenhof:

Yes, if you treat upgradeability as an "optimization" on which nobody can
ever depend. Any reader can request upgrade, and one of the readers may be
granted an atomic upgrade while the others need to re-evaluate. Very
dangerous, in my opinion, because it'd be trivially easy to write bad code
that'll be really hard to test. You're adding a weird beastie: an
"alternate success" status that's not really an error. "You got it; but
it's not what you may think." What would we call it? EALMOST? Or maybe
EYOUASKEDFORITBUTYOUDIDNTGETIT?

Actually, you'd be better off with a "request upgrade" that'd either
convert or return failure leaving the caller with read access. This fits
much better with the normal UNIX "do this or fail without changing
anything" model.

And, OK, one could deal with the naming issues. Documentation, though,
would be easily misunderstood. (That MUST be a prime concern in the design
of any interface.) And, in the end, what do you have? Every call site that
requests upgrade MUST be able to handle either return, but there's no way
to predict for sure whether any given call will succeed or "not quite
succeed". Easy to misunderstand and misuse, tough to test. Bad combination.

The query operation sounds like an invitation to even greater screwups, to
me. More complication, harder to test... for very little added value.

Me:

Well, I guess that one could argue that the whole
read/write locking concept is just an "'optimization'
on which nobody can ever depend". ;-)

Butenhof:

Well, yes, given the looseness of definitions to allow experimentation in
read/write preference, and all that, it's true that the actual guarantee
for concurrent read access is slim at best. (In fact, it provides for an
"implemention defined" limit on concurrent readership, and there's nothing
to prevent an implementation from defining that to the value "1".)

regards,
alexander.


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk