Re: [Threads-devel] Mutexes

From: Matt Hurd (matt.hurd_at_[hidden])
Date: 2006-03-01 14:44:17

<snip>
> >> In C++, there are several primary usage scenarious for mutex objects:
> >>
> >> 1. Standalone, as an object of static storage duration at namespace or
> >> block scope.
> >>
> >> 2. As a class member, for a class object of static storage duration.
> >>
> >> 3. As a class member, for a class object created on the stack or heap.
> >>
> >> In each case, the mutex object is used to synchronize access to other
> >> objects at the same scope.
> >
> > Not always.  Different scoping is not that uncommon is practice I think.
>
> [snip examples]
>
> Ok. My main point here was the different scoping of the mutex, and the
> requirements that imposes.

Yes your cases capture > 95% of my code, but theres is an important 5% where 
performance and resource usage require the different scoping my examples 
suggest.

> > A common structure we should support to prevent deadlocks is the idea of
> > a group of mutexes for simulataneous locking.  Deadlock is guaranteed not
> > to occur if they are always accessed in the same order.  Enforcement of
> > ordered access will prevent deadlock, a noble goal.
>
> That would be useful. Something akin to the Win32 API
> WaitForMultipleObjects?

Doesn't have to be that complicated, but similar in some respects in terms of 
operating on a group of things.  

A simple vector of mutexii where ownership is requested could just acquire 
them in index order.  Or a vector of references to mutexes where the 
addresses are compared and they are acquired in arbitrary but consistent 
order (comparing addresses with < is not really standard compliant I think 
(Dave?) but would work on all the platforms I know of).  You could prepare 
such a structure with a preliminary sort...  This idea is worth pursuing as 
it would guarantee no deadlocks for all use (where they are recursive) which 
is a bit of dream.

> >> It is essential that the mutex be correctly initialized by the time the
> >> first thread attempts to lock it. For objects of static storage
> >> duration, this requires that the mutex can be initialized with a static
> >> initializer, and not rely on dynamic initialization, since dynamic
> >> initialization exposes the possibility of race conditions.
> >
> > Static mutexes are really handy and very annoying due to the static
> > syntax messiness of their static initialisation requirements.  It would
> > be nice if there were some syntax sugar that lead to their safe
> > concurrent
> > initialisation at start-up.  The syntax you suggest below of the pthread
> > like BOOST_MUTEX_INITIALIS(Z)ER is good.  It is necessary to support this
> > as the initialisation can then be at compile time and end up as a zero in
> > the executable image for example.  The messiness of always needing
> > external initialisation of the static to the class and therefore cpp
> > location or an anonymous namespace trick makes me wonder if a
> > registration process/macro where all the static mutexes get initialise in
> > a one off singleton object on start up might be neat... Dunno.
>
> Singletons aren't ideal, so I'd rather not go there.

Static mutexes are useful yet cumbersome.  I wish I could think of a nicer 
solution to their initialisation at the point of declaration.

<snip>
>>
> >> Therefore, I suggest that the most straightforward way to deal with
> >> destruction order race conditions is for the mutex objects to have no
> >> destructors (which is consistent with being POD).
> >
> > This is unacceptable I feel because of the resource consumption issues on
> > some platforms.
>
> What did you have in mind? I'm only suggesting this for mutexes with static
> storage duration, which therefore have a lifetime equal to that of the
> program. All POSIX OSes I know, and Windows, all reclaim their mutexes at
> program termination, so there's not a lot of point explicitly freeing them
> just beforehand, and exposing the consequent race conditions.

yes there is.  some systems are resource constrained and mutexes are 
resources.  you simply must free them.  waiting till program termination is 
not an option.  My memory of windows 95 land is that they are system 
resources which are finite and valuable.

> >> When I last looked at this, I named the basic_mutex version
> >> lightweight_mutex, and had a discussion about it with Roland. The
> >> earlier version is still in CVS, but is no longer used for boost::mutex.
> >> I believe the current version is marginally simpler, and also
> >> boost::detail::lightweight_mutex is a name used by the shared_ptr
> >> implementation, which is why I have changed it to basic_mutex. The old
> >> implementation has been left in, as I haven't yet changed my
> >> implementation of read_write_mutex, which uses it.
> >>
> >> One of Roland's concerns was that this essentially duplicates
> >> CRITICAL_SECTION functionality.
> >
> > Nothing wrong with that a critical section is a mutual exclusion
> > guarantee.
>
> Yes, but I think Roland's point was "why not then use a CRITICAL_SECTION?",
> which I address below.
>
> >> The next challenge is timed_mutex --- this cannot be written as an
> >> extension of the current scheme, since that would expose a race
> >> condition. I might have to revert to my lightweight_mutex scheme for
> >> that.
> >
> > Hmmm, the mutex isn't timed.  The lock is timed, or rather, the attempt
> > to lock is timed.  Important difference.
>
> Absolutely, though the current boost interface uses boost::timed_mutex to
> mean a mutex that supports timed_lock operations. I think the interface
> could do with changing here, if only to give things better names.
>
> My current implementation of basic_mutex doesn't support timed_lock
> operations, whereas my old lightweight_mutex does, at the expense of being
> slightly more cumbersome overall.

