Subj : Re: Challenge: Multithreading & Synchronization
To   : comp.programming.threads
From : Giancarlo Niccolai
Date : Sat May 21 2005 03:02 pm

doug wrote:


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


No, because a misread won't cause any harm.

if ( owner_id == CurrentThread() ) {
        // fast path
}
else {
        //slow path
}

The owner_id may be seen as 
- INVALID
- Any valid value different from CurrentThread()
- CurrentThread().

If another thread gets the lock in another CPU, it will put its
CurrentThread inside owner_id. This thread won't see it, it will still
thing owner_id is INVALID. So what? 

Be owner_id INVALID or any other valid thread id different from
CurrentThread, the result don't change: you go to the slow path and only
THEN you acquire the barrier.

That's because only the FAST path is interested in knowing if it already 
owns the lock, and owner_id == CurrentThread() -> TRUE is safe because this
may happen ONLY when the lock is already held and no other thread can alter
this fact.



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

Correct. You'll READ an old value, but this won't change the outcome of the
test. Unless some other thread can put YOUR thread ID in the owner field,
but we suppose that every thread is fair and can only stack it's own thread
ID in the owner field, or set it to INVALID if it's freed.

Wether the lock is free or held by another thread, it does change nothing
for you; you have to acquire the lock through the barrier anyhow, so
reading it's free while it's locked WON'T HARM YOU. Got it?

Giancarlo.

.