Subject: Re: [linux-audio-dev] futex vs lock-free
From: Simon Jenkins (sjenkins_AT_blueyonder.co.uk)
Date: Sat Aug 28 2004 - 15:47:50 EEST
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)
This archive was generated by hypermail 2b28 : Sat Aug 28 2004 - 14:43:36 EEST