Re: Threads: rw_mutex design + sample implementation

From: danl_miller (danl_miller_at_[hidden])
Date: 2002-03-10 23:43:31

--- In boost_at_y..., "dmoore99atwork" <dmoore_at_a...> wrote:
> I have uploaded design documentation as well as a
> prototype implementation for reader/writers locks to the
> file library:

> 
> http://groups.yahoo.com/group/boost/files/thread_rw_lock.zip
> 
> The design allows for a number of scheduling policies
> between readers and writers.  The prototype implementation
> uses a pair of mutexes and a condition variable and
> derives directly from that used for pthreads- win32.  The
> boost::mutex used for internal state mutual exclusion and
> tends to favor a new writer if only readers are currently
> holding a lock.  If readers and writers are waiting, the
> ordering falls back to the ordering of the underlying
> mutex.

  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:

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

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

  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.

  [If only one of the four choices is provided by a
less-flexible rwmutex, then that single mode-of-operation in
practice most frequently is strictly-prefer-write, but
either of the interleaved choices is probably a better
single mode-of-operation to completely eliminate the
possibility of both write-starvation and read-starvation,
regardless of the frequency of read-operations versus the
frequency of write-operations.]

  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.)

  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.

  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.

  All of these issues must be addressed for an rwmutex
implementation to not be dangerous to use.  Because safe
rwmutexes are hard to find and hard to design/implement,
that so many engineers use mutexes (on uniprocessor
architectures) and spinlocks (on multiprocessor
architectures) for most real-time embedded software, the
industry where multithread software has been around for
decades.  Based on my observation only database-management
systems have invested the effort to properly solve the
entire categorized lock problem.  Rwmutexes are merely one
type of categorized lock.  In the database world, instead of
merely read/shared versus write/exclusive, database
management systems often have a SIX-lock: S=shared,
X=exclusive, IX=intention-to-have-exclusive,
IS=intention-to-have-shared, and
SIX=shared-plus-intention-to-have-exclusive.  But the
database world typically has very rich semantics regarding
transactions and abort-transation to handle the
upgradability of locks from IX to X, from IS to S, from S to
SIX, from IX to SIX, and from SIX to X, where aborting
transactions is one of the primary weapons in the
deadlock-correction arsenal.  In C++, exceptions are the
closest thing to an abort-transaction mechanism.
  

  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 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.

> Comments and feedback of any nature are welcome, but I am
> especially interested in hearing other's views on:
>
> 1. Reader "promotion" to writer status w/o releasing the
> lock.  To me, this is only safe when the promotion is
> treated as a try and return, a la boost::try_mutex.  If you
> let a promotion request block, then any other promotion
> request can lead to deadlock, or complex queuing is
> required.  With the prototype implementation, adding
> promotion to try_rw_mutex is straightforward.  Adding it
> elsewhere is tricky...

  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.

  [ 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.]

> 2. Naming of rw_mutex.  Everyone else calls them rw_locks,
> but that seemed to conflict with the scoped_lock family of
> concepts/classes, so I tried to avoid it.  I have no
> problem renaming it to rw_lock, though.

  Not "everyone" calls them rwlocks.  ACE calls them
RW_Mutexes (and RW_Thread_Mutex and RW_Process_Mutex).

  I agree that rwlock is a drastically
much-more-widely-accepted term than rwmutex.  I agree that
it is unfortunate that Boost.Threads library (e.g., mutex)
uses the term "lock" where "guard" is more common/accepted
(e.g., ACE, RogueWave Threads.h++, the threads module of
RogueWave SourcePro Core).  If Boost.Threads library had
used the term "guard" where it uses "lock", then, yes, this
unfortunate terminology collision would not have occurred.
Bill Kempf, are you interested in changing "lock" to the
more common "guard" in Boost.Threads' mutex for the case of
ctor-is-resource-acquisition & dtor-is-resource-release?

  reference to ACE's multithread/multiprocess concurrency
  http://www.cs.wustl.edu/~schmidt/PDF/ACE-concurrency.pdf

  reference to RogueWave's threads module in SourcePro Core
(formerly Threads.h++)
  http://www.roguewave.com/support/docs/SourcePro/threadsref/II.cfm

> 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.