Copyright (C) 1997 by the University of Kansas Center for Research, Inc. This software was developed by the Information and Telecommunication Technology Center (ITTC) at the University of Kansas. Partial funding for this project was provided by Sprint. This software may be used and distributed according to the terms of the GNU Public License, incorporated herein by reference. Neither ITTC nor Sprint accept any liability whatsoever for this product.
This project was developed under the direction of Dr. Douglas Niehaus.
Please send bug-reports/suggestions/comments to firstname.lastname@example.org
Linux, as well as most other operating systems maintain a sense of time using a periodic interrupt from a timer chip, which is known as the "heartbeat" of the system. The heartbeat of the Linux kernel is 10 ms for the i386 and 1ms for the DEC Alpha. In our efforts to impart real-time characteristics to the Linux kernel, such a coarse-grained timing mechanism was found to be insufficient.
Since we have concentrated on implementing UTIME for the i386, the rest of this document uses terms that are specific to the i386.
One of the ways to increase the temporal granularity of Linux would be to program the timer chip of the PC to interrupt the kernel at higher frequencies. This is not an acceptable solution as the overhead increase due to this is tremendous. For example, if we program the timer chip to interrupt the CPU at 40 micro-sec, the interrupt processing cost is so high there is no time left for any other computation. So, basically, we need to program the timer chip to generate interrupts only when there is some scheduled work that needs to be accomplished. This is what we have achieved.
The following graph shows the time between when the time an event was scheduled to occur and the time it was actually executed. This was measured on a Pentium-200.
Figure: Distribution Plot for a Pentium (PS, GIF)
The graph below is on a Pentium-200 simulating a non-Pentium. (This shows the effectiveness of using the timer chip for keeping track of time).
Figure: Distribution Plot for a Non-Pentium (PS, GIF)
To use the UTIME system, patch the kernel with the supplied patch (Use patch -p1 -s < patch_file_name). Then configure the kernel and enable CONFIG_UTIME. This option is located in the "Kernel Hacking" submenu.
Once you configure the kernel and build it then when you boot up this kernel, it will try to calibrate itself. The calibrated speed can be observed with "cat /proc/cpuinfo". For example, for a 200 MHz Pentium "cat /proc/cpuinfo" should give you:
To add timers with microsecond resolution, set the timer->usec and the timer->expires field appropriately and use "add_timer()" to add the timer. You can test the UTIME subsystem by enabling CONFIG_UTIMER_TEST in the kernel configuration. Enabling this, would add random timers to the timeout queue and measure the time difference between when the timer was supposed to expire and when it actually did. A histogram of this is output to the console using syslog (The printk()'s use KERN_DEBUG as the level, so the messages should be in /var/log/debug, depending on your syslog configuration).
KU Real-Time (KURT) Linux is a firm real-time system we have developed that can take advantage of the increased precision of UTIME. (Note: The KURT patch already includes UTIME, so you only need to download one patch)
We have implemented the UTIME system for the i386. All of the architecture-dependent code is in the files:
The latter two files contain inline routines specific to the Pentium and above processors and the 386/486 processors, respectively. To port the UTIME system to other architectures, you would have to provide the equivalent routines and macros listed in the above asm include files.
We have moved the timers part in sched.c into a new file kernel/timers.c This has been done to reduce the clutter in sched.c
To achieve microsecond resolution timing, we have added a field to the timer_list structure (see include/linux/timer.h). This field (usec) indicates the microsecond within the current "jiffy" that the timer is to timeout.
To maintain compatability with the rest of the kernel, we have introduced the notion of a software clock. This clock maintains the "jiffies" granularity and calls the "do_timer()" routine every jiffy, so that the rest of the system which depends on this would run properly.
In addition to the "jiffies" variable which tracks the number of 10ms ticks that have passed since startup, we have added a "jiffies_u" variable which tracks the micro-seconds within a 10ms tick. In the pentium and above processors we use the Pentium TSC to maintain this increased resolution. In non-Pentium machines we use the timer chip itself to get this increased resolution, though this is not very accurate.
We have introduced two modes of operation.
You can switch the mode that the kernel is operating in by calling change_timer_mode() (see kernel/utime.c for usage).
Currently, the kernel is switched to oneshot mode as soon as the CPU counter is calibrated.
The current patch (version 1.17 - April 23, 1998) can be applied to a clean version of Linux 2.1.75. See the Change Log for changes since the last version.
A modified patch (version 1.17 - April 23, 1998) that will apply to a clean version of 2.0.33 is also available.
We would like to thank Sprint Inc. for funding the research in this area. We are indebted to them. We would also like to thank Raghavan Menon who wrote the first draft of this system and Furquan Ansari, Apurva Seth and Jason Keimig who started this whole thing. I would like to thank Michael Barabanov for helping me with the non-Pentium code. Obviously without Dr. Niehaus' support and continued encouragement, we would never have had this in its present form. Presently the people working on this project are Balaji Srinivasan and Shyam Pather.
Please send all bug-reports/questions/suggestions to email@example.com. Comments are welcome on how we can improve this system.
UTIME @ ITTC Last modified: Tue Sep 25 15:52:13 CDT 2001