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)
