Boost.Threads

Introduction

Locking Strategies

Recursive

Checked

Unchecked

Unspecified

Scheduling Policies

Concept Requirements

Models

Introduction

A rw_mutex (short for reader-writer mutual-exclusion) concept serializes access to a resource shared between multiple threads, where multiple readers can share simultaneous access, but writers require exclusive access.  The RWMutex concept, with TryRWMutex and TimedRWMutex refinements, formalize the requirements. A model that implements RWMutex and its refinements has three states: shared-locked ,exclusive-locked and unlocked. Before reading from a  shared resource, a thread shared-locks a Boost.Threads rw_mutex model object, insuring thread-safe access for reading from the shared resource. Before writing to a shared resource, a thread exclusive-locks a Boost.Threads rw_mutex model object, insuring thread-safe access for altering the shared resource.  When use of the shared resource is complete, the thread unlocks the mutex model object, allowing another thread to acquire the lock and use the shared resource.

Some traditional C thread APIs like Pthreads provide implementations for rw_mutex (also known as reader-writer locks).  Others like Windows thread APIs do not provide a rw_mutex primitive.  Some of those APIs expose functions to lock and unlock a rw_mutex model. This is dangerous since it's easy to forget to unlock a locked rw_mutex. When the flow of control is complex, with multiple return points, the likelihood of forgetting to unlock a rw_mutex model would become even greater. When exceptions are thrown, it becomes nearly impossible to ensure that the rw_mutex is unlocked properly when using these traditional API's. The result is deadlock.

Many C++ threading libraries use a pattern known as Scoped Locking [Schmidt 00] to free the programmer from the need to explicitly lock and unlock rw_mutexes. With this pattern, a lock concept is employed where the lock model's constructor locks the associated rw_mutex model and the destructor automatically does the unlocking. The Boost.Threads library takes this pattern to the extreme in that lock concepts are the only way to lock and unlock a rw_mutex model: lock and unlock functions are not exposed by any Boost.Threads rw_mutex models. This helps to ensure safe usage patterns, especially when code throws exceptions.

Locking Strategies

Every rw_mutex model follows one of several locking strategies. These strategies define the semantics for the locking operation when the calling thread already owns a lock on the rw_mutex model.

Recursive

With a recursive locking strategy when a thread attempts to acquire an additional lock on the rw_mutex model for which it already owns a lock, the operation is successful, except possibly in the case where a shared-lock holding thread attempts to obtain an exclusive lock. 

Lock Type Held	Lock Request Type	Action
shared-lock	shared-lock	Grant the shared lock immediately
shared-lock	exclusive-lock	If this thread is the only holder of the shared-lock, grants the exclusive lock immediately.  Otherwise throws lock_error() exception.
exclusive-locked	shared-lock	Grants the (additional) shared lock immediately.
exclusive-locked	exclusive-lock	Grant the exclusive lock immediately

Internally a lock count is maintained and the owning thread must unlock the mutex model the same number of times that it's locked it before the mutex model's state returns to unlocked. Since mutex models in Boost.Threads expose locking functionality only through lock concepts, a thread will always unlock a mutex model the same number of times that it locked it. This helps to eliminate a whole set of errors typically found in traditional C style thread APIs.

Classes recursive_rw_mutex, recursive_try_rw_mutex and recursive_timed_rw_mutex will use this locking strategy.  Successful implementation of this locking strategy may require thread identification (see below).

Checked

With a checked locking strategy when a thread attempts to acquire a lock on the mutex model for which the thread already owns a lock, the operation will fail with some sort of error indication, except in the case of multiple shared-lock acquisition which is a normal operation for ANY RWMutex.  Further, attempts by a thread to unlock a mutex that was not locked by the thread will also return some sort of error indication. In Boost.Threads, an exception of type lock_error would be thrown in these cases.

Boost.Threads does not currently provide any rw_mutex models that use this strategy.  A successful implementation of this locking strategy would likely require thread identification.

Unchecked

With an unchecked locking strategy when a thread attempts to acquire a lock on the rw_mutex model for which the thread already owns a lock the operation will deadlock. In general this locking strategy is less safe than a checked or recursive strategy, but it can be a faster strategy and so is employed by many libraries.

Lock Type Held	Lock Request Type	Action
shared-lock	shared-lock	Grant the shared lock immediately
shared-lock	exclusive-lock	Deadlock
exclusive-locked	shared-lock	Deadlock
exclusive-locked	exclusive-lock	Deadlock

Boost.Threads does not currently provide any mutex models that use this strategy.  For RWMutexes on platforms that contain natively recursive synchronization primitives, implementing a guaranteed-deadlock can actually involve extra work, and would likely require thread identification.

Unspecified

With an unspecified locking strategy, when a thread attempts to acquire a lock on a rw_mutex model for which the thread already owns a lock the operation results in undefined behavior. When a rw_mutex model has an unspecified locking strategy the programmer must assume that the rw_mutex model instead uses an unchecked strategy as the worse case, although some platforms may exhibit a mix of unchecked and recursive behavior.

Lock Type Held	Lock Request Type	Action
shared-lock	shared-lock	Grant the shared lock immediately
shared-lock	exclusive-lock	Undefined, but generally deadlock
exclusive-locked	shared-lock	Undefined, but generally deadlock
exclusive-locked	exclusive-lock	Undefined, but generally deadlock

In general a rw_mutex model with an unspecified locking strategy is unsafe, and it requires programmer discipline to use the rw_mutex model properly. However, this strategy allows an implementation to be as fast as possible with no restrictions on its implementation. This is especially true for portable implementations that wrap the native threading support of a platform. For this reason, the classes rw_mutex, try_rw_mutex and timed_rw_mutex use this locking strategy despite the lack of safety.

