Transcript Time Sources and Timing

Time Sources and Timing
David Ferry, Chris Gill
CSE 522S - Advanced Operating Systems
Washington University in St. Louis
St. Louis, MO 63143
1
Questions From Last Time
Q: Why does the kernel create an init
thread at boot instead of using the original
execution context? – Robert
A: The start_kernel execution context in
main.c eventually becomes the main
processor idle loop, a.k.a. the swapper or
sched process.
(Follow the start_kernel function through
to cpu_idle_loop() )
CSE 522S – Advanced Operating Systems
2
Questions From Last Time
Q: Do we really need to issue make clean when rebuilding the
kernel? – John
A: Not always, but probably…
unistd.h
#define NR_SYSCALLS 388
foo.c
foo.o
NR_SYSCALLS = 388
CSE 522S – Advanced Operating Systems
3
Questions From Last Time
Q: Do we really need to issue make clean when rebuilding the
kernel? – John
A: Not always, but probably…
unistd.h
#define NR_SYSCALLS 292
foo.c
bar.c
foo.o
NR_SYSCALLS = 388
bar.o
NR_SYSCALLS = 292
CSE 522S – Advanced Operating Systems
4
What is meant by Time?
Absolute time since some past event, E.g.:
– Seconds since Unix Epoch
– Seconds since system boot
Relative time, E.g.:
– Seconds between two events
– Ten seconds into the future
– Execution time of a program segment
World time, E.g.:
– February 4th, 10:37 AM
An OS must approximate time to provide time-based
functions for users.
CSE 522S – Advanced Operating Systems
5
Time Sources
RTC (Real-Time Clock)
– Available on most computers (not on RPI 2)
– Low precision (as low as 0.5 seconds)
Hardware Timers
–
–
–
–
–
–
Might be used to generate interrupts, might be queryable
Run at a variety of frequencies
Programmable Interval Timer (PIT)
High-Performance Event Timer (HPET)
Programmable Interrupt Controller (PIC)
Advanced Programmable Interrupt Controller (APIC)
Processor Cycles
– Timestamp Counter (TSC) on x86, 64-bit
– Cycle Counter (CCNT) on ARM, 32-bit, 64-cycle divider, not
accessible in user mode
– Potentially very high accuracy
– Can generate interrupts on x86 with TSC-deadline
CSE 522S – Advanced Operating Systems
6
How does the kernel schedule services?
Three approaches:
1. Timer interrupts to regularly provide service
e.g.: task scheduling, current time update
2. Kernel timers (hrtimers, legacy timers)
3. Kernel threads (not time dependent)
A portable OS must use whatever timer
hardware is available to support actions #1
and #2.
CSE 522S – Advanced Operating Systems
7
Basic Timer Interrupt in Linux
Historically the OS would run periodically:
– Fundamental timestep is variable HZ found in
/include/asm-generic/param.h
– OS function tick_periodic() runs each 1/HZ seconds
– jiffies variable tracks number of ticks since boot
– xtime variable tracks wall-clock time
– Current time since boot: jiffies * 1/HZ
– Current wall time: boot_time + jiffies * 1/HZ
– Timers are checked for expiry each tick
As a modern approach:
– Excessive power consumption (can’t really idle processors)
– Inappropriate for highly virtualized systems
– Might be appropriate for real-time systems
CSE 522S – Advanced Operating Systems
8
Modern Timer Interrupt in Linux
Two fundamental operation modes:
– Periodic (CLOCK_EVT_MODE_PERIODIC)
– One-shot (CLOCK_EVT_MODE_ONESHOT)
One-shot mode (CONFIG_NO_HZ):
– All timer events are independent (not periodic)
– Next timer event is scheduled for:
• Next hrtimer expiration
• Next 1/HZ interval, whichever is sooner
• Not rescheduled if no runnable tasks
– jiffies is maintained as though periodic
– Big power savings in idle
CSE 522S – Advanced Operating Systems
9
Problems with legacy time system
Legacy timers could only expire each tick
– Latency problems: with 10ms tick a timeout might be
delivered 9.9ms late
– Resolution problems: with a 10ms tick all we know was
that timeout was 0-9.9ms ago
Legacy timer wheel implementation problems:
– Bad worst case expiration running time (O(N))
– 95-99% of timers never actually expire (e.g. http
timeouts, error checking) but still incur overhead
– Thus, not optimized for “millions of network timers” case
CSE 522S – Advanced Operating Systems
10
hrtimers subsystem
The kernel now provides a high resolution
timing subsystem: hrtimers
– Not bound to jiffies
– Can use multiple time sources
– High resolution (nanosecond representation)
Implementation:
– Per-CPU timer list stored as a sorted red-black tree
for fast expiration
– Separate list for fast removal (no tree walking)
– Expiration handled by dedicated interrupts
CSE 522S – Advanced Operating Systems
11