The lowdown on Embedded Linux and its use in real-time applications: Part 1 - Embedded.com

The lowdown on Embedded Linux and its use in real-time applications: Part 1

When Linux began life on an Intel i386 processor, noone ever expected the success Linux would enjoy in server applications.That success has led to Linux being ported to many differentarchitectures and used by developers for embedded systems from cellularhandsets to telecommunications switches. Not long ago, if yourapplication had real-time requirements, you might not have includedLinux among the choices for your operating system. That has all changedwith the developments in real-time Linux driven, in large part, byaudio and multimedia applications.

In this two part series, we start with a brief lookat the historical development of real-time Linux features. Then we lookat the facilities available to the real-time programmer and how thesefacilities are used.

What Is Real Time?
Ask five people what “real time” means, and, chances are, you will getfive different answers. Some might even cite some numbers. For thepurposes of the discussion to follow, we discuss some scenarios andthen propose a definition. Many requirements might be said to be softreal time, while others are called hard real time.

Soft Real Time
Most agree that soft real time means that the operation has a deadline,but if the deadline is missed, the quality of the experience could bediminished (but not fatal). Your desktop workstation is a perfectexample of soft real-time requirements. When you are editing adocument, you expect to see the results of your keystrokes immediatelyon the screen. When playing your favorite .mp3 file, you expect to havehigh-quality audio without any clicks, pops, or gaps in the music.

In general terms, humans cannot see or hear delaysbelow a few tens of milliseconds. Of course, the musicians in the crowdwill tell you that music can be colored by delays smallerthan that. If a deadline is missed by these so-called soft real-timeevents, the results may be undesirable, leading to a lower level of”quality” of the experience, but not catastrophic.

Hard Real Time
Hard real time is characterized by the results of a missed deadline. Ina hard real-time system, if a deadline is missed, the results are oftencatastrophic. Of course, ­catastrophic is a relative term. If yourembedded device is controlling the fuel flow to a jet aircraft engine,missing a deadline to respond to pilot input or a change in operationalcharacteristics can lead to disastrous results.

Note that the duration of the deadline has no bearingon the real-time characteristic. Servicing the tick on an atomic clockis such an example. As long as the tick is processed within the1-second window before the next tick, the data remains valid. Missingthe processing on a tick might throw off our global positioning systemsby feet or even miles!

With this in mind, we draw on a commonly used set ofdefinitions for soft and hard real time. For soft real-time systems,the value of a computation or result is diminished if a deadline ismissed. For hard real-time systems, if a single deadline is missed, thesystem is considered to have failed, and might have catastrophicconsequences.

Linux Scheduling
UNIX and Linux were both designed for fairness in their processscheduling. That is, the scheduler tries its best to allocate availableresources across all processes that need the CPU and guarantee eachprocess that they can make progress. This very design objective iscounter to the requirement for a real-time process. A real-time processmust run as soon as possible after it is ready to run. Real time meanshaving predictable and repeatable latency.

Latency
Real-time processes are often associated with a physical event, such asan interrupt arriving from a peripheral device. Figure 17-1 below illustrates thelatency components in a Linux system. Latency measurement begins uponreceipt of the interrupt we want to process.

This is indicated by time t0 in Figure 17-1. Sometimelater, the interrupt is taken and control is passed to the InterruptService Routine (ISR). This is indicated by time t1. This interruptlatency is almost entirely dictated by the maximum interrupt offtime1—the time spent in a thread of execution that has hardwareinterrupts disabled.

It is considered good design practice to minimize theprocessing done in the ­actual interrupt service routine. Indeed,this execution context is limited in capability (for example, an ISRcannot call a blocking function, one that might sleep), so it isdesirable to simply service the hardware device and leave the dataprocessing to a Linux bottom half, 2 also called softIRQs.

