26 Aug
2004
26 Aug
'04
4:29 a.m.
hi all,
i'm considering to add lock free queue support to packet forth, just to
follow the hype, and maybe also because i like the concept. but i'm
wondering if it would make much sense to go through all the trouble with
fast mutexes being available in 2.6
in other words, how much better (apart from being more elegant) are lock
free structures wrt a mutex approach where there is a minimal system
penalty? (not many collisions) did anyone look into this? or have i not
been lurking properly? ;)
cheers
tom
26 Aug
26 Aug
6:10 a.m.
Tom Schouten wrote:
hi all,
i'm considering to add lock free queue support to packet forth, just to
follow the hype, and maybe also because i like the concept. but i'm
wondering if it would make much sense to go through all the trouble with
fast mutexes being available in 2.6
in other words, how much better (apart from being more elegant) are lock
free structures wrt a mutex approach where there is a minimal system
penalty? (not many collisions) did anyone look into this? or have i not
been lurking properly? ;)
OK, futexes are fast in the uncontested case so, with sufficiently rare
collisions,
you expect performance to approach that of a lock-free implementation.
And in terms of overall throughput, it probably does. But in terms of
worst case
delay when there *is* a collision things are no better. The point of the
lock-free
approach is to minimise this worst case delay in a real-time system, so
if this is
important to you then lock-free is the way to go (but see below).
I'm not sure if/when they'll become mainstream, but fuqueues might also be
worth a quick look. (Yes: It is an unfortunate name. Enough said.) They
tackle
the priority inversion problems that can occur with standard
m(/f)utexes, and
are intended for real-time use.
Simon Jenkins
(Bristol, UK)
5:26 p.m.
in other words,
how much better (apart from being more elegant) are lock
free structures wrt a mutex approach where there is a minimal system
penalty? (not many collisions) did anyone look into this? or have i not
been lurking properly? ;)
OK, futexes are fast in the uncontested case so, with sufficiently rare
collisions, you expect performance to approach that of a lock-free
implementation.
And in terms of overall throughput, it probably does. But in terms of
worst case delay when there *is* a collision things are no better. The
point of the lock-free approach is to minimise this worst case delay in
a real-time system, so if this is important to you then lock-free is the
way to go (but see below).
I'm not sure if/when they'll become
mainstream, but fuqueues might also be
worth a quick look. (Yes: It is an unfortunate name. Enough said.)
thanks for the tip. sure looks interesting.
seems i need to do more digging before attacking the issue.
cheers
tom
11:22 p.m.
Tom Schouten wrote:
clear. the hard vs. soft rt thing. thanks for explaining, simon.
As you point out yourself below, this isn't exactly "hard rt". The
issue is
more like soft rt vs not rt.
in other words, how much better (apart from being more
elegant) are lock
free structures wrt a mutex approach where there is a minimal system
penalty? (not many collisions) did anyone look into this? or have i not
been lurking properly? ;)
OK, futexes are fast in the uncontested case so, with sufficiently rare
collisions, you expect performance to approach that of a lock-free
implementation.
And in terms of overall throughput, it probably does. But in terms of
worst case delay when there *is* a collision things are no better. The
point of the lock-free approach is to minimise this worst case delay in
a real-time system, so if this is important to you then lock-free is the
way to go (but see below).
small remark though. if i'm correct, most lock-free
approaches use compare
and swap, and during collisions there will be a retry. am i correct in
saying this retry-delay will be neglegible compared to system overhead for
a futex?
or in other words, it seems to me that in theory this retry-time is not
bounded in time, just the probability decays very fast. so not exactly
hard rt, though it's treated as if it is, because multiple retries become
very unlikely.
something like that?
During collisions there is a busy retry loop, but
1) everything else trying to access the protected structure during the
collision
is also in a busy retry loop
and
2) any of them can succeed, at any time, by making it once through the loop
without something else hitting the structure. It doesn't matter where in
their
loops the contenders were.
Each instance of an N-way collision will cause only (and exactly) N-1
retries
because a retry is what you do when you find out there has been a collision
which you have *already lost*. Its the fact that one of the colliders
has won
and gone on its way which is causing you to retry.
So if you're getting processor time at all (you're in a busy loop so you
certainly /want/ to run) then only a continual barage of *new* collisions
can starve you of access to the structure.
Simon Jenkins
(Bristol, UK)
28 Aug
28 Aug
9:53 a.m.
Simon Jenkins wrote:
During collisions there is a busy retry loop, but
1) everything else trying to access the protected structure during the
collision
is also in a busy retry loop
and
2) any of them can succeed, at any time, by making it once through the
loop
without something else hitting the structure. It doesn't matter where
in their
loops the contenders were.
<correction>
Bah! Woke up with a hangover and now I'm eating words for breakfast.
This analysis....
Each instance of an N-way collision will cause only
(and exactly) N-1
retries
because a retry is what you do when you find out there has been a
collision
which you have *already lost*.
is wrong.
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.
</correction>
Its the fact that one of the colliders has won
and gone on its way which is causing you to retry.
So if you're getting processor time at all (you're in a busy loop so you
certainly /want/ to run) then only a continual barage of *new* collisions
can starve you of access to the structure.
Simon Jenkins
(Bristol, UK)
Simon Jenkins
(Bristol, UK)
30 Aug
30 Aug
12:58 a.m.
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.
Simon Jenkins <sjenkins(a)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.
In my view, this is a purely theoretical problem, and not a practical
issue of concern for soft realtime implementors.
--
joq
2:29 p.m.
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(a)blueyonder.co.uk>
writes:
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)
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.
4 Sep
4 Sep
12:07 p.m.
i tried the midi-share code in this message from the LAD list:
Subject: [linux-audio-dev] Lock-free LIFO used in MidiShare
From: Yann Orlarey (orlarey_AT_grame.fr)
Date: Fri Jul 21 2000 - 17:06:15 EEST *
seems to be a perfect compromise to get at least my mem reuse
stacks lock free. (i found out in some cases the mutexes here
take about 50% of the execution time..)
now i was wondering if anyone got a tried-and-true implementation
for powerpc?
(maybe it's in the midishare sources, i didn't look yet)
1:27 p.m.
Tom Schouten wrote:
i tried the midi-share code in this message from the
LAD list:
Subject: [linux-audio-dev] Lock-free LIFO used in MidiShare
From: Yann Orlarey (orlarey_AT_grame.fr)
Date: Fri Jul 21 2000 - 17:06:15 EEST *
seems to be a perfect compromise to get at least my mem reuse
stacks lock free. (i found out in some cases the mutexes here
take about 50% of the execution time..)
now i was wondering if anyone got a tried-and-true implementation
for powerpc?
This page:
http://www.audiomulch.com/~rossb/code/lockfree
points to various implementations, including a link to the Yann Orlarey
LAD post you mentioned, and also to much information. One of the
implementations - "lock-free-lib" - is reported to be GPL'd and to cover
Alpha, Mips, ia64, x86, PPC and Sparc.
Simon Jenkins
(Bristol, UK)
7167
days inactive
7176
days old
linux-audio-dev@lists.linuxaudio.org
8 comments
3 participants
participants (3)
-
Jack O'Quin -
Simon Jenkins -
Tom Schouten