recursive mutexes

5884 views
Skip to first unread message

red floyd

unread,
Jul 15, 2004, 3:09:51 PM7/15/04
to

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

unread,
Jul 15, 2004, 3:15:12 PM7/15/04
to
red floyd <no....@here.dude> writes:

> 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

unread,
Jul 15, 2004, 3:55:24 PM7/15/04
to
red floyd <no....@here.dude> writes:

>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

unread,
Jul 15, 2004, 4:54:56 PM7/15/04
to
Casper H.S. Dik wrote:
> 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

unread,
Jul 15, 2004, 5:29:27 PM7/15/04
to

red floyd wrote: ...

Don't use recursive mutexes. It's akin to sex with used condoms. ;-)

regards,
alexander.

Loic Domaigne

unread,
Jul 15, 2004, 7:42:20 PM7/15/04
to
Hello,

> 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

unread,
Jul 15, 2004, 7:45:07 PM7/15/04
to
> Don't use recursive mutexes. It's akin to sex with used condoms. ;-)

YIKES!


red floyd

unread,
Jul 15, 2004, 7:45:08 PM7/15/04
to

May I ask why?

David Schwartz

unread,
Jul 15, 2004, 7:59:58 PM7/15/04
to
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?

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

unread,
Jul 15, 2004, 8:21:05 PM7/15/04
to
> 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.

There good for hashed locks.


David Schwartz

unread,
Jul 15, 2004, 10:47:24 PM7/15/04
to
SenderX wrote:

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

unread,
Jul 16, 2004, 5:32:32 AM7/16/04
to
red floyd wrote:

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

unread,
Jul 16, 2004, 10:59:25 AM7/16/04
to

> 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

unread,
Jul 16, 2004, 2:14:46 PM7/16/04
to
Martin James wrote:

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

unread,
Jul 16, 2004, 3:00:14 PM7/16/04
to

> 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

unread,
Jul 16, 2004, 4:59:12 PM7/16/04
to
Martin James wrote:

> 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

unread,
May 15, 2005, 2:05:49 AM5/15/05
to
"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.
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

unread,
May 15, 2005, 6:13:43 AM5/15/05
to

"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

unread,
May 15, 2005, 6:41:35 AM5/15/05
to
"Uenal Mutlu" <52000108...@t-online.de> 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.

> 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

unread,
May 15, 2005, 8:41:38 AM5/15/05
to
"David Schwartz" wrote
>
> "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

unread,
May 15, 2005, 9:03:41 AM5/15/05
to
"Måns Rullgård" wrote

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

unread,
May 15, 2005, 10:22:24 AM5/15/05
to
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.


Uenal Mutlu

unread,
May 15, 2005, 10:45:03 AM5/15/05
to
"Måns Rullgård" wrote
> "Uenal Mutlu" writes:
>
> >> >> 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?
>
> No, because having unlocked the mutex, you can be certain that the
> 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

unread,
May 15, 2005, 10:59:07 AM5/15/05
to
"Peter Dimov" wrote

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

unread,
May 15, 2005, 11:11:37 AM5/15/05
to
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().

> 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

unread,
May 15, 2005, 11:11:46 AM5/15/05
to
"Uenal Mutlu" wrote

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

unread,
May 15, 2005, 11:48:09 AM5/15/05
to
"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.
> >>
> >> 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

unread,
May 15, 2005, 1:24:16 PM5/15/05
to
Uenal Mutlu wrote:

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

unread,
May 15, 2005, 2:56:08 PM5/15/05
to

"Uenal Mutlu" <52000108...@t-online.de> wrote in message
news:d67fm3$hah$00$1...@news.t-online.com...

> 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

unread,
May 15, 2005, 2:58:45 PM5/15/05
to

"Uenal Mutlu" <52000108...@t-online.de> wrote in message
news:d67h31$utf$01$1...@news.t-online.com...

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

unread,
May 15, 2005, 3:01:10 PM5/15/05
to
"David Schwartz" <dav...@webmaster.com> writes:

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

unread,
May 15, 2005, 3:03:05 PM5/15/05
to

"Uenal Mutlu" <52000108...@t-online.de> wrote in message
news:d67mtf$roq$03$1...@news.t-online.com...

