ArrayBlockingQueue: concurrent put and take

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

ArrayBlockingQueue: concurrent put and take

Satnam Singh

Is it possible to implement ArrayBlockingQueue to support concurrent calls to put and take?

One could use a slightly different representation to help partition the data structure to facilitate concurrent access but then perhaps this is not in the spirit of the specification for ArrayBlockingQueue?

 

I’ve been looking at an STM-based implementation but a straight-forward approach where transacted variables are used for the head, tail and empty-status does not seem to allow concurrent calls to put and take.

 

Thank you.

 

Kind regards,


Satnam

 


Satnam Singh
Microsoft
One Microsoft Way
Redmond
Washington 98052-6399
USA

http://research.microsoft.com/~satnams
Email:
[hidden email][hidden email]
Telephone: +1 425 705 8208
Cell: +1 408 718 2588
UK cell: +44 7979 648412
Pager: 
[hidden email]

 


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

Re: ArrayBlockingQueue: concurrent put and take

Brian Goetz
> Is it possible to implement ArrayBlockingQueue to support concurrent
> calls to put and take?

No, but LinkedBlockingQueue does.  It uses a two-lock algorithm to
support concurrent puts and takes.  LBQ offers greater concurrency, but
more memory churn.  That's why there are two versions.

> One could use a slightly different representation to help partition the
> data structure to facilitate concurrent access but then perhaps this is
> not in the spirit of the specification for ArrayBlockingQueue?

Right.  You're taking an incremental step towards LinkedBlockingQueue.
In most cases, allocation is dirt cheap -- certainly cheaper than
contention -- so in most cases LBQ is preferable.  In RT environments,
where memory is more constrained and GC pauses are less acceptable, ABQ
may be more appropriate.

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

Re: ArrayBlockingQueue: concurrent put and take

vikas
It may be a naive question,  But i have the same question on why ABQ cant use two-lock algorithm.
It would be a great help if somebody can point out to me, why two-lock algorithm wouldn't work in ABQ. Which scenario or race condition makes two-lock algo infeasible in ABQ.  A simple example of that race conditon would help a lot.

Thanks for having such a great mailing a list. I have learned a lot and still learning.
vikas
Reply | Threaded
Open this post in threaded view
|

Re: ArrayBlockingQueue: concurrent put and take

Martin Buchholz-3
LinkedBlockingQueue has a two-lock strategy, but ArrayBlockingQueue does not.  It took us years to figure out how to get the iterator to behave perfectly in ABQ, and I'm afraid of touching it again or introducing additional complexity.  Using a backing array instead of a linked list has some advantages, but it is hostile to concurrent collection implementers ... yes, even when everything is guarded by a single lock.


On Wed, Jul 2, 2014 at 4:03 PM, vikas <[hidden email]> wrote:
It may be a naive question,  But i have the same question on why ABQ cant use
two-lock algorithm.
It would be a great help if somebody can point out to me, why two-lock
algorithm wouldn't work in ABQ. Which scenario or race condition makes
two-lock algo infeasible in ABQ.  A simple example of that race conditon
would help a lot.

Thanks for having such a great mailing a list. I have learned a lot and
still learning.
vikas



--
View this message in context: http://jsr166-concurrency.10961.n7.nabble.com/ArrayBlockingQueue-concurrent-put-and-take-tp1306p11143.html
Sent from the JSR166 Concurrency mailing list archive at Nabble.com.
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


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

Re: ArrayBlockingQueue: concurrent put and take

vikas
Thanks Martin,  
    I agree with functionality like iterator etc, implementations becomes more difficult.
But if narrow down the scope of ABQ to only put and take. Then i think it would be possible to have
concurrent put and take with a single contention point on the AtomicCounter
Reply | Threaded
Open this post in threaded view
|

Re: ArrayBlockingQueue: concurrent put and take

Martin Buchholz-3
But what are you trying to achieve?  If you have perfect timing, and a put and take are always concurrent, and the queue is always half-full, then you might be able to get (only!) a 2x speedup.  But you're not going to get those perfect conditions.

Anyways, go ahead and implement it and see what happens.


On Wed, Jul 2, 2014 at 6:07 PM, vikas <[hidden email]> wrote:
Thanks Martin,
    I agree with functionality like iterator etc, implementations becomes