Have to think about this some more.  As it is the lock that is timed, not the 
mutex but the mutex can be the repository of timing housekeeping...

<snip>
>
> The only deadlock you can detect with a single mutex is a recursive
> lock. Otherwise, deadlocks come from sets of mutexes. I don't fancy writing
> code that identifies that thread A is trying to lock mutex X, whilst
> holding a lock on mutex Y, and whilst thread B is trying to lock mutex Y,
> whilst holding a lock on mutex X, let alone the multiple thread/multiple
> mutex case. That said, it would be useful.

Shouldn't be too hard if the threads and mutexes are named in debug mode.  At 
least your debugger will show you who has the mutex your waiting on.  

Some SQL databases do this kind of deadlock detection by examining waiting 
processes and determining if there is mutual waiting going on.  It is not a 
great leap to imagine this via a global register in debug version.

> > Some more food for thought.
> >
> > A condition variable relies on a mutex.  We haven't considered the
> > orthogonality of a condition being able to be built around any mutex
> > concept. This is important to consider as it would be great to do but
> > makes building conditions very difficult as we have to write one rather
> > than rely on just a posix wrapper on posix platforms.
>
> Yes. It just extends to Posix the difficulties we're going to face on
> Windows.

Yes.  It rather annoys my sense of sensability that a condition can only lock 
on one type of mutex.  It breaks all sorts of higher level components when 
you try to write nice generic code.  The practicality of avoiding anything 
but simple mutex support so that posix condition vars can be used without 
fuss seems overwhelming though.  I wish truth and beauty were easier...

> > A shared mutex and null mutex need to be considered.
>
> What is a shared mutex?

Better known as a read/write mutex.  I hate the name read_write mutex as it is 
a shared/exclusive mutex that is usually used for read write control but 
conceivably could be multi-writer, single reader in which case you'd take a 
read lock to write and a write lock to read ;-)

> > I use this pattern a lot and have a synch wrapper that wraps the boost
> > mutex implementation to give me this.  Such a wrapper also exposes other
> > synch stuff, like atomic ops and fencing, so these can be used w.r.t. to
> > the conceptual need at the time, so to speak.
> >
> > In my opinion all of STL should support such a concept for the containers
> > and this could be an extension that boost offers.
> >
> > Going back to the containers for a second there is a natural two level
> > mutex concept that we should think about doing out of the box.  A
> > container has activity is at a container level _and_ each object in the
> > container may have its own mutex requirement.  There is a relationship
> > here as a common pattern is for resource pools of mutexes for a container
> > to limit resource consumption and provide better scalability than a
> > single mutex for all objects.  So there is a container access mutex and a
> > mutex per object and the mutex may be one and the same for simple
> > requirements.
>
> Interesting thought.

It has nice parallels at the container level to iterator semantics.  In my 
view container operation specifications should all be described in 
shared_mutex semantics which will then have a natural degradation by the 
Liskov rules to the null_synch case.  At one level is it simply that const 
operations need a shared lock, non-const needs an exclusive lock.  Not quite 
as simple as concurrent writes will potentially invalidate iterators, so it 
is not just about the containers, but the iterators too. And good luck to us 
making this play nice and easily without a recursive mutex.  A recursive 
mutex is essential to do this simply otherwise every interface needs a locked 
and unlocked version.  The locked and unlocked version approach would be 
better though as then you only pay for the lock once.  

I have cases where I provide dual interfaces to objects too as they are 
sometimes in a application state that allows concurrent access and sometimes 
in a different part of the app that is built for speed and is single threaded 
and only the non-locking interface is desired.  I have MACRO foo to simply 
this but it is butt ugly to do that.  Perhaps the named parameter interface 
style could be extended to support locking and non-locking interface 
generation a bit better than MACRO foo.

Also a type trait should exist that tells you if the size of a type, given the 
correct alignment, is atomic w.r.t. to memory access as then no locking is 
required to access or set if (and only if) it is sufficiently indpendent to 
other state.  This is especially useful for the often encountered property 
like getters and setters. 

I think that hierarchy I drew before is wrong now I think about it.  I added 
the recursive thing at the spur of the moment and clearly (well to me now) 
that is orthogonal in concept.

> > Deadlock becomes a real possibility with such things as the potential
> > ordering of access needs to be constrained.  E.g. if you need to lock on
> > two or more objects in the collection then the locks should be required
> > to be accessed in the same order or a scheme where if you are locked and
> > need another object then you may have to give up your lock and attempt
> > then attempt to acquire both, otherwise you're inviting a deadlock.
>
> I wrote a double-locker once that did this --- it acquired one lock, then
> tried to acquire the second. If that failed, it released the lock it had,
> and then tried again, in the other order. It kept switching orders until it
> had both mutexes locked.

Cute! 

Often doesn't work or come up in practice though as having to give up a lock 
means rolling back the work (transaction rollback) and if you need two locks 
then you would normally be able to aware of this and acquire them upfront in 
the same order.  The real answer to this takes you into wait free techniques 
and away from locking so there are limits on what we should try and provision 
for locking.

Regards,

matt.