[threads] mutex observable behaviour (more concepts...)

From: John Maddock (John_Maddock_at_[hidden])
Date: 2000-08-15 06:20:13

I've been reading through the material produced by Jeremy and Deitmar
(covering various mutex concepts) and believe that there are a few missing.
 I've put together a short document that covers what could be described as
"concepts that effect the observable behaviour of a mutex", and placed this
in the vault at 
http://www.egroups.com/files/boost/threads/lock_semantics.htm (is this the
right place for this stuff?).  For ease of access, a plain text version is
attached below (although the html version is a lot easier to read IMO)

- John.

********************************************
lock_semantics.htm
********************************************

Thread locking semantics
Copyright John Maddock 2000

The following short paper is intended to supplement the material already
put forward by Dietmar Kuehl and Jeremy Siek, although for the sake of
completeness there may be some overlap. The following list is intended to
define the various properties that a mutex can have, many of these
properties are also applicable to condition-variables and other
synchronisation primitives. The intent is that this list can be used as the
basis of a feature diagram, or as a "specification list" for a particular
mutex implementation. It would also be useful to construct a table of
native locking primitives and which (if any) of the following concepts they
support. In addition the following concepts can be tested at run-time, at
some stage there should be a test suite that verifies that the stated
behaviour of a locking primitive matches its observable behaviour. This is
particularly important when a primitive is being ported to a new platform,
possibly using combinations of platform-native primitives to emulate the
required behaviour.

Recursion: A mutex is recursive if it can be acquired by a thread that
already owns the mutex, without blocking. Recursive mutexes need to be
released the same number of times that they are acquired. 

Statically initialised: If a mutex can be statically initialised then it
must be an aggregate type, and have a well defined initialiser-list that
can be used to initialise the mutex before any user code runs in the
process. Statically initialised mutexes greatly simplify process start-up
code, but generally have limited functionality. The initialiser-list may be
a macro (as in PTHREAD_MUTEX_INITIALIZER for example), or an empty
initialiser list, in which case all the data members of the mutex are
default initialised. 

Priority inversion: Imagine that a thread T1 is blocked by a mutex owned by
thread T2 with a lower priority. Depending upon the how threads are
scheduled by the process, thread T1 may starve T2 of processor time thereby
creating a deadlock. For many native locking primitives priority inversion
involves suspending the waiting thread until the mutex becomes available,
however other strategies are available including priority inheritance and
priority ceilings. This also becomes an issue when a the behaviour of a
locking primitive is being emulated on a particular platform - particular
care need to be taken to ensure that high priority threads waiting on the
lock do not starve the lock's owner of processor time. 

Priority inheritance: This one way of dealing with priority-inversion. In
this case the priority of a thread owning the mutex is the greater of its
own priority, and of the highest priority of all the threads waiting on the
mutex. 

Priority ceiling: Another way of dealing with priority inversion. In this
case, the thread owning the mutex has its priority set to the greater of
its own priority, and the value of the priority ceiling of the mutex; in
other words all threads that take ownership of the mutex have their
priority boosted to at least the value of the mutex's priority ceiling. 

Process sharable: If a mutex is process sharable then it is accessible to
all processes running on the machine, not just the current process.
Differing platforms deal with this in different ways: Win32 uses monikers
to name mutex handles, pthread's use pthread_mutex_t's constructed in
shared memory to achieve the same ends. Since all shared memory resides in
a named file on POSIX systems, there is some overlap between the two
approaches, however, note that native Win32 locking primitives can not be
constructed in shared memory, so portable implementations of this concept
are probably going to have to use a moniker based scheme. 

Scheduling strategy: If a mutex has more than one thread waiting on it when
it becomes unlocked, then the mutex's scheduling strategy determines which
of the waiting threads acquires the lock. There are three main strategies:
FIFO: threads waiting for the mutex to become available acquire the lock in
the same order that locking requests are made. This can help prevent a high
priority thread from starving lower priority threads that are also waiting
on the mutex. Priority driven: 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 has high contention and there is always at
least one high-priority thread waiting. 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. 

Non-blocking: A mutex is non-blocking if an attempt to acquire the lock
does not block the calling thread; either the lock is acquired or not, but
in either case control is returned immediately to the calling thread. If
the lock is not acquired then this probably does not constitute an
exceptional condition, however some method of dealing with a failed attempt
is required that is not prone to error-checking programming errors.
Non-blocking behaviour is almost always optional, the default behaviour is
normally to block indefinitely. 

Blocking timeout: A mutex is has a timeout, if an attempt to acquire the
lock will always return control to the calling thread within a specified
timeout. This is a similar concept to non-blocking, and has similar pros
and cons. Timeouts are almost always optional, the default behaviour is
normally to block indefinitely. 
Checking: This is really a debugging tool, but is supported natively by
some systems (including pthreads), so is worthwhile mentioning here. If a
lock performs checking then it will generate an error condition (probably a
C++ exception in this case) if an attempt is made to release a lock that
the calling thread does not own, or re-acquire a non-recursive mutex that
the thread already owns. 

Downward compatibilty
~~~~~~~~~~~~~~~
With the exception of the mutex's scheduling strategy, all of the features
described above are downwards compatible; that is a mutex that supports the
feature is compatible with one that is assumed not to support the feature.
This means that platform native primitives can be used to implement a
particular mutex type, provide they support at least the minimum feature
set specified for that mutex type.

Single-threaded processes
~~~~~~~~~~~~~~~~~~
For processes that have only one thread of execution, a stub "do nothing"
mutex implementation behaves "as if" all of the features above were
present; attempted locks always succeed, and there is no observable
behaviour that can be used to show otherwise.

 

---------------------------------------------------------------------------
-----

Revised 14th August 2000

© Copyright John Maddock 2000. Permission to copy, use, modify, sell and
distribute this document is granted provided this copyright notice appears
in all copies. This document is provided "as is" without express or implied
warranty, and with no claim as to its suitability for any purpose.