[concurrency-interest] ConcurrentLinkedQueue unexpected behavior ?

Hanson Char hanson.char at gmail.com
Mon Apr 9 16:54:17 EDT 2007


Here is the proof:

Running the following test, occasionally I got both x and y as null:
    http://svn.sourceforge.net/viewvc/beanlib/trunk/beanlib-test/dl/TwoConcurrentLinkedQueueLoops.java?view=markup

(In the test, x is referred to as result.r1, and y as result.r2)

This "impossible" case can happen both on Windows and Linux.  Not
always.  So you may need to run the test several times before hitting
it.

So is ConcurrentLinkedQueue broken ?  Or at least it doesn't seem to
behavior the way it should.  Or am I missing/overlooking something ?

Hanson Char

PS:

To reproduce the problem, add TwoConcurrentLinkedQueueLoops.java to
the jsr166/src/test/loops directory:

    http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/test/loops/

Compile and run it.

On 4/9/07, Hanson Char <hanson.char at gmail.com> wrote:
> Doug,
>
> > That's true for the implementation.
>
> If I could empirically prove that the current implementation of
> ConcurrentLinkedQueue can result in both x and y being null, does it
> mean the implementation is broken ?
>
> Hanson Char
>
> On 4/9/07, Doug Lea <dl at cs.oswego.edu> wrote:
> > Joseph Seigh wrote:
> > > Hanson Char wrote:
> > >
> > >> Say we have two initially empty j.u.c.ConcurrentLinkedQueue, clq1 and
> > >> clq2.  If two threads offered to each queue individually at the same
> > >> time, followed by polling the other queue, is it possible for both
> > >> threads to observer the other queue as being empty ?
> > >>
> > >> In other words:
> > >>
> > >> Time   Thread1      Thread2
> > >> 0         clq1.offer     clq2.offer
> > >> 1         x=clq2.poll   y=clq1.poll
> > >>
> > >> Can both x and y be null ?
> > >>
> > >>
> > >
> > > No.  ConcurrentLinkedQueue contains volatile fields which give it
> > > acquire and release semantics.
> > >
> >
> > That's true for the implementation. But the spec doesn't
> > say anything about consistency properties spanning multiple
> > queues. We've discussed whether we should add some. Doing
> > so hits several gray areas though, that we'd have to resolve
> > first.
> >
> > -Doug
> > _______________________________________________
> > Concurrency-interest mailing list
> > Concurrency-interest at altair.cs.oswego.edu
> > http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
> >
>


More information about the Concurrency-interest mailing list