Re: Threads: rw_mutex design + sample implementation

From: dmoore99atwork (dmoore_at_[hidden])
Date: 2002-03-11 06:12:27

> 
>   This abdication of controlling the ordering of writers
> versus readers is thoroughly unacceptable, because a
> sustained influx of frequent read-operations forever may
> starve out write-operations forever.  A  general-purpose
> rwmutex should permit explicit control over 4
> read versus write preferences:

While providing -only- an unspecifed SchedulingPolicy rw_mutex may be 
throroughly unnacceptable to many users of the Boost.Threads library, 
it is directly analagous to providing a "plain" mutex type which 
offers no guarantees in a standardese sense, but may provide in 
actual fact a fair and fast scheduling policy on a particular 
platform.

I can provide stonger language in the documentation as to the 
possible dangers of this scheduling mechanism.
 
>   1) strictly prefer (infrequent) write-operations over
> (frequent) read-operations when readers & writers are at the
> same thread-priority

This is documented in rw_mutex_concepts.html as the WriterPriority 
scheduling policy.  I agree that offering this in a final version of 
the library is important.

 
>   2) strictly prefer (infrequent) read-operations over
> (frequent) write operations when readers & writers are at
> the same thread-priority

This is documented in rw_mutex_concepts.html as the ReaderPriority 
scheduling policy.  I agree that offering this in a final version of 
the library is important.
 
>   3) interleave reads & writes by preferring a
> write-operation then permitting all queued up
> read-operations to complete then prefer write-operation and
> so forth, where readers & writers are at the same
> thread-priority.  In this case there would be a burst of
> read-permissions granted concurrently, then the exclusive
> write, followed by a burst of read-permissions granted
> concurrently, then the exclusive write.
> 
>   4) interleave reads & writes by preferring a
> write-operation then permitting a single read-operation to
> complete then prefer write-operation and so forth, where
> readers & writers are at the same thread-priority.  In this
> case multiple read-permissions would be granted concurrently
> only if there were no write-requests waiting.

These are both refinements of the AlternatingPriority documented in 
rw_mutex_concepts.html.  I agree that offering some form of this in a 
final version of the library is important.

