About Articles Projects Links Apps Feed

Real-Time Kernels and Scheduling

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

– Linus Torvalds

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.

  • Globally in /etc/security/limits.conf.
  • setrlimit() for a single task.
  • ulimit to show some values.

See the respective man pages for more details.

Schedulers

There are several scheduling policies.

  • Shared time
  • Other (Linux default)
  • Batch (Linux only)
  • Idle (Linux only)
  • Real time
  • FIFO
  • Round-Robin

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.

  • Interactive tasks need a low response time for best user experience.
  • Batch processes run in the background; they perform a lot of computation with little I/O.
  • Real-time processes need low response time, minimal variance and should not be blocked when avoidable.

Preemption happens when one of the following condition is met:

  • A hardware interrupt was received.
  • The end of the time quantum was reached.
  • A process with higher priority is active.

Shared-time

Various commands:

  • chrt -m: show current values.
  • chrt -ap PID: display PID’s policy and priority, as well as for its current threads if any.
  • ps ma -o command,ni,pri displays the priority and the niceness for various processes and threads. See the ps(1) man page.

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:

  • Linux: sysconf(_SC_NPROCESSORS_ONLN): return the number of online processors.
  • GNU: sched_setaffinity(): change the affinity of a task (process or thread). The equivalent for threads is available in the GNU
  • pthread library as an extension (and thus non-POSIX).

From a shell, 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.

  • RTLinux is a micro kernel running the entire Linux kernel as a process, thus it is fully preemptible. The development of this proprietary kernel has been discontinued and the source have been released under GPL2.
  • Xenomai is one of the most active project in the field. It is free and open-source.

Comments

Date: 2014-11-24 (Last update: 2018-08-12)

Made with Emacs 27.0.50 (Org mode 9.1.9)

Creative Commons License