[linux-audio-dev] futex vs lock-free

[Simon Jenkins]

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)