Re: Workqueues in Ada

[Wiktor Moskwa <wiktorDOTmoskwa@gmail.com>]

On 28.07.2007, Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote:
> Why? What I don't understand is why removing from a queue should deallocate
> anything. It might be an artefact of Ada.Containers, but in general case it
> is not unnecessary. Removing just means that it is the task who will hold
> the item. Technically the item will be either in no list or in the list of
> one item long owned by the task. You have one list of items waiting for
> service and n lists of items being serviced, where n = number of worker
> tasks. Interlocking is only necessary when you move an item from list to
> list.

In GNAT GPL 2007 implementation of Doubly_Linked_Lists an Element is kept
in a limited record called Node. When Append is called, new Node is
created and when Delete - Free(Node) is called. Everything happens in
a default storage pool and is transpated to malloc and free.

Could you elaborate the concept of having an additional list of items
per task? When it can be useful? I'm interested.

> If you do this you would not need any lists, just a ring buffer of items.

That's the name I was looking for :)

> With a relatively small number of worker tasks the overhead of skipping
> items in use is not that big, but you will have another potential problem:
> unbalanced servicing. When an item was serviced a bit longer than its
> neighbours, it might miss its train of servicing. What is worse it could
> become a systematic problem for some items with a huge impact in result.

I agree, I haven't consider balancing yet.

> Doubly-linked lists do not have this problem, while removing and inserting
> overhead is just negligible. You can shuffle items between lists very
> efficiently.

If you could write more about using more lists... thanks!

-- 
Wiktor Moskwa