more difficult.
But if narrow down the scope of ABQ to only put and take. Then i think it
would be possible to have
concurrent put and take with a single contention point on the AtomicCounter




--
View this message in context: http://jsr166-concurrency.10961.n7.nabble.com/ArrayBlockingQueue-concurrent-put-and-take-tp1306p11145.html
Sent from the JSR166 Concurrency mailing list archive at Nabble.com.
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


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

Re: ArrayBlockingQueue: concurrent put and take

vikas
i am just trying to understand the rationale behind juc implementations of these Two BQ implementations.
Moreover i have pasted a small snippet on of ABQ using LBQ idea. only PUT and Take are implemented.
If somebody can point me any possible race condition in the code, my problem would be solved.

thanks
vikas
Reply | Threaded
Open this post in threaded view
|

Re: ArrayBlockingQueue: concurrent put and take

vikas
Ohh i forgot the link
http://pastebin.com/ZD1uFy7S
Reply | Threaded
Open this post in threaded view
|

Re: ArrayBlockingQueue: concurrent put and take

Viktor Klang
In reply to this post by Martin Buchholz-3
I think it was a mistake to have the BlockingQueue interface too broad. (A general issue with the JDK collections)
(There's also a lack of non-blocking SPSC, MPSC and SPMC queues in the JDK.)


On Thu, Jul 3, 2014 at 1:37 AM, Martin Buchholz <[hidden email]> wrote:
LinkedBlockingQueue has a two-lock strategy, but ArrayBlockingQueue does not.  It took us years to figure out how to get the iterator to behave perfectly in ABQ, and I'm afraid of touching it again or introducing additional complexity.  Using a backing array instead of a linked list has some advantages, but it is hostile to concurrent collection implementers ... yes, even when everything is guarded by a single lock.


On Wed, Jul 2, 2014 at 4:03 PM, vikas <[hidden email]> wrote:
It may be a naive question,  But i have the same question on why ABQ cant use
two-lock algorithm.
It would be a great help if somebody can point out to me, why two-lock
algorithm wouldn't work in ABQ. Which scenario or race condition makes
two-lock algo infeasible in ABQ.  A simple example of that race conditon
would help a lot.

Thanks for having such a great mailing a list. I have learned a lot and
still learning.
vikas



--
View this message in context: http://jsr166-concurrency.10961.n7.nabble.com/ArrayBlockingQueue-concurrent-put-and-take-tp1306p11143.html
Sent from the JSR166 Concurrency mailing list archive at Nabble.com.
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


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




--
Cheers,

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

Re: ArrayBlockingQueue: concurrent put and take

Kasper Nielsen-4
On Thu, Jul 3, 2014 at 11:35 AM, √iktor Ҡlang <[hidden email]> wrote:
I think it was a mistake to have the BlockingQueue interface too broad. (A general issue with the JDK collections)

I think that is a matter of personal preference. I prefer the simple interface hierarchy of JDK collections over something more complex with separate  modifiable/immutable interfaces.

- Kasper



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

Re: ArrayBlockingQueue: concurrent put and take

Viktor Klang



On Thu, Jul 3, 2014 at 1:17 PM, Kasper Nielsen <[hidden email]> wrote:
On Thu, Jul 3, 2014 at 11:35 AM, √iktor Ҡlang <[hidden email]> wrote:
I think it was a mistake to have the BlockingQueue interface too broad. (A general issue with the JDK collections)

I think that is a matter of personal preference. I prefer the simple interface hierarchy of JDK collections over something more complex with separate  modifiable/immutable interfaces.

It's not about preference, it's about implementablilty.
 

- Kasper



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




--
Cheers,

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

Re: ArrayBlockingQueue: concurrent put and take

Martin Buchholz-3
In reply to this post by Viktor Klang



On Thu, Jul 3, 2014 at 2:35 AM, √iktor Ҡlang <[hidden email]> wrote:
I think it was a mistake to have the BlockingQueue interface too broad. (A general issue with the JDK collections)

It was certainly very natural to have BlockingQueue extend Collection.  And then it was natural to try to properly implement all the Collection methods if it was not too onerous.  An alternative would have been to throw UOE on "interior" methods like remove(Object).  In the case of ArrayBlockingQueue, we eventually succeeded in implementing all the Collection methods without performance penalty to ordinary intended usage, but there is definitely implementation complexity penalty.

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