[concurrency-interest] A little lock free algorithm [the code]

studdugie studdugie at gmail.com
Fri Mar 31 13:24:42 EST 2006


You are quite right about the race. It's been nagging at me since I
first wrote it. It's the reason why I wanted to post the code here in
the first place because after testing the code and not seeing the race
happen I wasn't so sure anymore.So I wanted to see if anyone else
thought it was a problem besides me and whatever else they might find.

As I write this, it just dawned on my why the race didn't show up in
testing. I'm running Gentoo Linux w/ a custom kernel w/ preemption
turned of.  In the scenario you've described the race requires some
mechansim to stall Thread B long enough for A to acquire and release
"locked" and in my test environment there simply isn't enough going on
in other parts of the system to stall Thread B's execution and w/o
preemption that makes it more so.

Thanks for confirming my suspicions.

Cheers,

Dane

On 3/31/06, Dawid Kurzyniec <dawidk at mathcs.emory.edu> wrote:
> I think that unless you put the test "now < expiration" inside the
> "lock", there is a potential race condition:
>
> 1. Thread A determines that expiration passed, succeeds at compareAndSet.
> 2. Thread B determines that expiration passed
> 3. Thread A updates backoff and expiration, unlocks, and returns
> 4. Thread B succeeds at compareAndSet, and thus also updates backoff and
> expiration
>
> Regards,
> Dawid
>
>



More information about the Concurrency-interest mailing list