Subject: Re: [linux-audio-dev] futex vs lock-free
From: Jack O'Quin (joq_AT_io.com)
Date: Mon Aug 30 2004 - 05:42:18 EEST
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_AT_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
This archive was generated by hypermail 2b28 : Mon Aug 30 2004 - 05:50:24 EEST