Subj : Re: Challenge: Multithreading & Synchronization To : comp.programming.threads From : doug Date : Mon May 23 2005 10:24 am "doug" wrote in message news:7KFje.104692$Cq2.64196@fe2.news.blueyonder.co.uk... > > "Giancarlo Niccolai" wrote in message > news:d6n80p$el4$1@newsread.albacom.net... >> 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. >> > > Yep, thanks. Peter also explained this. Seems good to me! > > Doug > Actually, I have a (hopefully) quick question. Is the above algorithm safe in a system where you dynamically create the recursive mutex? E.g. one thread allocates a control block (which includes creating a recursive mutex), and a second thread comes along later and attempts to acquire the sema4. Is it not possible that this second thread might misread uninitialised 'garbage' from the owner field, and may think it already owns the sema4? (Pretty low odds, I know, but still finite.) .