Overview

KURT (KU Real-Time Linux) is a real-time modification to the Linux operating system that allows scheduling of real-time events at the resolution of 10's of microseconds. Rather than relying on priority based scheduling or strictly periodic schedules, KURT schedules are explicitly specified by the application programmer. KURT can function in two modes: focussed mode, where only real-time processes are allowed to run; and mixed mode, where the execution of real-time processes still takes precedence, but all non-real-time processes are allowed to run within the “gaps” of the real-time schedule. KURT works on any x86 compatible platform with a time-stamp counter (Pentium processors or their equivalent).

I. Introduction

A real-time system is one in which, in addition to the logical correctness of results, the timeliness is also of importance. Generally, real-time systems are classified into two categories:

• Soft real-time systems: In these types of systems the results are not catastrophic when deadlines are not met. Linux has Posix soft real-time scheduling. Processes whose scheduling policy is not SCHED_OTHER are soft real-time processes. These processes are preferentially selected over normal processes for execution.

• Hard real-time systems: In these systems, the cost of missing deadlines is usually very high. In these systems, efficiency is not usually of concern; timeliness is. RTLinux is a hard real-time Linux.

Some types of processing (eg. multimedia) do not fit well into the hard or soft real-time categories. The periodic requests made by multimedia applications are sensitive to variations in timing. As such, they are not well served by the loose guarantees provided by soft real-time systems. Hard real-time systems are often faced with providing guarantees at the expense of providing services. Thus, while they can meet the timing requirements of a multimedia application, many times they cannot meet it's other service requirements. For example, real-time processes running under RTLinux have no access to any of the Linux services.

A purely binary distinction between hard and soft real-time is clearly not acceptable for all applications. Many applications have requirements spanning a continuum between the two. To service a wider range of requirements, we have developed a firm real-time Linux. We call this system “KURT” Linux for KU Real-Time Linux.

KURT Linux allows for explicit scheduling of any real-time events rather than just processes. This provides a more generic framework onto which normal real-time process scheduling is mapped. Since event scheduling is handled by the system, addition of new events such as periodic sampling data acquisition cards (video, lab equipment, etc.) is highly simplified.

KURT introduces two modes of operation – the normal mode and the real-time mode. In normal mode, the system acts as a generic Linux system. When the kernel is running in real-time mode, it only executes real-time processes. While in real-time mode, the system can no longer be used as a generic workstation, as all of its resources are dedicated to executing its real-time responsibilities as accurately as possible.

A simple system call allows the kernel to be toggled between real-time and normal mode. During the setup phase, the schedule of events to be executed in real-time mode is specified and the various processes that are to be executed in real-time mode are marked. The kernel is then switched to real-time mode. When all of the real-time tasks finish execution, the kernel can be switched back to the normal mode.

Presently, this system is available only for the i386 architecture. Porting KURT to other architectures requires only minimal additions. If you are interested in porting KURT to other architectures, please send mail to [email protected].

II. Glossary of Terms

• Real-Time Events: Real-time events can be any event that needs to be scheduled in real-time mode. For example, you may want to write a traffic generator that generates traffic according to a predefined schedule. Such a system could be used to test the performance of network equipment like switches, etc. To achieve this in a normal real-time system would entail writing a user process that would generate the real-time traffic and write it to a socket. Such a system is inherently inefficient because it causes excessive switching between the kernel and the user space. Another problem in such a system is that, once the user process has written the data to the socket, its up to the kernel to send it out of the network interface card (NIC). Hence the whole purpose of generating traffic according to a specified pattern is defeated. We have solved this problem by introducing the concept of a real-time module.

• Real-Time Framework: KURT consists of a real-time framework that takes care of scheduling any real-time event. When a real-time event is to be executed, the real-time framework calls the event handler of the associated RTmod. By splitting the functionality of scheduling and actual execution into two separate entities, we have simplified the process of adding more functionality to our real-time system. For example, adding the capability of generating network traffic according to a specified schedule is as easy as writing an RTMod that would make the network card send out a packet whenever it is invoked. Scheduling the invocations of this RTMod is the responsibility of the real-time framework. This framework provides system calls which switch the kernel into and out of real-time mode, schedule real-time events, and list all of the registered real-time modules.

• Real-time Modules: Real-time modules (RTMods) are kernel modules, that can be loaded at runtime, which perform certain actions when invoked. We have written an RTMod that switches context to a specified user process when it is invoked. We have also written an RTMod that flips the bits on a parallel port. Such a real-time module has to register itself with the real-time framework. One real-time module that is always present is the “process” module. This module schedules the waking up of a process when it is invoked.

• rt_id: the identification number associated with each KURT process. Each KURT process can request or be given an rt_id when it registers itself with the process module using set_rtparams. A KURT process can change its rt_id using the same system call.

