Embedded Systems.. EASY questions!

profileWolverineX
embedded_linux_realtime.pdf

1 Free Electrons. Kernel, drivers and embedded Linux development, consulting, training and support. http://free­electrons.com

Embedded Linux system development

Real­time in  embedded Linux 

systems Michael Opdenacker Thomas Petazzoni

Gilles Chanteperdrix Free Electrons

© Copyright 2004­2011, Free Electrons. Creative Commons BY­SA 3.0 license Latest update: Feb 21, 2011,  Document sources, updates and translations: http://free­electrons.com/docs/realtime Corrections, suggestions, contributions and translations are welcome!

2 Free Electrons. Kernel, drivers and embedded Linux development, consulting, training and support. http://free­electrons.com

Real Time in Embedded Linux Systems

Introduction

3 Free Electrons. Kernel, drivers and embedded Linux development, consulting, training and support. http://free­electrons.com

Embedded Linux and real time

Due to its advantages, Linux and the open­source softwares are  more and more commonly used in embedded applications

However, some applications also have real­time constraints

They, at the same time, want to

Get all the nice advantages of Linux: hardware support,  components re­use, low cost, etc.

Get their real­time constraints met

?

4 Free Electrons. Kernel, drivers and embedded Linux development, consulting, training and support. http://free­electrons.com

Embedded Linux and real time

Linux is an operating system part of the large Unix family

It was originally designed as a time­sharing system

The main goal is to get the best throughput from the available  hardware, by making the best possible usage of resources (CPU,  memory, I/O)

Time determinism is not taken into account

On the opposite, real­time constraints imply time determinism,  even at the expense of lower global throughput

Best throughput and time determinism are contradictory  requirements

5 Free Electrons. Kernel, drivers and embedded Linux development, consulting, training and support. http://free­electrons.com

Linux and real­time approaches

Over time, two major approaches have been taken to bring real­ time requirements into Linux

Approach 1

Improve the Linux kernel itself so that it matches real­time  requirements, by providing bounded latencies, real­time APIs, etc.

Approach taken by the mainline Linux kernel and the  PREEMPT_RT project.

Approach 2

Add a layer below the Linux kernel that will handle all the real­time  requirements, so that the behaviour of Linux doesn't affect real­time  tasks.

Approach taken by RTLinux, RTAI and Xenomai

6 Free Electrons. Kernel, drivers and embedded Linux development, consulting, training and support. http://free­electrons.com

Approach 1 Improving the main Linux kernel with 

PREEMPT_RT

7 Free Electrons. Kernel, drivers and embedded Linux development, consulting, training and support. http://free­electrons.com

Understanding latency

When developing real­time applications with a system such as  Linux, the typical scenario is the following

An event from the physical world happens and gets notified to the  CPU by means of an interrupt

The interrupt handler recognizes and handles the event, and then  wake­up the user­space task that will react to this event

Some time later, the user­space task will run and be able to react to  the physical world event

Real­time is about providing guaranteed worst case latencies for  this reaction time, called latency

Something not very important... Your important real­time task !

Interrupt ! ?

8 Free Electrons. Kernel, drivers and embedded Linux development, consulting, training and support. http://free­electrons.com

Linux kernel latency components

Waiting task

interrupt latency

Interrupt handler Scheduler

Running task

Interrupt

Scheduling latency

scheduler latency

scheduler duration

Process context

Interrupt context

Makes the task runnable

kernel latency = interrupt latency + handler duration + scheduler latency + scheduler duration

handler duration

9 Free Electrons. Kernel, drivers and embedded Linux development, consulting, training and support. http://free­electrons.com

Interrupt latency

Waiting task

interrupt latency

Interrupt handler Scheduler

Running task

Interrupt

handler duration

scheduler latency

scheduler duration

Makes the task runnable

Time elapsed before executing the interrupt handler

Scheduling latency

10 Free Electrons. Kernel, drivers and embedded Linux development, consulting, training and support. http://free­electrons.com

Source of interrupt latency

One of the concurrency prevention mechanism used in the kernel  is the spinlock

It has several variants, but one of the variant commonly used to  prevent concurrent accesses between a process context and an  interrupt context works by disabling interrupts

