Re: Queues, prioritization, changing priorities and algorithms

From: Brad BARCLAY (bbarclay_at_jsyncmanager.org)
Date: 10/06/03 

Date: Mon, 06 Oct 2003 00:11:22 GMT

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


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)