Queues, prioritization, changing priorities 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

[Phil...]

This problem has been around for over 35 years and there
are lots of papers etc. available in the literature, and many
viable techniques. Search the web.
"AlanR" <al***********@yahoo.com> wrote in message
news:3a**************************@posting.google.c om...

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

[Brad BARCLAY]

AlanR wrote:

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.

Yes, you need a data structure called a "priority queue". These have
been around for decades -- you should find all sorts of hits if you do a
web search on this topic.

Basically, what you want to do is to enqueue items based on their
priority, as opposed to just sticking them at the back. In this way,
you don't have to scan the queue each time you need to consume an item
-- just take the item at the front.

Brad BARCLAY

--
=-=-=-=-=-=-=-=-=
From the OS/2 WARP v4.5 Desktop of Brad BARCLAY.
The jSyncManager Project: http://www.jsyncmanager.org


[Phil...]

Seems like all techniques would require synchronization,
so if that is too slow, I guess you're screwed.
If you are on Linux or UNIX you can have separate processes,
one for each priority and let UNIX take care of modulating
the priority of each process to prevent starvation.

"AlanR" <al***********@yahoo.com> wrote in message
news:3a**************************@posting.google.c om...

Had already looked at priority queues and done some research.
It is quite difficult to find something efficient where priorities get
increased after a certain time period to prevent starvation.
ie. Priority is not so efficient where priorities change. ie. I would
need to monitor the queue for "expired priorities" and then pop them
from the queue, and push them back on when the priority changes. In a
multithreaded environment the locking/synchronization of the data
structure would really slow things down.

Brad BARCLAY <bb******@jsyncmanager.org> wrote in message

news:<Kq******************@news04.bloor.is.net.cab le.rogers.com>...

AlanR wrote:

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.

Yes, you need a data structure called a "priority queue". These have
been around for decades -- you should find all sorts of hits if you do a
web search on this topic.

Basically, what you want to do is to enqueue items based on their
priority, as opposed to just sticking them at the back. In this way,
you don't have to scan the queue each time you need to consume an item
-- just take the item at the front.

Brad BARCLAY

[Mark A. Washburn]

al***********@yahoo.com (AlanR) wrote in message news:<3a**************************@posting.google. com>...

http://www.cs.ukc.ac.uk/projects/ofa/jcsp/
( a method for verifiably correct parallel thread processing)
maybe one possible soultion
read the sections on Alternative --> fairSelect
( for real time prioritization )
read PriParallel --> insertProcessAt
( for native Java Threads )

maw

[Raymond DeCampo]

AlanR wrote:

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.

First, I suggest forgetting about using Lists. Instead use a SortedSet
(e.g. TreeSet) and a custom Comparator than compares based on priority.

When your timer task wants to play around with priorities, use the
following technique to minimize lock time. Lock the set and make a
copy. Unlock the original set. Iterate through the copy and determine
what needs to be done. Lock the original set and make the needed
changes. Note: when you change the priority of an object, first remove
it from the set, change the priority and then add it back in. This is
necessary because of the custom Comparator. Otherwise your set will get
quite screwed up.

Another approach; create a custom Comparator that takes into account
priority AND how long the request has been waiting. Now we are back to
lists. Use the Collections.binarySearch() method to insert new
requests. Periodically sort the list based on the custom Comparator.
Enjoy,
Ray