From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,43993a8e7e771588,start X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2002-05-02 05:05:11 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!npeer.kpnqwest.net!news.edf.fr!not-for-mail From: OPERA Newsgroups: comp.lang.ada Subject: Ada OS : dispatching Date: Thu, 02 May 2002 13:51:15 +0200 Organization: EDF Message-ID: <3CD12833.3D1949B8@edf.fr> NNTP-Posting-Host: cnn00007.cnen.de.edf.fr Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Trace: clnews.edf.fr 1020340276 29943 144.165.69.7 (2 May 2002 11:51:16 GMT) X-Complaints-To: newsadm@news.edf.fr NNTP-Posting-Date: 2 May 2002 11:51:16 GMT X-Mailer: Mozilla 4.5 [fr] (WinNT; I) X-Accept-Language: fr Xref: archiver1.google.com comp.lang.ada:23402 Date: 2002-05-02T11:51:16+00:00 List-Id: 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 !!!