recursive mutexes
red floyd
Does POSIX define what happens when a pthread currently holding a mutex
locks the same mutex?
i.e.
void f()
{
pthread_mutex_lock(&some_mutex);
pthread_mutex_lock(&some_mutex);
}
The Linux (MDK9.1) implementation of pthreads has a non-portable mutex
attribute letting you specify what behavior you want in said situation.
I'd like to try to write portable code, though.
j...@invalid.address
> Does POSIX define what happens when a pthread currently holding a
> mutex locks the same mutex?
Yes, see
http://www.opengroup.org/onlinepubs/009695399/functions/pthread_mutex_lock.html
Joe
--
We can't all be heroes because someone has to sit on the curb and
clap as they go by.
- Will Rogers
Casper H.S. Dik
>i.e.
>void f()
>{
> pthread_mutex_lock(&some_mutex);
> pthread_mutex_lock(&some_mutex);
>}
Portable:
pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_RECURSIVE);
Casper
--
Expressed in this posting are my opinions. They are in no way related
to opinions held by my employer, Sun Microsystems.
Statements on Sun products included here are not gospel and may
be fiction rather than truth.
red floyd
> red floyd <no....@here.dude> writes:
>
>
>
>>Does POSIX define what happens when a pthread currently holding a mutex
>>locks the same mutex?
>
>
>>i.e.
>
>
>>void f()
>>{
>> pthread_mutex_lock(&some_mutex);
>> pthread_mutex_lock(&some_mutex);
>>}
>
>
>>The Linux (MDK9.1) implementation of pthreads has a non-portable mutex
>>attribute letting you specify what behavior you want in said situation.
>
>
>>I'd like to try to write portable code, though.
>
>
> Portable:
>
> pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_RECURSIVE);
>
> Casper
OK, thanks Joe and Casper. I guess my systems implementation is older,
and thus the recursive mutex hadn't yet been standardized or something.
So I'll simply #define something like this
#ifdef USE_NON_PORTABLE_RECURSIVE_MUTEX_
#define RECURSIVE_MUTEX_ATTR PTHREAD_MUTEX_RECURSIVE_NP /* MDK9.1 */
#else
#define RECURSIVE_MUTEX_ATTR PTHREAD_MUTEX_RECURSIVE /* other */
#endif
and use RECURSIVE_MUTEX_ATTR, so that I don't have to worry about it in
the future.
Alexander Terekhov
red floyd wrote: ...
Don't use recursive mutexes. It's akin to sex with used condoms. ;-)
regards,
alexander.
Loic Domaigne
> Don't use recursive mutexes. It's akin to sex with used condoms. ;-)
what's going on, Alexander? Are you now using now sentences that everybody can
understand?
I am not used to that ;-)
Cheers,
Loic.
--
Article posté via l'accès Usenet http://www.mes-news.com
Accès par Nnrp ou Web
SenderX
YIKES!
red floyd
May I ask why?
David Schwartz
> May I ask why?
There are two possibilities:
1) You don't know the mutex is being used recursively. In this case, the
recursive mutex will hide a serious problem.
2) You know the mutex is being recursively. In this case, just don't
lock it since you know it's already locked anyway.
The problem is that recursive mutexes hide something from you and that
something is extremely important. Consider code like this:
A) Lock mutex
B) Unlock mutex
C) Do something, assuming the mutex is unlocked
What happens if the mutex is recursive?
The only value of a recursive mutex is that it allows you to write a
function that works properly whether or not a mutex is locked. But the
caller must know that the mutex is locked anyway, so why not just have two
versions of the function? (With the one you call without a lock possibly
just being a wrapper that grabs the lock and calls the other function.)
It's just too hard and dangerous to write sensible code that works with
a mutex that might or might not start out with that mutex locked and with no
way to tell which. And the only value of recursive mutexes is that they let
you do this.
DS
SenderX
with
> a mutex that might or might not start out with that mutex locked and with
no
> way to tell which. And the only value of recursive mutexes is that they
let
> you do this.
There good for hashed locks.
David Schwartz
I can't imagine how. The only way they might help is if you have code
that grabs more than one object and they might 'happen to' have the same
lock protecting them. But if your code does this, they might also happen to
have different locks protecting them. In this case, you must enforce your
lock ordering rules or else you can deadlock.
In other words, if one thread can grab object A then object B, grabbing
lock 1 followed by lock 2, another thread could grab object C followed by
object D, grabbing lock 2 followed by lock 1. Then you deadlock.
So if you're going to use hashed locks, you may either hold two locks at
once or you may not. If you may not, recursive locks don't help.
If you may, then you must check to see what locks they refer to so that
you acquire them in the right order. While you're doing this, it's just as
easy to check if they're the same lock, and if so only acquire it once. So
recursive locks don't help you in this case.
Worse, recursive locks might lull you into thinking you don't have to
check what locks you are acquiring, and then you are vulnerable to lock
order reversal and deadlocks.
DS
Giancarlo Niccolai
Other than Mr. Schwartz reply (which I consider absolutely good), I may add
also that recursive mutexes are slower (they must check if they are locked
or not) and brings you to program less carefully about shared resource
usage. If you stop to think twice about that, you'll realize that when you
want to lock a resource, you just want to know that you are the owner of
that, and not that you've been entitled to be the owner N times...
The only reason I can see for recursive mutexes is to call recursive
functions, where the locks are so complex that writing a wrapper is not a
viable way, or to create "onion peel" like libraries where the lower levels
are completely obscure and abstracted to the higher ones, and there is
sometimes the need to "extend" the mutex locking also to some function in
the higher levels; but in both the cases there are probably better ways to
deal with the problem with a non recursive mutex, with a little more
cleaner design effort.
Giancarlo.
Martin James
> It's just too hard and dangerous to write sensible code that works
with
> a mutex that might or might not start out with that mutex locked and with
no
> way to tell which. And the only value of recursive mutexes is that they
let
> you do this.
>
Uhh.. OK I have a class protected by an internal mutex. I wish to derive
from the class & add some extra private data & methods in my descendant. I
want the private data in the child to be protected by the mutex, so I obtain
it in the child. The methods in the child call the inherited methods of the
parent, which attempt to get the mutex.again & deadlock the single caller.
Now what? I can add protected 'unlocked' methods in the parent class that
are called from public methods in the parent that get the mutex first. The
child must then ensure that it only calls the unlocked methods that don't
get the mutex. Is this messy & dangerous compared with recursive mutexes or
what?
No, I will not use two mutexes :)
Rgds,
Martin
David Schwartz
>> It's just too hard and dangerous to write sensible code that
>> works with a mutex that might or might not start out with that mutex
>> locked and with no way to tell which. And the only value of
>> recursive mutexes is that they let you do this.
> Uhh.. OK I have a class protected by an internal mutex. I wish to
> derive from the class & add some extra private data & methods in my
> descendant. I want the private data in the child to be protected by
> the mutex, so I obtain it in the child. The methods in the child
> call the inherited methods of the parent, which attempt to get the
> mutex.again & deadlock the single caller.
Right, that would be bad.
> Now what? I can add protected 'unlocked' methods in the parent
> class that are called from public methods in the parent that get the
> mutex first. The child must then ensure that it only calls the
> unlocked methods that don't get the mutex. Is this messy & dangerous
> compared with recursive mutexes or what?
No, it's cleaner and safer by *far*. What happens when someone adds some
code to the class that looks like this:
LockMutex();
while (ObjectIsNotReady())
{
UnlockMutex();
BlockOnEvent();
LockMutex();
}
DoStuff();
UnlockMutex();
Now, all of a sudden, that 'UnlockMutex()' is a nop, and the loop will
spin forever. The problem is that the functions in the inner class can
*only* look exactly like this:
LockMutex();
DoStuff();
UnlockMutex();
Otherwise, the functionality in derived classes may change what code is
run holding the mutex and what code is run without it, and that's very, very
scary.
> No, I will not use two mutexes :)
That may or may not make more sense.
DS
Martin James
> No, it's cleaner and safer by *far*. What happens when someone adds
some
> code to the class that looks like this:
>
> LockMutex();
> while (ObjectIsNotReady())
> {
> UnlockMutex();
> BlockOnEvent();
> LockMutex();
> }
> DoStuff();
> UnlockMutex();
>
> Now, all of a sudden, that 'UnlockMutex()' is a nop, and the loop will
> spin forever.
I guess it's a moot point whether a deadlock or livelock is spotted first :)
The problem is that the functions in the inner class can
> *only* look exactly like this:
>
> LockMutex();
> DoStuff();
> UnlockMutex();
Anther moot point is whether the chances of a developer adding dubious code
that attmpts to unlock a mutex inside an encapsulated object is any greater
or less than a developer accidentally calling the locking, rather than the
lockfree, method of a parent.
> Otherwise, the functionality in derived classes may change what code
is
> run holding the mutex and what code is run without it, and that's very,
very
> scary.
Once acquired, always acquired, that's what I say :)
I have to agree that code can be written to screw up almost anything. I'm
quite happy to put up with the onerous restriction of:
> LockMutex();
> DoStuff();
> UnlockMutex();
in order to avoid the complications of locking and unlocking methods in the
same class.
> > No, I will not use two mutexes :)
>
> That may or may not make more sense.
No thanks. Four classes down, I'm acquiring four mutexes & some developer
will find a way of acquiring them out-of-order.
Rgds,
Martin
David Schwartz
> No thanks. Four classes down, I'm acquiring four mutexes & some
> developer will find a way of acquiring them out-of-order.
Recursive mutexes make the risk of this *much* greater and *much* harder
to detect. What happens when some member of your class hierarchy calls
another function that needs to acquire a mutex?
DS
Uenal Mutlu
> red floyd wrote:
>
> > May I ask why?
>
> There are two possibilities:
>
> 1) You don't know the mutex is being used recursively. In this case, the
> recursive mutex will hide a serious problem.
>
> 2) You know the mutex is being recursively. In this case, just don't
> lock it since you know it's already locked anyway.
>
> The problem is that recursive mutexes hide something from you and that
> something is extremely important. Consider code like this:
>
> A) Lock mutex
> B) Unlock mutex
> C) Do something, assuming the mutex is unlocked
>
> What happens if the mutex is recursive?
Recursive locks work only for the same (current) thread.
The code above is IMO wrong, obviously it should be:
A) Lock mutex
B) Do something
C) Unlock mutex
and this is ok too (here the recursive feature is in action):
A) Lock mutex
B) Do something
C) Lock mutex
D) Do something2
E) Unlock mutex
F) Unlock mutex
C and E are redundant, however application code (the current thread)
cannot always know that it alread has the lock, though it could test for it.
But testing is unnessary because calling such a Lock() will already do
the testing implicitly, so then there is no need for an explicit testing in
applic code, it just would make code longer and slow down the performance.
To clarify:
there is Lock() without recursive feature,
and there is Lock() with recursive feature.
And: such lock objects are initialized at creation.
> The only value of a recursive mutex is that it allows you to write a
> function that works properly whether or not a mutex is locked. But the
> caller must know that the mutex is locked anyway, so why not just have two
usually the calling thread must not know that; it simply can issue a Lock()
request of its own. If it is already locked by this thread then recursion
is in effect and the lock will be granted very fast.
> versions of the function? (With the one you call without a lock possibly
> just being a wrapper that grabs the lock and calls the other function.)
>
> It's just too hard and dangerous to write sensible code that works with
> a mutex that might or might not start out with that mutex locked and with no
> way to tell which. And the only value of recursive mutexes is that they let
> you do this.
Lock objects are initialized at creation, they don't have a random state.
Recursive locks are very practical. It saves coding and prevents from self-deadlocking.
David Schwartz
"Uenal Mutlu" <52000108...@t-online.de> wrote in message
news:d66ogb$2fe$00$1...@news.t-online.com...
> C and E are redundant, however application code (the current thread)
> cannot always know that it alread has the lock, though it could test for
> it.
Yes, it can and must know that it already has the lock. A function that
operates on X should be defined as being called with X locked, or with X
unlocked. It could even take a boolean that indicates whether the caller has
locked the object or not, though this is rarely the right thing to do.
Simply put, the only thing recursive mutexes gives you is the ability to
write code that deals with X that can be called whether or not X is locked.
This is not only almost never useful, but it's almost always dangerous.
DS
Måns Rullgård
> "David Schwartz" wrote
>> red floyd wrote:
>>
>> > May I ask why?
>>
>> There are two possibilities:
>>
>> 1) You don't know the mutex is being used recursively. In this case, the
>> recursive mutex will hide a serious problem.
>>
>> 2) You know the mutex is being recursively. In this case, just don't
>> lock it since you know it's already locked anyway.
>>
>> The problem is that recursive mutexes hide something from you and that
>> something is extremely important. Consider code like this:
>>
>> A) Lock mutex
>> B) Unlock mutex
>> C) Do something, assuming the mutex is unlocked
>>
>> What happens if the mutex is recursive?
>
> Recursive locks work only for the same (current) thread.
I sure hope so.
> The code above is IMO wrong, obviously it should be:
> A) Lock mutex
> B) Do something
> C) Unlock mutex
David meant what he said. What if the something is signaling another
thread to go ahead with something that locks the mutex, and then wait
for that other thread to signal you back? Deadlock.
> and this is ok too (here the recursive feature is in action):
> A) Lock mutex
> B) Do something
> C) Lock mutex
> D) Do something2
> E) Unlock mutex
> F) Unlock mutex
>
> C and E are redundant, however application code (the current thread)
> cannot always know that it alread has the lock, though it could test
> for it.
Bad application design. A properly designed application will always
know what to expect.
>> It's just too hard and dangerous to write sensible code that
>> works with a mutex that might or might not start out with that
>> mutex locked and with no way to tell which. And the only value of
>> recursive mutexes is that they let you do this.
>
> Lock objects are initialized at creation, they don't have a random
> state. Recursive locks are very practical. It saves coding and
> prevents from self-deadlocking.
In all the years I've been programming, I have never used a recursive
mutex (except in Java, but that's another story).
--
Måns Rullgård
m...@inprovide.com
Uenal Mutlu
>
> "Uenal Mutlu" wrote
>
> > C and E are redundant, however application code (the current thread)
> > cannot always know that it alread has the lock, though it could test for
> > it.
>
> Yes, it can and must know that it already has the lock. A function that
> operates on X should be defined as being called with X locked, or with X
> unlocked. It could even take a boolean that indicates whether the caller has
> locked the object or not, though this is rarely the right thing to do.
You are unnecessarily complicating things and make the program
slower by doing these testings. These tests are not necessary if
your design is good.
> Simply put, the only thing recursive mutexes gives you is the ability to
> write code that deals with X that can be called whether or not X is locked.
Not true. It is the caller's job to call X only after having the lock.
It is not X's job to check whether the object was locked.
Do you see the difference, and the consequence, and what it means for performance?
> This is not only almost never useful, but it's almost always dangerous.
Recursive locking has less dangers than locking without recursive feature.
Proof: using recursive locking you never can block or deadlock yourself,
but using a locking method without recursive feature you can very easily deadlock yourself.
In the latter case even just blocking (ie. waiting for the lock) means deadlock!
Don't you see that?
Uenal Mutlu
> "Uenal Mutlu" writes:
>
> > "David Schwartz" wrote
> >> red floyd wrote:
> >>
> >> > May I ask why?
> >>
> >> There are two possibilities:
> >>
> >> 1) You don't know the mutex is being used recursively. In this case, the
> >> recursive mutex will hide a serious problem.
> >>
> >> 2) You know the mutex is being recursively. In this case, just don't
> >> lock it since you know it's already locked anyway.
> >>
> >> The problem is that recursive mutexes hide something from you and that
> >> something is extremely important. Consider code like this:
> >>
> >> A) Lock mutex
> >> B) Unlock mutex
> >> C) Do something, assuming the mutex is unlocked
> >>
> >> What happens if the mutex is recursive?
> >
> > Recursive locks work only for the same (current) thread.
>
> I sure hope so.
>
> > The code above is IMO wrong, obviously it should be:
> > A) Lock mutex
> > B) Do something
> > C) Unlock mutex
>
> David meant what he said. What if the something is signaling another
> thread to go ahead with something that locks the mutex, and then wait
> for that other thread to signal you back? Deadlock.
This has nothing to do with recursive locking per se, does it? I mean: the same
would happen also without recursive locking, wouldn't it?
And, apart from that I don't think this way. In my thinking each thread
knows itself only and tries to lock the shared object(s) before changing
its/their content. We are talking of locking some shared objects here, don't we?
You maybe should give a practical example in pseudocode for what you mean.
> > and this is ok too (here the recursive feature is in action):
> > A) Lock mutex
> > B) Do something
> > C) Lock mutex
> > D) Do something2
> > E) Unlock mutex
> > F) Unlock mutex
> >
> > C and E are redundant, however application code (the current thread)
> > cannot always know that it alread has the lock, though it could test
> > for it.
>
> Bad application design. A properly designed application will always
> know what to expect.
This is a shortsighted view. What do you think recursive locking is intended for?
Recursive locking has nearly no overhead if the implementation of lock()
and unlock() were properly done.
They have many many advantages.
> >> It's just too hard and dangerous to write sensible code that
> >> works with a mutex that might or might not start out with that
> >> mutex locked and with no way to tell which. And the only value of
> >> recursive mutexes is that they let you do this.
> >
> > Lock objects are initialized at creation, they don't have a random
> > state. Recursive locks are very practical. It saves coding and
> > prevents from self-deadlocking.
>
> In all the years I've been programming, I have never used a recursive
> mutex (except in Java, but that's another story).
Then you must have overlooked their real value.
Peter Dimov
> "David Schwartz" wrote
>> Yes, it can and must know that it already has the lock. A
>> function that operates on X should be defined as being called with X
>> locked, or with X unlocked. It could even take a boolean that
>> indicates whether the caller has locked the object or not, though
>> this is rarely the right thing to do.
>
> You are unnecessarily complicating things and make the program
> slower by doing these testings.
No, he's in fact making the program faster.
Uenal Mutlu
> "Uenal Mutlu" writes:
>
> >> >> you and that something is extremely important. Consider code
> >> >> like this:
> >> >>
> >> >> A) Lock mutex
> >> >> B) Unlock mutex
> >> >> C) Do something, assuming the mutex is unlocked
> >> >>
> >> >> What happens if the mutex is recursive?
> >> >
> >> > Recursive locks work only for the same (current) thread.
> >>
> >> I sure hope so.
> >>
> >> > The code above is IMO wrong, obviously it should be:
> >> > A) Lock mutex
> >> > B) Do something
> >> > C) Unlock mutex
> >>
> >> David meant what he said. What if the something is signaling another
> >> thread to go ahead with something that locks the mutex, and then wait
> >> for that other thread to signal you back? Deadlock.
> >
> > mean: the same would happen also without recursive locking, wouldn't
> > it?
>
> other thread will be able to acquire it. If the mutex is recursive,
> you can't know which level you just unlocked.
You are expecting a specific thread will get the released lock?
This can't work.
> > And, apart from that I don't think this way. In my thinking each
> > thread knows itself only and tries to lock the shared object(s)
> > before changing its/their content. We are talking of locking some
> > shared objects here, don't we?
>
> If "each thread knows itself only", how can we be talking about shared
> objects at all?
Because we are talking of threads and not processes...
> > You maybe should give a practical example in pseudocode for what you
> > mean.
>
> I don't think that's needed.
It sure would clarify what you mean.
> >> > and this is ok too (here the recursive feature is in action):
> >> > A) Lock mutex
> >> > B) Do something
> >> > C) Lock mutex
> >> > D) Do something2
> >> > E) Unlock mutex
> >> > F) Unlock mutex
> >> >
> >> > C and E are redundant, however application code (the current thread)
> >> > cannot always know that it alread has the lock, though it could test
> >> > for it.
> >>
> >> Bad application design. A properly designed application will always
> >> know what to expect.
> >
> > This is a shortsighted view. What do you think recursive locking is
> > intended for?
>
> They are for lazy programmers unwilling to learn proper design.
I would say this applies exactly to yourself.
> > Recursive locking has nearly no overhead if the implementation of lock()
> > and unlock() were properly done.
>
> I'm not worried about overhead. I'm worried about writing buggy code.
Then continue worrying. Using recursive locking is safer than using
one which doesn't have such recursive feature.
> > They have many many advantages.
>
> Prove it. Show me one problem that can't be solved better without them.
Since you don't believe me it's your turn to prove that recursive locking
is more dangerous (your saying) than using no recursive locking.
My point is: recursive locking is much safer than non-recursive locking.
> >> >> It's just too hard and dangerous to write sensible code that
> >> >> works with a mutex that might or might not start out with that
> >> >> mutex locked and with no way to tell which. And the only value of
> >> >> recursive mutexes is that they let you do this.
> >> >
> >> > Lock objects are initialized at creation, they don't have a random
> >> > state. Recursive locks are very practical. It saves coding and
> >> > prevents from self-deadlocking.
> >>
> >> In all the years I've been programming, I have never used a recursive
> >> mutex (except in Java, but that's another story).
> >
> > Then you must have overlooked their real value.
>
> Or I realized their real danger.
I doubt it because there is no danger in using recursive locking over
non-recursive locking. OTOH recursive locking has advantages over
non-recursive locking. So what? If you doubt this then prove it.
(Follow-up set to comp.programming.threads where it belongs to)
Uenal Mutlu
Are you sure? Let's see:
void X::f()
{
Lock();
for (int i = 0; i < 1000; i++)
f();
Unlock();
}
void X::g()
{
if (!IsLocked())
return;
//...do..something...
}
Are you saying the above version of g() is faster than this one: ?
void X::g()
{
//...do..something...
}
Peter Dimov
> "Peter Dimov" wrote
>> Uenal Mutlu wrote:
>>> "David Schwartz" wrote
>>>> Yes, it can and must know that it already has the lock. A
>>>> function that operates on X should be defined as being called with
>>>> X locked, or with X unlocked. It could even take a boolean that
>>>> indicates whether the caller has locked the object or not, though
>>>> this is rarely the right thing to do.
>>>
>>> You are unnecessarily complicating things and make the program
>>> slower by doing these testings.
>>
>> No, he's in fact making the program faster.
>
> Are you sure? Let's see:
>
> void X::f()
> {
> Lock();
> for (int i = 0; i < 1000; i++)
> f();
Stack overflow or deadlock here, you probably wanted to call g().
> Unlock();
> }
>
> void X::g()
> {
> if (!IsLocked())
> return;
> //...do..something...
> }
>
> Are you saying the above version of g() is faster than this one: ?
> void X::g()
> {
> //...do..something...
> }
Of course not. Why would you want to test anything if you could just use the
above? We're talking about recursive mutexes, remember?
void X::f()
{
Lock();
for (int i = 0; i < 1000; i++)
{
g();
}
Unlock();
}
void X::g()
{
Lock();
//...do..something...
Unlock();
}
compared to
void X::f()
{
Lock();
for (int i = 0; i < 1000; i++)
{
g( false );
}
Unlock();
}
void X::g( bool lock )
{
if( lock ) Lock();
//...do..something...
if( lock ) Unlock();
}
Let's overlook the fact that the correct version is of course:
void X::f()
{
Lock();
for (int i = 0; i < 1000; i++)
{
g_unlocked();
}
Unlock();
}
void X::g_unlocked()
{
//...do..something...
}
void X::g()
{
Lock();
g_unlocked();
Unlock();
}
Uenal Mutlu
Besides being slower, the first version is also buggy. And I don't know
what he or you want do if the object is not already locked. I guess you will do the following:
void X::g()
{
bool fILockedItHere = false;
if (!IsLocked())
{
Lock();
fILockedItHere = true;
}
//...do..something...
if (fILockedItHere)
Unlock();
}
But, this is not thread safe!!! :-) Do you know why?
The only consequence is: my method is the only right one, believe me! :-)
Uenal Mutlu
> Uenal Mutlu wrote:
> > "Peter Dimov" wrote
> >> Uenal Mutlu wrote:
> >>> "David Schwartz" wrote
> >>>> Yes, it can and must know that it already has the lock. A
> >>>> function that operates on X should be defined as being called with
> >>>> X locked, or with X unlocked. It could even take a boolean that
> >>>> indicates whether the caller has locked the object or not, though
> >>>> this is rarely the right thing to do.
> >>>
> >>> You are unnecessarily complicating things and make the program
> >>> slower by doing these testings.
> >>
> >> No, he's in fact making the program faster.
> >
> > Are you sure? Let's see:
> >
> > void X::f()
> > {
> > Lock();
> > for (int i = 0; i < 1000; i++)
> > f();
>
> Stack overflow or deadlock here, you probably wanted to call g().
:-) Of course g() was meant.
> > Unlock();
> > }
> >
> > void X::g()
> > {
> > if (!IsLocked())
> > return;
> > //...do..something...
> > }
> >
> > Are you saying the above version of g() is faster than this one: ?
> > void X::g()
> > {
> > //...do..something...
> > }
>
> Of course not. Why would you want to test anything if you could just use the
> above? We're talking about recursive mutexes, remember?
No I haven't. See below
> void X::f()
> {
> Lock();
>
> for (int i = 0; i < 1000; i++)
> {
> g();
> }
>
> Unlock();
> }
>
> void X::g()
> {
> Lock();
>
> //...do..something...
>
> Unlock();
> }
The above solution works only if your Lock() understands recursive locking.
Otherwise a deadlock will happen.
> compared to
>
> void X::f()
> {
> Lock();
>
> for (int i = 0; i < 1000; i++)
> {
> g( false );
> }
>
> Unlock();
> }
>
> void X::g( bool lock )
> {
> if( lock ) Lock();
>
> //...do..something...
>
> if( lock ) Unlock();
> }
I don't like the above because one usually uses a locker
class like this one to automate the unlocking:
Locker
{
Locker(mutex& Am) : m(Am)
{
m.Lock();
}
~Locker()
{
m.Unlock();
}
private:
mutex& m;
};
void X::f()
{
Locker(m);
for (int i = 0; i < 1000; i++)
g();
}
void X::g()
{
//...do..something...
}
> Let's overlook the fact that the correct version is of course:
>
> void X::f()
> {
> Lock();
>
>
> for (int i = 0; i < 1000; i++)
> {
> g_unlocked();
> }
>
> Unlock();
> }
>
>
> void X::g_unlocked()
> {
> //...do..something...
> }
>
> void X::g()
> {
> Lock();
> g_unlocked();
> Unlock();
> }
You don't need 2 versions of g() if you use recursive locking.
The overhead of recursive locking is neglectable because
it's just incrementing a counter in Lock() and decrementing it in Unlock().
Giancarlo Niccolai
>
>>
>> In all the years I've been programming, I have never used a recursive
>> mutex (except in Java, but that's another story).
>
> Then you must have overlooked their real value.
Sorry if I jump in late in the discussion, but I believed that David was
enough to fix this mental bug that you have encountered.
IMHO usage of recursive mutexes is generally an immediate and incontestable
proof of poor design.
It's not a matter of multithreading theoremes, it's a matter of parallel
activity design. Coordination is an high level activity in any parallel
process, be it coordination between firm divisions, production chains,
information processing or simply programming.
You don't want a magazine clerk of the production function to coordinate
with a magazine clerk of the provisions. The production manager will raise
the phone and talk with the provision manager (or the other way around)
when they need coordination. And believe me, they both know when they take
up the phone (lock) and when they put it down (unlock), and it's unlikely
that they can raise the phone twice without lowering it first.
Same for threads. When threads need coordination, a well designed system
will put this coordination in a place that each thread can perfectly
manage, and will make sure that coordination will 1) take less time and
computational power as possible and 2) nothing else will be done during
coordination step.
Locking a mutex means your agents are phoning each other. It's not polite to
have listener(s) hanging because you must do something while phoning them,
even if this something is somehow a recursive function call.
Locking for everything else except coordination (that is, inter-thread
communication) is bad design. Not just bad programming, but bad
understanding of parallel processing logic.
Bests,
Giancarlo Niccolai.
David Schwartz
> Recursive locking has less dangers than locking without recursive feature.
> Proof: using recursive locking you never can block or deadlock yourself,
> but using a locking method without recursive feature you can very easily
> deadlock
> yourself.
> In the latter case even just blocking (ie. waiting for the lock) means
> deadlock!
> Don't you see that?
Okay, suppose I write a function that supposed to only be called if X is
not locked. Calling it with X locked is a *bug*. Now suppose I make a
mistake -- I am only human. I call the function by mistake with X locked.
The function goes to lock X itself. I *want* this to break because it
indicates a *bug*. It is *bad* if this just magically works because then the
bug will not get discovered.
DS
David Schwartz
>> > The code above is IMO wrong, obviously it should be:
>> > A) Lock mutex
>> > B) Do something
>> > C) Unlock mutex
>> David meant what he said. What if the something is signaling another
>> thread to go ahead with something that locks the mutex, and then wait
>> for that other thread to signal you back? Deadlock.
> This has nothing to do with recursive locking per se, does it?
Yes, it does.
> I mean: the same
> would happen also without recursive locking, wouldn't it?
No. Because with locks that are not recursive, an 'unlock' function
actually unlocks something.
> And, apart from that I don't think this way. In my thinking each thread
> knows itself only and tries to lock the shared object(s) before changing
> its/their content. We are talking of locking some shared objects here,
> don't we?
> You maybe should give a practical example in pseudocode for what you mean.
Okay, let me put it as simple as possible. There are some things you can
only do when you hold a lock, like manipulate shared data. There are some
things you can only do when you don't hold a lock, like block or wait for
shared data to change. Thus code that manipulates shared data needs to know
whether it holds a lock or not.
> This is a shortsighted view. What do you think recursive locking is
> intended for?
> Recursive locking has nearly no overhead if the implementation of lock()
> and unlock() were properly done.
> They have many many advantages.
The *only* advantage is that you can write code that acquires a
particular lock without knowing whether it already holds that same lock.
However, code has to know what locks it holds *anyway* in order to be
developed sanely.
DS
Måns Rullgård
In other words, recursive mutexes are nothing but a way of papering
over design flaws in an application.
--
Måns Rullgård
m...@inprovide.com
David Schwartz
> Since you don't believe me it's your turn to prove that recursive locking
> is more dangerous (your saying) than using no recursive locking.
> My point is: recursive locking is much safer than non-recursive locking.
We've already done this over and over. Consider:
x.Lock();
DoSomeStuff();
x.Unlock();
DoSomeStuffThatTakesALongTime();
If the lock for x is not recursive, we know that we can safely take a
long time without stalling other threads that might want the x lock. If the
lock is recursive, we might unknowingly hold the x lock while we do the
stuff that takes a long time.
Here's another one:
x.Lock();
while (x.IsReservedByAnotherThread())
{
x.Unlock();
DoOtherStuffSinceXIsNotReady();
}
x.DoStuff();
x.Unlock();
This code will deadlock if the x mutex is recursive. The other thread
can never clear its reservation because this thread might still hold the x
mutex through the entire 'while' loop.
We really mean what we're saying. Really, really. Recursive mutexes are
really bad and they really do hide serious bugs.
You could write either of the two code sections above and *never* detect
the problem because it may only result in performance issues during your
tests. But in another environment where the functions erroneously held with
locks take longer, the result could be catastrophic.
DS
David Schwartz
> Are you sure? Let's see:
>
> void X::f()
> {
> Lock();
> for (int i = 0; i < 1000; i++)
> f();
> Unlock();
> }
>
> void X::g()
> {
> if (!IsLocked())
> return;
> //...do..something...
> }
>
> Are you saying the above version of g() is faster than this one: ?
> void X::g()
> {
> //...do..something...
> }
I never argued the performance issue. But here's a more realistic
example:
Without recursive mutexes:
protected:
f_locked(void)
{ // call with mutex locked
DoStuff();
}
public:
f(void)
{ // call with mutex unlocked
Lock();
f_locked();
Unlock();
}
many_f(void)
{ // call with mutex unlocked
Lock();
for(int i=0; i<1000; i++) f_locked();
Unlock();
}
With recursive mutex:
public:
f(void)
{ // call with mutex in any state
Lock();
DoStuff();
Unlock();
}
many_f(void)
{ // call with mutex in any state
Lock();
for(int i=0; i<1000; i++) f();
Unlock();
}
Which do you think is faster?
DS
doug
S'not true. You can't just increment/decrement a counter in
Lock()/Unlock() - these operations require memory barriers or they won't
work properly across multiple threads and CPUs. With recursive locks, too.
You keep arguing about silly things, proclaiming people to be wrong (e.g.
"see below..." - where!?!), and never providing evidence (only faulty code).
When someone questions you, you answer rather indignantly. Each post sounds
as though you've read the next chapter in your threading book and want to
share.
Anyways, this is interesting. More technical than alt.guitar.bass, but just
as much flamebait, if better disguised!
With baited breathe,
Doug
doug
This is exactly what I mean.
Uenal Mutlu
>
> "Uenal Mutlu" wrote
> > "Peter Dimov" wrote
> >> Uenal Mutlu wrote:
> >> > "Peter Dimov" wrote
> >> >> Uenal Mutlu wrote:
> >> >>> "David Schwartz" wrote
> >> >>>> Yes, it can and must know that it already has the lock. A
> >> >>>> function that operates on X should be defined as being called with
> >> >>>> X locked, or with X unlocked. It could even take a boolean that
> >> >>>> indicates whether the caller has locked the object or not, though
> >> >>>> this is rarely the right thing to do.
> >> >>>
> >> >>> You are unnecessarily complicating things and make the program
> >> >>> slower by doing these testings.
>
> > The overhead of recursive locking is neglectable because
> > it's just incrementing a counter in Lock() and decrementing it in
> > Unlock().
>
> S'not true. You can't just increment/decrement a counter in
> Lock()/Unlock() - these operations require memory barriers or they won't
> work properly across multiple threads and CPUs. With recursive locks, too.
You seem to not understand what I'm talking about.
Do you understand this fact: "Recursive locking is defined for the current lock owning thread only"?
Since you already have the lock you can do what ever you want since nobody
else can change anything, but you can do! You simply increment it in Lock()
and decrement it in Unlock(). Because it is safe because you already have it locked.
Uenal Mutlu
>
> I never argued the performance issue. But here's a more realistic
> example:
The example was in response to Peter's posting who wrote "No, he's in fact making the program faster."
To your question regarding the speed of recursive vs. non-recursive locks:
True, recursive locking is slower than non-recursive locking.
But recursive locking simplifies coding (no need to have a locked and unlocked
version of a function) and makes the application safer wrt self-deadlocking.
And my point is: if the recursive-locking is a fast implementation, then the
overhead of recursive locking is minimally (inc and dec). And if this is true (and it is)
then why make life complicated by not using them since they have the above
positive properties.
And, IMO it is not a good design to test in f() whether the object
was locked or not. I prefer the following "agreement" or "contract":
It is the caller's job to call f() only after having the lock.
It is not f()'s job to check whether the object was locked.
This too simplies coding, and it leads to faster programs.
Uenal Mutlu
>
> "Uenal Mutlu" wrote
>
> > is more dangerous (your saying) than using no recursive locking.
> > My point is: recursive locking is much safer than non-recursive locking.
>
> We've already done this over and over. Consider:
>
> x.Lock();
> DoSomeStuff();
> x.Unlock();
> DoSomeStuffThatTakesALongTime();
>
> If the lock for x is not recursive, we know that we can safely take a
> long time without stalling other threads that might want the x lock. If the
> lock is recursive, we might unknowingly hold the x lock while we do the
> stuff that takes a long time.
You are putting operations into 2 categories:
1) operations which can be done only if the object is locked
2) operations which can be done only if the object is not locked
This is unneccessary complication, and it's dangerous.
My point of view is: all operations on a shared object can be done only
in a locked state (#1 above). So one has to forget #2 and never assume to do #2.
An object can be modified only in a locked state, otherwise wait or
give up your time-slice back to the schedular.
The result is: simplication, safety, speed.
> Here's another one:
>
> x.Lock();
> while (x.IsReservedByAnotherThread())
> {
> x.Unlock();
> DoOtherStuffSinceXIsNotReady();
> }
> x.DoStuff();
> x.Unlock();
>
> This code will deadlock if the x mutex is recursive. The other thread
> can never clear its reservation because this thread might still hold the x
> mutex through the entire 'while' loop.
The same would happen with non-recursive locking too, wouldn't it?
Besides this, it is a bad and buggy design. You never should lock an
object in a scope and unlock it in a different scope.
> We really mean what we're saying. Really, really. Recursive mutexes are
> really bad and they really do hide serious bugs.
This is simply not true. Recursive locking is a superset of non-recursive locking.
Everthing possible in non-recursive locking is possible in recursive-locking too,
except deadlocking himself. So then how can recursive-locking be more dangerous
than non-recursive locking? This is simple basic logic.
Chris Thomasson
You do not seem to understand what "you" are talking about.
Chris Thomasson
> sounds as though you've read the next chapter in your threading book and
> want to share.
It sure does. He seems a bit inexperienced...
doug
> You seem to not understand what I'm talking about.
> Do you understand this fact: "Recursive locking is defined for the current
> lock owning thread only"?
> Since you already have the lock you can do what ever you want since nobody
> else can change anything, but you can do! You simply increment it in
> Lock()
> and decrement it in Unlock(). Because it is safe because you already have
> it locked.
>
>
Think carefully. How is this possible?
It is possible if you store 'have I got this lock?' in thread local storage.
So yes, by keeping a counter here, you don't need a memory barrier in
recursive Lock()/Unlock() *. However, when you find that you don't have the
semaphore, you still need synchronisation between threads so that the sema4
is acquired safely.
What you've ended up doing here is accessing TLS for *every* acquire - thus
making the common case of 'semaphore not acquired' slower.
(* not true on certain SMP architectures. Without a memory barrier in
Lock()/Unlock(), a thread rescheduled on a different CPU may mis-read the
recursive counter (depending on how TLS is implemented).)
Time to read your next chapter...
doug
"Chris Thomasson" <_no_damn_spam_cristom@_no_damn_comcast.net_spam> wrote in
message news:2pOdndaD_5x...@comcast.com...
It's good that he gave it a stab, but I don't understand his reluctance to
read up on existing 'well-known' practises in this area and his
unwillingness to listen to others.
For the current code I'm working on, it would take me several hours, perhaps
days, to type in the lock information his tool requires. That's not to
mention the fact that threads are created dynamically, and their behaviour
is unpredictable (I see nothing in his tool that allows you to grab this
lock OR that lock, depending on some state.). All he's done is specialise
hierarchical locking for simplified scenarios.
Uenal Mutlu
>
> > You seem to not understand what I'm talking about.
> > Do you understand this fact: "Recursive locking is defined for the current
> > lock owning thread only"?
> > Since you already have the lock you can do what ever you want since nobody
> > else can change anything, but you can do! You simply increment it in
> > Lock()
> > and decrement it in Unlock(). Because it is safe because you already have
> > it locked.
> >
> Think carefully. How is this possible?
It is really basic stuff. Ask yourself how you would extend a non-recursive
locking method to make it recursive? Recursivity starts with the 2nd Lock()
call on the same object within the same thread, true? So, after the 1st you
already have the lock, don't you? From then on just use a simple unprotected counter.
It is intended for the current _lock owning thread_ only. It is irrelevant for all
other threads because they don't have the lock.
Let me know if this makes sense to you.
> It is possible if you store 'have I got this lock?' in thread local storage.
> So yes, by keeping a counter here, you don't need a memory barrier in
> recursive Lock()/Unlock() *. However, when you find that you don't have the
> semaphore, you still need synchronisation between threads so that the sema4
> is acquired safely.
> What you've ended up doing here is accessing TLS for *every* acquire - thus
> making the common case of 'semaphore not acquired' slower.
>
> (* not true on certain SMP architectures. Without a memory barrier in
> Lock()/Unlock(), a thread rescheduled on a different CPU may mis-read the
> recursive counter (depending on how TLS is implemented).)
I think I now know what the reason of these misunderstandings are:
You and some others seem to see a lock as a property of a thread,
and by this you do "lock the thread". I on the other hand see a lock as
a property of the shared object.
I don't use any TLS, I use just the usual sharing mechanism of threads;
ie. all objects in a program can be accessed by all threads.
By this, I put locks on objects, not threads.
Each such shared object has its own mutex, and not one mutex per thread,
and of course also not one mutex for all threads (which IMO is nonsense).
Sergei Organov
> "David Schwartz" wrote
> > I never argued the performance issue. But here's a more realistic example:
>
> The example was in response to Peter's posting who wrote "No, he's in fact
> making the program faster."
>
> To your question regarding the speed of recursive vs. non-recursive
> locks: True, recursive locking is slower than non-recursive locking.
> But recursive locking simplifies coding (no need to have a locked and
> unlocked version of a function) and makes the application safer wrt
> self-deadlocking.
Yes, it simplifies coding in the sense that it makes it easier to write
"working" program that is in fact incorrect. Please try to understand
what others already told you: dead lock could be a good thing as getting
it early and correct the problem is much better than hiding the problem
behind recursive locks.
If you in fact don't care about correctness of your programs, it's
better to get rid of all the locking altogether, -- absolutely safe wrt
deadlocks, simple, and pretty fast program you will get ;)
--
Sergei.
Uenal Mutlu
>
> "Chris Thomasson" wrote in
> >> When someone questions you, you answer rather indignantly. Each post
> >> sounds as though you've read the next chapter in your threading book and
> >> want to share.
> >
> > It sure does. He seems a bit inexperienced...
> >
> It's good that he gave it a stab, but I don't understand his reluctance to
> read up on existing 'well-known' practises in this area and his
> unwillingness to listen to others.
> For the current code I'm working on, it would take me several hours, perhaps
> days, to type in the lock information his tool requires. That's not to
> mention the fact that threads are created dynamically, and their behaviour
> is unpredictable (I see nothing in his tool that allows you to grab this
> lock OR that lock, depending on some state.). All he's done is specialise
> hierarchical locking for simplified scenarios.
It is more an educational tool. It can be extended to eliminate step 1 (entering
the list of objects). This list then could be filled from the thread objects.
I will add this later.
If you put your input data into a text file then you can feed the file by using
input redirection on the command line. ie. DeadlockDetect <myinput.txt
Uenal Mutlu
> "Uenal Mutlu"
> > "David Schwartz" wrote
> > > I never argued the performance issue. But here's a more realistic example:
> >
> > The example was in response to Peter's posting who wrote "No, he's in fact
> > making the program faster."
> >
> > To your question regarding the speed of recursive vs. non-recursive
> > locks: True, recursive locking is slower than non-recursive locking.
> > But recursive locking simplifies coding (no need to have a locked and
> > unlocked version of a function) and makes the application safer wrt
> > self-deadlocking.
>
> Yes, it simplifies coding in the sense that it makes it easier to write
> "working" program that is in fact incorrect. Please try to understand
> what others already told you: dead lock could be a good thing as getting
> it early and correct the problem is much better than hiding the problem
> behind recursive locks.
But you forget the fact that recursive locks have the property to
not deadlock the thread. Then it is not valid to say that because
I called Lock() twice that this leads to deadlock, no! I'm willingly
making use of its recursivity feature because it simplifies many things,
and most importantly it is safer than non-recursive locking, though
it has a neglectable overhead. If I use a _recursive locking method_
then I'm of course aware of these facts.
> If you in fact don't care about correctness of your programs, it's
I do care very much of the correctness of my program. It has highest
priority, second is performance, third is simplicity/maintainability.
> better to get rid of all the locking altogether, -- absolutely safe wrt
> deadlocks, simple, and pretty fast program you will get ;)
:-)
Unfortunately, impossible to not use locking in nowadays projects.
Locking has become very important and will be in future.
Lockless shared access is practically seen impossible to do if
there are at least two threads sharing the same resource.
Uenal Mutlu
>
> For the current code I'm working on, it would take me several hours, perhaps
> days, to type in the lock information his tool requires.
If you strictly follow the deadlock theorem I posted here, then you can
be assured that no deadlock will happen.
> That's not to mention the fact that threads are created dynamically, and their behaviour
> is unpredictable (I see nothing in his tool that allows you to grab this
> lock OR that lock, depending on some state.).
It is intended for locks put on individual shared objects. Ie. it is not
for "locking threads" or something that.
It is irrelevant when the threads are created. It is important what the
threadproc does: ie. in which order it locks the objects.
The requirement is: you must create a list of all your shared objects (the order
is irrelevant), then in each threadproc pick the objects you want to use
just in the same order as they are on the list.
> All he's done is specialise hierarchical locking for simplified scenarios.
Not true. The deadlock theorem I formulated is an important generalization.
Sergei Organov
> > > To your question regarding the speed of recursive vs. non-recursive
> > > locks: True, recursive locking is slower than non-recursive locking.
> > > But recursive locking simplifies coding (no need to have a locked and
> > > unlocked version of a function) and makes the application safer wrt
> > > self-deadlocking.
> >
> > Yes, it simplifies coding in the sense that it makes it easier to write
> > "working" program that is in fact incorrect. Please try to understand
> > what others already told you: dead lock could be a good thing as getting
> > it early and correct the problem is much better than hiding the problem
> > behind recursive locks.
>
> But you forget
No, I didn't.
> the fact that recursive locks have the property to not deadlock the
> thread.
Sure, and that's one thing that is bad about them, -- they don't
deadlock where deadlock (or some other indication of failure) is
appropriate. Please try to stop answering immediately and think a little
bit, 1 to 7 days of thinking seems to be enough to understand that
deadlock is not the ultimate and the only enemy in programming and that
deadlock could well be programmers friend, -- then come back and tell us
something new.
> Then it is not valid to say that because I called Lock() twice that
> this leads to deadlock, no!
Sure, it is not valid, but nobody said that it is. Please *read* what
you are replying to, as currently you are replying to your own thoughts,
not to what I wrote, and if you need to talk to yourself, there is no
reason to use public newsgroup for that.
> I'm willingly making use of its recursivity feature because it
> simplifies many things, and most importantly it is safer than
> non-recursive locking,
It depends on the definition of "safer". For me "safer" is not equal to
"no deadlock". Using my definition of "safer", the recursive lock is not
safer due to the fact that it allows actual problems in the code to be
hidden for a long time.
> though it has a neglectable overhead. If I use a _recursive locking
> method_ then I'm of course aware of these facts.
If you were aware of the experience that has been gathered in this
field, you won't use recursive locking method in the first place.
The recursive locks simplify your life by allowing you not to think
about quality of your design. Kinda like favorite goto's in programming
languages, -- they do simplify programming in the short run but the
result is usually a wrong and unmaintainable problem^H^H^H^Hgram in the
long run. If you consider such simplifications to be a good thing, --
it's your problem.
--
Sergei.
Torsten Robitzki
> "David Schwartz" wrote
>
>>"Uenal Mutlu" wrote
>>
>> Yes, it can and must know that it already has the lock. A function that
>>operates on X should be defined as being called with X locked, or with X
>>unlocked. It could even take a boolean that indicates whether the caller has
>>locked the object or not, though this is rarely the right thing to do.
>
>
> You are unnecessarily complicating things and make the program
> slower by doing these testings.
It doesn't really matter if you code this test by yourself or let the
recursive lock do this test for you. As this explicit coded flag does
not need any synchronization it might even be faster then the necessary
test a recursive lock have to do.
> These tests are not necessary if
> your design is good.
Right, and the only way to get rid of this tests is to design the code
in such a way that you know for every function if a lock is held of if a
lock have to be acquired.
regards
Torsten
P.S. never used recursive locks and never had any serious problems with
deadlocks.
Torsten Robitzki
> "doug" wrote
>
>>>You seem to not understand what I'm talking about.
>>>Do you understand this fact: "Recursive locking is defined for the current
>>>lock owning thread only"?
>>>Since you already have the lock you can do what ever you want since nobody
>>>else can change anything, but you can do! You simply increment it in
>>>Lock()
>>>and decrement it in Unlock(). Because it is safe because you already have
>>>it locked.
>>>
>>
>>Think carefully. How is this possible?
>
>
> It is really basic stuff. Ask yourself how you would extend a non-recursive
> locking method to make it recursive? Recursivity starts with the 2nd Lock()
> call on the same object within the same thread, true?
First one have to check if this lock request comes from the thread
holding the mutex or not. This can not be implemented by a simple
increment.
regards
Torsten
Uenal Mutlu
That's the point. I'm arguing that one should not think this way.
I prefer the following "contract" (I wrote about this in prev. posting):
It is the caller's job to call f() only after having the lock.
It is not f()'s job to check whether the object was locked or not.
If you follow this theorem then you don't need to know inside f()
whether the necessary lock was set or not. Locking should be
done by the caller, not by the called one.
The net effect of this guideline is that it simplifies many things.
> P.S. never used recursive locks and never had any serious problems with
> deadlocks.
Just curious: for which target OS do you program and which thread pkg do you use?
Uenal Mutlu
In the mean time can you just tell me for which target OS you
do develop and which threading pkg you use?
Uenal Mutlu
I can only repeat: The code which increments the counter cannot be
executed by anyone else but the current lock holding thread.
Do you know what a critical section is?
In your other posting you wrote:
> P.S. never used recursive locks and never had any serious problems with
> deadlocks.
May I ask: have you ever either implemented any mutex (recursive or non-recursive)
by yourself or have you ever used a non-recursive mutex in your projects?
For which OS and using which threading pkg do you develop?
Sergei Organov
First, please try to learn not to skip the text you are answering to.
Second, I don't need you to wait, I just suggested you to think about
things you have been told by different rather experienced people before
answering.
Third, if you indeed curious, my primary target OSes are eCos and RTEMS,
and less frequently I write for Linux, Linux being my primary host OS.
--
Sergei.
Torsten Robitzki
> "Torsten Robitzki" wrote
>
>>Uenal Mutlu wrote:
>>>
>>>It is really basic stuff. Ask yourself how you would extend a non-recursive
>>>locking method to make it recursive? Recursivity starts with the 2nd Lock()
>>>call on the same object within the same thread, true?
>>
>>First one have to check if this lock request comes from the thread
>>holding the mutex or not. This can not be implemented by a simple
>>increment.
>
>
> I can only repeat: The code which increments the counter cannot be
> executed by anyone else but the current lock holding thread.
What will a thread that does not hold the lock prevent it from
incrementing the counter if not by checking if it's holding the lock or
not? A lock is not some magical device, it's just a bunch of data with
some associated functions. Looks to me that you are inventing a thread
private lock here ;-)
> Do you know what a critical section is?
Sure, it Microsoft's name for a recursive, maybe a little bit spinning
in front of blocking, mutex or lock.
> In your other posting you wrote:
>
>
>>P.S. never used recursive locks and never had any serious problems with
>>deadlocks.
>
>
> May I ask: have you ever either implemented any mutex (recursive or non-recursive)
> by yourself or have you ever used a non-recursive mutex in your projects?
I've implemented a mutex (both recursive and non-recursive) in a very
simple manner by using an atomic swap plus wait. And yes I'm using
non-recursive locks in my projects.
> For which OS and using which threading pkg do you develop?
OpenVMS/Alpha with some C++ wrapper around pthread.
doug
You're missing the point of the question. If you have the lock, yes, you
can increment a counter. But you need to check if you own the lock first,
don't you?
Your description above sounds like you're saying:
- use a lock for the first time you grab the counter
- use a counter thereafter.
But then your thread needs to know if already owns the lock. So this isn't
a recursive semaphore at all.
Let's start again. Here is some pseudocode for a recursive Lock() routine.
A recursive lock consists of a mutex (lock control), a signal var
(condivar), a counter, and a thread identifier.
Lock()
{
acquire_lock_control
if (lock.owner == me)
}
lock.counter++;
}
else
{
while (lock.counter > 0)
{
release_lock_control
wait_for_condivar
acquire_lock_control
}
lock.counter = 1;
lock.owner = me;
}
release_lock_control
}
The above is portable, and SMP safe.
Can you write us a recursive Lock() using psuedocode that shows what you
mean? The people reading this don't believe it can be done without
syncronisation (i.e. without those acquire/release_lock_control calls).
>> It is possible if you store 'have I got this lock?' in thread local
>> storage.
>> So yes, by keeping a counter here, you don't need a memory barrier in
>> recursive Lock()/Unlock() *. However, when you find that you don't have
>> the
>> semaphore, you still need synchronisation between threads so that the
>> sema4
>> is acquired safely.
>> What you've ended up doing here is accessing TLS for *every* acquire -
>> thus
>> making the common case of 'semaphore not acquired' slower.
>>
>> (* not true on certain SMP architectures. Without a memory barrier in
>> Lock()/Unlock(), a thread rescheduled on a different CPU may mis-read the
>> recursive counter (depending on how TLS is implemented).)
>
> I think I now know what the reason of these misunderstandings are:
> You and some others seem to see a lock as a property of a thread,
> and by this you do "lock the thread". I on the other hand see a lock as
> a property of the shared object.
> I don't use any TLS, I use just the usual sharing mechanism of threads;
> ie. all objects in a program can be accessed by all threads.
> By this, I put locks on objects, not threads.
> Each such shared object has its own mutex, and not one mutex per thread,
> and of course also not one mutex for all threads (which IMO is nonsense).
>
>
No, I think of a lock as related to one or more pieces of data, not a
thread. Threads acquire the lock to access the data. Recursive locks, IMO,
are used to 'convenience' of coding, where it's easier and/or faster to use
a recursive lock than get your locking design completely correct. If you're
writing an API, recursive locks are a bad idea. If you're writing a
self-contained piece of code and maintainability isn't the
be-all-and-end-all, recursive locks are acceptable.
The TLS was an idea here to implement recursive locking without
syncronisation when you already own the sema4, but as I pointed out, it a)
won't work on all SMP machines, and b) will run slower.
Again, you've not actually answered any of my questions. You've pointed out
that I'm wrong, and you're right, but not why.
doug
He's getting at this - how do you decide if you own the lock? If multiple
threads can possibly be reading/writing the same location, you need
synchronisation. If not, why are you even using a lock in the first place?
You say "The code which increments the counter cannot be executed by anyone
else but the current lock holding thread." But how does the current thread
know if has the lock? I assume this is code internal to the Lock() routine,
but surely it must be accessing some shared data - a field in the lock
saying who owns it, for example?
See my post above. Write some pseudocode for Lock() and we'll see.
doug
Again, not answering the points. They are:
- I cannot enumerate the list of locks. Many are dynamically created on the
fly (to protect a dynamically created piece of data). There are hundreds
of threads, and thousands of semaphores. I cannot actually generate the
input your program requires. I see how it would be useful for small stuff,
e.g. for a Uni project, though.
- Your theory provides no allowance for dynamic flow-of-control - i.e. the
behaviour of the program must be completely predicatable a priori (or do you
expect the user to sit and type is every possible combination of acquires
for each thread??). Therefore, it's a specialisation, not a generalisation.
You have tightened the general rules of hierarchical locking to suit your
restricted problem space.
doug
"doug" <no...@nowhere.co.uk> wrote in message
news:ds2ie.56042$a9.5...@fe3.news.blueyonder.co.uk...
^^^ Sorry, the above two lines were supposed to be on the same line, editor
folded them for me. It's supposed be be an atomic release-and-wait (e.g.
pthreads pthread_cond_wait)
David Schwartz
> You seem to not understand what I'm talking about.
> Do you understand this fact: "Recursive locking is defined for the current
> lock owning
> thread only"?
> Since you already have the lock you can do what ever you want since nobody
> else can change anything, but you can do! You simply increment it in
> Lock()
> and decrement it in Unlock(). Because it is safe because you already have
> it locked.
Holy cow! Have you actually seen the way any recursive lock is actually
implemented?
DS
David Schwartz
> "David Schwartz" wrote
>> I never argued the performance issue. But here's a more realistic
>> example:
> The example was in response to Peter's posting who wrote "No, he's in fact
> making the
> program faster."
> To your question regarding the speed of recursive vs. non-recursive locks:
> True, recursive locking is slower than non-recursive locking.
Right, so there's a performance penalty.
> But recursive locking simplifies coding (no need to have a locked and
> unlocked
> version of a function)
Simplifies? How hard is to write:
void locked_f()
{
Lock();
f();
Unlock();
}
Or even:
void f(bool locked)
{
LockHolder lh(locked);
// code goes here
}
> and makes the application safer wrt self-deadlocking.
Actually, as I've showed many times, it makes it much less safe because
the semantics of the 'unlock' function are ambiguous.
> And my point is: if the recursive-locking is a fast implementation, then
> the
> overhead of recursive locking is minimally (inc and dec). And if this is
> true (and it is)
> then why make life complicated by not using them since they have the above
> positive properties.
Actually, it's not true. A recursive lock must first determine what
thread holds the lock, and this can be an expensive operation.
> And, IMO it is not a good design to test in f() whether the object
> was locked or not. I prefer the following "agreement" or "contract":
> It is the caller's job to call f() only after having the lock.
> It is not f()'s job to check whether the object was locked.
> This too simplies coding, and it leads to faster programs.
I agree, however, this is exactly what using recursive mutexes does. The
first thing the implementation of a recursive mutex must do is check whether
the current thread holds the lock or not.
DS
David Schwartz
> You are putting operations into 2 categories:
> 1) operations which can be done only if the object is locked
> 2) operations which can be done only if the object is not locked
Right.
> This is unneccessary complication, and it's dangerous.
Huh?
> My point of view is: all operations on a shared object can be done only
> in a locked state (#1 above).
What?! No. There are plenty of operations on a shared object that can
only be done in an unlocked state. For example, one cannot wait for another
thread to do something to a shared object when that object is in a locked
state!
> So one has to forget #2 and never assume to do #2.
Have you ever worked on a project of any significance, say 25,000 lines
or more, that involved multi-threading?!
> An object can be modified only in a locked state, otherwise wait or
> give up your time-slice back to the schedular.
Exactly. But before you wait or give up your time-slice, you must
release any locks you hold or you'll be waiting *forever*.
>> Here's another one:
>>
>> x.Lock();
>> while (x.IsReservedByAnotherThread())
>> {
>> x.Unlock();
>> DoOtherStuffSinceXIsNotReady();
>> }
>> x.DoStuff();
>> x.Unlock();
>>
>> This code will deadlock if the x mutex is recursive. The other thread
>> can never clear its reservation because this thread might still hold the
>> x
>> mutex through the entire 'while' loop.
> The same would happen with non-recursive locking too, wouldn't it?
No. Because 'x.Unlock()' is *guaranteed* to unlock the object if the
lock is not recursive.
> Besides this, it is a bad and buggy design. You never should lock an
> object in a scope and unlock it in a different scope.
What?! So you don't like:
x.Lock();
if(x.IsAlreadyDone())
{
x.Unlock();
return();
}
/* lots of code here to do what has to be done */
x.Unlock();
What is wrong with that exactly?!
>> We really mean what we're saying. Really, really. Recursive mutexes
>> are
>> really bad and they really do hide serious bugs.
> This is simply not true. Recursive locking is a superset of non-recursive
> locking.
> Everthing possible in non-recursive locking is possible in
> recursive-locking too,
> except deadlocking himself. So then how can recursive-locking be more
> dangerous
> than non-recursive locking? This is simple basic logic.
HAHAHAHAHAHAHAHAHA!
A loaded gun is a superset of an unloaded gun. Everything possible with
an unloaded gun is possible with a loaded gun. So how can a loaded gun be
more dangerous than an unloaded gun? This is your brand of logic.
DS
David Schwartz
> Ok, I'll wait a while before replying to what you have written.
> In the mean time can you just tell me for which target OS you
> do develop and which threading pkg you use?
If you were talking to me, I develop multi-threaded software for WIN32,
Linux, Solaris, FreeBSD, and a few other UNIXes. As for which threading
package you use, I'm not sure what you mean. WIN32 has its threading
primitives and UNIXes have theirs. I do have a set of adaptation classes
that gives me a consistent set of C++ threading classes on both platforms.
DS
David Schwartz
> I can only repeat: The code which increments the counter cannot be
> executed by anyone else but the current lock holding thread.
> Do you know what a critical section is?
Why don't you show us some pseudo-code for how you think a recursive
mutex lock function is implemented.
DS
doug
hierarchical locking theorem has another serious drawback. Not only does
each thread have to know exactly what it has done in the past (i.e. you must
have predefined sets of callstacks, limiting flexibility), but each thread
*needs to know exactly what every other thread is doing too*. This is a
huge drawback - bang goes your decoupled design. Components will be so
coupled in their locking requirements, that any serious long-term
maintenance and/or large scale project will be doomed to failure. You are
writing code to work with other threads, rather than a set of well-defined
rules.
David Butenhof
> "David Schwartz" wrote
>>really bad and they really do hide serious bugs.
>
>
> This is simply not true. Recursive locking is a superset of non-recursive locking.
> Everthing possible in non-recursive locking is possible in recursive-locking too,
> except deadlocking himself. So then how can recursive-locking be more dangerous
> than non-recursive locking? This is simple basic logic.
Simple, basic logic.
First, implementation of efficient and reliable threaded code revolves
around one simple and basic principle: follow your design. That implies,
of course, that you have a design, and that you understand it.
A correct and well understood design does not require recursive mutexes.
While recursive mutexes may seem a convenience for debugging, in fact
it's the opposite -- you're better off with a "strict" debugging mutex
(like the POSIX error-check attribute) that checks, tracks, and enforces
ownership restrictions a "normal" mutex may ignore in favor of runtime
efficiency.
Many implementations may have arrived at the concept of recursive
mutexes for any number of reasons -- some perhaps even because someone
really thought they were a good idea. But allow me to explain, for the
sake of context, why POSIX has recursive mutexes. Bear with me, because
I'll follow into some more objective commentary.
In the early days of POSIX, we were also working with the Open Software
Foundation to provide a thread library for DCE (known commonly as "DCE
threads" or sometimes "D4 threads" because the interface vaguely
resembles that of the draft 4 version of the POSIX threads amendment).
We came to the realization that the biggest contraint was compatibility
with existing NON-threaded operating systems.
The biggest problem with threading existing code is that locking
requires analysis and understanding of the data and code relationships.
That can be a stupendous and impractical job for something the size and
complexity of, for example, the typical C runtime of a non-threaded
operating system. Especially when you consider that we were supplying
reference code for upwards of a dozen operating systems. Most (though
not all) were from the "UNIX" family -- but of vastly differing
branches. Analyzing and repairing even one was infeasible, and we
couldn't ignore any of them.
There's one common idiom to deal with this sort of task, external
locking: ( lock_mutex(&a); x = malloc(size); unlock_mutex(&a); ). But of
course every facility in the process that calls malloc() needs to agree
on a single mutex "a". And because something you call while holding the
lock might also call malloc(), the lock must have the property that the
owning thread can re-lock without deadlocking.
But unless you can do enough analysis to identify all possible execution
paths, you can only use a single mutex within the process: a "global
lock". There need be only one; there CAN be only one. Because if you
know that it's OK to have more than one, you don't need any at all; you
can simply lock properly in the first place, where needed.
And so DCE threads has pthread_lock_global() and
pthread_unlock_global(). But if that's all that's necessary, why does
POSIX have recursive mutexes?
Because of a dare.
We were pushing in the POSIX working group for our concept of attributes
objects. And in particular the idea that one could support a range of
potentiallyf useful and non-standard fundamental mutex behaviors without
substantially complicating a simple and fast "inline lock" code path or
invalidating basic POSIX semantics; that is, all the complication would
be kept out of the main and common lock code. Some people just didn't
believe us.
So I proved it by generalizing "the global lock" into a recursive mutex
attribute. Of course it worked, though we never actually bothered to DO
anything with the proof. However, having implemented it, I didn't bother
to delete it, and it went into our code base. And that made it part of
DCE threads on the next code drop to OSF. And it seemed silly to have it
and not document it. Besides, I also built a strict "error-check" mutex
type that would rigidly enforce mutex ownership, and that was useful for
debugging.
But nobody was supposed to use recursive mutexes. For the original
intended purpose, only the global mutex would work anyway. And if you
could analyze the code paths enough to know that a separate mutex was
safe, why the heck would anyone want the overhead and complication of a
recursive mutex instead of just doing it right? I still didn't delete
it, but I more or less stopped thinking about it for many years. POSIX
finally became threaded with the approval of POSIX 1003.1c-1995, and
POSIX 1003.1, 1996 edition, integrated it all into a single document.
And then along came The Open Group, which had already successfully tied
together the "1170" common interfaces of disparate UNIX environments
into a single portable specification, UNIX 93. And then followed with
UNIX 95, adding more common features. All very nice. And now they were
working on UNIX 98, and it would include threads.
But they didn't want just "POSIX threads". They wanted common and
reasonably widely accepted EXTENSIONS to threads. Many of these
extensions were really useful. Some were utterly stupid (like
pthread_setconcurrency(), meaningful only to pitifully busted 2-level
scheduler hacks, though I won't say any more at the risk of beginning to
sound a little biased ;-) ). In particular, though, almost everyone
thought that recursive mutexes should be in there. And they are.
OK, I said I'd actually comment on the objective facts. So here are a
couple...
1) The biggest of all the big problems with recursive mutexes is that
they encourage you to completely lose track of your locking scheme and
scope. This is deadly. Evil. It's the "thread eater". You hold locks for
the absolutely shortest possible time. Period. Always. If you're calling
something with a lock held simply because you don't know it's held, or
because you don't know whether the callee needs the mutex, then you're
holding it too long. You're aiming a shotgun at your application and
pulling the trigger. You presumably started using threads to get
concurrency; but you've just PREVENTED concurrency.
I've often joked that instead of picking up Djikstra's cute acronym we
should have called the basic synchronization object "the bottleneck".
Bottlenecks are useful at times, sometimes indispensible -- but they're
never GOOD. At best they're a necessary evil. Anything. ANYTHING that
encourages anyone to overuse them, to hold them too long, is bad. It's
NOT just the straightline performance impact of the extra recursion
logic in the mutex lock and unlock that's the issue here -- it's the far
greater, wider, and much more difficult to characterize impact on the
overall application concurrency.
People often say "I added threads to my application and it got slower.
Stupid threads". And the answer is almost always, no (but we'll be more
tactful here), "uninformed programmer". They forget to unlock when they
need to, because they forget that where you unlock is just as important
as where you lock. Threading is NOT just about about "a different model
for application structure", it's about concurrency. Locks kill
concurrency. Locks held longer than necessary for "safety" kill
concurrency even worse.
2) Sometimes you need to unlock. Even if you're using recursive mutexes.
But how do you know how to unlock? Threaded programming is built around
predicates and shared data. When you hand a recursive mutex down from
one routine to another, the callee cannot know the state of predicates
in the caller. It has to assume there are some, because it cannot verify
there aren't; and if the caller had known that there were no broken
predicates, it should have allowed concurrency by unlocking.
So how can you wait? You need to release (not just unlock) the mutex in
order to allow some other thread to change a predicate. But if you
release, you've left your predicates dangling in the wind... unchecked,
unknown, unprotected. That's idiotic design, and the most fundamental
error in the Java language. "Don't call while holding broken
predicates", is all they can say by way of excuse. But if there are no
broken predicates, you UNLOCK so the application can have a chance to
act concurrent. If you're ever going to design a language that tries to
do this, make sure it has real first-class support for predicates, so
that it understands who they are and what they mean, and can make
decisions like this for you, reliably. At the very least it has to be
able to diagnose when you blow it... and Java can't even do that.
POSIX, luckily, doesn't provide the mechanism to perform this sort of
data demolition. You can only unlock, and you cannot detect when an
unlock will release. That is, when you call pthread_cond_wait() on a
recursive mutex, you may NOT release... and in that case you've
deadlocked. You'll never continue from your predicate loop until some
other thread changes the predicate, which it can't do because you hold
the lock. The rest of the application may or may not eventually come to
a halt, but you sure haven't done it any good. You're squeezing the
entire application through your bottleneck.
Recursive mutexes are a hack. There's nothing wrong with using them, but
they're a crutch. Got a broken leg or library? Fine, use the crutch. But
at least be aware that you're using a crutch, and why; and once in a
while check out the leg (or library) to be sure you still need the
crutch. And if it's not healing up, go see a doctor, because that's just
not OK. When you have no choice, there's no shame in using a crutch...
but you can't run very well on a crutch, and you'll also be slowing down
anyone who depends on you.
Recursive mutexes can be a great tool for prototyping thread support in
an existing library, exactly because it lets you defer the hard part:
the call path and data dependency analysis of the library. But for that
same reason, always remember that you're not DONE until they're all
gone, so you can produce a library you're proud of, that won't
unnecessarily contrain the concurrency of the entire application.
Or sit back and let someone else do the design.
--
Dave Butenhof, David.B...@hp.com
HP Utility Pricing software, POSIX thread consultant
Manageability Solutions Lab (MSL), Hewlett-Packard Company
110 Spit Brook Road, ZK2/3-Q18, Nashua, NH 03062
Dragan Cvetkovic
[snip]
> A correct and well understood design does not require recursive
> mutexes. While recursive mutexes may seem a convenience for debugging, in
> fact it's the opposite -- you're better off with a "strict" debugging mutex
> (like the POSIX error-check attribute) that checks, tracks, and enforces
> ownership restrictions a "normal" mutex may ignore in favor of runtime
> efficiency.
>
> Many implementations may have arrived at the concept of recursive mutexes
> for any number of reasons -- some perhaps even because someone really
> thought they were a good idea. But allow me to explain, for the sake of
> context, why POSIX has recursive mutexes. Bear with me, because I'll follow
> into some more objective commentary.
[snip of the excellent description of recursive mutex history]
> Recursive mutexes can be a great tool for prototyping thread support in an
> existing library, exactly because it lets you defer the hard part: the call
> path and data dependency analysis of the library. But for that same reason,
> always remember that you're not DONE until they're all gone, so you can
> produce a library you're proud of, that won't unnecessarily contrain the
> concurrency of the entire application.
>
> Or sit back and let someone else do the design.
Dave, you should collect all these essays of yours posted to c.p.t and
publish the (long awaited) second edition of your book around it :-)
Dragan
--
Dragan Cvetkovic,
To be or not to be is true. G. Boole No it isn't. L. E. J. Brouwer
!!! Sender/From address is bogus. Use reply-to one !!!
David Butenhof
> David Butenhof <david.b...@hp.com> writes:
> [snip of the excellent description of recursive mutex history]
Thanks. For the "excellent", that is, not for the "snip". ;-)
>>Recursive mutexes can be a great tool for prototyping thread support in an
>>existing library, exactly because it lets you defer the hard part: the call
>>path and data dependency analysis of the library. But for that same reason,
>>always remember that you're not DONE until they're all gone, so you can
>>produce a library you're proud of, that won't unnecessarily contrain the
>>concurrency of the entire application.
>>
>>Or sit back and let someone else do the design.
>
> Dave, you should collect all these essays of yours posted to c.p.t and
> publish the (long awaited) second edition of your book around it :-)
You know, I actually got bugged by an editor at A-W a week or so ago,
and I really am thinking about it. I just need to survive this bloody
HP-UX release and get some time to come up for air. (It's been rare that
I find time even to skim through the newsgroup in the past few months,
but I do miss it. ;-) )
On the other hand, while I've had fun writing long POSIX reminiscences,
I could probably fill a whole book just with that, nevermind fitting in
actual information. Might be fun... but would it sell? I'm not quite old
enough to call it "Musings of a Threads Curmudgeon" (and anyway I'd
already bestowed that title on a previous manager).
Dragan Cvetkovic
> Dragan Cvetkovic wrote:
>> Dave, you should collect all these essays of yours posted to c.p.t and
>> publish the (long awaited) second edition of your book around it :-)
>
> You know, I actually got bugged by an editor at A-W a week or so ago, and I
> really am thinking about it. I just need to survive this bloody HP-UX
> release and get some time to come up for air.
Nice to hear that. Never mind HP-UX :-)
doug
"David Butenhof" <david.b...@hp.com> wrote in message
news:8erie.5568$FJ4....@news.cpqcorp.net...
I'd buy it...
Thomas Mueller
>
> On the other hand, while I've had fun writing long POSIX reminiscences,
> I could probably fill a whole book just with that, nevermind fitting in
> actual information. Might be fun... but would it sell?
If Stroustrup's "The Design and Evolution of C++" sells, then
yours should sell too.
--
Thomas Mueller
Markus Elfring
> 1) operations which can be done only if the object is locked
> 2) operations which can be done only if the object is not locked
>
> An object can be modified only in a locked state, otherwise wait or
> give up your time-slice back to the schedular.
How does your statement fit to existing lock-free algorithms?
Regards,
Markus
Uenal Mutlu
We were talking about locking.
Lock-free shared access is IMO an illusion, usabe for some very small
and limited cases only, but not for 99.9% of practical requirements.
And IMO they are also slower than a method which uses locking, even
if this might sound counter-intuitive.
David Butenhof
Lock-free is NOT a 100% solution. (There have been fanatics who denied
that and made the whole thing look a bit unsavory... but I think we're
all long over that. I thought we were past the fanaticism on the other
side, too; but maybe not.) It's overly complicated for many simple jobs,
though a lot of people are working on packages (particularly C++
template libraries) to make it easier and more portable. Still, it DOES
provide substantial benefit not only in straightline performance but
also in process and system throughput for many common tasks when used
carefully and properly.
Lock-free has different contention properties. There ARE algorithms
where the SPEEDUP due to lock-free will DECREASE application throughput.
But that's not because lock-free is inherently bad, or slow; only
because the improvement has shifted the bottleneck to other parts of the
application that lack scalability (and may often be harder to fix). In
tuning a commercial thread library, I've had personal experience with
this effect in many commercial applications; and they don't hesitate to
complain that the new release "slowed their code". It IS a risk, and can
require substantial design work to overcome. But it just means the
application design was bad in the first place; and if you're willing and
able to fix it you can benefit enormously from the previously untapped
concurrency.
If you want to investigate the relationships (both cooperative and
adversarial) between lock-free and locked design strategies, google
through the archives of this newsgroup -- we've had some quite "lively"
discussions on that topic over the years. ;-)
Uenal Mutlu
>
> "Uenal Mutlu" wrote in message
> > "doug" wrote
it is done inside Lock() --> TryLock(); see below.
> Your description above sounds like you're saying:
> - use a lock for the first time you grab the counter
> - use a counter thereafter.
> But then your thread needs to know if already owns the lock. So this isn't
> a recursive semaphore at all.
>
> Let's start again. Here is some pseudocode for a recursive Lock() routine.
> A recursive lock consists of a mutex (lock control), a signal var
> (condivar), a counter, and a thread identifier.
>
> Lock()
> {
> acquire_lock_control
> if (lock.owner == me)
> }
> lock.counter++;
> }
> else
> {
> while (lock.counter > 0)
> {
> release_lock_control
> wait_for_condivar
> acquire_lock_control
> }
> lock.counter = 1;
> lock.owner = me;
> }
> release_lock_control
> }
>
> The above is portable, and SMP safe.
>
> Can you write us a recursive Lock() using psuedocode that shows what you
> mean? The people reading this don't believe it can be done without
> syncronisation (i.e. without those acquire/release_lock_control calls).
It indeed can be done. Hint: just make use of the "other possible values" of the counter itself.
Here's a skelleton of my recursive mutex (pseudo code):
void Lock(someparam)
{
if (TryLock(someparam))
return;
//...magic and undisclosed part here :-)
}
void Unlock(someparam)
{
//...magic and undisclosed part here :-)
}
bool TryLock(someparam)
{
if (++cLocked == 1) // actually an atomic pre-increment operator (ie. class method)
{
// first Lock; ie. thread has locked it
//...magic and undisclosed part here :-)
}
// else test whether the current thread is the same thread which holds the lock,
// and if yes then return success (counter cLocked will be >1)
//...magic and undisclosed part here :-)
}
It uses an atomic variable named cLocked and true atomic operations to inc/set/chg it.
The key thing is the first statement in TryLock()...
There are of course some decrements too, but just try to figure it out yourself...
Uenal Mutlu
Oops, should mean "... to inc/dec/set it".
Dragan Cvetkovic
Does it matter? I don't think anybody is listening to you any more.
Chris Thomasson
> that and made the whole thing look a bit unsavory...
The old SenderX... I have seen the light!
:)
I am finding that an effective marriage between lock-based and lock-free can
provide optimal solutions for all sorts of well-known problems...
> It's overly complicated for many simple jobs, though a lot of people are
> working on packages (particularly C++ template libraries) to make it
> easier and more portable.
Yes. Once you get the required infrastructure up and running, hiding a
lock-free algorithm behind a simple API can be relatively easy. As for
portability, I still don't trust C compilers. They can reorder instructions
under your nose. This is why I try to keep all of my lock-free code in
externally assembled functions. This can limit the number of chances a C
compiler has to screw you over:
http://groups-beta.google.com/group/comp.programming.threads/msg/423df394a0370fa6
;)
> Still, it DOES provide substantial benefit not only in straightline
> performance but also in process and system throughput for many common
> tasks when used carefully and properly.
>
> Lock-free has different contention properties. There ARE algorithms where
> the SPEEDUP due to lock-free will DECREASE application throughput. But
> that's not because lock-free is inherently bad, or slow; only because the
> improvement has shifted the bottleneck to other parts of the application
> that lack scalability (and may often be harder to fix). In tuning a
> commercial thread library, I've had personal experience with this effect
> in many commercial applications; and they don't hesitate to complain that
> the new release "slowed their code". It IS a risk, and can require
> substantial design work to overcome. But it just means the application
> design was bad in the first place; and if you're willing and able to fix
> it you can benefit enormously from the previously untapped concurrency.
Well said.
> If you want to investigate the relationships (both cooperative and
> adversarial) between lock-free and locked design strategies, google
> through the archives of this newsgroup -- we've had some quite "lively"
> discussions on that topic over the years. ;-)
The SenderX files?
;)
--
http://appcore.home.comcast.net/
(portable lock-free data-structures)
Uenal Mutlu
> Uenal Mutlu wrote:
>
> > "Torsten Robitzki" wrote
> >
> >>Uenal Mutlu wrote:
> >>>
> >>>It is really basic stuff. Ask yourself how you would extend a non-recursive
> >>>locking method to make it recursive? Recursivity starts with the 2nd Lock()
> >>>call on the same object within the same thread, true?
> >>
> >>First one have to check if this lock request comes from the thread
> >>holding the mutex or not. This can not be implemented by a simple
> >>increment.
> >
> >
> > I can only repeat: The code which increments the counter cannot be
> > executed by anyone else but the current lock holding thread.
>
> What will a thread that does not hold the lock prevent it from
> incrementing the counter if not by checking if it's holding the lock or
> not?
What about a policy?
FYI: in reply to doug I've posted a code-snippet to show this.
> > For which OS and using which threading pkg do you develop?
>
> OpenVMS/Alpha with some C++ wrapper around pthread.
Do you know or believe that your OS makes no use recursive mutexes?
I personally cannot believe that any complex system of nowadays like an
OS or any server application can be developed without recursive mutices.
Uenal Mutlu
> "Uenal Mutlu" wrote in message
For the code see my other reply to you.
Uenal Mutlu
>
> "Uenal Mutlu" wrote in message
>
> > executed by anyone else but the current lock holding thread.
> > Do you know what a critical section is?
>
> Why don't you show us some pseudo-code for how you think a recursive
> mutex lock function is implemented.
See my reply to doug.
Uenal Mutlu
>
> "Uenal Mutlu" wrote in message
>
> > Do you understand this fact: "Recursive locking is defined for the current
> > lock owning
> > thread only"?
> > Since you already have the lock you can do what ever you want since nobody
> > else can change anything, but you can do! You simply increment it in
> > Lock()
> > and decrement it in Unlock(). Because it is safe because you already have
> > it locked.
>
> Holy cow! Have you actually seen the way any recursive lock is actually
> implemented?
Sure, I've even researched and stress tested them, developed many variants myself.
Otherwise I wouldn't discuss them. For code see my reply to doug.
Casper H.S. Dik
>Do you know or believe that your OS makes no use recursive mutexes?
>I personally cannot believe that any complex system of nowadays like an
>OS or any server application can be developed without recursive mutices.
The Solaris kernel does not use recursive mutexes; that, I think,
sufficiently discredits your "belief".
The Solaris runtime does implement recursive mutexes, as
part of the POSIX thread library/UI threads (they're the
same). I know of one use in the Solaris runtime, but
only because we've decided to use the same lock
for flockfile() as we use for ordinary stdio
calls. But there's no particular reason that it
has to be implemented that way.
(The recursive mutex is only slightly more expensive
than the ordinary mutex as the unlock path is more
expensive)
Casper
--
Expressed in this posting are my opinions. They are in no way related
to opinions held by my employer, Sun Microsystems.
Statements on Sun products included here are not gospel and may
be fiction rather than truth.
Uenal Mutlu
>
> "Uenal Mutlu" wrote in message
> >>
> >> For the current code I'm working on, it would take me several hours,
> >> perhaps
> >> days, to type in the lock information his tool requires.
> >
> > If you strictly follow the deadlock theorem I posted here, then you can
> > be assured that no deadlock will happen.
> >
> >> That's not to mention the fact that threads are created dynamically, and
> >> their behaviour
> >> is unpredictable (I see nothing in his tool that allows you to grab this
> >> lock OR that lock, depending on some state.).
> >
> > It is intended for locks put on individual shared objects. Ie. it is not
> > for "locking threads" or something that.
> > It is irrelevant when the threads are created. It is important what the
> > threadproc does: ie. in which order it locks the objects.
> > The requirement is: you must create a list of all your shared objects (the
> > order
> > is irrelevant), then in each threadproc pick the objects you want to use
> > just in the same order as they are on the list.
> >
> >> All he's done is specialise hierarchical locking for simplified
> >> scenarios.
> >
> > Not true. The deadlock theorem I formulated is an important
> > generalization.
> >
>
> Again, not answering the points. They are:
> - I cannot enumerate the list of locks. Many are dynamically created on the
> fly (to protect a dynamically created piece of data). There are hundreds
> of threads, and thousands of semaphores. I cannot actually generate the
> input your program requires. I see how it would be useful for small stuff,
> e.g. for a Uni project, though.
Actually, for nothing else it was intended.
> - Your theory provides no allowance for dynamic flow-of-control - i.e. the
> behaviour of the program must be completely predicatable a priori (or do you
> expect the user to sit and type is every possible combination of acquires
> for each thread??).
I must say that people sometimes unnecessarily complicate things.
Just make a lists of the shared objects and apply the deadlock theorem.
Just see how I did it in the other posting of today where a class with
3 independent data members had to be shared by an arbitrary number
of threads (even more than 1000).
> Therefore, it's a specialisation, not a generalisation.
> You have tightened the general rules of hierarchical locking to suit your
> restricted problem space.
It is not hierarhical locking. My method sees all objects as being
independent of each other. If you must build hierarchies then you
can do this by simply locking each object in order of its hierarchy.
For example: oDatabase, oTable, oField would be locked as follows:
oDatabase.lock();
o.Table.lock();
oField.lock();
now all 3 are locked hierarchically (in the same thread of course).
As such, my method is flexible to create even such hierarchies on the fly.
This technique was also used in the above mentioned solution.
David Schwartz
If you mean this:
void Lock(someparam)
{
if (TryLock(someparam))
return;
//...magic and undisclosed part here :-)
}
void Unlock(someparam)
{
//...magic and undisclosed part here :-)
}
bool TryLock(someparam)
{
if (++cLocked == 1) // actually an atomic pre-increment operator (ie.
class method)
{
// first Lock; ie. thread has locked it
//...magic and undisclosed part here :-)
}
// else test whether the current thread is the same thread which holds
the lock,
// and if yes then return success (counter cLocked will be >1)
//...magic and undisclosed part here :-)
}
It's so horribly broken that, if anything, it proves my point. For
example, the 'TryLock' function increments the lock count even if some other
thread holds the lock. It's hard to imagine how you can write a sane
'Unlock' function once you've made it impossible to tell whether the lock
actually gets unlocked or not.
DS
Uenal Mutlu
It is not broken, and your observation is correct. Just think of a decrement somewhere
and you'll have found the holy grail... :-)
David Butenhof
>>Lock-free is NOT a 100% solution. (There have been fanatics who denied
>>that and made the whole thing look a bit unsavory...
>
> The old SenderX... I have seen the light!
Are you seriously claiming that "Chris Thomasson == SenderX"?
Fascinating. That would certainly explain some things...
Huh. ;-)
> :)
>
> I am finding that an effective marriage between lock-based and lock-free can
> provide optimal solutions for all sorts of well-known problems...
>
>>It's overly complicated for many simple jobs, though a lot of people are
>>working on packages (particularly C++ template libraries) to make it
>>easier and more portable.
>
> Yes. Once you get the required infrastructure up and running, hiding a
> lock-free algorithm behind a simple API can be relatively easy. As for
> portability, I still don't trust C compilers. They can reorder instructions
> under your nose. This is why I try to keep all of my lock-free code in
> externally assembled functions. This can limit the number of chances a C
> compiler has to screw you over:
However, there are a lot of linkers that can do optimization and
restructing at LINK time, too. A far better solution is a compiler that
understands multithread visibility rules and does the right thing in the
first place. Realistically, most C/C++ compilers are "close enough",
though lock-free certainly stretches the limits further than simple
pthread ops. Still, the atomic ops and fences tend to be call-outs or
builtins (whether asm() or more specialized) that the compiler will
treat as call-outs, and that buys you a lot if you're careful.
Realistically, this may be almost as much as using assembly code buys
you -- and with better readability.
But then... to each their own paranoia, eh? I definitely understand
"where you're coming from". In this context, though, I prefer staying at
the higher level where at all possible... "trust... but verify". ;-)
I look forward to a standardized C++ concurrent memory model. A
standardized C++ threading API would be nice, too, if a useful model can
survive the compromises; but the memory model is what we absolutely
need, now.
> http://groups-beta.google.com/group/comp.programming.threads/msg/423df394a0370fa6
>
> ;)
>
>>Still, it DOES provide substantial benefit not only in straightline
>>performance but also in process and system throughput for many common
>>tasks when used carefully and properly.
>>
>>Lock-free has different contention properties. There ARE algorithms where
>>the SPEEDUP due to lock-free will DECREASE application throughput. But
>>that's not because lock-free is inherently bad, or slow; only because the
>>improvement has shifted the bottleneck to other parts of the application
>>that lack scalability (and may often be harder to fix). In tuning a
>>commercial thread library, I've had personal experience with this effect
>>in many commercial applications; and they don't hesitate to complain that
>>the new release "slowed their code". It IS a risk, and can require
>>substantial design work to overcome. But it just means the application
>>design was bad in the first place; and if you're willing and able to fix
>>it you can benefit enormously from the previously untapped concurrency.
>
> Well said.
>
>>If you want to investigate the relationships (both cooperative and
>>adversarial) between lock-free and locked design strategies, google
>>through the archives of this newsgroup -- we've had some quite "lively"
>>discussions on that topic over the years. ;-)
>
>
> The SenderX files?
Catchy. I like it. ;-)
Markus Elfring
> and limited cases only, but not for 99.9% of practical requirements.
How "limited" is the application of lock-free algorithms for fundamental data structures
like trees, linked lists or queues?
> And IMO they are also slower than a method which uses locking, even
> if this might sound counter-intuitive.
Would you like to show benchmarks for such differences in execution speed?
(Other papers contain statistics that show the opposite runtime behaviour.)
Regards,
Markus
Casper H.S. Dik
>Chris Thomasson wrote:
>>>Lock-free is NOT a 100% solution. (There have been fanatics who denied
>>>that and made the whole thing look a bit unsavory...
>>
>> The old SenderX... I have seen the light!
>Are you seriously claiming that "Chris Thomasson == SenderX"?
>Fascinating. That would certainly explain some things...
>Huh. ;-)
Yep.
http://groups-beta.google.com/group/comp.arch/msg/ff4c28f2c98d98ca?dmode=source
David Schwartz
>> It's so horribly broken that, if anything, it proves my point. For
>> example, the 'TryLock' function increments the lock count even if some
>> other
>> thread holds the lock. It's hard to imagine how you can write a sane
>> 'Unlock' function once you've made it impossible to tell whether the lock
>> actually gets unlocked or not.
> It is not broken, and your observation is correct. Just think of a
> decrement somewhere
> and you'll have found the holy grail... :-)
That won't help you. The thread that does the increment holds no locks
of any kind at the time it does the increment (assuming it's this thread's
first try at the lock), so there's no way to make the thread doing the
unlock wait until after the decrement.
Remember, the code was:
> void Lock(someparam)
> {
> if (TryLock(someparam))
and
> bool TryLock(someparam)
> {
> if (++cLocked == 1) // actually an atomic pre-increment operator (ie.
> class method)
So the thread atomically increments 'cLocked' even if another thread
holds the lock and without holding any locks itself. Suppose the thread just
finishes the '++cLocked' and then gets pre-empted for a long time. What
happens when the thread that holds the lock decrements 'cLocked' and it
doesn't go to zero? It will think it still holds the lock.
There could possibly be ways to get yourself out of this mess in the
"magic and undisclosed" parts. But it would be a horribly ugly and
frightening implementation. It certainly would bear no resemblance to
recursive mutexes as they're actually implemented.
In any event, a single atomic increment costs about 200 cycles on a P4.
DS
Uenal Mutlu
> "Uenal Mutlu" writes:
> > "Sergei Organov" wrote
> > > "Uenal Mutlu"
>
> > I'm willingly making use of its recursivity feature because it
> > simplifies many things, and most importantly it is safer than
> > non-recursive locking,
>
> It depends on the definition of "safer". For me "safer" is not equal to
> "no deadlock".
True, and nobody has said that. A recursive mutex helps only for the
current thread to not deadlock itself. But apart from this the same dangers
for deadlock exist equally for both non-recursive and recursive mutices.
If you apply my deadlock theorem then a deadlock cannot occur.
If you also want to exclude self-deadlocking then the use of
a recursive-mutex will solve even that case. What's left?
> Using my definition of "safer", the recursive lock is not
> safer due to the fact that it allows actual problems in the code to be
> hidden for a long time.
It depends whether you see the use of a recursive mutex
as a problem or not. As I said: if I use a recursive mutex then
I'm making use of its recursion feature. This then cannot
be seen as an error (but we already had discussed this case).
> > though it has a neglectable overhead. If I use a _recursive locking
> > method_ then I'm of course aware of these facts.
>
> If you were aware of the experience that has been gathered in this
> field, you won't use recursive locking method in the first place.
I respect all the old veterans, but please let us also make
some progress in the field, and not always chew the old gum..
> The recursive locks simplify your life by allowing you not to think
> about quality of your design. Kinda like favorite goto's in programming
> languages, -- they do simplify programming in the short run but the
> result is usually a wrong and unmaintainable problem^H^H^H^Hgram in the
> long run. If you consider such simplifications to be a good thing, --
> it's your problem.
I would say that it is even much easier to develop a complex system
and also much easier to maintain it by the use of recursive mutices.
Nevertheless, this seems to be a religious issue, so I do respect your
and other's view on this, but please try to respect my view and my preferance
for recursive mutices too, since I've researched this field and am a
prefessional developer with more than 15 yrs of experience, so
I too know of what I'm talking of. Besides this, I strongly believe the future
belongs to the recursive mutices for their simplicity and safety over
non-recursive mutices, esp. for the huge and complex requirements
nowadays and of the future.
David Schwartz
> I would say that it is even much easier to develop a complex system
> and also much easier to maintain it by the use of recursive mutices.
Have you ever developed and maintained a complex system? Say a project
involving at least 150,000 lines of code, at least 4 programmers, and at
least 4 released versions. I've found that it's much easier when every piece
of code knows what mutexes it holds.
DS
Uenal Mutlu
>
> "Uenal Mutlu" wrote in message
>
> > and also much easier to maintain it by the use of recursive mutices.
>
> Have you ever developed and maintained a complex system? Say a project
> involving at least 150,000 lines of code, at least 4 programmers, and at
> least 4 released versions. I've found that it's much easier when every piece
> of code knows what mutexes it holds.
The biggest project I worked was developing the OS and the application code
of Siemens mobile phones until about 3 yrs ago for two generations (releases).
There were more than 30 developers working on it. Unfortunately I cannot tell
exactly how many LOCs it had, but I remember there were more than 1000 source
files (most C files). Of course we used a concurrent versioning system.
As I once wrote in my previous postings, one has to use encapsulation
to master a complex system. By this one only needs to concentrate on
smaller pieces (modules), and develop them as independent functional modules,
so within such a functional module you normally don't need to know what other
modules do. But, it's maybe all up to the specifics of the project.
I mean: I try to get my own lock. If it fails then it fails --> I then know someone
else has the lock so I give up my time-slice, because what else can I do..?
Steve Thompson
Absolutely agree. I have developed a multi-platform (unix/windows/vms)
batch system called NBS, with over 400K lines of code. The queue
manager/job scheduler portion of this package uses threads heavily. The
first incarnation of the threaded version of this code (a few years ago
now) used recursive mutexes, since at the time I was relatively new to
pthreads and made the newbie mistake of thinking that a recursive mutex
would ease the porting of the previous non-threaded version. Big mistake:
recursive mutexes turn out to be a great way to initially mask design
problems that ultimately lead to a rat's nest of other problems as the
code evolves. It is clear that when multiple structures are being
protected by a per-structure mutex, the use of recursive mutexes can be a
fantastically efficient way to create deadlocks. The qmgr worked, but not
very well (hangs after a few days of operation were common). All recursive
mutexes are gone, the design is much cleaner as a result, the code is
solid as a rock (runs for months on end), and I promise to never ever use
a recursive mutex again. Honest.
-steve
Uenal Mutlu
> > Lock-free shared access is IMO an illusion, usabe for some very small
> > and limited cases only, but not for 99.9% of practical requirements.
>
> How "limited" is the application of lock-free algorithms for fundamental data structures
> like trees, linked lists or queues?
Sounds interessting, but I would be convinced only after testing
their performance. And here I doubt it can be faster, because
I myself had experimented with such structures too and had read papers
on this, but unfortunately the performance was very poor due to the
additional code checks one has to make. It sums up and degrades
the performance.
> > And IMO they are also slower than a method which uses locking, even
> > if this might sound counter-intuitive.
>
> Would you like to show benchmarks for such differences in execution speed?
> (Other papers contain statistics that show the opposite runtime behaviour.)
This assumption is by the fact that you need to put more code to check.
That is: more code must be executed; even just two or three if statements
can mean too much compared to a classical mutex method using atomic counter.
Uenal Mutlu
> "Uenal Mutlu" writes:
...
> (The recursive mutex is only slightly more expensive
> than the ordinary mutex as the unlock path is more
> expensive)
Actually it is just an increment and a comparision of the currentthreadid vs.
the lock holding threadid in Lock(), and a simple decrement in Unlock().
The overhead for recursively locking is far less than the first aquisition
(== non-recursive mutex) of the lock. Cf. code snippet of my other posting to doug and David.
doug
laughing too hard after the second line.
I just seriously hope that I never come across you in my professional
career, or any of the code you've ever touched. I will obviously now avoid
Seimens mobile phones.
David Hopwood
> red floyd wrote:
>
>>May I ask why?
>
> There are two possibilities:
>
> 1) You don't know the mutex is being used recursively. In this case, the
> recursive mutex will hide a serious problem.
>
> 2) You know the mutex is being recursively. In this case, just don't
> lock it since you know it's already locked anyway.
It is sometimes the case that you have code which can usefully be called either
with the mutex already held or with it not already held. This happens in
particular when you have an object protected by a mutex, and some method of
that object can potentially take the same object as an argument.
It's not a very common case, admittedly.
--
David Hopwood <david.nosp...@blueyonder.co.uk>
David Butenhof
> "Sergei Organov" wrote
>
>>"Uenal Mutlu" writes:
>>
>>>"Sergei Organov" wrote
>>>
>>>>"Uenal Mutlu"
>>
> and also much easier to maintain it by the use of recursive mutices.
> Nevertheless, this seems to be a religious issue, so I do respect your
> and other's view on this, but please try to respect my view and my preferance
> for recursive mutices too, since I've researched this field and am a
> prefessional developer with more than 15 yrs of experience, so
> I too know of what I'm talking of. Besides this, I strongly believe the future
> belongs to the recursive mutices for their simplicity and safety over
> non-recursive mutices, esp. for the huge and complex requirements
> nowadays and of the future.
OK, here's a new thought.
If you are in fact writing UNIPROCESSOR code with threads doing nothing
more than slowing down your application through pointless context
switches (that is, strictly as a "code structuring" mechanism), then,
fine. You've got no concurrency in the first place, you want no
concurrency, and recursive mutexes do little harm on top of the cycles
you're wasting already. In that case I'll believe you.
But if any of your code is intended for multiprocessor applications,
take a look at the scalability. Do you run twice as fast with two times
as many threads, or twice as slow? Have you ever looked? Extensive use
of recursive locking is a sure way to prevent concurrency. (Note, I
didn't say "recursive mutexes", but "recursive locking"... if your
recursive mutexes are rarely locked recursively, you're just wasting
straightline compute cycles with the extra recursion logic and they're
essentially just slow normal mutexes... you would be better off USING
normal mutexes for reliability and simplicity, but I'd be willing to
leave THAT as a matter of personal taste.)
Most of the people in this newsgroup do not use threads just to say they
did; they use them because they care about concurrency and scalability
on multiprocessor systems. Fundamentally uniprocessor thinking is not
generally well received when disguised as something else.
Sure, you can argue that recursive mutexes are easier to use. In one
respect (and depending on your goals and and sensitivity), that's even
true. But then, there are many respected computer scientists who argue
against any use of threads for the same reason... plain old sequential
programming is "easier". Threading is hard in a complicated system; all
the more so if you care about throughput and scalability rather than
just pretty code using cool functions. Your "easy" and "reliable"
shortcuts simply run counter to the main point of using threads for most
of us.
Yet, on the other hand, one of the valid (though certainly not the
strongest) reasons to use threads is indeed as a program structuring
tool. And sometimes that's really all you need. And then the performance
consequences aren't a big deal. If that's what you mean, just say so,
and we can wind all this up really quick with a "gee, why didn't you say
so", and "have a nice day".
But, once again, if you're trying to claim that your recursively locked
thread-per-client code SCALES even close to linearly on large
multiprocessors... well, you'll have to prove it. And not with another
load of doubletalk.