When the ISR/bottom half has finished its processing,the usual case is to wake up a user space process that is waiting forthe data. This is indicated by time t2 in Figure 17-1 below . At some point intime later, the real-time process is selected by the scheduler to runand is given the CPU. This is indicated by time t3 in Figure 17-1.Scheduling latency is affected primarily by the number of processeswaiting for the CPU and the priorities among them.

Setting the Real Time attribute on a process gives ithigher priority over normal Linux processes and allows it to be thenext process selected to run, assuming that it is the highest priorityreal-time process waiting for the CPU. The highest-priority real-timeprocess that is ready to run (not blocked on I/O) will always run.You'll see how to set this attribute shortly.

Figure17-1. Latency components

Kernel Preemption
In the early Linux days of Linux 1.x, there was no kernel preemption.This meant that when a user space process requested kernel services, noother task could be scheduled to run until that process either blocked(goes to sleep) waiting on something (usually I/O), or until the kernelrequest is completed. Making the kernel ­preemptable3 means thatwhile one process is running in the kernel, another process can preemptthe first and be allowed to run even though the first process had notcompleted its in-kernel processing. Figure 17-2 illustrates this.

In this figure, Process A has entered the kernel viaa system call. Perhaps it was a call to write() to a device such as theconsole or a file. While executing in the kernel on behalf of ProcessA, Process B with higher priority is woken up by an interrupt. Thekernel preempts Process A and assigns the CPU to Process B,even though Process A had neither blocked nor completed its kernelprocessing.

Figure17-2. Kernel preemption

Impediments toPreemption

The challenge in making the kernel fully preemptableis to identify all the places in the kernel that must be protected frompreemption. These are the critical sections within the kernelwhere preemption cannot be allowed to occur.

For example, assume that Process A in Figure 17-2 above is executing inthe kernel performing a file system operation. At some point, the codemight need to write to an in-kernel data structure representing a fileon the file system. To protect that data structure from corruption, theprocess must lock out all other processes from accessing the shareddata structure. Listing 17-1 below illustratesthis concept using C syntax.

Listing 17-1
Locking Critical Sections

  preempt_disable();
  …
  /* Critical section */
  update_shared_data();
  …
  preempt_enable();

If we did not protect shared data in this fashion,the process updating the shared data structure could be preempted inthe middle of the update. If another process attempted to update thesame shared data, corruption of the data would be vir­tuallycertain. The classic example is when two processes are operatingdirectly on ­common variables and making decisions on their values.Figure 17-3 illustrates such a case.

In Figure 17-3 below ,Process A is interrupted after updating the shared data but before itmakes a decision based on it. By design, Process A cannot detect thatit has been preempted. Process B changes the value of the shared databefore Process A gets to run again.

As you can see, Process A will be making a decisionbased on a value determined by Process B. If this is not the behavioryou seek, you must disable ­preemption in Process A around theshared data—in this case, the operation and decision on the variablecount.

Figure17-3. Shared data currency error

Preemption Models
The first solution to kernel preemption was to place checks atstrategic locations within the kernel code where it was known to besafe to preempt the current thread of execution. These locationsincluded entry and exit to system calls, release of certain kernellocks, and return from interrupt processing. At each of these points,code similar to Listing 17-2 below was used to perform preemption.

Listing 17-2
Check for Preemption a la Linux 2.4 + Preempt Patch

  /*
   * This code is executed at strategic locations within
   * the Linux kernel where it is known to be safe to
   * preempt the current thread of execution
   */
  if (kernel_is_preemptable() && current->need_resched)
    preempt_schedule();

  /*
   * This code is in …/kernel/sched.c and is
   * invoked from those strategic locations as
above
   */
  #ifdef CONFIG_PREEMPT
  asmlinkage void preempt_schedule(void)
  {
      while (current->need_resched) {
          ctx_sw_off();
          current->state |= TASK_PREEMPTED;
           schedule();
          current->state &= ~TASK_PREEMPTED;
          ctx_sw_on_no_preempt();
      }
  }
  #endif

