[concurrency-interest] ConcurrentLinkedBoundedBlockingQueue

Hanson Char hanson.char at gmail.com
Thu Apr 5 13:25:07 EDT 2007


This is the first draft of a bounded concurrent blocking queue:


http://svn.sourceforge.net/viewvc/beanlib/trunk/beanlib/src/net/sf/beanlib/util/concurrent/ConcurrentLinkedBoundedBlockingQueue.java?view=markup

which is extended from CLBQ:


http://svn.sourceforge.net/viewvc/beanlib/trunk/beanlib/src/net/sf/beanlib/util/concurrent/ConcurrentLinkedBlockingQueue.java?view=markup

Similar to LinkedBlockingQueue, one can specify a capacity.   Unlike LBQ,
CLBBQ is entirely locked free.

Note this is only the 1st draft, but it basically illustrates how the same
technique of CLBQ can be used, almost mechanically :)

Cheers,
Hanson Char

On 4/4/07, Hanson Char <hanson.char at gmail.com> wrote:
>
> Hmm...on 2nd thought, it wouldn't be too hard to support a capacity based
> concurrent (ie lock free) blocking queue.  Let me think a bit more.
>
> Stay tuned :)
>
> Hanson Char
>
> On 4/4/07, Hanson Char <hanson.char at gmail.com> wrote:
> >
> > And of course CLBQ cannot be a drop-in replacement for LBQ in the case
> > when a fixed "capacity" is specified.
> >
> > Alright, so they are just different implementation of BlockingQueue.
> >
> > Hanson Char
> >
> > On 4/4/07, Hanson Char <hanson.char at gmail.com > wrote:
> > >
> > > Hi Szabolcs,
> > >
> > > >it waits if necessary for space to become available.
> > >
> > > In this case it's not necessary and therefore there is no need to
> > > wait.  The condition is still satisfied, isn't it ?  (The statement "if A
> > > then B" is always trivially true if the condition A is false.)
> > >
> > > >This means that on an LBQ the put waits when the queue has already
> > > >Integer.MAX_VALUE number of elements. It is not the same for your
> > > CLBQ
> > > >if you forward the put to an instance of a ConcurrentLinkedQueue as
> > > an
> > > >add call.
> > >
> > > True, they are not the same in the sense that when the number of
> > > elements in the queue reached Integer.MAX_VALUE.
> > >
> > > So I guess technically CLBQ is not a drop-in replacement for LBQ,
> > > since CLBQ would allow one to continue inserting to the queue and there is
> > > always no need to wait, whereas LBQ would block if the the number of queue
> > > items reached Integer.MAX_VALUE.
> > >
> > > In practice, however, I doubt if there is any application that would
> > > rely on this peculiar behavior of LBQ to remain correct.
> > >
> > > So CLBQ is not but can be used as a replacement for LBQ in most cases,
> > > unless your application correctness relies on the queue to block upon the
> > > number of elements reaching Integer.MAX_VALUE.
> > >
> > > Hanson Char
> > >
> > > On 4/4/07, Szabolcs Ferenczi < szabolcs.ferenczi at gmail.com> wrote:
> > > >
> > > > On 04/04/07, Hanson Char < hanson.char at gmail.com > wrote:
> > > > > The put method in CLBQ, being unbounded, will always succeed
> > > > "immediately"
> > > > > without waiting.  But waiting with zero time doesn't mean it does
> > > > not
> > > > > satisfy the contract of the BlockingQueue put method, as the
> > > > happen-before
> > > > > relationship is still satisfied by the current implementation.
> > > > >
> > > > > Or am I missing something here ?
> > > >
> > > > Hi Hanson,
> > > >
> > > > I think you miss that the semantics of put in the interface
> > > > BlockingQueue says that it waits if necessary for space to become
> > > > available. It is not the same as method add which does not wait but
> > > > returns a boolean.
> > > >
> > > > On the other hand, you claim that your CLBQ can replace LBQ. Now LBQ
> > > > is bounded. By default, the capacity is Integer.MAX_VALUE . This
> > > > means
> > > > that on an LBQ the put waits when the queue has already
> > > > Integer.MAX_VALUE number of elements. It is not the same for your
> > > > CLBQ
> > > > if you forward the put to an instance of a ConcurrentLinkedQueue as
> > > > an
> > > > add call. Do you agree?
> > > >
> > > > Best Regards,
> > > > Szabolcs
> > > >
> > >
> > >
> >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: /pipermail/attachments/20070405/9ead057c/attachment.html 


More information about the Concurrency-interest mailing list