>   Note that controlling write-preference versus
> read-preference is controlling the order of *sets* of
> threads.  First of all, an rwmutex would categorize threads
> into two categories: the set R of threads requesting
> read-permission versus the set W threads requesting
> write-permission versus the set G threads to which
> permission has already been granted (and which
> permission---read or write---the threads in G have been
> granted).  Second, an rwmutex would grant permission to all
> of each of the threads in W sequentially before granting
> permission to any/all of the threads in R (choice #1 above);
> or an rwmutex would grant permission to all of the threads
> in R before granting permission to any of the threads in W
> (choice #2 above); or an rwmutex would methodically
> alternate preference of R and W like a pendulum swings back
> & forth to eliminate any possibility of starvation (choices
> #3 and #4 above).
> 
>   Note that controlling the order of granting permission to
> threads within R is not what is being discussed here in this
> per-set preference.  (That per-individual-thread ordering
> would be discussed in the topic of "strong rwmutex" which is
> able to make strong guarantees that order of read-request
> implied order of read-grant.)  Note that controlling the
> order of granting permission to threads within W is not what
> is being discussed here in this per-set preference.  (That
> per-individual-thread ordering would be discussed in the
> topic of "strong rwmutex" which is able to make strong
> guarantees that order of write-request implied order of
> write-grant.)

In rw_mutex_concept.html, I refer to these concepts as "inter-
request" (R vs. W) priority and "intra-request" priorities (within 
R).  I think that labeling the groups as you suggest may make this 
more clear.

>   Intrinsic in these 3 choices is that the preference
> applies only to threads with the same thread-priority
> metric.  If a lower-priority thread acquires an exclusive
> lock (i.e., the superior write lock in rwmutex), then
> higher-priority threads request a shared lock (i.e., the
> inferior read lock in rwmutex), then in many environments
> (e.g., RTOSes, DBMSes) the over-all system can enter a state
> where the lower-priority thread is never scheduled to run
> and the higher-priority threads all block due to their
> inferior lock requests, waiting for this never-scheduled
> lower-priority thread to release its superior lock.  In some
> system-states, the lower-priority thread will never be
> scheduled to execute and thus will never be able to get
> around to executing the code which releases its superior
> lock.  Thus a deadlock situation occurs.  This case is
> called priority inversion.

This very case is my motivation behind documenting in rw_mutex.html 
that the underlying mutex controlling exclusive access is a 
parameterized type so that users on these platforms can select an 
appropriate mechanism for providing the exclusive lock.

>   Thus not only must rwmutex be aware of write-preference
> versus read-preference versus interleaved-preference.
> Rwmutex must also be aware of thread-priority when granting
> locks, possibly including adjusting thread-priorities up or
> down (depending on implementation & operating system) and/or
> aborting transactions on lower-priority threads.

No more so than an ordinary mutex would have to be aware of such a 
problem, right?

>   The deadlock and abort-transaction concepts must be fully
> analyzed and fleshed out before rwmutexes (or any other
> categorized lock) can be accepted into Boost.

I hope to generate plenty of feedback and that the strongest possible 
design is accepted into Boost.

>   I deliver a stern & harsh warning to anyone thinking of
> using this class in its current state: DO NOT USE THIS
> RWMUTEX CLASS UNTIL THE DEADLOCK CASES IDENTIFIED IN MY/THIS
> POSTING ARE INVESTIGATED & ADDRESSED.  YOUR MULTITHREAD
> SOFTWARE MAY SPONTANEOUSLY LOCK UP DUE TO DEADLOCK, WHERE
> RWMUTEX IN ITS CURRENT DESIGN & IMPLEMENTATION NEITHER
> DETECTS NOR CORRECTS SUCH DEADLOCKS.

I certainly hope that no one would use a prototype implementation 
tested on only one platform in the "real world!"  I won't be.  It is 
my belief that the implementation provided is only as "unsafe" 
against deadlock as the underlying mutex on a particular platform.  
In actual practice, if the underlying Mutex is basically FIFO, this 
rw_mutex will be basically FIFO.  But, that's why I called it 
Unspecified Scheduling priority.

 
>   Let's define "tricky".  Here "tricky" is not merely a
> little bit of more complexity here & there in the
> implementation.  Rather "tricky" in fact is deadlock
> detection & correction.  (And "deadlock correction" in this
> case involves one of the aforementioned techniques: aborting
> a transaction.)
> 
> 
>   [ PRESENCE OF UPGRADABILITY IN RWMUTEX CAUSES DEADLOCK ]
> 
>   For example, thread r1 acquires a read lock on datum d at
> time t1.  Thread r2 acquires a read lock on d at time t2
> while r1 still holds its previously-granted read lock on d.
> Thread r1 decides that it in fact needs a write-lock on d
> (or a function f1 needing write-access to d is called in r1
> where f1 has no idea that a read-lock on d has already been
> acquired by one of its callers which is quite common) at
> time t3 while r2 still holds its read-lock on d.  Note that
> r1's write-upgrade blocks on the read-lock on d which r2
> still holds.  Thread r2 decides that it in fact needs a
> write-lock on d (or a function f2 needing write-access is
> called in r2 where f2 has no idea that a read-lock on d has
> already been acquired by one of its callers).  Note that
> r2's write-upgrade blocks on the read-lock on d which r1
> still holds.  This is hard deadlock.  As long as rwmutex is
> used (instead of mutex) and as long as read-locks are
> upgradable to write-locks, no amount of a priori analysis of
> system-state & scheduling will completely eliminate this
> series of events transpiring in the way given as a thorny
> example here.  Thus if upgradability of read-locks to
> write-locks exists, then deadlocks may occur in certain
> system-states.  These deadlocks must be detected and
> corrected for upgradable locks to work correctly all of the
> time.

Yes, that is a much better defininiton of "tricky". (ha)  Thanks!

> 
>   [ ABSENCE OF UPGRADABILITY IN RWMUTEX CAUSES DEADLOCK ]
> 
>   For example, thread r0 acquires a read-lock on datum d.
> Then r0 calls function f10 which in turn calls function f11
> which in turn calls function f12 which in turn calls
> function f13 which in turn calls function f14 which in turn
> calls function f15 which in turn calls function f16 which in
> turn calls function f17 which in turn calls function f18
> which in turn calls function f19.  Function f19 needs a
> write-lock on d.  Thus, f19 attempts to acquire a write-lock
> on d despite the fact that a read-lock on d already has been
> granted to r0.  Thus r0 deadlocks on r0 because 1) r0's
> write-request in f19 will wait until r0's already-granted
> read-lock is released; 2) r0's read-lock will never be
> released because f19 will never return.  Without
> upgradability, the resolution to this
> deadlock-by-(accidental-)design is for r0 to acquire a
> write-lock initially instead of read-lock.
> 
>   As another example, thread w0 acquires a write-lock on
> datum d.  Then w0 calls function f20 which in turn calls
> function f21 which in turn calls function f22 which in turn
> calls function f23 which in turn calls function f24 which in
> turn calls function f25 which in turn calls function f26
> which in turn calls function f27 which in turn calls
> function f28 which in turn calls function f29.  Function f29
> needs a read-lock on d.  If the implementation of rwmutex
> considers w0's read-request as any garden-variety
> read-request as rwmutex would if the read-request were
> instead from another/non-w0 thread, then w0 will deadlock on
> w0 because 1) w0's read-request in f29 will wait until w0's
> already-granted write-lock is released; 2) w0's write-lock
> will never be released because f19 will never return.  [This
> case is more lock-convertability (write implies read)
> instead of upgradability, but, since deadlocks are possible
> in certain implementations, this case must be called out so
> that it is handled correctly.]
 

