[concurrency-interest] A question about ConcurrentLinkedQueue.remove()

Martin Buchholz martinrb at google.com
Mon Jun 8 17:01:19 EDT 2009


David Holmes:
Please re-categorize bug 6785442 to classes_util_concurrent
and mark the bug FIP - Doug and I are working on it.

Dave Clausen:
Thank you very much for filing this.
I hope a fix will be in OpenJDK7 within a month or so.

Martin


On Mon, Jun 8, 2009 at 12:40, Dave Clausen <daveclausen at gmail.com> wrote:

> FYI I filed a bug report with Sun a while back that basically covers
> the same ground as this thread:
>
> http://bugs.sun.com/view_bug.do?bug_id=6785442
>
> There's not really any new information there.  I'm only mentioning it
> so you can close out the ticket when you make the fix.  I apologize if
> you've already got it covered.
>
> Thanks,
> Dave Clausen
>
> On Fri, Feb 27, 2009 at 12:35 PM, Joe Bowbeer <joe.bowbeer at gmail.com>
> wrote:
> > I agree that poll should be coded as:
> >
> >    if (item != null && first.casItem(item, null)) {
> >        return item;
> >    }
> >
> > That's how I read "equivalently" in the spec.
> >
> > Note that this remove method is specified by Collection, and the two
> > phrasings were equivalent before concurrent collections arrived on the
> > scene.  The object was either present *and* removed, or it wasn't, or
> there
> > was a ConcurrentModificationException.
> >
> > The proposed implementation is also more testable.  It should be the case
> > that the number of items inserted is equal to the number of successful
> polls
> > plus the number of successful removals.
> >
> > Joe
> >
> > On Fri, Feb 27, 2009 at 3:55 AM, Doug Lea wrote:
> >
> >> James Gan wrote:
> >>
> >>>
> >>> Let's consider following scenario. Assume thread A is removing the
> element
> >>> inside first node and thread B is popping, it seems to me that both of
> them
> >>> can succeed.
> >>>
> >>
> >> This is a byproduct of a spec decision that is worth
> >> revisiting. The question is: What should be the return value
> >> of remove when the item was present on entry but not on return
> >> of the method? The spec is a little vague ...
> >>
> >>  Returns true if this queue contained the specified element (or
> >>  equivalently, if this queue changed as a result of the call).
> >>
> >> ... especially since the "equivalently" clause is not exactly
> >> equivalent under most people's interpretations! If the item was in
> >> the process of being polled, then you might (and you did!) conclude
> >> that the queue did not change as a result of the remove call but
> >> of the poll. As David mentioned, your interpretation, which
> >> is probably more common, could be ensured by using
> >> casItem in poll. We probably ought to do this, and then strengthen
> >> and clarify the spec/javadoc.
> >>
> >> While I'm at it: jsr166y.LinkedTransferQueue, which can be used as
> >> a plain ConcurrentLinkedQueue, not only doesn't have this
> >> issue, but also includes an internal node cleanup algorithm,
> >> which prevents the accumulation of embedded cancelled/removed nodes,
> >> so is always preferable if you do this a lot. In fact, for Java7.
> >> there is no reason not to replace the internals of CLQ by delegating
> >> to LTQ, so we will probably do this.
> >>
> >> -Doug
> >
>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20090608/72e68a86/attachment.html>


More information about the Concurrency-interest mailing list