Re: Multiple linked data structure

[Dmitry A. Kazakov <mailbox@dmitry-kazakov.de>]

On 27 Aug 2003 08:52:55 -0700, fjloma@andaluciajunta.es (Francisco
Javier Loma Daza) wrote:

>I am reading some OS sources (C sources), and I have seen a common
>structure, for example: a procces can be waiting on the processor wait
>queue, disk queue and network queue. This is implemented by several
>next pointer on the respective queue; add a new queue, then add a new
>pointer on the task structure, and potentially a new set of queue
>operations. In C this can be alleviated by preprocessor tricks, and I
>was wondering how to make this in Ada.
>
>The first option can be to have a generic queue instantiated with the
>task record type, but then some combined iteration can be more
>complicated. For example, iterating through the processor queue and
>quering if it has pending io requests by testing null for some
>(network, disk) next pointers. With the separate queue object, it
>would be needed to have some bits on the task structure to cache this
>information, or simply iterate the correspondings queues ......
>
>Have you faced a similar question?

Yes. I have flatten the set of queues. 

> are there a design pattern that
>encapsulates and solves efficiently this kind of problems?

In fact Ada already has such queues implemented.

If you map a scheduling item to an Ada task (and I see no reason why
not), then when a task goes after a rendezvous to another task or
spins to a protected object, then, in effect, it is placed into a
queue. Timed calls you will have for free.

As for the question of many queues. One can have one queue for
everything and map the "original" queues into the entry point quards.
When quards depend on some external things, you can use the requeue
statement.

Though it could be a bit tricky, especially with the obscure issues of
the requeue statement, but the advantage is that you can rely on a
well tested and specified implementation.

One could object that it should be slow as compared with a manual
implementation of multiple queues, but I am not so sure about it.

---
Regards,
Dmitry Kazakov
www.dmitry-kazakov.de