Real time Linux systems terminology and concepts

Real Time

A Linux system is real time when timeliness is a dimension of correctness; that means a correct answer delivered late is the same as an answer that has never been delivered. Real-time systems abound in the real world. To a degree, all systems are real time, because they have real-world deadlines: an airline ticketing program needs to issue tickets before the plane leaves, for example. Meeting deadlines is one aspect of real-time systems; the other is that the system behaves in a predictable manner. If the aforementioned airline reservation system issues tickets within 24 hours and does so for every ticketing request, the system can be considered real time. Real-time Linux systems that can tolerate missing an occasional deadline, with a reduction in performance or quality of output, are known as soft real-time systems. In the ticketing program, missing a deadline results in some lost revenue and probably a dissatisfied customer, but that is the extent of the damage. Most real-time systems fall into the soft category: a video decoder that doesn't produce new frames fast enough occasionally has a display that flickers now and then; most viewers never notice the missed deadline. On a hard real-time system, a missed deadline has serious consequences: when a deadline is missed, a saw may cut at the wrong angle; or a flow-control valve may not close, resulting in flooding. Many safety-critical hard real-time systems, like those in avionics and health devices, can't tolerate the uncertainty of missing a deadline to the point that no operating system is used and the problem of resource contention is solved by having only one thread of execution.

In a multiprocess system (one that runs several programs), such as Linux, the system's deadlines must be met, or missed infrequently in the case of a soft real-time system, no matter what other processes are running. Furthermore, a real-time system must also efficiently share system resources, so that any one process doesn't miss a deadline because it's waiting for a resource being used by another process. In any system, limited resources must be allocated and shared in such a way that that the deadlines can be met. The most obvious resource is the processor itself, which can only perform a limited amount of instructions per clock cycle; but there are other resources like the memory in the system (for heap allocations) and data structures that need to be read and written to in a structured manner. In order to meet deadlines, real-time systems must have methods for multiple threads of execution contending for the same resource.

Real-Time Core Concepts

Real time has some specific terminology and concepts. Taking time to understand these concepts can help you understand not only the real-time technologies that Linux offers but also what a real-time system is and how you can use it. These terms are probably familiar, but not in the context of real-time systems. They're frequently misused because real time is thought of as a high-throughput or quick-responsiveness technology, rather than one focusing on predictability. In addition, many of the projects/conversations you'll encounter in Linux focusing on real time use these terms without explicit definition.

Deadline

A deadline is a point in time at which some action must occur. Deadlines are very important for a realtime system, because the ability to regularly meet a deadline is the defining characteristic of such a system. In a hard real-time system, every deadline must be met every time; work completed after the deadline has no value. In a soft real-time system, work can be completed late on occasion, but the system's performance suffers. In a soft real-time system, it's assumed that a deadline will be missed: the question is the frequency and magnitude.

Latency

Latency is the time between when something should happen and when it does. Latency appears throughout real-time systems: scheduling latency, interrupt latency, deadline latency, and timer latency are common examples. In an ideal system, latency would be zero; but in reality, the computer needs time because of hardware signaling or software that needs to run. For example, interrupt latency involves hardware in that the pins signaling an interrupt are attached to a part of the processor that indicates that the interrupt has been triggered, which then runs software in response to the event. Although this all happens quickly, it still takes some time, and that time is latency.

Jitter

When latency varies, that variance is jitter. In the previous example, the time between the raising of the interrupt and when the software runs that recognizes the interrupt isn't constant. All systems have some degree of jitter-it's a degree of chaos that results in the same actions taking a different amount of time to complete. In an ideal real-time system, the jitter is zero, meaning deadlines are always met with a predefined amount of latency. On a system running many processes, jitter occurs when a process must wait for a resource that another process is using. Because a system's thread scheduling is nondeterministic, the wait for resources is different each time the thread runs.

Predictability

Predictability means knowing in advance how long an operation will require and having the operation take the required amount of time to complete. An ideal system with zero latency and jitter could be completely predictable if the code performed a repeatable process. A perfect, hard real-time system is completely predictable. In the real world, a little jitter predictability is always included within the bounds of the worst case.

Worst Case

Because all systems have some degree of latency and jitter, the question becomes the degree of jitter and latency. For a real-time system, the key is predictability; by budgeting for the worst-possible scenario, the system can operate in a predictable manner. When you use the worst case, you plan that some operation will take its normal execution time plus the worst amount of jitter possible.

Priority Inversion

