Tom Schouten wrote:
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).
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.
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)
