What Makes a Kernel/Os Real-Time

What makes a kernel/OS real-time?

After doing some research, talking to poeple (Jamie Hanrahan, Juha Aaltonen @linkedIn Group - Device Driver Experts) and ofcourse the input from @Jim Garrison, this what I can conclude:

In Jamie Hanrahan's words-

What makes a kernel real time?

The sine qua non of a real time OS -

• The ability to guarantee a maximum latency between an external interrupt and the start of the interrupt handler.

  Note that the maximum latency need not be particularly short (e.g. microseconds), you could have a real time OS that guaranteed an absolute maximum latency of 137 milliseconds.

• A real time scheduler is one that offers completely predictable (to the developer) behavior of thread scheduling - "which thread runs next".

  This is generally separate from the issue of a guaranteed maximum latency to responding to an interrupt (since interrupt handlers are not necessarily scheduled like ordinary threads) but it is often necessary to implement a real-time application. Schedulers in real-time OSs generally implement a large number of priority levels. And they almost always implement priority inheritance, to avoid priority inversion situations.

So, it is good to have a guaranteed latency for an interrupt and predictability of thread scheduling, then why not make every OS real time?

• Because an OS suited for general purpose use (servers and/or desktops) needs to have characteristics that are generally at odds with real-time latency guarantees.

  For example, a real-time scheduler should have completely predictable behavior. That means, among other things, that whatever priorities have been assigned to the various tasks by the developer should be left alone by the OS. This might mean that some low-priority tasks end up being starved for long periods of time. But the RT OS has to shrug and say "that's what the dev wanted." Note that to get the correct behavior, the RT system developer has to worry a lot about things like task priorities and CPU affinities.

  A general-purpose OS is just the opposite. You want to be able to just throw apps and services on it, almost always things written by many different vendors (instead of being one tightly integrated system as in most R-T systems), and get good performance. Perhaps not the absolute best possible performance, but good.

  Note that "good performance" is not just measured in interrupt latency. In particular, you want CPU and other resource allocations that are often described as "fair", without the user or admin or even the app developers having to worry much if at all about things like thread priorities and CPU affinities and NUMA nodes. One job might be more important than another, but in a general-purpose OS, that doesn't mean that the second job should get no resources at all.

  So the general purpose OS will usually implement time-slicing among threads of equal priority, and it may adjust the priorities of threads according to their past behavior (e.g. a CPU hog might have its priority reduced; an I/O bound thread might have its priority increased, so it can keep the I/O devices working; a CPU-starved thread might have its priority boosted so it can get a little bit of CPU time now and then).

Can a kernel be called real time just because it has a real time scheduler?

• No, an RT scheduler is a necessary component of an RT OS, but you also need predictable behavior in other parts of the OS.

Does it require any support from the hardware?

• In general, the simpler the hardware the more predictable its behavior is. So PCI-E is less predictable than PCI, and PCI is less predictable than ISA, etc. There are specific I/O buses that were designed for (among other things) easy predictability of e.g. interrupt latency, but a lot of R-T requirements can be met these days with commodity hardware.

Real time kernel vs real time OS

There are a variety of opinions on that question. One, held by systems programmers and the like, is that an OS kernel is a minimal set of services to abstract the underlying computer hardware, making it easier to write an OS or even applications on the machine. OS kernels typically operate in their own space, separate from user space where the rest of the OS (or even applications) reside. There is also the concept of a microkernel (and nanokernel), which is intended specifically to serve higher level (e.g., user space) OS services--although different microkernels partition OS services differently in kernel vs. user space. Check Wikipedia as a start (although some of its related entries have some factual errors).

Sometimes the embedded computing community refers to a kernel as a minimal OS, expecting applications, not more OS functionality, to use the kernel.

This may seem like an insignificant distinction, but it does effect the design and implementation of the kernel.

Do you need a realtime operating system in order to ensure your program is never taken off the CPU?

Do you need to act on sensor readings in a constant time frame? How complicated this action should be? If all you need is to never miss a reading and you're ok with buffering them - just add a microcontroller or an FPGA in between your non-realtime device and a sensor.

Also, you can ensure some soft real time constraints even with an unpatched Linux. You can pin a process to a CPU and avoid using any syscalls in it - spin and poll instead, at 100% CPU utilisation, and then it's likely kernel will never touch it. Make sure the process binary and all the dynamic libraries (if any) are on a RAM disk (to avoid paging) and disable swap.

What are the best ways to do close to real-time tasks on a non real-time OS/kernel?

The sched_setscheduler(2) and friends allow you to use two different soft real-time schedulers, SCHED_FIFO SCHED_RR. Processes running under these schedulers are prioritised higher than regular processes. So as long as you only have a few of theses processes, and control the priorities between them, you can actually get pretty descent real-time responses.

As requested in a comment, here is the difference between SCHED_FIFO and SCHED_RR:

