Queues, prioritization, changing priorites and algorithms

[AlanR]

Hi,

I have to implement(or possibly acquire) a queue that manages
priorities. Low priority elements cannot get lost in the queue
indefinitely if there is a sustained, constant flow of high priority
messages.I am thinking the best way to do this is to up the priority
of lower priority items after a defined time period, eg. with a
TimerTask.

I have looked at using multiple LinkedLists, one for each priority,
but the cost of adding and removing items every time a priority
changes would be too high. ie. the suppliers to the queue are
multithreaded. The synchronization/locking would be too costly if the
queues also need to be locked every time an item's priority changes.
So I'm thinking of using a single linked list. This means there is no
need to synchronize the list when a priority changes. However, this
means that the consumer of the queue must iterate across the queue
every time it consumes. If the high priority items happen to be near
the back of the queue, this could get costly.

Has anyone any experience, advice or info on this.

Thanks in advance,

Al

 

[xarax]

Hi,

I have to implement(or possibly acquire) a queue that manages
priorities. Low priority elements cannot get lost in the queue
indefinitely if there is a sustained, constant flow of high priority
messages.I am thinking the best way to do this is to up the priority
of lower priority items after a defined time period, eg. with a
TimerTask.

I have looked at using multiple LinkedLists, one for each priority,
but the cost of adding and removing items every time a priority
changes would be too high. ie. the suppliers to the queue are
multithreaded. The synchronization/locking would be too costly if the
queues also need to be locked every time an item's priority changes.
So I'm thinking of using a single linked list. This means there is no
need to synchronize the list when a priority changes. However, this
means that the consumer of the queue must iterate across the queue
every time it consumes. If the high priority items happen to be near
the back of the queue, this could get costly.

Has anyone any experience, advice or info on this.

Thanks in advance,

Al

You may want to consider multiple queues, each of which
represent a priority "bucket".

You could use a selection algorithm that distributes
across the buckets. Maybe something like an odometer style
that selects up to 10, say, elements from bucket#0, then
it is forced to an element from bucket#1 before going back
to bucket#0 for another 10. After 10 elements are taken
from bucket#1, then it is forced to take an element from
bucket#2. If a bucket is empty, then move to the next lower
priority bucket. I hope that's clear. You may have to tune
the odometer roll-over counter (10) to get reasonable
through-put. Maybe a higher or lower roll-over, and maybe
it is different for each bucket. When a bucket counter
rolls over, then you move to the next lower priority bucket
and take an element (adjusting its roll-over counter).

Taking an element from a bucket may mean processing the
element right then or just adding it to the end of the next
higher priority bucket (taking a much longer time to become
eligible for processing). I would suggest implementing the
former, rather than the latter.

This approach should guarantee that an element will
get processed and it appears to be directly quantifiable
to the element's priority as to the upper limit of how many
higher priority elements will be processed before it is
processed.

A synchronized doubly-linked list for each bucket should perform
adequately, because you only synchronize on the particular
list when you are ready to take an element off of it or add a new
element to it. A doubly-linked list can pull elements off the
front and add elements to the back in constant time. You can
use the element priority as an array index to select the
appropriate list instance.

2 cents worth. Your mileage (!) may vary.

 

[Eric Sosman]

Hi,

I have to implement(or possibly acquire) a queue that manages
priorities. Low priority elements cannot get lost in the queue
indefinitely if there is a sustained, constant flow of high priority
messages.I am thinking the best way to do this is to up the priority
of lower priority items after a defined time period, eg. with a
TimerTask.

I have looked at using multiple LinkedLists, one for each priority,
but the cost of adding and removing items every time a priority
changes would be too high. ie. the suppliers to the queue are
multithreaded. The synchronization/locking would be too costly if the
queues also need to be locked every time an item's priority changes.
So I'm thinking of using a single linked list. This means there is no
need to synchronize the list when a priority changes. However, this
means that the consumer of the queue must iterate across the queue
every time it consumes. If the high priority items happen to be near
the back of the queue, this could get costly.

How about "biasing" each item's priority when it's inserted,
and using your TimerTask to increase the bias value every so
often? For example (let's assume that high numeric values
correspond to high priorities), you could begin with a bias
of zero and subtract that bias from the priority of each new
entry. Five seconds later, you increase the bias to one and
start subtracting *that* from each new entry. Since newer
items tend to get lower and lower priorities as time passes,
old starved items' priorities get higher and higher relative
to the newcomers.

(Let's see: if you adjust the bias by one unit once per
second, you can only run for about sixty-eight years before
overflowing an `int' -- you may recognize this number in
connection with Unix' vastly over-hyped "2038 Bug." If
this is an issue, use a `long' and you'll be good for just
under three hundred billion years, by which time you will be
in a position to ignore bug reports.)

 

[Roedy Green]

How about "biasing" each item's priority when it's inserted,
and using your TimerTask to increase the bias value every so
often?

There was the technique used in the OS 360 operating system. It would
do something like service 5 items from the highest priority queue,
then one of the second highest, etc. right on down to the lowest.

Each priority represented not a strict priority but rather a relative
speed of processing.

This is roughly the way you prioritise your life. If you always did
the highest priority thing, you would never clean under the fridge.

 

[Michael Borgwardt]

I have looked at using multiple LinkedLists, one for each priority,
but the cost of adding and removing items every time a priority
changes would be too high. ie. the suppliers to the queue are
multithreaded. The synchronization/locking would be too costly if the
queues also need to be locked every time an item's priority changes.
So I'm thinking of using a single linked list.

Stop dabbling; grab yourself a book on data structures and check out
those that are designed specifically to handle large priority queues
quickly, like heaps or even fibonacchi queues. There are probably
free implementations already out there, too.

 

[xarax]

/snip/
This is roughly the way you prioritise your life. If you always did
the highest priority thing, you would never clean under the fridge.

that's what co-processors are for (and significant others)...

 

[Hugo Pragt]

Have a look at the Quartz program on www.sourceforge.com !

Hugo