Re: small footprint priortiy queue

On 11 Feb 2006 03:01:20 -0800, "Gerr" <gertvierman@xxxxxxxxxxx> wrote:

Oops, I forgot to set a proper follow-up on my original post, my
apologies.

Paul Keinanen wrote:
On 11 Feb 2006 00:46:13 -0800, "Gerr" <gertvierman@xxxxxxxxxxx> wrote:
This would be no problem when the queue was implemented as some kind of
dynamic data structure (linked list, etc), but as I said before, this
is no option because of memory restrictions.

Linked lists do not require a dynamic memory allocation system.

True.

Simply put all free memory into a pool of equal size blocks and put
them all initially into the 'Free' list. If the memory block are of
the same size, there is no point of storing a full pointer to the next
block, but just use an index into the next block. With 16 entries, try
to find 4 free bits from each entry for the pointer value. Thus, you
will be able to walk the priority queue.

This is an alternative I already considered. But before re-inventing
the wheel (I happen to do that every now and then), I wanted to hear
some other opinions about possible solutions.

Do you really need a priority queue ?

Maybe I don't.

What I need is a way to make sure some events are handled with a higher
priority then others (in this case, received network messages are
considered 'more important' then keyboard presses). Since the system
already uses a single queue, the obvious solution of was to rework the
queue mechanism to allow high-prio events to be inserted before others,
instead of putting them on the end of the queue. This would probably
have the least impact on the rest of the project, since all the changes
occur inside the event-queue handling code only. Only the queue itself
needs to know the priority for each kind of event, the rest of the
modules can be oblivious of this.

If you have only a few priority levels, then you can have different
queues for different priority levels. Tasks from higher a priority
queue gets executed before tasks from a lower priority queue.
If your current code is written in a resonable manner, you can use
the same code to handle the different queues.

Regards
Anton Erasmus
.

Relevant Pages

  • 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: 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 ... (memory in this case, though having the UI lag behind the actual ...
    (microsoft.public.dotnet.framework)
  • 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: Cpp Considered Harmful
    ... was received would push it on the queue. ... It's main advantages are the multiple use ... research and experience into concurrency and system design in order to ... Threads share memory, the problem is they share all memory (well not ...
    (comp.lang.cpp)