Re: Queues, prioritization, changing priorities and algorithms

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

Date: 7 Oct 2003 00:29:26 -0700

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 <bbarclay@jsyncmanager.org> wrote in message news:<Kq2gb.34681$ko%.3982@news04.bloor.is.net.cable.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

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)