Actually, I consider this case to be solved by the template parameter 
to rw_mutex which allows the user to select the underlying exclusive 
lock mechanism.  For maximum portability, rw_mutex should use a mutex 
which can be locked recursively mutex by default, perhaps.  This 
would avoid this particular brand of deadlock where r0 or w0 would 
block themselves in trying to re-acquire the lock.  Or, this is 
certainly a detectable case, and exceptions/abort type techniques can 
be used to prevent it as you say.

> > 3. It would be nice to be able to use scoped_lock with
> > rw_mutex, and be able to use scoped_rw_lock with mutex....
> > There are times during application design & testing where
> > it is nice to be able to experiment with swapping a mutex
> > for a rw_mutex, to see if the rw_mutex is truly needed.
> > It would be nice if scoped_rw_lock<mutex> would just
> > lock() the mutex even if a sharedlock() was requested, and
> > if scoped_lock<rw_mutex> would always just call lock() on
> > the rw_mutex.  It seems that some solution involving
> > lock_ops() is possible, but I'd like more input on this.
> >
> > Dave
> 
>   If some interchangability is desired between mutex and
> rwmutex, then I recommend that the application-domain
> engineer write a class called, say, "Synchronization" (and
> Synchronization::Guard) in that engineer's own source code
> which ricochets to either mutex or rwmutex depending on that
> engineer's current whim.  I recommend against polluting the
> interfaces of either mutex or rwmutex or both to accomplish
> some sort of source-code switcheroo for the purpose of
> experimenting.  A mutex is what it is.  An rwmutex is what
> it is.  Neither should be forced to be the other.  If the
> engineer wishes to experiment, the application engineer
> needs an application-domain laboratory class in which to
> conduct these experiments.  Neither Boost nor the C++0x
> standard libraries should be (forced to be) that engineer's
> laboratory.

I think that's a fair point.  I wouldn't want a mutex implementation 
to have a useless "sharedlock()" function just to support that 
functionality.  An application-domain version of the 
shared_lock/lock_ops classes is more appropriate.

Thanks for the feedback!
Dave