30 Aug
2004
30 Aug
'04
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