Understanding Time Management in Operating Systems
Explore the concept of time in computer systems, including absolute and relative time, how the kernel tracks time, real-time clocks, system timers, and timer interrupts. Discover how time is a critical resource utilized by operating systems to provide essential functions for users.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Time Sources and Timing David Ferry, Chris Gill, Brian Kocoloski, Marion Sudvarg CSE 422S - Operating Systems Organization Washington University in St. Louis St. Louis, MO 63143 1
What is meant by Time? to a computer 2 CSE 422S Operating Systems Organization
What is meant by Time? to a computer What time of day is it? ($ date) Wake me up in 5 seconds ($ sleep 5) 3 CSE 422S Operating Systems Organization
What is meant by Time? to a computer What time of day is it? ($ date) Wake me up in 5 seconds ($ sleep 5) Q: is time a resource? Q: or, is time a means with which to share other resources? 4 CSE 422S Operating Systems Organization
What is meant by Time? Absolute time since some fixed past event, e.g.: Seconds since start of the Unix Epoch (00:00:00 UTC on 1 January 1970) Seconds since system boot Relative time, E.g.: Seconds between two events Ten seconds into the future (from now) Execution time of a program segment World time, E.g.: January 30th, 9:00 AM An OS must approximate time to provide time-based functions for users. 5 CSE 422S Operating Systems Organization
How does the kernel keep track of time? Some hardware support Real-time clock: track system time even when machine is off System timer: fires at known periodic intervals Allows the kernel to say to the CPU: stop the currently running process and let me run after some period of time has expired Programs timer interrupts to fire at known points in the future E.g., program the system timer to always interrupt the processor every 10 ms 6 CSE 422S Operating Systems Organization
Timer interrupts ./test CPU core (executing instructions) User space Kernel space Timer (hardware that supports delivery of interrupts) 7 CSE 422S Operating Systems Organization
Timer interrupts ./test ./test CPU core (executing instructions) User space Kernel space Timer (hardware that supports delivery of interrupts) 8 CSE 422S Operating Systems Organization
Timer interrupts ./test ./test Interrupt! CPU core (executing instructions) User space Kernel space Timer (hardware that supports delivery of interrupts) 9 CSE 422S Operating Systems Organization
Timer interrupts ./test ./test Interrupt! CPU core (executing instructions) User space Kernel space Timer Timer interrupt (hardware that supports delivery of interrupts) Interrupt forces the CPU to enter kernel mode where a special function called the timer interrupt will execute 10 CSE 422S Operating Systems Organization
Timer interrupts ./test ./test Interrupt! CPU core (executing instructions) User space Kernel space Timer Timer interrupt (hardware that supports delivery of interrupts) Interrupt forces the CPU to enter kernel mode where a special function called the timer interrupt will execute 11 CSE 422S Operating Systems Organization
Timer interrupts ./test User space Kernel space Timer interrupt Timer interrupt Timer interrupt 12 CSE 422S Operating Systems Organization
Time Sources RTC (Real-Time Clock) Available on most computers (not on RPi 2 or 3 unless you add it) Comparatively low precision (as low as 0.5 seconds) Higher Precision Hardware Timers Might be used to generate interrupts, might be queryable Run at a variety of frequencies Programmable Interval Timer (PIT) High Precision 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- or 64-bit, 64-cycle divider, not accessible in user mode Potentially very high accuracy Can generate interrupts on x86 with TSC-deadline 13 CSE 422S Operating Systems Organization
Questions How can timer interrupts be used to determine an absolute, real-world measurement of time? How can timer interrupts be used to implement arbitrary user timers? (e.g., when user executes sleep(5)) 14 CSE 422S Operating Systems Organization
Timer Tick Rate: HZ The kernel operates on the granularity of timer interrupts Every 1/HZ seconds, stop the currently running process and figure out what to do next (run another process, run kernel-level services, etc.) What should HZ be set to? High HZ = frequent timer interrupts Low HZ = infrequent timer interrupts Tradeoff between high throughput and low latency 15 CSE 422S Operating Systems Organization
Latency vs Throughput Target: low latency, high throughput Throughput Latency 16 CSE 422S Operating Systems Organization
Latency vs Throughput Target: low latency, high throughput . Throughput . 10 HZ . . Latency 17 CSE 422S Operating Systems Organization
Latency vs Throughput Target: low latency, high throughput . Throughput . 10 HZ Where should 100 HZ go? . . Latency 18 CSE 422S Operating Systems Organization
Latency vs Throughput Target: low latency, high throughput . 1 HZ Throughput . 10 HZ . 100 HZ . 1000 HZ Latency 19 CSE 422S Operating Systems Organization
Basic Timer Interrupt in Linux Historically the OS would run periodically: 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 Concerns with this approach: Unnecessary interrupts when only few processes running Excessive power consumption (can t really idle processors) 20 CSE 422S Operating Systems Organization
Modern Timer Interrupt in Linux Two fundamental operating 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 interrupt is programmed for the next timer expiration Not rescheduled if no runnable tasks jiffies is maintained as though periodic Big power savings in idle 21 CSE 422S Operating Systems Organization
Measuring Time in Userspace The timespec struct is declared in <time.h> Stores time info (in seconds and nanoseconds) struct timespec { time_t tv_sec; /* seconds */ long tv_nsec; /* nanoseconds */ }; May need to normalize when adding, subtracting, etc. temp.tv_sec = t2.tv_sec - t1.tv_sec; // ok: monotonically non- decreasing temp.tv_nsec = t2.tv_nsec - t1.tv_nsec; // could give negative value Watch out for overflow (use unsigned long long etc.) 22 CSE 422S Operating Systems Organization
Measuring Time in Kernelspace The ktime_t type is defined in <linux/ktime.h> Nanosecond scalar representation for kernel time values Not a transparent type use library functions ktime_sub(start, end) ktime_to_ns(const ktime_t kt) Can be converted to timespec ktime_to_timespec(kt) CSE 422S Operating Systems Organization 23
Todays Studio You will measure time (and timer resolution) in user space programs You will use ktime functions to measure time in a kernel module You will (optionally) benchmark by reading directly from the Intel x86 Time Stamp Counter CSE 422S Operating Systems Organization 24
C Language Notes const qualifier static qualifier for variable static qualifier for function Other questions? CSE 422S Operating Systems Organization 25
