Time Sensitive Linux
Summary
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
Choice of Timer | Pro | Con |
---|---|---|
Periodic | Periodicity | Event recognition latency |
One-shot | Timely | Overhead |
Soft | Reduce Overhead | Polling overhead, latency, checked on syscalls |
Firm | Combines all of above |
Firm Timer Design
Accurate timing with low overhead
- Combine
one-shot
andsoft
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