Queues, prioritization, changing priorities and algorithms

From: AlanR (alanroche2000_at_yahoo.com)
Date: 10/03/03 

Date: 2 Oct 2003 23:44:56 -0700

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

Relevant Pages

  • Re: Lahman, how ya doing?
    ... >> A priority queue is an interesting idea. ... So Timer just enqueues the event on the right queue. ... >effectively starts at the same time on the current tick. ... >was triggered just gets time-sliced based on priority. ...
    (comp.object)
  • Re: Lahman, how ya doing?
    ... Suppose you had 64 Thermometers and at run time you wanted to give priority to some of them dynamically (e.g., where the temperature gradient was greatest) because processing all 64 samples at once can't be done in a single "tick". ... So Timer just enqueues the event on the right queue. ... So I addressed both the bitmap processing basics via indexed OR mask and the deferredBitmap variable assumption about bit count. ...
    (comp.object)
  • Re: cooperative multitasking scheme
    ... >> equal priority or where priorities aren't specifically used. ... where I choose not to use preemption at ... the action of the timing event is to move the process from the sleep queue ... I very much appreciate having a sleep queue. ...
    (comp.arch.embedded)
  • Re: Best way to design multithreading application
    ... The data acquisition is more important than UI updates, ... adding it to a Queue 1 as it acquires more. ... B, which is medium-to-high priority, loops over and over, and when it ... But when the threads involved are dependent on each other, as they are here, it makes little sense to make one thread higher priority than another, and for the reason you note: you really do need each of these threads to, at least on average, process the data at the same rate, otherwise you will eventually consume all your resources (memory in this case, though having the UI lag behind the actual processing is probably not desirable either). ...
    (microsoft.public.dotnet.framework)
  • Re: So... What are the alternatives? Was: I dont use an RTOS because...
    ... This configuration parameter decides whether or not preemption is allowed. ... queue will be treated as though they have equal priority. ... The real-time clock serves two primary purposes in my O/S. ...
    (comp.arch.embedded)