[concurrency-interest] BoundedPriorityBlockingQueue ?

David Holmes dcholmes at optusnet.com.au
Tue Sep 12 20:48:30 EDT 2006


The basic issue here is that you use a PriorityBlockingQueue to prioritize
tasks, under the expectation that the queue will actually fill to some
extent, so the relative importance of tasks is, well, important. You then
place a bound on that queue and the result is you now have a second
(unbounded) queue of threads trying to submit prioritized tasks. So then you
wonder if those threads should be unblocked in order of priority of their
tasks? But that way madness lies ... this isn't real-time priority
preemptive systems programming. If you really think that the threads need to
be queued in priority order too then make your priority queue bigger. If you
size things out and you really must bound the size of the queue and you
really expect lots of threads to block waiting to put to the queue and you
really think the priority of the tasks those threads are submitting need to
be accounted for, then you have a problem. Basically you would have to have
each submitter check if its task is more important than the lowest priority
one in the queue and try to swap the new task for the old one; and then keep
retrying to submit the swapped out task. This is really, really messy. Throw
in priority-aging to avoid starvation and things get even worse. :)

Sometimes there is no complete solution - you have to define the boundaries
where you take into account things like priority. Sometimes the answer is to
have a completely different mechanism for things that are really important
(most queueing systems (banks, airlines etc) don't use priority ordered
queues, they use different queues for different "priorities" or allow
bypassing of the queue altogether.

Just my 2c.

David Holmes
  -----Original Message-----
  From: concurrency-interest-bounces at cs.oswego.edu
[mailto:concurrency-interest-bounces at cs.oswego.edu]On Behalf Of Hanson Char
  Sent: Wednesday, 13 September 2006 6:20 AM
  To: rbalamohan at sonoasystems.com
  Cc: Brian Goetz; concurrency-interest; Kasper Nielsen
  Subject: Re: [concurrency-interest] BoundedPriorityBlockingQueue ?

  I see blocking on put on a BoundedPriorityBlockingQueue is not such a good

  How about making the put method return a false boolean value upon queue
full, or alternatively throwing something like a QueueFullException ?

  Would this be useful/sensible ?


  On 9/12/06, Brian Goetz <brian at quiotix.com> wrote:
    The tricky part is if you want to guarantee that the thread offering the
    element of highest priority is first to be unblocked.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: /pipermail/attachments/20060913/f2678629/attachment.html 

More information about the Concurrency-interest mailing list