Critical sections protected by spinlocks, or other section in which  interrupts are explictly disabled will delay the beginning of the  execution of the interrupt handler

The duration of these critical sections is unbounded

Other possible source: shared interrupts

Kernel code

Critical section protected by spinlock

Interrupt handler

Interrupt ?

11 Free Electrons. Kernel, drivers and embedded Linux development, consulting, training and support. http://free­electrons.com

Interrupt handler duration

Waiting task

interrupt latency

Interrupt handler Scheduler

Running task

Interrupt

handler duration

scheduler latency

scheduler duration

Makes the task runnable

Time taken to execute the interrupt handler

Scheduling latency

12 Free Electrons. Kernel, drivers and embedded Linux development, consulting, training and support. http://free­electrons.com

Interrupt handler implementation

In Linux, many interrupt handlers are split in two parts

A top­half, started by the CPU as soon as interrupt are  enabled. It runs with the interrupt line disabled and is  supposed to complete as quickly as possible.

A bottom­half, scheduled by the top­half, which starts after all  pending top­half have completed their execution.

Therefore, for real­time critical interrupts, bottom­half  shouldn't be used: their execution is delayed by all other  interrupts in the system.

Top half

Interrupt ACK Exit

Bottom half

Schedule bottom half

Other interrupt handlers...

Handle device data...

Wake up waiting tasks

User space...

13 Free Electrons. Kernel, drivers and embedded Linux development, consulting, training and support. http://free­electrons.com

Scheduler latency

Waiting task

interrupt latency

Interrupt handler Scheduler

Running task

Interrupt

handler duration

scheduler latency

scheduler duration

Makes the task runnable

Time elapsed before executing the scheduler

Scheduling latency

14 Free Electrons. Kernel, drivers and embedded Linux development, consulting, training and support. http://free­electrons.com

Understanding preemption (1)

The Linux kernel is a preemptive operating system

When a task runs in user­space mode and gets interrupted by an  interruption, if the interrupt handler wakes up another task, this  task can be scheduled as soon as we return from the interrupt  handler.

Task A (running in user mode)

Interrupt handler Wakes up Task B

Task B (running in user mode)

Interrupt

15 Free Electrons. Kernel, drivers and embedded Linux development, consulting, training and support. http://free­electrons.com

Understanding preemption (2)

However, when the interrupt comes while the task is executing a  system call, this system call has to finish before another task can  be scheduled.

By default, the Linux kernel does not do kernel preemption.

This means that the time before which the scheduler will be  called to schedule another task is unbounded.

Task A (user mode)

Interrupt handler Wakes up Task B

Task B (user mode)

System call

Task A (kernel mode)

Task A (kernel mode)

Interrupt

? Return from syscall

16 Free Electrons. Kernel, drivers and embedded Linux development, consulting, training and support. http://free­electrons.com

Scheduler duration

Waiting task

interrupt latency

Interrupt handler Scheduler

Running task

Interrupt

handler duration

scheduler latency

scheduler duration

Makes the task runnable

Time taken to execute the scheduler and switch to the new task.

Scheduling latency

17 Free Electrons. Kernel, drivers and embedded Linux development, consulting, training and support. http://free­electrons.com

Other non­deterministic mechanisms

Outside of the critical path detailed previously, other non­ deterministic mechanisms of Linux can affect the execution time  of real­time tasks

Linux is highly based on virtual memory, as provided by an MMU,  so that memory is allocated on demand. Whenever an application  accesses code or data for the first time, it is loaded on demand,  which can creates huge delays.

Many C library services or kernel services are not designed with  real­time constraints in mind.

18 Free Electrons. Kernel, drivers and embedded Linux development, consulting, training and support. http://free­electrons.com

Priority inversion

Acquires a lock

Priority

Time

preempted

Tries to get the same 

lock waits

A process with a low priority might hold a lock needed by a higher  priority process, effectively reducing the priority of this process.  Things can be even worse if a middle priority process uses the CPU.

19 Free Electrons. Kernel, drivers and embedded Linux development, consulting, training and support. http://free­electrons.com

Interrupt handler priority

