|
|
Threads-Devel : |
From: David Abrahams (dave_at_[hidden])
Date: 2006-03-04 14:46:26
Matt Hurd <matt.hurd_at_[hidden]> writes:
I'm going to waste a little time in this thread, notwithstanding that
I still believe we need to be stabilizing the existing library before
pursuing any open-ended design discussions. Mostly I want to
understand what the concerns are, and get a feel for how many of them
are valid, but again let me stress that we need to do the hard work
before we move on to the fun stuff.
>>On Thursday 02 March 2006 00:58, Anthony Williams wrote:
>> Hi all,
>>
>> I thought I'd start off some discussion about mutexes, to inaugurate our
>> new mailing list.
>>
>> The mutex is the basic synchronization primitive for shared-memory
>> threading models, such as that of boost.thread, so it is very important
>> that the model, and implementation, is sound. With a working mutex, you can
>> build more expressive synchronization mechanisms, such as the smart shared
>> pointers proposed by Roland.
>
> Doesn't just apply to shared-memory threading models. As the name suggests it
> can be just to prevent concurrent access to a resource which may be
> re-entrancy protection in a single threaded model.
Unless you're now talking about process-level parallelism, I don't see
how any mutex other than one supporting try-locks could be useful in a
single-threaded program. Anything else leads to deadlocks or
pointless waiting. And a try-lock, in a single-threaded program, is
just a good old bool. Am I missing something?
> The concept is mutual exclusion as per its name. Might be a
> physical thing that can only be accessed one at time, like hardware
> registers of a device or some such.
>
> It is also important to remember that this may apply to a singly
> threaded restricted area in an application that is multi-threaded.
What may apply?
> For example, it is unfortunate that boost::shared_ptr adopts its
> concurrency policy based on whether or not it is a multi-threaded
> build.
It's a design choice with certain advantages and limitations. Other
design choices have their own advantages and limitations. A different
choice would be unfortunate in its own way.
> It is the conservative safe approach but restricts the
> usefulness of the pointer. I use boost::shared_ptr by default in my
> apps and replace it with a policy based pointer, usually Loki's,
> where I'm performance critical w.r.t. a lack of concurrent access.
That's appropriate. I would consider boost::intrusive_ptr, or, if
possible, uniqueu_ptr, where performance was critical, though. I
don't see why it makes anything about shared_ptr "unfortunate."
>> 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.
>
> On some platforms mutexes are not necessarily cheap resources and
> their number has a finite boundary. You may wish for object level
> locking for a big collection but you can't swing it. Older versions
> of windows are like this for example where your are restricted by
> "system resources" of 64 to 128K.
>
> Here a common structure might be a mutex pool, for example a vector
> of mutexes where the access is hashed on object address, and your
> object is initialised with a reference to a mutex in the pool that
> it shares with other objects.
>
> 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.
Sure, although it isn't always the best way. I recently put together
an example of deadlock prevention using ordered access. I was
surprised at the complexity of the resulting locking strategy required
(see enclosed). A loop around a pair of locking attempts with an
intervening unlocked section was required in order to make it work; it
reminded me of some of those lock-free algorithms. It was suggested to
me that it would have been cleaner to use timed locks (actually
try-locks sound better to me now, but I'm not a threading expert),
since I needed a loop anyway; then you can lock in any order and just
come back and try again if a deadlock would have occurred. It would
have saved the two-phase locking dance I do in the code.
>> 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.
That's what once routines are for, no?
For concurrently-accessed objects of static storage duration, you need
a once routine anyway, so you may as well initialize the object *and*
its mutex at the same time (?)
> 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.
I have serious doubts about whether this can work and still have the
mutex be useful and safe in other contexts. You'd have to do that
sort of initialization always, even when the mutex is used as a class
member, and if you forgot it, your program would be broken. I hate
some of the restrictions the current Boost threads interface imposes
in the name of safety, but I strongly agree with the basic idea that
C++ abstractions should be leveraged to avoid common errors like this
one. If you absolutely *have* to have static initialization (I don't
buy that idea yet), I there should be a separate
user_initialized_mutex type for that purpose.
> 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.
Interesting, but I'm not sure it's necessary. You need once routines
for those static objects anyway.
>> Constructor calls constitute dynamic initialization, so therefore we need
>> mutex objects which are aggregates, with no members that require
>> constructor calls, so there are no constructor calls. Ideally,
>> zero-initialization would be sufficient, as then the user would not have to
>> specify an initializer, but failing that, a static initializer akin to
>> PTHREAD_MUTEX_INITIALIZER would work. e.g.
>>
>> boost::mutex m=BOOST_MUTEX_INITIALIZER;
>>
>> At the other end of the application lifetime, we have destruction. Since we
>> have no idea how many threads will be running during application shutdown,
>> or what order objects will be destructed, we need to be conservative here,
>> too --- we need the mutex objects to remain usable for as long as possible.
>> On the platforms which I know about, it is acceptable to leak OS resources
>> such as mutexes, as these will be cleaned up by the OS on program exit.
>>
>> 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.
Mutexes being a system resource, you mean? I agree. Finally, this is
C++. If I want to program against the bare metal using no
abstractions, type safety, constructors, or destructors, I'll be doing
it in C. *If* it can be shown the cost of the usual C++ abstractions
will be too high for a significant part of the C++ community, it might
be worth developing a portable lightweight-but-dangerous sublibrary on
which the abstractions can be built, but you need to be *very* careful
about the knee-jerk "if there's a cost, they can't pay it" attitude
towards the embedded community. There are a broad range of embedded
applications, and most of those people can afford to pay a little for
safety. This library should not be skewed to serve requirements on
the margins at the expense of more mainstream requirements, like
safety.
>> I therefore suggest that we supply two mutex types, one of which is POD,
>> and requires a static initializer, and one of which has a default
>> constructor and a destructor. Of course, if we equip the first one with
>> explicit initialize() and destroy() functions, then the second can just be
>> a wrapper for the first that calls initialize() in the constructor, and
>> destroy() in the destructor.
>>
>> I suggest that these two different variants are named boost::static_mutex
>> and boost::mutex.
Okay, two different types. But why is static_mutex needed? I still
haven't seen a good argument, given that you need once routines to
initialize the shared data anyway.
>> 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.
In the boost design, not all mutexes have the capability of a timed
lock, and a mutex that does have that capability may consume more
resources. By having different mutex types, you prevent people from
attempting to use a timed lock on a mutex that was only initialized to
support blocking locks. I think that's the right design unless the
assumption that not all mutexes can support timed locking doesn't
reflect the reality of any real implementations.
>> I also have a "checked" version of basic_mutex (not in CVS), that checks
>> which thread owns the mutex, and throws if the same thread tries to lock it
>> twice, or a thread that doesn't own it tries to unlock it.
Uh, throws? Why? Isn't that a precondition violation? If so,
BOOST_ASSERT would be much more appropriate.
>> This requires additional storage for the ID of the locking thread,
>> and also has the overhead of the additional checks. Does anyone
>> think it's worth adding?
>
> Perhaps, especially for debugging.
For debugging, it *definitely* should not be a throw. It should be an
assertion.
> I also wonder if we should require a name concept for a mutex as
> this would derive some orthogonality across shared memory mutexes
> across process space.
I don't think a _requirement_ is appropriate. People who aren't
targeting shared memory will be extremely frustrated with the need to
provide unique names for every mutex.
> Also a debug version of a mutex could have conncurrent tests as well
> as logging to simply debugging.
I don't know what that means.
> Debugging errors in concurrent access is one of the nasiest and
> hardest things in programming. A debug mutex that can report its
> name and a deadlock condition and the names of the calling threads,
> for example, would be rather magic and very simple to implement.
> Worth its weight in electrons me thinks.
Sounds useful.
> 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.
>
> A shared mutex and null mutex need to be considered.
>
> Boost misses this requirement completely and it is devastating.
Boost has a read/write mutex, notwithstanding that it's currently
broken :)
> Libraries like ACE have support this for many years. We can go a
> step further and support a substituable conceptual heirarchy like
> this:
>
> shared_mutex
> ^
> |
> recursive_mutex
> ^
> |
> simple_mutex
> ^
> |
> null_mutex
Concept hierarchies (refinement) imply substitutability. You don't
need to say it. Normally they're written in the opposite order,
though ;-)
Are you sure that a shared_mutex can always support recursion without
penalty?
> This is a conceptual heirarchy which gives the Liskov subsitutability and
> enables generic code to be written to shared mutex with the knowledge that
> the don't pay for what you don't use concept is alive and good
It's not alive and good unless the assumptions I mentioned before
about the cost of lockability are false, or you're willing to
compromise safety by allowing code to create a timed lock on a mutex
only initialized for plain locking.
> as you can throw in a null mutex and have a normal class/object.
>
> 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.
That's very vague, sorry.
> I think the statically initialise mutex concept is orthogonal to
> this but I don't have a clear picture in my head.
>
> 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.
>
> 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.
>
> Containers of containers make this even more interesting :-)
I don't think this has anything in particular to do with containers.
I see no reason that locks needing to be acquired in order have to be
related by being grouped into the same data structure, as my enclosed
example illustrates. And conversely, I see no reason that objects in
the same data structure are more likely to be locked together in the
way you describe.
-- Dave Abrahams Boost Consulting www.boost-consulting.com