[boost] Re: Boost.Threads: Do we need all those mutexes?

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.