Countless computerized activities are driven by timing measurements, often behind the user’s back. For instance, if the screen is automatically switched off after you have stopped using the computer’s console, it is due to a timer that allows the kernel to keep track of how much time has elapsed since you pushed a key or moved the mouse. If you receive a warning from the system asking you to remove a set of unused files, it is the outcome of a program that identifies all user files that have not been accessed for a long time. To do these things, programs must be able to retrieve a timestamp identifying its last access time from each file. Such a timestamp must be automatically written by the kernel. More significantly, timing drives process switches along with even more visible kernel activities like checking for time-outs.
We can distinguish two main kinds of timing measurement that must be performed by the Linux kernel:
Keeping the current time and date so they can be returned to user
programs through the time( )
, ftime( )
, and gettimeofday( )
system calls (see
Section 6.7.1 later in
this chapter) and used by the kernel itself as timestamps for files
and network packets
Maintaining timers — mechanisms that are able to notify the kernel (see the later section Section 6.6) or a user program (see the later section Section 6.7.3) that a certain interval of time has elapsed
Timing measurements are performed by several hardware circuits based on fixed-frequency oscillators and counters. This chapter consists of four different parts. The first two sections describe the hardware devices that underlie timing and give an overall picture of Linux timekeeping architecture. The following sections describe the main time-related duties of the kernel: implementing CPU time sharing, updating system time and resource usage statistics, and maintaining software timers. The last section discusses the system calls related to timing measurements and the corresponding service routines.
On the 80 × 86 architecture, the kernel must explicitly interact with four kinds of clocks: the Real Time Clock, the Time Stamp Counter, the Programmable Interval Timer, and the timer of the local APICs in SMP systems. The first two hardware devices allow the kernel to keep track of the current time of day. The PIC device and the timers of the local APICs are programmed by the kernel so that they issue interrupts at a fixed, predefined frequency; such periodic interrupts are crucial for implementing the timers used by the kernel and the user programs.
All PCs include a clock called Real Time Clock (RTC ), which is independent of the CPU and all other chips.
The RTC continues to tick even when the PC is switched off, since it is energized by a small battery or accumulator. The CMOS RAM and RTC are integrated in a single chip (the Motorola 146818 or an equivalent).
The RTC is capable of issuing periodic interrupts on IRQ 8 at frequencies ranging between 2 Hz and 8,192 Hz. It can also be programmed to activate the IRQ 8 line when the RTC reaches a specific value, thus working as an alarm clock.
Linux uses the RTC only to derive the time and date; however, it
allows processes to program the RTC by acting on the
/dev/rtc
device file (see Chapter 13). The kernel accesses the RTC through the
0x70
and 0x71
I/O ports. The
system administrator can set up the clock by executing the
clock
Unix system program that acts directly on
these two I/O ports.
All 80 × 86 microprocessors include a CLK input pin, which receives the clock signal of an external oscillator.
Starting with the Pentium, many recent 80 × 86
microprocessors include a 64-bit
Time Stamp Counter
(TSC ) register that can be read by
means of the rdtsc
assembly language instruction.
This register is a counter that is incremented at each clock signal
— if, for instance, the clock ticks at 400 MHz, the Time Stamp
Counter is incremented once every 2.5 nanoseconds.
Linux takes advantage of this register to get much more accurate time measurements than those delivered by the Programmable Interval Timer. To do this, Linux must determine the clock signal frequency while initializing the system. In fact, since this frequency is not declared when compiling the kernel, the same kernel image may run on CPUs whose clocks may tick at any frequency.
The task of figuring out the actual frequency of a CPU is
accomplished during the system’s boot. The
calibrate_tsc( )
function computes the frequency
by counting the number of clock signals that occur in a relatively
long time interval, namely 50.00077 milliseconds. This time constant
is produced by properly setting up one of the channels of the
Programmable Interval Timer (see the next section). The long
execution time of calibrate_tsc( )
does not create
problems, since the function is invoked only during system
initialization.[45]
Besides the Real Time Clock and the Time Stamp Counter,
IBM-compatible PCs include another type of time-measuring device
called Programmable Interval Timer
(PIT ). The
role of a PIT is similar to the alarm clock of a microwave oven: it
makes the user aware that the cooking time interval has elapsed.
Instead of ringing a bell, this device issues a special interrupt
called
timer interrupt,
which notifies the kernel that one more time interval has
elapsed.[46] Another difference from the alarm clock
is that the PIT goes on issuing interrupts forever at some fixed
frequency established by the kernel. Each IBM-compatible PC includes
at least one PIT, which is usually implemented by a 8254 CMOS chip
using the 0x40
-0x43
I/O ports.
As we shall see in detail in the next paragraphs, Linux programs the
PIT to issue timer interrupts on the IRQ0 at a (roughly) 100-Hz
frequency — that is, once every 10 milliseconds. This time
interval is called a
tick,
and its length in microseconds is stored in the
tick
variable. The ticks beat time for all
activities in the system; in some sense, they are like the ticks
sounded by a metronome while a musician is rehearsing.
Generally speaking, shorter ticks result in higher resolution timers,
which help with smoother multimedia playback and faster response time
when performing synchronous I/O multiplexing (poll( )
and select( )
system calls). This is a
trade-off however: shorter ticks require the CPU to spend a larger
fraction of its time in Kernel Mode — that is, a smaller
fraction of time in User Mode. As a consequence, user programs run
slower. Therefore, only very powerful machines can adopt very short
ticks and afford the consequent overhead. Currently, most
Hewlett-Packard’s Alpha and Intel’s
IA-64 ports of the Linux kernel issue 1,024 timer interrupts per
second, corresponding to a tick of roughly 1 millisecond. The Rawhide
Alpha station adopts the highest tick frequency and issues 1,200
timer interrupts per second.
A few macros in the Linux code yield some constants that determine the frequency of timer interrupts. These are discussed in the following list.
HZ
yields the number of timer interrupts per
second — that is, their frequency. This value is set to 100 for
IBM PCs and most other hardware platforms.
CLOCK_TICK_RATE
yields the value 1,193,180, which
is the 8254 chip’s internal oscillator frequency.
LATCH
yields the ratio between
CLOCK_TICK_RATE
and HZ
. It is
used to program the PIT.
The first PIT is initialized by init_IRQ( )
as
follows:
outb_p(0x34,0x43); outb_p(LATCH & 0xff, 0x40); outb(LATCH >> 8, 0x40);
The outb( )
C function is equivalent to the
outb
assembly language instruction: it copies the
first operand into the I/O port specified as the second operand. The
outb_p( )
function is similar to outb( )
, except that it introduces a pause by executing a no-op
instruction. The first outb_p( )
invocation is a
command to the PIT to issue interrupts at a new rate. The next two
outb_p( )
and outb( )
invocations supply the new interrupt rate to the device. The 16-bit
LATCH
constant is sent to the 8-bit
0x40
I/O port of the device as two consecutive
bytes. As a result, the PIT issues timer interrupts at a (roughly)
100-Hz frequency (that is, once every 10 ms).
The local APIC present in recent Intel processors (see Section 4.2) provides yet another time-measuring device: the CPU local timer .
The CPU local timer is a device that can issue one-shot or periodic interrupts, which is similar to the Programmable Interval Timer just described. There are, however, a few differences:
The APIC’s timer counter is 32-bits long, while the PIT’s timer counter is 16-bits long; therefore, the local timer can be programmed to issue interrupts at very low frequencies (the counter stores the number of ticks that must elapse before the interrupt is issued).
The local APIC timer sends an interrupt only to its processor, while the PIT raises a global interrupt, which may be handled by any CPU in the system.
The APIC’s timer is based on the bus clock signal (or the APIC bus signal, in older machines). It can be programmed in such a way to decrement the timer counter every 1, 2, 4, 8, 16, 32, 64, or 128 bus clock signals. Conversely, the PIT has its own internal clock oscillator.
Now that we understand what the hardware timers are, we may discuss how the Linux kernel exploits them to conduct all activities of the system.