top priority task

Any interrupt

top priority task

Any interrupt...

In Linux, interrupt handlers are executed directly by the CPU  interrupt mechanisms, and not under control of the Linux  scheduler. Therefore, all interrupt handlers have an higher  priority than all tasks running on the system.

20 Free Electrons. Kernel, drivers and embedded Linux development, consulting, training and support. http://free­electrons.com

The PREEMPT_RT project

Long­term project lead by Linux kernel developers Ingo Molnar,  Thomas Gleixner and Steven Rostedt

https://rt.wiki.kernel.org

The goal is to gradually improve the Linux kernel regarding real­ time requirements and to get these improvements merged into  the mainline kernel

PREEMPT_RT development works very closely with the mainline  development

Many of the improvements designed, developed and debugged  inside PREEMPT_RT over the years are now part of the mainline  Linux kernel

The project is a long­term branch of the Linux kernel that ultimately  should disappear as everything will have been merged

21 Free Electrons. Kernel, drivers and embedded Linux development, consulting, training and support. http://free­electrons.com

Improvements in the mainline kernel

Coming from the  PREEMPT_RT project

Since the beginning of 2.6

O(1) scheduler

Kernel preemption

Better POSIX real­time API  support

Since 2.6.18

Priority inheritance support  for mutexes

Since 2.6.21

High­resolution timers

Since 2.6.30

Threaded interrupts

Since 2.6.33

Spinlock annotations

22 Free Electrons. Kernel, drivers and embedded Linux development, consulting, training and support. http://free­electrons.com

New preemption options in Linux 2.6

2 new preemption models offered by standard Linux 2.6:

23 Free Electrons. Kernel, drivers and embedded Linux development, consulting, training and support. http://free­electrons.com

1st option: no forced preemption

CONFIG_PREEMPT_NONE Kernel code (interrupts, exceptions, system calls) never preempted. Default behavior in standard kernels.

Best for systems making intense computations, on which overall throughput is key.

Best to reduce task switching to maximize CPU and cache usage (by reducing context switching).

Still benefits from some Linux 2.6 improvements: O(1) scheduler, increased multiprocessor safety (work on RT  preemption was useful to identify hard to find SMP bugs).

Can also benefit from a lower timer frequency (100 Hz instead of 250 or 1000).

24 Free Electrons. Kernel, drivers and embedded Linux development, consulting, training and support. http://free­electrons.com

2nd option: voluntary kernel preemption

CONFIG_PREEMPT_VOLUNTARY Kernel code can preempt itself

Typically for desktop systems, for quicker application reaction to  user input.

Adds explicit rescheduling points throughout kernel code.

Minor impact on throughput.

25 Free Electrons. Kernel, drivers and embedded Linux development, consulting, training and support. http://free­electrons.com

3rd option: preemptible kernel

CONFIG_PREEMPT Most kernel code can be involuntarily preempted at any time. When a process becomes runnable, no more need to wait for  kernel code (typically a system call) to return before running the  scheduler.

Exception: kernel critical sections (holding spinlocks), but a  rescheduling point occurs when exiting the outer critical section, in case a preemption opportunity would have been signaled while in the critical section.

Typically for desktop or embedded systems with latency  requirements in the milliseconds range.

Still a relatively minor impact on throughput.

26 Free Electrons. Kernel, drivers and embedded Linux development, consulting, training and support. http://free­electrons.com

Priority inheritance

One classical solution to the priority inversion problem is called  priority inheritance

The idea is that when a task of a low priority holds a lock requested  by an higher priority task, the priority of the first task gets temporarly  raised to the priority of the second task : it has inherited its priority.

In Linux, since 2.6.18, mutexes support priority inheritance

In userspace, priority inheritance must be explictly enabled on a  per­mutex basis.

27 Free Electrons. Kernel, drivers and embedded Linux development, consulting, training and support. http://free­electrons.com

High resolution timers

The resolution of the timers used to be bound to the resolution of  the regular system tick

Usually 100 Hz or 250 Hz, depending on the architecture and the  configuration

A resolution of only 10 ms or 4 ms.

Increasing the regular system tick frequency is not an option as it  would consume too much resources

