Ada OS : Some considerations about dispatching (Twice)

Ada OS : Some considerations about dispatching (Twice)

[OPERA]

Some considerations about dispatching in an Ada Operating System Kernel.

First excuse my english, I am not a native English speaker !

I have seen on the Adapower site that there is project to build an Ada
Operating System,
and therefore I would like to give some comments. In fact, since a
couple of months, I had
the idea of creating a microkernel for a linux system, that could bring
a better support
for real-time applications written in ADA on Linux. The fact is that I
don't have much
experience in programming operating systems and I believe that my
project will stay in an
earlier stage. But I believe that some general considerations can be of
interest for those
who are now specifying a new Ada operating system kernel. And if not, I
would be glad to
now what can be wrong in my expectations... !!

1. Process and task

We call a process, a set of ADA task ordered by priorities, on which you
can apply the following
primitives : create task, suppress, suspend and resume. Mutual exclusion
is provided through
the use of mutex. Each process work in a partition : a virtual memory
region with a protection
system to keep data integrity. Therefore each application have at least
one process.

Now we consider that scheduling is done by the ADA Real-Time Library of
the Application and
therefore that it is not the job of the microkernel ! We only consider
DISPATCHING which consists
in allocating CPU time to processes.


2. Class of processes
I distinguish three different kinds of processes, and for each kind I
propose a different treatment
by the kernel.

-a) Hard Real Time processes : they are typical of embedded systems. But
you need to have them on a Real-Time Desktop Computer so that you can
handle hardware modules, such as HD drives, CD drives (especially when
recording), modems, or any hardware module connected to the system. This
kind of processes must be deterministic and have reduced real-time
scheduling capabilities, and no dynamic allocations or virtual memory.
For them the "Ravenscar profile" was developed and pre-emptive
multitasking real-time kernel like ORK. I believe that on
multiprocessors you need to have one dispatching queue for each
processor. This queue is ordered with fixed priorities and dispatching
occurs according to the FIFO Within Priorities policy. Priorities are
set according to "Rate Monotonic Scheduling Algorithm" : "Assign the
priority of each task according to its period, so that the shorter the
period, the higher the priority" (the period is not the execution
duration of the task but the maximum duration that is given for it to
complete execution). Each process developed for that use will be
considered a kernel module and inserted only with system administrator
rights.

-b) Soft Real Time processes : they are typical ADA real-time
applications. They share between them Virtual Memory, and CPU time.
Therefore I believe that they must share a common dispatching queue
where all processors, when they have accomplished there hard real-time
jobs can find a task to execute. FIFO Within Priorities dispatching
occurs here and Mutex are set with Priority Ceiling Locking and busy
spinning. The scheduling is done by the ADA Real-Time Library of the
application and queuing is done according to priorities. The Kernel must
provide a dynamic priority support (for example through the support of
the "Earliest Deadline First" algorithm). Processes of this kind are
considered Real-Time Processes and therefore requires special rights to
be executed.

-c) User processes : the great majority of applications running on a
desktop computer don't need any
Real-Time support. But what they need is a fair allocation of CPU
resources. To do that I believe that we can use a dispatching queue
shared between processors (and processes) that use a multi-level
round-robin dispatching policy. For each level of the queue (defined by
a priority) we define a Quantum of time. The shorter the quantum the
higher the priority. Each task is first set to a priority according to
its expected duration, so that it executes in one quantum of time. If
not then at the end of the quantum, the task is queued at the level
under. Therefore we have almost a FIFO Within Priorities policy if the
priority of a task is correctly set. If it was not correctly set (which
is true for the majority of non real time processes) the kernel is able
to change its priority. Priority Ceiling Locking is still used provided
that we do not release a task that has expired its quantum of time when
it holds a Mutex. This dispatching policy aims at giving priority to
short jobs so that we can still use the system when the CPU load is
high.

Therefore dispatching occurs the following way for one processor :
1. Check if there is no private real-time job to do
2. If not, check if there is no shared real-time signal (=user
interruption) or task to do
3. check if there is no shared user signal (=user interruption)and if
not take a task to do in a quantum of time.

I know that this dispatching is far more complex than what is done yet,
but I believe that it is the price
to pay to have a very good real time desktop computer. I believe that
the kernel might be more complex but not especially less fast.



3. And finally let's take an example :
Suppose we have a nice electric train and we would like to use our PC or
Mac to control it. We need :

a) Automatic, real-time support for hardware interfaces. We want
automatic actions to occur for safety.
This is done by the per-processor "Ravenscar" system, with fixed
priority scheduling. For each CPU,
the load due to these processes will be kept low : (20% max in
conventional systems. (in theory not
above 70%))

b) A supervision application (for example a real-time database system)
which can watch and supervise
every element of the train system. We want real-time response but we
don't need to meet all deadlines.
Therefore we'll use a dispatching queue shared between all processors,
and dynamic priorities, that
are set according to the "earliest deadlines first" policy.

c) User Applications that are executed when all Real-Time constraints
have been fulfilled. We use a
multi-level Round-Robin system so that we have :
- A fair CPU allocation between users
- An acceptable response time when the system is heavily loaded because
we give priority to short jobs.


I would greatly appreciate any comment on these considerations, and hope
this could give ideas for the new Ada Kernel !!!

Vincent DIEMUNSCH