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

New Message Reply About this list Date view Thread view Subject view Author view Other groups

Subject: Re: [linux-audio-dev] futex vs lock-free
From: Simon Jenkins (sjenkins_AT_blueyonder.co.uk)
Date: Mon Aug 30 2004 - 20:24:42 EEST


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)


New Message Reply About this list Date view Thread view Subject view Author view Other groups

This archive was generated by hypermail 2b28 : Mon Aug 30 2004 - 19:18:47 EEST