Subj : Re: lockless low-overhead 'pipes' (w/semaphores)
To   : comp.programming.threads
From : Joe Seigh
Date : Fri Apr 22 2005 12:46 pm

On Fri, 22 Apr 2005 17:34:53 +0200, Alexander Terekhov <terekhov@web.de> wrote:

>
> Chris Thomasson wrote:
>>
>> > Apart from the SSE string stuff, on IA32 (compiler reordering aside
>> > for a moment), loads have acquire semantics, stores have release
>> > semantics, and interlocked stuff is fully-fenced (compound acquire +
>> > release semantics).
>>
>> Right. The OP should also understand that critical sections can overlap:
>
> Not on IA32 (spinlocks with just release store in unlock aside for a
> moment). Interlocked stuff is fully-fenced on IA32.
>
>>
>> 1: Lock( &l1 );
>> 2: l1_dat += 111;
>> 3: Unlock( &l1 );
>>
>> 4: Lock( &l2 );
>> 5: l2_dat += 222;
>> 6: Unlock( &l2 );
>>
>> Can be legitimately be reordered to:
>>
>> 4: Lock( &l2 );
>> 5: l2_dat += 222;
>> 1: Lock( &l1 );
>> 2: l1_dat += 111;
>> 6: Unlock( &l2 );
>> 3: Unlock( &l1 );
>
> This transformation is not legal. It changes the order of locking
> operations. In general, it is somewhat hard for compilers (but not
> hardware) to "overlap" critical regions because lock() can block,
> but legitimate transformation shall not block preceding unlock.
>
Does something somewhere actually say that last bit.  Actually
they can't overlap because it might cause deadlock, i.e. violate
lock hierarchy.

-- 
Joe Seigh

When you get lemons, you make lemonade.
When you get hardware, you make software.

.