Latency

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

Linux kernel latency components

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

Interrupt latency

Sources 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 explicitly 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 (not a real problem: mustn't be used for time-critical interrupt-sources anyway).

Interrupt handler duration

Interrupt handler implementation

• In Linux, many interrupt handlers are split in two parts
  • A top-half, started by the CPU as soon as interrupts 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-halves have completed their execution.
• Therefore, for real-time critical interrupts, bottom-halves shouldn't be used: their execution is delayed by all other interrupts in the system.

Scheduler latency

Understanding preemption

• 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.

• 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.

Scheduler duration

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.

Priority inversion

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.

Interrupt handler priority

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 a higher priority than all tasks running on the system.