LinkedBlockingQueue and iterator question

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

LinkedBlockingQueue and iterator question

ray-11
When a thread is using an iterator which point to an object in a
LinkedBlockingQueue, can other threads remove this object from the
queue? I think not, because if so, the iterator may point to a object
which is not in the queue. Right? Thanks
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: LinkedBlockingQueue and iterator question

Doug Lea
ray wrote:
> When a thread is using an iterator which point to an object in a
> LinkedBlockingQueue, can other threads remove this object from the
> queue?

Yes, they can. This is a property of "weakly consistent iterators"
See
http://java.sun.com/j2se/1.5.0/docs/api/java/util/concurrent/package-summary.html
which says in part:

    Most concurrent Collection implementations (including most Queues)
    also differ from the usual java.util conventions in that their
    Iterators provide weakly consistent rather than fast-fail traversal.
    A   weakly consistent iterator is thread-safe, but does not
    necessarily freeze the collection while iterating, so it may (or may
    not) reflect any updates since the iterator was created.

This means that an iterator need not reflect any concurrent updates
performed since the iterator was constructed. For example, one
legal implementation, that isn't actually used in LinkedBlockingQueue,
is to perform toArray() on the queue upon iterator construction, and
just iterate over that array. (The actual implementation is one
in which you may see some additions and removals since iterator
construction.)

This is the best policy we know.


-Doug
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: LinkedBlockingQueue and iterator question

ray-11
Thanks for your reply.

If I only want to iterate the objets IN the queue(other threads may
remove objects from the queue using the method of
LinkedBlockingQueue.take at the same time), should I lock the queue?
That seems too expensive. Or I can use toArray and iterate on that
array, but also seems not better.  Other ideas?

Doug Lea wrote:

> ray wrote:
>
>> When a thread is using an iterator which point to an object in a
>> LinkedBlockingQueue, can other threads remove this object from the
>> queue?
>
>
> Yes, they can. This is a property of "weakly consistent iterators"
> See
> http://java.sun.com/j2se/1.5.0/docs/api/java/util/concurrent/package-summary.html 
>
> which says in part:
>
>    Most concurrent Collection implementations (including most Queues)
>    also differ from the usual java.util conventions in that their
>    Iterators provide weakly consistent rather than fast-fail traversal.
>    A   weakly consistent iterator is thread-safe, but does not
>    necessarily freeze the collection while iterating, so it may (or may
>    not) reflect any updates since the iterator was created.
>
> This means that an iterator need not reflect any concurrent updates
> performed since the iterator was constructed. For example, one
> legal implementation, that isn't actually used in LinkedBlockingQueue,
> is to perform toArray() on the queue upon iterator construction, and
> just iterate over that array. (The actual implementation is one
> in which you may see some additions and removals since iterator
> construction.)
>
> This is the best policy we know.
>
>
> -Doug
>
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

RE: LinkedBlockingQueue and iterator question

David Holmes
Ray,

> If I only want to iterate the objets IN the queue(other threads may
> remove objects from the queue using the method of
> LinkedBlockingQueue.take at the same time), should I lock the queue?

You can't "lock" the queue. There is no single lock that protects access to
the queue - this is a concurrent data structure that supports concurrent put
and take operations.

I'm not clear what your requirements are. You say you want to iterate
objects IN the queue, but at the same time you are allowing the queue to be
modified concurrently - these conflict. You cannot guarantee that an item
returned by the iterator (or through an entry in toArray()) is still in
queue at the time you access it - you only know that it was in the queue.

If you need to exclude access to the queue while iterating you need a
higher-level protocol to provide that in your application. The simplest way
to get such a protocol is to not use a concurrent data structure like
LinkedBlockingQueue but, for example, a synchronizedList wrapping a
LinkedList.

What you need to do really depends on your exact requirements.

Cheers,
David Holmes

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: LinkedBlockingQueue and iterator question

ray-11



>I'm not clear what your requirements are. You say you want to iterate
>objects IN the queue, but at the same time you are allowing the queue to be
>modified concurrently - these conflict. You cannot guarantee that an item
>returned by the iterator (or through an entry in toArray()) is still in
>queue at the time you access it - you only know that it was in the queue.
>  
>
This is exactly my requirements. Now I see it's impossible using
LinkedBlockingQueue. Thanks!

>If you need to exclude access to the queue while iterating you need a
>higher-level protocol to provide that in your application. The simplest way
>to get such a protocol is to not use a concurrent data structure like
>LinkedBlockingQueue but, for example, a synchronizedList wrapping a
>LinkedList.
>  
>
One reason I use LinkedBlockingQueue is that it implements
BlockingQueue. Maybe I should write my data structure which extends
LinkedList and implements BlockingQueue.

>
>  
>
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest