[attachment=1249][attachment=1250]
[attachment=1248]
An Introduction To Real Time Linux
Raghu S.
An Introduction To Real Time Linux
Chapter 1. Introduction
GNU/Linux has conquered the minds and imagination of
computer enthusiasts throughout the world because it
is open source and adaptable to different hardware and
computing problems. As a general purpose Operating
System, however, the Linux kernel optimises average
performance and is not that appropriate for real-time
applications as such. For this reason there are some groups
spread around the world developing modifications to the
Linux kernel in order to provide an RTOS, all of them
following different strategies. The resulting real-time
operating systems are already used in many sophisticated
real-time applications and form a good basis for embedded
systems.
Basic Operating System Concepts
Real-time Operating Systems
RTOS is able to execute all its tasks without violating specified
timing constraints. the underlying principle is to achieve
maximum determinism over maximum throughput.
Soft Real-time & Hard Real-time
One often makes the distinction between soft real-time and
hard real-time "Soft" means that not meeting the specified
timing constraint is not a disaster, while it is a disaster for
hard real-time.
For example, playing an audio or video file is soft real-time
because few people notice when a sample came a fraction of
a second late. But steering a space probe is hard real-time.
Soft real-time require millisecond accuracy while hard realtime
require microsecond accuracy.
1
Chapter 1. Introduction
Real-time Terminology
We are familiar with most of the operating system terminology
like,
Rentrant functions
A rentrant function will behave identical if called by multiple
threads at the same time as it would if it is only called
once, that is any synchronisation or access of global data is
handled in a way that is safe to call these functions multiple
times and have them run interleaved.
Race conditions
If two executing processes compete for a resource and there
is no control provided as to when the resource is accessed
safely, unpredictable behaviour can occur. Race condition
can occur with any shared resource if no appropriate
synchronisation is done by all entities that require access to
this resource.
Dead lock
If synchronisation primitives are used inconsistently then
two threads may cause a dealock (interactive deadlock).
Real-time Quantification
In order to quantify the term real-time the following terms
are defined.
Response time or Latency
The latency of a task is the difference between the instant of
time on which the task should have started (or finished) and
the instant of time on which it actually did.
Latencies are due to several factors
2
Chapter 1. Introduction
¢ The timing properties of processor, bus, memory and peripheral
devices.
¢ The scheduling properties of the OS.
¢ The pre-emptiveness of its kernel.
¢ The load on the system.
¢ The context switch time.
Deadline
A time constraint for a process is called deadline, i.e. this is
the time when a result has to be delivered.
Jitter
The term jitter is used for describing the uncertainity of an
event in term of time. An event, for example, is supposed
to be a scheduled at a predefined sequence of time instances
T1, T2,........,Tn which constitute deadline, but actually there
is a certain time deviation at each such instance like #T1,
#T2,....,#Tn. This phenomenon of time deviation generally is
called jitter.
There is a far from exhaustive list of kernel activities that introduce
indeterminism into the timing behaviour of a (general
purpose) Operating system.
¢ Accessing the hard disk: Because the alignment of sectors,
and the distance between the track needed by a given task
are variable, that task cannot be sure about how long it
will take to access the data that it needs. In addition, hard
disks are mechanical devices, whose time scales are much
longer than purely electronic devices (such as RAM memory),
and accesses to the hard disk are â„¢bufferedâ„¢ in order
to reduce the average disk access time.
¢ Accessing a network: Especially with the TCP/IP protocol,
the packets are resent in case of transmission error.
¢ Unpredictable delays of timer chip.
3
Chapter 1. Introduction
¢ Non real-time device drivers.
¢ Memory allocation and management: After a task has asked
for more memory (eg: through malloc function call), the
time that the memory allocation task needs to fulfill the
request is unpredictable.
Timing Constraints
Different applications have different timing constraints,
which ideally, the RTOS should be able to satisfy.
¢ Deadline: A task has to be performed before a given instant
of time, but when exactly the task is perormed during the
time interval between now and the and the deadline is not
important for the inal result.
¢ Zero execution time: The task must be performed in a time
period that is zero in the ideal case. eg: digital control theory
assumes that taking a measurement, calculating the
control action, and sending it out to a peripheral device
all take place instantaneously.
¢ Quality of service: The task must get a fixed amount of "service"
per time unit. The QOS is often specified by means
of a small number of parameters: "s" seconds of service
in each time frame of "t" seconds. Thus a specification of 5
microseconds per 20 microseconds is much more real-time
QOS than a specification of 5 seconds per 20 seconds, although
on an average, both result in the same amount of
time allotted to the task.
Time Data Structures
The smallest time slice used in most general purpose OS is
longer than 1 ms. Not because the processors are fast enough
to do significant amount of work in that time slice, but because
32-bit machines have 2 ^ 32 slices before their timing
counter runs over at 1000 ticks per second. This corresponds
to less than 50 days which is certainly insufficient for servers
4
Chapter 1. Introduction
and embedded system. Linux uses a scheduling time slice
("jiffie") of 10 ms on most processors.
The timing constraints of real-time tasks are often expressed
with much higher resolution than those of general purpose
scheduler i.e, microseconds instead of milliseconds. Hence
the data structure in which the time is kept should be
adapted to this higher rate inorder to avoid overflow. For
example, the real-time Linux variants use a high-resolution
time data structure that counts time in nanoseconds.
POSIX has standardized "clocks" and "timers". The
timespec is a data structure that keeps the time in
two separate seconds and nanoseconds sub-structures
(/usr/include/linux/time.h) :
typedef long _kernel_time_t;
typedef _kernel_time_t time_t;
struct timespec{
time_t tv_sec;
long tv_usec;
};
The timespec datastructure uses 64-bits.
5
Chapter 1. Introduction
6
Chapter 2. Linux For Real-time
Task Management and Scheduling
Scheduling of tasks is one of the responsibilities of the task
management of the OS which has influence over the realtime
behaviour of the system.
Processes and Threads
The POSIX API provides the following functions
pthread_create();
pthread_mutex_lock();
pthread_mutex_unlock();
pthread_mutex_trylock();
An RTOS must also allow to specify the timing with which
threads have to be run. One typically uses two timing modes
¢ Periodic: The task must run at regular intervals
¢ One-Shot: The timing must run only once, at a predefined
instant in time.
One-shot timing sometimes requires a bit more
overhead, because of more involved hardware timer
programming. POSIX has no standardized function calls
for periodic timing. To overcome this RTLinux uses
pthread_make_periodic_up () for both options while RTAI has
rt_set_periodic_mode () and rt_set_oneshot_mode ()
Real-time Scheduling
As long as there is only one task or thread in a real-time system,
no real-time operating system would be necessary. eg: a
single control loop running on a processor. However usually
more threads are involved in a real-time system, like several
control loops at diffrent sampling times and with different
priorities. Given that each thread can be prempted, different
7
Chapter 2. Linux For Real-time
policies for scheduling multiple real-time threads are commonly
used like :
EDF Scheduler
In the Earliest Deadline First Scheduler it is not the priority
of a task which is used to decide what task to run, rather simply
the task with the closest deadline, that is then least time
left until it should be run is taken as a scheduling criteria.
RM Scheduler
A task gets a higher priority if it has to run more frequently.
So a task that has to be run every n milliseconds gets a higher
priority than a task that has to be run every m milliseconds
when n < m.
Priority Inversion Phenomena
Priority scheduling and locks are infact contradictory OS
primitives. Priority scheduling wants to run the highest
priority job first, while mutex excludes every other job
from running in a critical section that is already entered by
another job.
This can lead to a situation called priority inversion. A lower
priority task (i) is in a critical section for which it holds the
lock that blocks a high priority task (ii) it is self prempted
by a medium priority task that has nothing to do with the
critical section.
In both cases the high priority task has to wait for the completion
of a lower priority task leading to priority inversion.
The best known practical case of a priority inversion
problem occured during the MARS Pathfinder mission in
1997. (More info at http://kohalastart/papers.others/
pathfinder.html )
RTOSâ„¢s solve the problem of priority inversion by implementation
of two protocols
8
Chapter 2. Linux For Real-time
¢ Priority Inheritance: A low priority task that holds the lock
requested by a high priority task temporarily "inherits" the
priority of that high priority task, from the moment the
high priority task does the request. When the lock is released
the priority drops to its original level.
¢ Priority Ceiling: Every lock gets a priority level corresponding
to the priority of the highest priority task that can use
the lock. The lock gives this priority to every task that tries
the lock.
Priority Spaces
OS such as LINUX, UNIX, etc. have separate priority spaces
for different kind of tasks. Linux has user space and kernel
space.
Tasks running in user space can change their prioritities but
all of them are prempted by any task in the kernel space.
Kernel space itself has three prioritiy levels.
¢ Interrupts: The task that services a hardware interrupt has
the highest priority
¢ Tasklet functions and deffered service routines are functions
that run at the second highest priority.
¢ All other kernel tasks
Linux scheduler
The Linux scheduler is implemented in the file
/usr/src/linux/kernel/sched.c of the Linux source tree. It
orks in three scheduling modes SCHED_RR, SCHED_FIFO,
and SCHED_OTHER. SCHED_OTHER is the default.
SCHED_RR is the round robin time slicing algorithm. After a
task finishes its time slice, it is moved to the tail of its prioity
queue, such that another task in the same priority level can
start running.
SCHED_FIFO is a FIFO scheduling algorithm. All processes
and threads at the same priority are scheduled in the order
they arrived at a queue maintained by the kernel. A job
9
Chapter 2. Linux For Real-time
scheduler can monopolise the CPU as there is no mechanism
to prempt a job running with FIFO set.
10
Chapter 3. Linux Based Real-time
Operating System
GNU/Linux is an operating system for a general purpose
computer optimised for maximum throughput and average
performance of each process.
There are several approaches for building an RTOS.
Kernel Replacement
The first approach is to replace an existing non real-time kernel
by a small real-time kernel providing the same API. The
design guidelines for an RTOS include the following
¢ It needs to be compact, portable and efficient.
¢ It should not need to manage an excessive number of resources.
¢ It should not be dependent on any dynamically allocated
resources.
The pros and cons are listed.
¢ + complete new design of kernel adapted for the real-time
problem at hard.
¢ + Allows to grow and evolve with market by still keeping
the same API, in particular in the embedded field.
¢ - The OS becomes very complex making it difficult to ensure
determinism.
¢ - Drivers for hardware become very complex.
¢ - Since the core is an RTOS, the vast amount of free software
that is available cannot be used unmodified.
¢ - Maintenance costs for such systems are considerable.
11
Chapter 3. Linux Based Real-time Operating System
Kernel Modification
The most seemingly alternate strategy would be to add RT
capabilities to a general purpose OS by modifying the kernel.
One common technique is to insert premption points into the
kernel whenever it is safe to perform a context switch.
The pros and cons of such an approach is listed.
¢ + Performance improvements with little changes may be
sufficient.
¢ + All general tools for debugging and development can be
used.
¢ + Slight modification keeps the kernel near to the development
thread.
¢ + Kernel changes are in the scheduler far away from the
interrupt hardware.
The cons are
¢ - General purpose OS are event driven, not time triggered.
¢ - General purpose OS are not fully preemptive systems.
Making them fully preemptive requires modifications to
all hardware drivers and to all resource handling codes.
¢ - Optimisation strategies used in general purpose OS can
contradict RT requirements.
¢ - Modifying applications to be preemptive is very costly
and error prone.
Kernel co-existence
The kernel is split into two parts one part that runs as a general
purpose OS and a second part that is designed around
the real-time capabilities.
This is often used to add real-time capabilities to Microsoft
Windows OS. The major pros and cons are listed below.
¢ + Reduces all general features to a bare minimum.
12
Chapter 3. Linux Based Real-time Operating System
¢ + Allows the non real-time side of hte OS to provide all the
goodies that desktop users are used to.
¢ + Real-time side can be kept small, compact and deterministic.
¢ - RT threads are executed in supervisor mode.
¢ - Debugging in kernel is difficult.
¢ - Application must be divided in a real-time and non realtime
part which makes porting difficult.
Major issues
¢ Coarse Grained Synchronisation : The Linux kernel uses
coarse grained synchronisation which allows a kernel
task exclusive acces to some data for long periods . This
delays the execution of any POSIX real time task that
needs access to the same data.
¢ Kernel Preemption : Of course all user processes are preemptible
by the kernel, in particular by the scheduler after
a blocking system call . If the user process starts a kernel
activity on her behalf , the kernel itself cannot be preempted
any more (except, for ISRâ„¢s). Only when the mentioned
kernel activity is finished, a higher process can run.
¢ Scheduler : Meeting hard deadlines has not been forseen
in the Linux kernel as the scheduler and other kernel resources
were designed for average performance. This effect
is aggravated by the fact that the scheduler is called
periodically and after each system call which in statistical
terms increases its execution time proportional to the
number of processes and reduces response time.
¢ Task Queuing : Usually if a process blocks on a resource ,
it is put on wait queue without order priority . Once the
resource is available , all these process are made runnable
and are hence schedulable with not necessarily the highest
priority process winning the race .
¢ Interrupt Disable : Inorder to implement atomic operations
and critical regions, the kernel will disable the interrupts
sometimes for longer periods, especially in device drivers.
13
Chapter 3. Linux Based Real-time Operating System
during this period which can take some milliseconds, the
system does not respond to any other interrupt or signal.
¢ Thread Support : The Linux kernel does not directly support
threads. Rather the POSIX pthread library maps to
classical UNIX processes which are slower to be treated.
¢ Priority Inversion: Whenever multiple processes with different
priorities compete for a resource, priority inversion
can happen with a single priority process being blocked by
a lower priority one holding a resource, but not schedulable.
There are solutions to these issues but they have not yet
been addressed in current Linux kernel. Due to the fact
that Linux is open source, however, it can be adapted and
despite the difficulties and problems mentioned before and
there are several real-time Linux implementations in one of
the three methods.
14
Chapter 4. Kernel Modules
Kernel Modules
The Linux kernel design is similar to that of classic Unix systems:
it uses a monolithic architecture with file systems, device
drivers, and other pieces statically linked into the kernel
image to be used at boot time. The use of dynamic kernel
modules allows you to write portions of the kernel as separate
objects that can be loaded and unloaded on a running
system.
A kernel module is simply an object file containing routines
and/or data to load into a running kernel. When loaded,
the module code resides in the kernelâ„¢s address space
and executes entirely within the context of the kernel.
Technically, a module can be any set of routines, with
the one restriction that two functions, init_module() and
cleanup_module(), must be provided. The first is executed
once the module is loaded, and the second, before the
module is unloaded from the kernel.
The main functions to use to load /unload and inspect kernel
modules are contained in the modutils package. They are:
/sbin/insmod (insert a module into the running kernel)
/sbin/rmmod (remove a module from the running kernel)
/sbin/lsmod (inspect modules in the running codes)
Note that to manage with kernel modules you have to be
root. Once a module is loaded, it passes to form part of the
operating system, hence it can use all the functions and access
all variables and structures of the kernel. Similarly the
global symbols created are made available or exported to
other modules. If you donâ„¢t want to share some symbol (variable
or function), you have to declare it as static.
A module is built from a "C" source. Here is the simplest
example of a kernel module (simple1.c).
--------- simple1.c ------------
15
Chapter 4. Kernel Modules
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/version.h>
int var = 20;
int init_module(void)
{
printk("\nVariable value: %d \n\n", var);
return 0;
}
void cleanup_module(void)
{
printk("\n Bye \n\n");
}
This can be compiled with:
gcc -c -D__KERNEL__ -DMODULE -o simple1 simple1.c
Note that the kernel offers a different version of printf()
called printk(); this works almost identically to the first
except that it sends the output to a kernel ring buffer. At any
istant you can examine the contents of the buffer using the
command dmesg.
16
Chapter 5. Implementation Examples
In the following section two of the most popular Linux based
real-time operating systems are introduced.
Real-time Application Interface (RTAI) : Features
The RTAI consists of 5 complimentary features:
¢ The HAL(Hardware Abstraction Layer): It provides an interface
to the hardware ,on top of which both linux and hard
realtime can run.
¢ The Linux Compatibility Layer: It provides an interface to
the Linux operating system, with which RTAI can be integrated
into the Linux task management, without Linux
noticing anything.
¢ RTOS Core:This part offers the hard real time functionality
for task scheduling,IPCâ„¢s and locking.
¢ LX/RT(Linux RealTime):The LX/RT makes soft and hard
realtime features available to user space tasks in Linux.
LX/RT puts a strong emphasis on offering a symmetric
real-time API . The same RealTime functionality should be
usable with the same function calls from the user space as
well as kernel space.
¢ Extended Functionality Package:The core is extended with
useful extras such as several forms of IPCâ„¢s, network and
serial line drivers; POSIX interfaces etc.
RTAI Modules
To use RTAI, you have to load the modules that implement
whatever RTAI capabilities you need. According to 1.3 release,
available are the following core modules:
rtai
rtai_sched
rtai_fifos
rtai_shm
lxrt
rtai_pqueue
17
Chapter 5. Implementation Examples
rtai_pthread
rtai_utils
Letâ„¢s examine one by one.
¢ It is the really core module and nothing about the real
time services can be done without it. RTAI initializes all
of its control variables and structures, makes a copy of the
idt_table
¢ The real time scheduler module, which is in charge of distributing
the CPU to different tasks RTAI considers the
priority 0 as the highest priority and 0x3fffFfff the lowest.
Linux is given priority 0x7fffFfff. Given a priority level, the
first initialized task will be the first elected and will run to
completion unless a task with a higher priority is elected
or it terminates or the task calls a blocking system function.
RTAI supports both periodic and oneshot mode for
the real time scheduler.
You have three different schedulers:
¢ UP , only for uniprocessors
¢ SMP , for multiprocessors
¢ MUP , only for multiprocessors
The scheduler services are:
¢ Task functions
¢ Timing functions
¢ Semaphore functions
¢ Mailbox functions
¢ Intertask communication functions
All the functions can be used with any scheduler. Note that
when you load rtai_sched, automatically rtai is mounted.
¢ The module that implements the fifo services for RTAI.
Many applications appear to benefit from a synergy between
the real-time system side and the Linux side, for
18
Chapter 5. Implementation Examples
example for managing the data logging and displaying.
Simple fifo buffers are used to do this; they are called real
time fifos. The real-time task interface includes creation,
destruction, reading and writing functions, performed by
the rtai_fifos module. Linux user processes, on the other
hand, see rt-fifos as ordinary character devices. Note that
on the module side you always have only non blocking
put/get, so that any different policy should be enforced
by using appropriate user handler functions. Available are
an old and a new (strongly recommended) fifo implementation.
The last one is based on the mailboxes concepts,
symmetrically usable from kernel modules and Linux processes.
Even if fifos are strictly no more required in RTAI,
because of the availability of LXRT (see below), fifos are
kept for both compatibility reasons and because they are
very useful tools to be used to communicate with interrupt
handlers, since they do not require any scheduler to
be installed. In this sense you can see this new implementation
of fifos as a kind of universal form of device drivers,
since once you have your interrupt handler installed you
can use fifo services to do all the rest.
¢ The RTAI specific module that allows sharing memory
among different real time tasks and Linux processes,
simoultaneously (it is another mechanism available to
users, in addition to fifos). The services are symmetrical,
i.e. the same calls can be used both in real time tasks,i.e.
within the kernel, and Linux processes. The first
allocation does a real allocation, any subsequent call to
allocate with the same name from Linux processes just
maps the area to the user space or return the related
pointer to the already allocated space in kernel space.
Analogously the freeing calls have just the effect of unmapping
till the last is done, as that is the one the really
frees allocated memory. Clearly cooperating users have to
use the same name.
¢ The LX(Linux)RT(RealTime) module, which implements
services to make available any of the RTAI schedulers
functions to Linux processes, so that a fully symmetric
implementation of real time services is possible. To state it
more clearly, that means that you can share memory, send
19
Chapter 5. Implementation Examples
messages, use semaphores and timings: Linux to Linux,
Linux to RTAI and, naturally, RTAI to RTAI.
¢ Posix RTAI modules. rtai_pthread.o provides hard
real-time threads, where each thread is a RTAI task. All
threads execute in the same address space and hence
can work concurrently on shared data. rtai_pqueue.o
provides kernel-safe message queues.
RTLinux:Features
The core idea behind RTLinux is to run a full featured operating
system as one thread of a real-time executive ,so it
follows the kernal co-existance concept. In a logical sense
,"tasks" and "interrupts" are seperated in two classes ,the real
time ones running directly on behalf the executive ,and the
non-realtime ones being excuted with in common operating
sytem, with some means of communication between these
two priority spaces. "realtime" in this context is meant to be
hard real time as its deadlines have to be met in case. In order
to meet this goal , the general is to keep as many services
in non-realtime Linux as possible if they are not inherently
hard realtime ,like data display or storage.
As general purpose operating system Linux optimizes
average performance ,but is not appropriate for hard
realtime. the RTLinux modifications to the kernal ,however
-put a thin layer underneath yhr linux operaring system.
This core hard realtime mechanism takes over control of
the low level interrupt handling from Linux: in some cases
Linux kernal is modified to make this take over work
smoothly. RTLinux applies most changes directly to the
kernal source files,reulting in modifications and additions
to numerous linux kernal source fils. The low latency
interrupt handlers cannot be preemted by Linux acting
then only on emulated interrupts. All other functionalities
and communication means as schedulers,timers ,POSIX-io
,FIFOs,shared memory ,semaphores and mutexes can be
added by inserting a kernal module at runtime.
With the core functionality realtime ISRs can be installed already
as simple real-time "application". Once the modules
20
Chapter 5. Implementation Examples
for time and scheduling are inserted into the kernal ,both
"task" and "interrupt" priority spaces are created. From now
on the thin hard realtime layer constitutes a single process
per CPU running on the bare computer hardware with Linux
being inthe following just a low priority thread among realtime
threads and interrupt service routines(ISRs). Linux as
"task" works as usual in its own process space as illustrated
by Figure.From the userâ„¢s point of view ,the computer can be
used as a full featured workstation in normal mode.In case of
a realtime event,however ,Linux completely preempted and
the realtime threads or interrupt service routines are treated
immediately.Once they have finished and there is nothing
else to do in the "hard realtime world",Linux is scheduled
again.
21
Chapter 5. Implementation Examples
22
Chapter 6. References
¢ The Free Software Foundation, gnu.org.
¢ The Real Time Linux Foundation.
realtimelinuxfoundation.org.
¢ Yodaiken, Victor (1999), RTLinux, rtlinux.org.
¢ Wurnisdobler, Peter, Real Time Linux Operating Systems
(2001), ctm-france.com.
¢ Bruyninckx, Herman, Real Time and Embedded Guide.
23
Chapter 6. References
24
by Raghu S.
Table of Contents
Acknowledgement
..................................................................... i
1.
Introduction...........................................................
..................1
Basic Operating System Concepts......................................1
Real-time Operating Systems.......................................1
Soft Real-time & Hard Real-time.................................1
Real-time Terminology
........................................................1
Rentrant functions
.........................................................2
Race conditions
..............................................................2
Dead lock
.......................................................................
.2
Real-time
Quantification...............................................2
Deadline
.......................................................................
...3
Jitter
.......................................................................
..........3
Timing
Constraints............................................................
...4
Time Data
Structures............................................................4
2. Linux For Real-time
...............................................................7
Task Management and Scheduling....................................7
Processes and Threads
.........................................................7
Real-time Scheduling
...........................................................7
EDF
Scheduler..............................................................
..8
RM
Scheduler..............................................................
...8
Priority Inversion
Phenomena............................................8
Priority Spaces
......................................................................9
Linux scheduler
....................................................................9
3. Linux Based Real-time Operating System ......................11
Kernel Replacement
...........................................................11
Kernel Modification
...........................................................11
Kernel co-
existence.............................................................1
2
Major
issues.................................................................
........13
4. Kernel Modules
....................................................................15
Kernel
Modules................................................................
...15
5. Implementation
Examples..................................................17
Real-time Application Interface (RTAI) : Features.........17
RTAI Modules
..............................................................17
RTLinux:Features.......................................................
.........20
6.
References.............................................................
.................23
iii
iv
Acknowledgement
I express my sincere gratitude to Prof. M.N Agnisarman Namboothiri
( Head Of Department , Computer Science and Engineering
) and Mr. Zainul Abid ( Staff in charge ) for their kind
cooperation for the seminar presentation .
I also extend my sincere thanks to all other members of the
faculty of Computer Science And Engineering Department
and my friends for their guidance and encouragement .
i
Acknowledgement
ii