An Aside - Thread Identification

RWMutexes can support specific Locking Strategies (recursive and checked) which help to detect and protect against self-deadlock.  Self-deadlock can occur when a holder of a locked RWMutex attempts to obtain another lock.  Given an implemention "I" which is susceptible to self-deadlock but otherwise correct and efficient, a recursive or checked implementation "Ir" or "Ic" can use the same basic implementation, but make special checks against self-deadlock by tracking the identities of thread(s) currently holding locks.  This approach makes deadlock detection othrogonal to the basic RWMutex implementaion. 

Alternatively, a different basic implementation for RWMutex concepts , I' (I-Prime) may exist which uses recursive or checked versions of synchronization primitives to produce a recursive or checked RWMutex while still providing flexibility in terms of Scheduling Policies.

Please refer to the Boost.Threads mutex concept documentation for a discussion of locking strategies.  The rw_mutex supports both the recursive and unspecified locking strategies.  RWMutexes are parameterized on a Mutex type which they use to control exclusive-locking and access to internal state.

Another Aside - Lock Promotion

RWMutexes can support lock promotion, where a mutex which is in the shared-locked state transitions to an exclusive-locked state without releasing the lock.  If this functionality is supported at all by Boost.Threads, it will only be through an explicit promote() operations.  Extra care must be taken to ensure that only one thread holding a shared lock can block awaiting promotion at any given time.  If more than one shared-lock holder is allowed to enter a blocked state while waiting to be promoted, deadlock will result since both threads will be waiting for the other to release their shared lock.

Scheduling Policies

Every rw_mutex model follows one of several scheduling policies. These policies define the semantics when the mutex model is unlocked and there is more than one thread waiting to acquire a lock. In other words, the policy defines which waiting thread shall acquire the lock.  For rw_mutex, it is particularly important to define the behavior when threads are requesting both shared and exclusive access simultaneously.  This will be referred to as "inter-class scheduling".  

For some types of inter-class scheduling, an intra-class scheduling policy can also be defined that will describe the order in which waiting threads of the same class will acquire the thread.

ReaderPriority

With ReaderPriority, any pending request for a shared lock will have priority over a pending request for an exclusive lock, irrespective of the current lock state of the rw_mutex, and irrespective of the relative order that the pending requests arrive.

WriterPriority

With WriterPriority, any pending request for an exclusive lock will have priority over a pending request for a shared lock, irrespective of the current lock state of the rw_mutex, and irrespective of the relative order that the pending requests arrive.

AlternatingPriority/ManyReads

With AlternatingPriority/ManyReads, reader or writer starvation is avoided by alternatively granting shared or exclusive access when pending requests exist for both types of locks.  Outstanding shared-lock requests are treated as a group when it is the "reader's turn"

AlternatingPriority/SingleReads

With AlternatingPriority/ManyReads, reader or writer starvation is avoided by alternatively granting shared or exclusive access when pending requests exist for both types of locks.  Outstanding shared-lock requests are services one at a time when it is the "reader's turn"

Current rw_mutex state	Request Type	Action
unlocked	shared-lock	Grant the shared lock immediately.
shared-locked	shared-lock	Grant the additional shared lock immediately, -IF- no outstanding requests for an exclusive lock exist.  If outstanding exclusive-lock requests exist, this lock will not be granted until at least one of the exclusive locks is granted and released.
exclusive-locked	shared-lock	Wait to acquire the lock until the thread holding the exclusive-lock releases its lock. If other outstanding exclusive-lock requests exist, exactly one shared-lock request will be granted before the next exclusive lock is granted.
unlocked	exclusive-lock	Grant the exclusive lock immediately.
shared-locked	exclusive-lock	Wait to acquire the lock until all threads holding shared locks release their locks.  If other exclusive-lock requests exist, this lock will be granted to one of them in accordance with the intra-request scheduling policy.
exclusive-locked	exclusive-lock	Wait to acquire the lock until the thread holding the exclusive lock releases its lock.   If other outstanding shared-lock requests exist, this lock can not be granted until exactly one shared-lock request is granted and released.  If other exclusive-lock requests exist, this lock will be granted in accordance with the intra-request scheduling policy.

Intra-Request Scheduling Policy

Please refer to the Boost.Threads mutex concept documentation for a discussion of mutex scheduling policies, which are identical to RWMutex Intra-Request scheduling policies.  The rw_mutex supports only the Unspecified intra-request scheduling policy.  That is, given a set of threads waiting for exclusive locks, the order (amongst themselves) in which they receive the lock is unspecified.

Concept Requirements

RWMutex Concept

A RWMutex object has three states: shared-locked, exclusive-locked, and unlocked. RWMutex object state can only be determined by an object meeting the ScopedRWLock requirements and constructed for the RWMutex object.

A RWMutex is noncopyable.

For a RWMutex type RWM, and an object m of that type, the following expressions must be well-formed and have the indicated effects.

TryRWMutex Concept

A TryRWMutex must meet the RWMutex requirements. In addition, for a TryRWMutex type RWM and an object m of that type, the following expressions must be well-formed and have the indicated effects.

TimedRWMutex Concept

A TimedRWMutex must meet the TryRWMutex requirements. In addition, for a TimedRWMutex type RWM and an object m of that type, the following expressions must be well-formed and have the indicated effects.

Models

Boost.Threads currently supplies three classes which model rw_mutex concepts.

Revised 05 November, 2001

© Copyright {{author}} 2002. All Rights Reserved.