df3
Subj : Re: recursive mutexes
To   : comp.programming.threads
From : Uenal Mutlu
Date : Wed May 18 2005 08:54 pm

"doug" wrote
>
> "Uenal Mutlu" wrote in message
> > "doug" wrote
> >>
> >> > 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.
> >
> 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?

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

.

0