Re: Queues, prioritization, changing priorities and algorithms

From: Phil... (rynes_at_ieee.org)
Date: 10/03/03 

Date: Fri, 03 Oct 2003 07:33:33 GMT

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" <alanroche2000@yahoo.com> wrote in message
news:3a97e53c.0310022244.7cb93760@posting.google.com...
> 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: output.c error in multithreaded program
    ... >please see further below about a couple of semaphore questions). ... just modify your queue insertion routine to put the request in the ... scheduling priorities give you control over priority of how things are done). ... Why have an array of handles and an array of counts when the natural ...
    (microsoft.public.vc.mfc)