[concurrency-interest] MRULinkedBlockingQueue

Szabolcs Ferenczi szabolcs.ferenczi at gmail.com
Wed Apr 18 16:49:36 EDT 2007


On 18/04/07, Mike Quilleash <mike.quilleash at subexazure.com> wrote:

> @Szabolcs - I don't see any data race problems.  I think your scenario
> goes like this...
>
> T1 - Calls add() enters nextPos(), gets current = 0 and newValue = 1
> T2 - ditto
> T1 - compareAndSet( 0, 1 ), succeeds and returns 0.
> T3 - Calls add() enters nextPos(), gets current = 1 and newValue = 2
> T3 - compareAndSet( 1, 2 ), succeeds and returns 1.
> T2 - compareAndSet( 0, 1 ), fails and loops.
> T2 - current = 2 and newValue = 3
> T2 - compareAndSet( 2, 3 ), succeeds and return 2.
>
> Unless I'm missing or misunderstanding something.

I started the story with a limited capacity array of size 2. I hope it
is a legal assumption. Then the story goes a bit different. Also note
that I have assumed an indefinite long delay from the return of
nextpos(). It is again legitimate assumption. That is part of the game
in a concurrent situation just like race conditions, isn't it?  It is
the beauty of the lock-free algorithms that you can legally assume
any long delay between any two atomic operations and the algorithm
should keep the same functionality, if I might remark.

Szabolcs


More information about the Concurrency-interest mailing list