Priority inversion is used as both a noun and an adjective. As a noun, priority inversion happens when a lower-priority task holds a lock on a resource that a higher-priority task needs at the same time, thus keeping the higher-priority task from executing. The duration of time that the higher priority-task waits is the adjective. Priority inversions can't be avoided, but real-time systems minimize their duration. Non-real-time systems suffer from unbounded priority inversions, where the operating system makes no attempt to detect and advertise priority inversions through priority inheritance. Priority inheritance means a lower-priority task is allowed to run at a higher priority when a higher-priority task is waiting for a lock that's being held by the lower priority task.

Periodic Task

A periodic task is one that needs to execute at regular intervals, where the interval is the same for the entire life of the task. A classic example of a periodic task is the second hand of a clock, which must more or less than 60 seconds to sweep the dial, resulting in the clock gaining or losing time. If the soft real-time clock on your nightstand suffers from this effect, the result may be you missing your regular train to work; in a hard real-time system, an inaccurate clock could result in a transportation emergency.

The Linux Scheduler

Much effort has been put into making sure the processor resource is allocated properly. In Linux, the code that decides how the processor is used is the scheduler. Understanding how the scheduler works is important for understanding the real-time capabilities of the Linux kernel. The default scheduler used on a desktop system is the Completely Fair Scheduler, which isn't real time by design. The Completely Fair Scheduler (CFS) works by evenly allocating the amount of time available for processing among the processes that could be run. When tasks aren't running, each builds up a CPU allocation debt proportional to the number of tasks waiting. When the currently running task pays back its CPU allocation debt, it goes to the back of the line and begins building a CPU debt again. The task with the highest time debt is then pulled from the list of possible tasks and run. There is some tuning for priority, in which case the debt accumulates faster, thus resulting in the task accumulating the highest CPU debt more quickly. When the CFS is running on a system with several CPUs, it attempts to keep a process running on a single processor but allocates tasks across processors so that each is kept as busy as possible. There is no guarantee or expectation that a task will remain running on the same processor in a multiprocessor system.

Group Scheduling

The CFS uses group scheduling. Processes in a group are treated as one scheduling entity when calculating the CPU time debt. Suppose a system has ten processes running, where eight are in one group and two are ungrouped. This system has three entities accumulating CPU time debts: two independent tasks and one group of eight tasks. The CPU's time is roughly divided by three, with the time for the group of eight divided across the tasks in priority order. Group scheduling allows a system to reserve some minimum time for core processes no matter what else is running on the system. For instance, the group of tasks running the user interface may be allocated a certain amount of time so that you can still interact with the system even if many other tasks are running.

Real-Time Scheduler

The CFS seems appealing-who doesn't want to be fair, especially if you can do so completely? For a real-time system, unfairness is the order of the day, because a task that must perform predictably needs scheduling preference over regular tasks. In order to work properly, the real-time scheduler must know what to run and must allocate the necessary amount of time to processes that have a deadline or that need to continue running if the process still has work to do. The scheduler has two different ways of scheduling tasks:

First In First Out (FIFO): FIFO scheduling is very simple. When a task becomes runnable, it interrupts any other tasks with a lower priority and continues to run until the process waits on IO (like the disk or network device) or voluntarily yields to another process. FIFO scheduling can result in a system where just a few tasks are run, because a few tasks with a high enough priority can effectively consume most of the available time.
Round Robin (RR): RR scheduling is similar to FIFO scheduling, except that tasks run for a fixed amount of time before they're automatically moved to the back of the line. Like the FIFO scheduling method, RR scheduling can result in a few tasks running most of the time, starving other processes for execution time. For a realtime system, this starvation may be exactly what's necessary to ensure predictability.

Neither of these scheduling methods are inherently real time. The unpredictability of FIFO scheduling arises when a task doesn't properly yield, thus keeping some other task from running. On the other hand, if the task that doesn't yield is the real-time task, then this process is more predictable. RR scheduling allocates the time evenly across all processes in the system; as additional tasks are added, the amount of time allocated to any one task decreases, reducing the scheduling predictability. The important thing to remember is that the scheduler isn't a panacea that makes code real time. Scheduling has another dimension: the amount of time the system requires to make a scheduling decision, frequently referred to as scheduling latency or context switch time. Ideally, the amount of time required by the scheduler should be constant no matter how many threads are running on the system. All the schedulers in the 2.6 Linux kernel roughly match this description, known as O(1) by folks who have studied computer science.