Real-Time Kernels and Scheduling

Just go ahead and write your own multitasking multiuser os! Worked for me all the times. – Linus Torvalds

Updated 2017-01-11

Abstract

This article is mainly based on the French book Solution temps réel sous Linux by C. Blaess, chapters 1 to 8. I have summarized some results of my experiments while I was playing with the real-time capabilities of the Linux kernel. I am far from being an expert in the field, so feel free to send me any correction/suggestion.

Most of the references mentioned throughout this article refer to the book.

Playground

I wrote a small test program to display some real-time properties. It should be straightforward to compile:

${CC} -pthread -o rt rt.c

Have a look at the comments and the user options: tweaking them will show a different behaviour.

Problem overview

Real-time programming becomes necessary in a time-constrained context with various tasks executing in parallel. It can be useful in various contexts such as simulation, video games, media stream decoding, etc.

Priorities & niceness

Priorities

In real-time, priorities are scaled from 1 to 99 by default, but this is configurable. Shared time always has lower priority than real time, as if it would be of priority 0.

In shared time, the distinction between niceness and priority is somewhat fuzzy.

The niceness goes from -20 to 19, and has a value of 0 by default. A higher niceness means a lower priority. Be aware that priority can be tricky to use: the scheduler can penalize programs with higher priorities since they run more often, which leads to programs with lower priority having access to some resources before.

You need administrative privileges to make use of the real-time scheduler, to raise the priority or to lower the niceness below the default value. Otherwise, this would allow a non-privileged user to paralyze the machine.

Note however that Linux includes a guard on real-time processes. By default, lower priority processes still have a little share of time to run. This is made so that it is impossible to paralyze the whole system with a simple while(1);; albeit severely slowed down, the system can still kill the greedy task. This behaviour can be disabled with:

echo -1 > /proc/sys/kernel/sched_rt_runtime_us

Configuration

System resources such as priorities or niceness can be configured in different places.

See the respective man pages for more details.

Schedulers

There are several scheduling policies.

Linux < 2.6.23 default scheduler was known as the O(1) scheduler, using priority lists. The Completely Fair Schedular (CFS) was merged in Linux 2.6.23: it uses a red-black tree to choose the next task to run.

Some processus are CPU-bound (intensive computation), other are I/O-bound (a lot of time is spent on processing the input/output). The scheduling of tasks in shared time depends on their use.

Preemption happens when one of the following condition is met:

Shared-time

Various commands:

RT FIFO

This is the simplest: first in, first out. As soon as current task goes into a waiting state, the next task immediately goes into running state. It is ideal for a sequential execution.

RT Round Robin

This allows for parallel execution of several tasks. Unlike for the FIFO scheduler, CPU time slices play a role here (see page 154). For instance, on IPC synchronization, time gets wasted if synchronization happens at the beginning of the time slice. The solution is to use sched_yield() to control the scheduling.

Interrupts

Hardware interrupts cannot be software-managed: it is necessary to work at the kernel level. One solution is to write a dedicated module (driver). The main advantage of hardware interrupts is to allow for fine-tuning of the execution order.

Interrupts happen in two steps: the top half and the bottom half. The first is for the IRQs that are immediately processed and give information to the latter on how to execute. This second step can be deferred.

The purpose of this separation is to avoid blocking the processor on an interrupt for which the bottom half processing is long.

The bottom half processing happens through tasklets, workqueues, soft-IRQs, or threaded interrupts.

Interrupts can be displayed from the file /proc/interrupts. More precisely, it can be interesting to display its evolution over time:

watch -n 1 cat /proc/interrupts

(See pages 24, 28, 172.)

Software interrupts happen as soon as a specific instruction runs on the processor (e.g. division by 0, segmentation fault). In the general case a signal is sent to the calling process.

In any case, from the point of view of the process, interrupts consume CPU time. The time lapse between the moment when they might send a signal and when the process will actually receive it depends on when the process goes back to its running state. Thus it depends on the scheduler. To make sure that the process handler will run before anything else, we must make sure that the process has maximum priority.

Multiprocessors

A major challenge for scheduling is to handle the multi-CPU case: it is much more complex to control (i.e. to foresee) the running time of the different processes. When working in real time, we are better off to force the application to work on the same CPU by setting the affinity. This suggestion does not always apply, of course.

Some interesting functions worth knowing:

From a terminal, the affinity can be tweaked with taskset -pc CPUNO PID.

Linux, Linux-rt, and others

Linux

The standard kernel has been through several evolutions. Part of the linux-rt patch set has been merged into the 2.6 branch, so that the kernel now has a real-time scheduling policy as well as preemtible system calls.

Kernels before 2.6 are not preemtible. This can be checked with:

zcat /proc/config.gz | grep CONFIG_PREEMPT

On a 2.6+ kernel:

CONFIG_PREEMPT_RCU=y
CONFIG_PREEMPT_NOTIFIERS=y
# CONFIG_PREEMPT_NONE is not set
# CONFIG_PREEMPT_VOLUNTARY is not set
CONFIG_PREEMPT=y
CONFIG_PREEMPT_COUNT=y
# CONFIG_PREEMPT_TRACER is not set

The command uname -a also give some hints on the preemption capabilities. See page 129.

There is no difference in the ABI between the regular Linux kernel and Linux-rt. It means that there is full binary compatibility. Why not merging the Linux-rt branch entirely? Performance for a personal use happens to be worse.

Linux-rt

This patch set only changes some kernel parameters and makes system calls even more preemtible.

Interrupts are as such even more under control, and above all they have less impact on real-time processes. For instance, on a Linux machine where all processors are being used by a real-time application, a ping flood would halt the application. With Linux-rt, the application would continue (perhaps more slowly). See page 166.

The main purpose of Linux-rt lies in predictability. See chapter 8.

RTLinux, Xenomai

Linux and Linux-rt have interesting capabilities in term of soft real-time. However, they are almost worthless in a more constrained environment as we cannot prove the execution time. Some Linux-based hard real-time projects do exist, though.