The first snippet of code in Listing 17-2 (simplified from the actual cod e) isinvoked at those strategic locations described earlier, where it isknown that the kernel is safe to preempt. The second snippet of code inListing 17-2 above is theactual code from an early Linux 2.4 kernel with the preempt patchapplied. This interesting while loop causes a context switch via thecall to schedule() until all requests for preemption have beensatisfied.
Although this approach led to reduced latencies in the Linux system, itwas not ideal. The developers working on low-latency soon realized theneed to “flip the logic.” With earlier preemption models, we had this:

       The Linux kernel wasfundamentally nonpreemptable.
       Preemption checks were sprinkledaround the kernel at strategic locations known to be safe forpreemption.
       Preemption was enabled only at theseknown-safe points.

To achieve a further significant reduction inlatency, we want this in a preemptable kernel:
       The Linux kernel is fully preemptableeverywhere.
       Preemption is disabled only aroundcritical sections.

This is where the kernel developers have been headingsince the original preemptable kernel patch series. However, this is noeasy task. It involves poring over the entire kernel source code base,analyzing exactly what data must be protected from concurrency, anddisabling preemption at only those locations.

The method used for this has been to instrument thekernel for latency measurements, find the longest latency code paths,and fix them. The more recent Linux 2.6 kernels can be configured forvery low-latency applications because of the effort that has gone intothis “lock-breaking” methodology.

SMP Kernel
It is interesting to note that much of the work involved in creating anefficient multiprocessor architecture also benefits real time. The SMPchallenge is more complex than the uniprocessor challenge because thereis an additional element of concurrency to protect against.

In the uniprocessor model, only a single task can be­executing in the kernel at a time. Protection from concurrencyinvolves only ­protection from interrupt or exception processing.In the SMP model, multiple threads of execution in the kernel arepossible in addition to the threat from interrupt and exceptionprocessing.

SMP has been supported from early Linux 2.x kernels.A Big Kernel Lock (BKL) was used to protect againstconcurrency in the transition from uniprocessor to SMP operation. TheBKL is a global spinlock, which prevents any other tasks from executingin the kernel.

In his excellent book Linux Kernel Development(Novell Press, 2005) , Robert Love characterized the BKL as the”redheaded stepchild of the ­kernel.” In describing thecharacteristics of the BKL, Robert jokingly added “evil” to its list ofattributes!

Early implementations of the SMP kernel based on theBKL led to significant inefficiencies in scheduling. It was found thatone of the CPUs could be kept idle for long periods of time. Much ofthe work that led to an efficient SMP kernel also directly benefitedreal-time applications—primarily lowered latency. Replacing the BKLwith smaller-grained locking surrounding only the actual shared data tobe protected led to significantly reduced preemption latency.

Sources of Preemption Latency
A real-time system must be capable of servicing its real-time taskswithin a specified upper boundary of time. Achieving consistently lowpreemption latency is critical to a real-time system. The two singlelargest contributors to preemption latency are interrupt-contextprocessing and critical section processing where interrupts aredisabled.

You have already learned that a great deal of efforthas been targeted at reducing the size (and thus, duration) of thecritical sections. This leaves interrupt-­context processing as thenext challenge. This was answered with the Linux 2.6 real-time kernelpatch, the subject of the second part in this series.

Next in Part 2, “TheLinux 2.6 real-time kernel patch.”

ChristopherHallinan, field applications engineer at MontaVista Softwware, has worked formore than 20 years in assisgnments ranging from engineering andengineering management to marketing and busisness development. He spentfour years as an independent development consultant in the embeddedLinux marketplace.

This chapter is excerptedfrom the book titled “Embedded LinuxPrimer: A Practical Real-WorldApproach“, by Christopher Hallinan .Publishedby Prentice Hall Professional, as part of the PrenticeHall Open SourceSoftware Development SeriesISBN 0131679848; Copyright 2007 Pearson Education, Inc.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.