###  | # Boost.Threads ## Mutex Concepts

Introduction
Locking Strategies
Recursive
Checked
Unchecked
Unspecified
Scheduling Policies
FIFO
Priority Driven
Undefined
Unspecified
Concept Requirements
Mutex Concept
TryMutex Concept
TimedMutex Concept
Models

## Introduction

A mutex (short for mutual-exclusion) concept serializes access to a resource shared between multiple threads. The Mutex concept, with TryMutex and TimedMutex refinements, formalize the requirements. A model that implements Mutex and its refinements has two states: locked and unlocked. Before using a shared resource, a thread locks a Boost.Threads mutex model object, insuring thread-safe access to 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.

Traditional C thread APIs, like Pthreads or the Windows thread APIs, expose functions to lock and unlock a mutex model. This is dangerous since it's easy to forget to unlock a locked mutex. When the flow of control is complex, with multiple return points, the likelihood of forgetting to unlock a mutex model would become even greater. When exceptions are thrown, it becomes nearly impossible to ensure that the 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 mutexes. With this pattern, a lock concept is employed where the lock model's constructor locks the associated 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 mutex model: lock and unlock functions are not exposed by any Boost.Threads mutex models. This helps to ensure safe usage patterns, especially when code throws exceptions.

## Locking Strategies

Every 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 mutex model.

### Recursive

With a recursive locking strategy when a thread attempts to acquire a lock on the mutex model for which it already owns a lock, the operation is successful. Note the distinction between a thread, which may have multiple locks outstanding on a recursive mutex, and a lock object, which even for a recursive mutex cannot have its lock() function called multiple times without first calling unlock().

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_mutex, recursive_try_mutex and recursive_timed_mutex use this locking strategy.

### 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. 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 mutex models that use this strategy.

### Unchecked

With an unchecked 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 deadlock. In general this locking strategy is less safe than a checked or recursive strategy, but it's also a faster strategy and so is employed by many libraries.

Boost.Threads does not currently provide any mutex models that use this strategy.

### Unspecified

With an unspecified locking strategy, when a thread attempts to acquire a lock on a mutex model for which the thread already owns a lock the operation results in undefined behavior. When a mutex model has an unspecified locking strategy the programmer must assume that the mutex model instead uses an unchecked strategy.

In general a mutex model with an unspecified locking strategy is unsafe, and it requires programmer discipline to use the 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 mutex, try_mutex and timed_mutex use this locking strategy despite the lack of safety.

## Scheduling Policies

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

### FIFO

With a FIFO scheduling policy, threads waiting for the lock will acquire it in a first come first serve order (or First In First Out). This can help prevent a high priority thread from starving lower priority threads that are also waiting on the mutex lock.

### Priority Driven

With a Priority Driven scheduling policy, the thread with the highest priority acquires the lock. Note that this means that low-priority threads may never acquire the lock if the mutex model has high contention and there is always at least one high-priority thread waiting. This is known as thread starvation. When multiple threads of the same priority are waiting on the mutex lock one of the other scheduling priorities will determine which thread shall acquire the lock.

### Undefined

Threads acquire the lock in no particular order. Users should assume that low-priority threads may wait indefinitely, and that threads of the same priority acquire the lock in essentially random order.

### Unspecified

The mutex model does not specify which scheduling policy is used. The programmer must assume that an undefined scheduling policy is used. In order to ensure portability, all Boost.Threads mutex models use an unspecified scheduling policy.

## Concept Requirements

### Mutex Concept

A Mutex object has two states: locked and unlocked. Mutex object state can only be determined by an object meeting the ScopedLock requirements and constructed for the Mutex object.

A Mutex is noncopyable.

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

Expression | Effects
`M m;` | Constructs a mutex object m. Post-condition: m is unlocked.
`(&m)->~M();` | Precondition: m is unlocked. Destroys a mutex object m.
`M::scoped_lock` | A type meeting the ScopedLock requirements.

### TryMutex Concept

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

Expression | Effects
`M::scoped_try_lock` | A type meeting the ScopedTryLock requirements.

### TimedMutex Concept

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

Expression | Effects
`M::scoped_timed_lock` | A type meeting the ScopedTimedLock requirements.

## Models

Boost.Threads currently supplies six classes which model mutex concepts.

Concept | Refines | Classes Modeling the Concept
Mutex |  | mutex recursive_mutex
TryMutex | Mutex | try_mutex recursive_try_mutex
TimedMutex | TryMutex | timed_mutex recursive_timed_mutex

Revised 01 October, 2001

© Copyright William E. Kempf 2001 all rights reserved.