Ada OS : dispatching

Ada OS : dispatching

[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.

1. 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.

2. 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.

3. 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 :

1. 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%))

2. 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.

3. 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. A fair CPU allocation between users
b. A 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 !!!

Re: Ada OS : dispatching

[Nick Roberts]

On Thu, 02 May 2002 13:51:15 +0200, OPERA <vincent.diemunsch@edf.fr>
wrote:

>Some considerations about dispatching in an Ada Operating System Kernel.
>...

Your suggestions duly noted, Vincent. Many thanks.

Good old Exec 8!

[Petter Fryklund]

This is exactly how it was done!.

Re: Good old Exec 8!

[Preben Randhol]

On Mon, 6 May 2002 08:52:34 +0200, Petter Fryklund wrote:
> This is exactly how it was done!.

?

Preben

Re: Good old Exec 8!

[Gary Scott]

I preferred EXEC II, myself.

Petter Fryklund wrote:
> 
> This is exactly how it was done!.