[linux-audio-dev] futex vs lock-free
sjenkins at blueyonder.co.uk
Mon Aug 30 13:24:42 EDT 2004
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
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
>>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
>>you indefinitely) stands. Also, I suspect you'd need N separate
>>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
unable to get at the lock until the low priority process regains the
and clears the critical section. The "convoy" metaphor is of a queue of
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.
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
relentless barrage of new and successful structure accesses from other
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
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. Convoying and other priority inversions, OTOH,
are scheduling artifacts which can cause missed deadlines even on a lightly
 On SMP systems one processor may be overwhelming another so that
cycles are available but not able to be used. The protected structure
a bottleneck and you have to start thinking in terms of the structure itself
being overworked rather than the processors.
More information about the linux-audio-dev