• Registration of RTMods: An RTMod registers itself with the real-time framework by providing a name, and pointers to functions for the event handler, initialization, and clean up. When a real-time module is registered, an identification number is assigned to it which is used when scheduling events for this particular module.

• Real-Time Schedule: A real-time schedule is a file that specifies which RTMod needs to be invoked and at what time. This schedule is passed to the real-time framework, and it takes care of scheduling each event and invoking the appropriate event handler at the appropriate time. We have provided a sample program that generates this schedule.

• Scheduling Modes: The real-time framework can schedule events according to two modes:
  
  
  • FROM_MEM: In this mode, the schedule file is completely read into kernel memory and then the scheduling of each event takes place. It is possible to repeat this schedule any number of times in a cyclic fashion. The disadvantage of this mode is that there should be enough memory to hold the complete schedule file. Each event takes 24 bytes of memory.

  • FROM_DISK: In this mode, the schedule file is read into kernel memory one page at a time. Arbitrarily long schedules can be submitted to the real-time framework for scheduling. The disadvantage of this mode is that there could be some distortion in scheduling events because of the intermittent reading from the disk.
  
  
• UTIME: KURT uses the utime system to schedule events with micro-second resolution. Events can be scheduled with 10ms resolution if UTIME is not installed.

III. Structure of an Executive Process

An executive process controls the scheduling of all KURT processes and all RTMods. The main actions the executive process takes are shown below:

int main()
{
set the scheduler of the current process to SCHED_KURT;
wait for all of the KURT processes to register themselves;
switch to real-time mode;
schedule the real-time events;
switch to normal mode;
}

An example executive process is available.

Note: In the current version of KURT (v1.23) we do not need an executive process to schedule periodic processes. Each of the periodic processes schedule themselves. This scheduling is started when the first rt_suspend call is issued.

IV. Structure of a KURT Process

Most KURT processes have the following structure:

int main()
{
set the scheduler of the current process to SCHED_KURT;
while(1) {
suspend until woken up by the executive process;
do stuff;
}
}

An example KURT process is available. An example of a periodic KURT process is also available.

V. System Calls

System Calls in the Real-Time Framework

The following system calls are present in the core real-time framework:

• switch_to_rt: Switches the kernel into real-time mode. Once the kernel is switched to real-time mode (with rt_mode=SCHED_KURT_PROCS), only processes that are marked as SCHED_KURT processes are allowed to run. If rt_mode = SCHED_ALL_PROCS in the call to switch_to_rt, then all processes are allowed to run, and KURT processes can be explicitly scheduled. The prototype of this system call is:
  
  int switch_to_rt(int timer_mode, unsigned long period, int rt_mode, char *cmdline, int length);

  See the UTIME web page for the definition of the timer mode and the period. cmdline is a character string that is passed to the init function of all the registered RTMod. For example to pass something to the process module the cmdline would be “process=xxxxx”. The kernel passes the appropriate parameters to the various modules, based on the module names. length is the length of the cmdline.

  
  
• rtmod_cmd: This allows a real time module to provide a new interface to any user programs using it. Using this system call the user program can ask the RTMod to perform a certain action. The correct RTMod is located and the command and the buffer is passed to the RTMod. The prototype is:
  
  int rtmod_cmd(int rtmod_id, int command, void *buf, unsigned long length);
  
  
• switch_to_normal: Switches the kernel back into normal mode. This allows the use of the PC as a normal workstation. The force parameter can be set to force the kernel to be switched to normal mode by deleting all the events that have already been scheduled. If the force parameter is not set, then this call blocks till all the events that have already been scheduled have finished executing. The prototype is:
  
  int switch_to_normal(int force);
  
  
• rt_schedule_events: This system call schedules the events as per the schedule file. The prototype of this system call is:
  
  int rt_schedule_events(struct timeval *start_time, int sched_mode, int num_times, char *filename);
  
  Where
  
  start_time is the time when the scheduling should start.
  num_times is used only in the case the scheduling mode is FROM_MEM.
  
  
• get_rtmod_num: This is not a system call, but a library call included in librt.a. This call allows a user to get the RTMod Id of a module by passing the name of the RTMod to this function. The prototype of this call is as follows:
  
  int get_rtmod_num(char *name);

System Calls in the Process Module

The “process” module, takes care of switching context to a specified process when it is invoked. It modifies some existing system calls and, in addition, provides the other system calls mentioned below:

• set_rtparams: This system call has been added to the linux kernel to mark a particular process as a SCHED_KURT process. Only those processes whose scheduling policy is SCHED_KURT are allowed to run in real-time mode. Each process can request a rt_id which is used when scheduling a real-time process. The prototype is:
  
  int set_rtparams(int pid, int policy, struct rtparams *);

  pid is the pid of the process whose rtparams we are modifying. If this parameter is set to 0, then the call applies to the currently running process.

  policy: This specifies the scheduling policy that the given process should be set to. So, to mark a process as arealtime process you would set the policy to be SCHED_KURT. Also to unmark a SCHED_KURT process, you need to set this to either SCHED_OTHER, SCHED_FIFO, or SCHED_RR. (Note: you cannot use the sched_setscheduler system call to unmark a SCHED_KURT process.)

  struct rtparams: This structure specifies the characteristics of the SCHED_KURT process. It is defined as follows:

  
  struct rtparams {
  int rt_id;
  int priority;
  unsigned long proc_req;
  unsigned long period;
  }

  priority: KURT uses a round-robin scheduling mechanism to schedule processes that have not been explicitly scheduled. This member of rtparams gives the priority of the KURT process.

  proc_req: is the processing requirements of the current process every time it is invoked. If the scheduling mode is PERIODIC then the next process is scheduled proc_req microseconds later than this process.The kernel takes care of including the scheduling overhead when scheduling these processes.

  period: is the period of this process. Currently all KURT processes should have the same period. This can be set to 0, for aperiodic processes that are being scheduled using the rt_schedule_events system call.

  
  When a SCHED_KURT process forks or clones, the child process inherits the SCHED_KURT status. The process RTMod takes care of assigning a rt_id to the child process. This rt_id can be changed by a call to the set_rtparams system call. Information on the scheduling policy as well as the rt_id and the processing requirements of a process can be obtained using the get_rtparams system call. (Note: the forked process inherits the priority of the parent process, and is marked with a processing requirement of 0.)
  
  
• get_num_rtprocs: Returns the number of SCHED_KURT processes. The prototype is:
  
  int get_num_rtprocs(void);
  
  
• rt_suspend: Suspends a SCHED_KURT process until it is woken up by the process module. See the structure of a KURT process above for details on use of this system call. The prototype is as follows:
  int rt_suspend(int susp_mode);

  susp_mode can be either START_SCHED or STOP_SCHED. If the process is a periodic process (ie rt_params.period!=0) then START_SCHED starts scheduling the process according to its period.
  STOP_SCHED stops scheduling a periodic process. In addition these flags can also be ORed with SUSPEND_IF_NRT which causes the process to suspend till the kernel gets switched to realtime mode after which it can start scheduling. Explicitly scheduled processes (ie those processes that get scheduled using a schedule file) need not use the START_SCHED, STOP_SCHED flags.

  
  
• get_rt_stats: Returns a rtstats structure for the current process. The rt_info structure is of the form (Please see the structure of a KURT process before proceeding):
  
  struct rtstats {
  int rt_id;
  int rt_abort;
  int suspended;
  unsigned long rt_num_woken_up;
  unsigned long rt_num_suspended;
  unsigned long rt_num_missed;
  }

  rt_abort is set when a process over steps its allocated time and another process is scheduled in. This means that the process needs to abort whatever it is doing and perform a rt_suspend as soon as possible.

  The suspended field is set when a process calls the rt_suspend system call.

  rt_num_woken_up is the number of times the current process has been woken up.

  rt_num_suspended is the number of times the current process has performed an rt_suspend.

  rt_num_missed is the number of times the current process missed its scheduling because it had not finished its previous iteration.

VI. /proc filesystem:

We have added an entry into the /proc filesystem called rt. This directory has entries for the statistics of the real-time system (ie. the number of events handled, the number of events delayed, etc.) in the stats subdirectory. The various registered RTMods can be found in the rt_mods entry. The various realtime processes that have been registered and their statistics can be found in the processes.

VII. Files changed:

A whole new directory called rt has been introduced into the kernel source. Apart from the files in this directory, the following files have been modified or added:

kernel/sched.c
kernel/sysctl.c
kernel/fork.c
kernel/exit.c
arch/i386/kernel/entry.S
arch/i386/kernel/setup.c
mm/vmscan.c
init/main.c
include/asm-i386/unistd.h
include/linux/rt.h
include/linux/sched.h
drivers/char/sysrq.c

Please visit the UTIME page for information on the files that have been modified as part of the UTIME patch.

VIII. Copyright and Credits

Copyright (C) 1997 by the University of Kansas Center for Research, Inc. This software was developed by the Information and Telecommunication Technology Center (ITTC) at the University of Kansas. Partial funding for this project was provided by Sprint. This software may be used and distributed according to the terms of the GNU Public License, incorporated herein by reference. Neither ITTC nor Sprint accept any liability whatsoever for this product.

This project was developed under the direction of Dr. Douglas Niehaus.

Authors: Balaji S.

Please send bug-reports/suggestions/comments to [email protected]

IX. Mailing List

There is also a mailing list for KURT related questions. If you would like to subscribe to the KURT mailing list please send an email to [email protected], with the body . . .

subscribe linux-kurt

 
This article was originally published on LinuxDevices.com and has been donated to the open source community by QuinStreet Inc. Please visit LinuxToday.com for up-to-date news and articles about Linux and open source.