Time Sensitive Linux

Summary

• Sources of Latency
• Timers Available
• Firm Timer Design
• Firm Timer Implementation
  • Reducing Kernel Preemption Latency

Sources of Latency

• Timer latency
  • Lag between timer event and interrupt
• Preemption latency
  • Time between interrupt and kernel handing control to handler
• Scheduler latency
  • Priority queues

Timers Available

Firm Timer Design

Accurate timing with low overhead

• Combine one-shot and soft timers
• Overshoot: knob between hard and soft
  • Allow for soft-timer expiration before hard interrupt

Firm Timer Implementation

Timer-q data structure

• Linked List sorted by expiry-time

APIC Hardware

• Advanced Programmable Interrupt Controller
• Reprogramming: few cycles
• Counter decrements at each memory-bus cycle
• Eliminates need for fielding oneshot int

Long oneshot distance means dispatch oneshot and next periodic timer

Reducing Kernel Preemption Latency

Approaches:

• Explicit insertion of preemption points in kernel
• Allow preemption anytime kernel is not manipulating shared data structures

Lock-Breaking Preemptible kernel combines both approaches

• Change long critical sections into multiple shorter critical sections with explicit preemption points

Proportional Period Scheduling

• If one task request 2/3 proportion of time quantum, then a second task also requests 2/3, the second gets delayed until the next quantum

Priority Inversion

• If a high priority client blocks on a low priority server, and a medium priority client comes in, it can preempt the low priority server which delays the higher priority task.
• If a client blocks on a server, the server will upgrade its priority to match the caller