With the "real-time" schedulers, there are up to 100 different priorities (POSIX only requires 32 distinct levels, so one should use sched_get_priority_min(2) and sched_get_priority_max(2) to get the actual number. The schedulers both work by preempting processes and threads with lower priority, the difference is in how they handle tasks with the same priority.

SCHED_FIFO, is a first in first out scheduler (hence the name). This means that the task that hits the run queue first, is allowed to run until it is done, voluntarily gives up its space on the run queue, or is preempted by a higher priority task.

SCHED_RR, is a round robin scheduler. This means that tasks with the same priority are only allowed to run for a certain time quantum. If the task is still running when this time quantum runs out the task is preempted, and the next task in the run queue (with same priority) is allowed to run for up to its time quantum. As with SCHED_FIFO, higher priority tasks preempt lower priority ones, how ever, when a task which was preempted by a higher priority task is allowed to run again, then it's only allowed to run for the time left in its quantum. See the Noes-section in sched_rr_get_interval(2) for how to set the time quantum for a task.

Why isn't every OS real-time?

RTOS typically trade throughput performance and features for predictability and tractability. The usual definition of "real-time" folks apply is "deterministic"; you can't have determinism without paying for it.

In general purpose OS'es, we're motivated by "common-case" behaviors -- we want really good average performance, and a lot of flexibility. In RTOS, we want a reliable ceiling on "worst case" behaviors, and we pay (often dearly) in throughput or common-case behaviors.

Yes, it's possible to create hybrids, like Windows or even Linux real-time threads. But somewhere you're typically paying a penalty because ultimately there is only the finite set of resources available (CPUs, IO bandwidth, whatever) and consumer OS'es and RTOS'es optimize around different criteria. Some of the RT Linux approaches deal with this explicitly, by having partitions. Different assumptions and different optimality criteria are optimized for in each partition.

What features are traded? I can't offer a precise list -- it's more that general-purpose OS'es tend to have a zillion drivers, and be able to keep up with the churn of new devices; RTOS tend to focus on a much smaller set for which timeliness can be either well-understood or explicitly kept from interfering with other activities. You probably won't have the same selection of drivers on a normal RTOS because it's not reasonable to implement them, typically.

Throughput Remember "real-time" != "real-fast". When a system is real-time, it means that activities' time of completion is part of their correctness. In some cases, this means processing many activities very quickly (high throughput); in others it may be processing at a relatively slow but extremely predictable period. The structures in an RTOS may have high throughput, but typically can't achieve the throughput of an equivalent RTOS because the techniques used to achieve that throughput fairly (caching, fancy interactivity-driven scheduling approaches, "fair" queuing and lock contention) militate against predictability of any single task's timeliness.

Am I Really Using A Real-Time Kernel?

To see whether the currently running kernel has the RT_PREEMPT patch, use uname and look for PREEMPT and RT:

ubuntu10:~$ uname -a
Linux ubuntu10 2.6.31-11-rt #154-Ubuntu SMP PREEMPT RT Wed Jun 9 12:28:53 UTC 2010 i686 GNU/Linux

If you are asking for evidence or proof of RT_PREEMPT's real-time performance, search the Internet, there are a lot of options. Here is one place to start: http://elinux.org/Realtime_Testing_Best_Practices

How do Real Time Operating Systems work?

Meeting deadlines is a function of the application you write. The RTOS simply provides facilities that help you with meeting deadlines. You could also program on "bare metal" (w/o a RTOS) in a big main loop and meet you deadlines.

Also keep in mind that unlike a more general purpose OS, an RTOS has a very limited set of tasks and processes running.

Some of the facilities an RTOS provide:

• Priority-based Scheduler
• System Clock interrupt routine
• Deterministic behavior

Priority-based Scheduler

Most RTOS have between 32 and 256 possible priorities for individual tasks/processes. The scheduler will run the task with the highest priority. When a running task gives up the CPU, the next highest priority task runs, and so on...

The highest priority task in the system will have the CPU until:

• it runs to completion (i.e. it voluntarily give up the CPU)
• a higher priority task is made ready, in which case the original task is pre-empted by the new (higher priority) task.

As a developer, it is your job to assign the task priorities such that your deadlines will be met.

System Clock Interrupt routines

The RTOS will typically provide some sort of system clock (anywhere from 500 uS to 100ms) that allows you to perform time-sensitive operations.
If you have a 1ms system clock, and you need to do a task every 50ms, there is usually an API that allows you to say "In 50ms, wake me up". At that point, the task would be sleeping until the RTOS wakes it up.

Note that just being woken up does not insure you will run exactly at that time. It depends on the priority. If a task with a higher priority is currently running, you could be delayed.

Deterministic Behavior

The RTOS goes to great length to ensure that whether you have 10 tasks, or 100 tasks, it does not take any longer to switch context, determine what the next highest priority task is, etc...

In general, the RTOS operation tries to be O(1).

One of the prime areas for deterministic behavior in an RTOS is the interrupt handling. When an interrupt line is signaled, the RTOS immediately switches to the correct Interrupt Service Routine and handles the interrupt without delay (regardless of the priority of any task currently running).

Note that most hardware-specific ISRs would be written by the developers on the project. The RTOS might already provide ISRs for serial ports, system clock, maybe networking hardware but anything specialized (pacemaker signals, actuators, etc...) would not be part of the RTOS.

This is a gross generalization and as with everything else, there is a large variety of RTOS implementations. Some RTOS do things differently, but the description above should be applicable to a large portion of existing RTOSes.

---

Related Topics