> 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

unread,
May 15, 2005, 3:06:34 PM5/15/05
to

"Uenal Mutlu" <52000108...@t-online.de> wrote in message
news:d67npb$enc$01$1...@news.t-online.com...

> 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

unread,
May 15, 2005, 3:24:02 PM5/15/05
to

"Uenal Mutlu" <52000108...@t-online.de> wrote in message
news:d67qjn$9o1$00$1...@news.t-online.com...

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

unread,
May 15, 2005, 3:24:54 PM5/15/05
to
"Uenal Mutlu" <52000108...@t-online.de> wrote in message
news:d67h31$utf$01$1...@news.t-online.com...

This is exactly what I mean.


Uenal Mutlu

unread,
May 16, 2005, 12:30:48 AM5/16/05
to
"doug" wrote

>
> "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.
>
> > 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().
>
> 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

unread,
May 16, 2005, 1:04:42 AM5/16/05
to
"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.
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

unread,
May 16, 2005, 1:36:09 AM5/16/05
to
"David Schwartz" wrote
>
> "Uenal Mutlu" wrote
>
> > 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.

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

unread,
May 16, 2005, 1:48:28 AM5/16/05
to
> You seem to not understand what I'm talking about.

You do not seem to understand what "you" are talking about.


Chris Thomasson

unread,
May 16, 2005, 1:52:29 AM5/16/05
to
> 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...


doug

unread,
May 16, 2005, 4:16:43 AM5/16/05
to

> 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

unread,
May 16, 2005, 4:24:58 AM5/16/05
to

"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

unread,
May 16, 2005, 5:01:09 AM5/16/05
to
"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? 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

unread,
May 16, 2005, 5:06:00 AM5/16/05
to
"Uenal Mutlu" <52000108...@t-online.de> writes:
> "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

unread,
May 16, 2005, 5:13:14 AM5/16/05
to
"doug" wrote
>
> "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

unread,
May 16, 2005, 5:29:11 AM5/16/05
to
"Sergei Organov" wrote
> "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.

Message has been deleted

Uenal Mutlu

unread,
May 16, 2005, 6:13:52 AM5/16/05
to
"doug" wrote

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

unread,
May 16, 2005, 8:03:02 AM5/16/05
to
"Uenal Mutlu" <52000108...@t-online.de> writes:
> "Sergei Organov" wrote
> > "Uenal Mutlu"
[...]

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

unread,
May 16, 2005, 8:50:36 AM5/16/05
to
Uenal Mutlu wrote:

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

unread,
May 16, 2005, 9:06:01 AM5/16/05
to
Uenal Mutlu wrote:

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

unread,
May 16, 2005, 10:02:12 AM5/16/05
to
"Torsten Robitzki" wrote

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

unread,
May 16, 2005, 10:09:04 AM5/16/05
to
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?


Uenal Mutlu

unread,
May 16, 2005, 10:30:33 AM5/16/05
to
"Torsten Robitzki" wrote

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

unread,
May 16, 2005, 10:26:19 AM5/16/05
to

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

unread,
May 16, 2005, 10:45:13 AM5/16/05
to
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? 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

unread,
May 16, 2005, 10:51:53 AM5/16/05
to

"Uenal Mutlu" <52000108...@t-online.de> wrote in message
news:d69n7p$on9$04$1...@news.t-online.com...

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

unread,
May 16, 2005, 10:55:25 AM5/16/05
to

"Uenal Mutlu" <52000108...@t-online.de> wrote in message
news:d6aae5$9ac$02$1...@news.t-online.com...

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

unread,
May 16, 2005, 10:59:47 AM5/16/05
to

"Uenal Mutlu" <52000108...@t-online.de> wrote in message
news:d69rcq$r6b$01$1...@news.t-online.com...

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

unread,
May 16, 2005, 11:04:36 AM5/16/05
to

"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

unread,
May 16, 2005, 3:00:38 PM5/16/05
to

"Uenal Mutlu" <52000108...@t-online.de> wrote in message
news:d6979h$15a$02$1...@news.t-online.com...

> 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

unread,
May 16, 2005, 3:05:04 PM5/16/05