The high­resolution timers infrastructure, merged in 2.6.21,  allows to use the available hardware timers to program interrupts  at the right moment.

Hardware timers are multiplexed, so that a single hardware timer is  sufficient to handle a large number of software­programmed timers.

Usable directly from user­space using the usual timer APIs

28 Free Electrons. Kernel, drivers and embedded Linux development, consulting, training and support. http://free­electrons.com

Threaded interrupts

To solve the interrupt inversion problem, PREEMPT_RT has  introduced the concept of threaded interrupts

The interrupt handlers run in normal kernel threads, so that the  priorities of the different interrupt handlers can be configured

The real interrupt handler, as executed by the CPU, is only in  charge of masking the interrupt and waking­up the corresponding  thread

The idea of threaded interrupts also allows to use sleeping  spinlocks (see later)

Merged since 2.6.30, the conversion of interrupt handlers to  threaded interrupts is not automatic : drivers must be modified

In PREEMPT_RT, all interrupt handlers are switched to threaded  interrupts

29 Free Electrons. Kernel, drivers and embedded Linux development, consulting, training and support. http://free­electrons.com

PREEMPT_RT specifics

30 Free Electrons. Kernel, drivers and embedded Linux development, consulting, training and support. http://free­electrons.com

CONFIG_PREEMPT_RT (1)

The PREEMPT_RT patch adds a new « level » of preemption,  called CONFIG_PREEMPT_RT

This level of preemption replaces all kernel spinlocks by mutexes  (or so­called sleeping spinlocks)

Instead of providing mutual exclusion by disabling interrupts and  preemption, they are just normal locks : when contention happens,  the process is blocked and another one is selected by the scheduler

Works well with threaded interrupts, since threads can block, while  usual interrupt handlers could not

Some core, carefully controlled, kernel spinlocks remain as normal  spinlocks

31 Free Electrons. Kernel, drivers and embedded Linux development, consulting, training and support. http://free­electrons.com

CONFIG_PREEMPT_RT (2)

With CONFIG_PREEMPT_RT, virtually all kernel code becomes  preemptible

An interrupt can occur at any time, when returning from the interrupt  handler, the woken up process can start immediately

This is the last big part of PREEMPT_RT that isn't fully in the  mainline kernel yet

Part of it has been merged in 2.6.33 : the spinlock annotations. The  spinlocks that must remain as spinning spinlocks are now  differentiated from spinlocks that can be converted to sleeping  spinlocks. This has reduced a lot the PREEMPT_RT patch size !

32 Free Electrons. Kernel, drivers and embedded Linux development, consulting, training and support. http://free­electrons.com

Threaded interrupts

The mechanism of threaded interrupts in PREEMPT_RT is still  different from the one merged in mainline

In PREEMPT_RT, all interrupt handlers are unconditionally  converted to threaded interrupts.

This is a temporary solution, until interesting drivers in mainline  get gradually converted to the new threaded interrupt API that  has been merged in 2.6.30.

33 Free Electrons. Kernel, drivers and embedded Linux development, consulting, training and support. http://free­electrons.com

Setting up PREEMPT_RT

34 Free Electrons. Kernel, drivers and embedded Linux development, consulting, training and support. http://free­electrons.com

PREEMPT_RT setup (1)

PREEMPT_RT is delivered as a patch against the mainline  kernel

Best to have a board supported by the mainline kernel, otherwise  the PREEMPT_RT patch may not apply and may require some  adaptations

Many official kernel releases are supported, but not all. For  example, 2.6.31 and 2.6.33 are supported, but not 2.6.32.

Quick set up

Download and extract mainline kernel

Download the corresponding PREEMPT_RT patch

Apply it to the mainline kernel tree

35 Free Electrons. Kernel, drivers and embedded Linux development, consulting, training and support. http://free­electrons.com

PREEMPT_RT setup (2)

In the kernel configuration, be sure to enable

CONFIG_PREEMPT_RT

High­resolution timers

Compile your kernel, and boot

You are now running the real­time Linux kernel

Of course, some system configuration remains to be done, in  particular setting appropriate priorities to the interrupt threads,  which depend on your application.