[concurrency-interest] MRULinkedBlockingQueue

Szabolcs Ferenczi szabolcs.ferenczi at gmail.com
Wed Apr 18 06:48:32 EDT 2007


Hi,

I do not exactly get what do you mean by "concurrent" in case of a
data structure. I guess you mean that lock-free stuff. Right? Is it
really a requirement in this situation?

The other question is what do you mean by maintaining the insertion order.

Anyway, the following problem appears to me in this lock-free
solution: Let us assume there are three threads using an already
filled queue of this kind. Each thread calls method add() very
frequently. Now, it may happen that two of them do not let the third
progress. So, this algorithm is prone to starvation.

Assume T1 starts operation add(item1), the queue is full so
offer(item1) fails and T1 makes some room by poll(). As soon as there
is a slot, T2 sneaks in and fills the queue by operation add(item2)
for which the offer(item2) succeeds. Now, poor T1 makes some room
again. But T3 puts item3 immediately, so that T1 has to make some room
again. And so on and so on.

I hope this helps.

Best Regards,
Szabolcs

On 18/04/07, Mike Quilleash <mike.quilleash at subexazure.com> wrote:
>
>
> Hi all,
>
> Has anyone seen or comes across an collection implementation that has the
> following characteristics.
>
> 1) Concurrent
> 2) Maintains insertion order (for iteration)
> 3) Capacity bound
> 4) An add() that would cause the capacity to exceed the limit would remove
> the oldest element and add a new one.
>
> I thought of the following extension to LinkedBlockingQueue which simply
> loops in add() trying to offer() and removing an element from the queue if
> the offer() fails.
>
>
> public class MRULinkedBlockingQueue< T > extends LinkedBlockingQueue< T >
> {
>     public MRULinkedBlockingQueue( int capacity )
>     {
>         super( capacity );
>     }
>
>     @Override
>     public boolean add( T o )
>     {
>         for ( ;; )
>         {
>             // try and offer the element
>             if ( offer( o ) )
>                 return true;
>
>             // remove the head of the queue to make room if the offer
> failed.
>             poll();
>         }
>     }
> }
>
>
> Any comments appreciated.
>
>
>   This e-mail is bound by the terms and conditions described at
> http://www.subexazure.com/mail-disclaimer.html
>
>
>
> _______________________________________________
> 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