Subj : Re: Challenge: Multithreading & Synchronization
To   : comp.programming.threads
From : doug
Date : Fri May 20 2005 09:45 am


"David Holmes" <dholmes@--remove-this-part-dltech.com.au> wrote in message 
news:428d693c_2@news.melbourne.pipenetworks.com...
> "doug" <noone@nowhere.co.uk> wrote in message
> news:2SOie.16460$2k2.12826@fe1.news.blueyonder.co.uk...
>> I don't want the 'solution' for your code, I want the
>> pseudocode/implementation of a recursive lock that doesn't use memory
>> barriers on recursive calls by the lock owner.  That's it.  That's all.
>> Nothing else.
>
> I don't want to get embroiled in the rest of this mess, but I'm not sure
> what the problem is here.
>
> Accessing the owner field of a recursive lock, by the owner thread does 
> not
> require any memory barriers.

I agree, but what about other threads?  When they grab the lock, they need 
to check to see if they are the owner (the answer will be no, but they still 
need to check).  There must be a memory barrier:
- before the read of the owner field by a thread
- after the write of the owner field by a thread
- before and after reads of the counter too (or it won't work on SMP 
systems, where a thread can be rescheduled on another CPU, and the cache 
lines containing the recursive lock data on the new CPU have not yet been 
invalidated (by the previous lock()).)

 Memory barriers are required to ensure
> consistent memory views between different threads. When a thread becomes 
> the
> owner, or relinquishes ownership, then a memory barrier is involved. When 
> a
> thread is the owner then no memory barrier is needed. This assumes the 
> owner
> field is suitably aligned and can be read atomically. It also assumes that
> no other thread maliciously stores the wrong thread-id in the owner field.
>
> It is not uncommon for Java monitor locks to be implemented this way. The
> psuedocode is:
>
>    mon_enter() {
>      if (mon.owner == currentThread())
>          count++;
>     else
>         mon_enter_slow();  // blocks until monitor is free
>
>   mon_exit() {
>      if (mon.owner == currentThread()) {
>        if (--count == 0)
>           mon_release_slow();
>     }
>     else throw an error
>
> There are no memory barriers on the fast-paths.
>
> David Holmes
>
>

I don't think this is safe - I think it's a disguised case of the 
double-checked locking pattern.
Without a memory barrier before readig mon.owner, you risk reading an old 
value.

Granted, this is unlikely to happen in a JVM (and I thiunk the new java 
memory model is addressing this sort of stuff), but as a general algorithm, 
it doesn't work.  Implement the above in C, and it'll break.  I know, 
because I had to fix a bug exactly like this a few months back.

(Also, you would need to 'unset' the mon.owner in mon_exit)

As for TLS to track recursive locks - yes, as I've said before, you *can* do 
this.  But why would you want to?  You then need to add a TLS access to 
*every* acquire, to check to see if you already own the semaphore.  Thus, 
you make the common case of uncontested acquire slower.  Surely, better just 
to get your locking right - and lock as little as possible, non-recursively.

I may have got something wrong above - please let's discuss if you think so.

Ta,
Doug

.