Boost logo

Threads-Devel :

From: Anthony Williams (anthony_at_[hidden])
Date: 2006-03-01 17:13:40


Matt Hurd <matt.hurd_at_[hidden]> writes:

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

You can use std::less to compare the addresses (but not plain <). It would
guarantee no deadlocks if everyone used it, but not if some code locked the
mutexes independently.

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

If you can rely on zero initialization, then you don't need an explicit
initializer for static mutexes, only for non-static ones. This means that on
POSIX you can't use PTHREAD_MUTEX_INITIALIZER (as it's not guaranteed to be
zero-initialization), and must instead have some kind of "initialized" flag,
and do lazy-init, which is hard without atomic ops.

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

Yes. For non-static mutexes (my case 3), you need to ensure that the OS
resources are cleaned up at destruction time. That's why I suggested we have
separate static-friendly mutexes and stack-friendly mutexes --- one needs
constructors and destructors for explicit init/destroy, and the other really
could do without either.

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

Aha.

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

This technique doesn't work if you're already holding one of the locks ---
it's a mechanism for acquiring two locks together, when other threads may hold
either or both. At the time, it was just what I needed, but I only needed it
the once.

Anthony

-- 
Anthony Williams
Software Developer
Just Software Solutions Ltd
http://www.justsoftwaresolutions.co.uk

Threads-Devel list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk