[linux-audio-dev] futex vs lock-free

[Simon Jenkins]

Jack O'Quin wrote:

>I wholly agree with Simon's point that most lock-free structures are
>"good enough for practical purposes."
>
>But, like him, I enjoy a good theoretical discussion, sometimes.
>
Heh. In case it seems like this is all I ever do, I /am/ working away in the
background on some actual useful code which I'll get around to releasing
eventually :)

But back to the theoretical discussion...

>Simon Jenkins <sjenkins at blueyonder.co.uk> writes:
>
>>Bah! Woke up with a hangover and now I'm eating words for breakfast.
>>
>>After one of the N contenders has won, you could get an (N-1)-way
>>re-collision
>>    
>>
>>making the worst-case number of retries spread across all contenders:
>>
>>1 + 2 + ... +  (N-1)
>>
>>Note this is still finite so the conclusion (that only new collisions
>>can starve
>>
>>you indefinitely) stands. Also, I suspect you'd need N separate
>>processors to
>>
>>actually achieve the worst-case figure in practice.
>>    
>>
>This ignores the "convoying" phenomenon, which can occur when the
>original "contention winner" comes back again while there are still
>threads waiting.  The usual spin lock implementation may allow some
>requesters to suffer indefinite starvation if lower priority (or just
>plain unlucky) when Murphy's Law strikes your system.
>
You're describing "starvation", but not "convoying".

Convoying occurs in locking implementations when a low priority process
loses the processor whilst holding a lock. Higher priority processes are 
then
unable to get at the lock until the low priority process regains the 
processor
and clears the critical section. The "convoy" metaphor is of a queue of 
traffic
stuck behind a slow moving vehicle on a single-lane section of road.

Convoying and other priority inversions are completely avoided in lock-free
implementations because a lower priority process never puts the protected
structure into a state where a higher priority process can't access it. 
On single
processor systems, if you can keep the processor for more than a couple of
instructions you can always access the structure. On SMP systems you might
still fail to access the structure, but only for so long as there is a 
continual,
relentless barrage of new and successful structure accesses from other
processors.

Despite the harsher metaphor, starvation is not nearly so bad as convoying.
If a lower priority process goes hungry for a while because a higher 
priority
process is accessing a structure... well... thats what you *want* to happen.
Its only when the lower priority process goes hungry for so long that it
misses some deadline that you have a problem. This is "starvation". The
important point is that starvation is a symptom of an overloaded system
where there simply aren't enough processor cycles available to get all the
work done on time. Nothing's going to solve that except a lighter workload
or a faster processor[1].  Convoying and other priority inversions, OTOH,
are scheduling artifacts which can cause missed deadlines even on a lightly
loaded system.

[1] On SMP systems one processor may be overwhelming another so that
cycles are available but not able to be used. The protected structure 
becomes
a bottleneck and you have to start thinking in terms of the structure itself
being overworked rather than the processors.

Simon Jenkins
(Bristol, UK)