Multiple linked data structure

Multiple linked data structure

[Francisco Javier Loma Daza]

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? are there a design pattern that
encapsulates and solves efficiently this kind of problems?

Thanks in advance

Re: Multiple linked data structure

[Matthew Heaney]

fjloma@andaluciajunta.es (Francisco Javier Loma Daza) writes:

> Have you faced a similar question? are there a design pattern that
> encapsulates and solves efficiently this kind of problems?

It sounds like most of your problems can be solved with lists.

The Charles library has both single and double-linked lists.  When you
insert an item in the list, an iterator is returned that designates the
new list item.

You can then put the list iterator into any other kind of container,
such as a queue or even another list.

If you need to perform lookups that have better then O(n) time
complexity you can use the sets or maps.

Charles is available at my home page.

http://home.earthlink.net/~matthewjheaney/charles/

Re: Multiple linked data structure

[Dmitry A. Kazakov]

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