University of Kaiserslautern | Computer Science | Distributed Systems | Research | Squirrel

Next: Clock Synchronization | Up: The BEAT Communication Service | Previous: Network Transmission

3 Clock Granularity

The Linux System Clock | Changing Timer Granularity | Performance

The system clock plays an important role in resource management, particularly in real-time systems. It provides two basic functions: The clock allows applications and the kernel to query the current time, which is crucial for dealing with time constraints. It also provides an alarm clock, which the operating system and applications use to be notified at specified times. For this purpose, there is a timer mechanism inside the kernel, which for instance is used by the token mechanism described in Chapter 2 to implement the token holding time. Time slices for CPU scheduling are based on the system clock, too. Kernel timers are also used for setting timeouts, for network protocols or device drivers, for instance. At user level, applications can request signals generated by timer interrupts by the setitimer function and apply timeout mechanisms using the select call.

3.1 The Linux System Clock

System clocks are usually based on periodic hardware interrupts. The kernel maintains the current time and advances it at every interrupt [2,16]. The structure of the clock hardware of typical Intel PCs is shown in Figure 3.1. An oscillator generates clock pulses that drive a counter C. Every time the counter reaches the value of a programmable latch L, an interrupt is generated and the counter is reset. At each of these ticks the kernel then increases the internal variable jiffies, which simply counts clock ticks, as well as the variable xtime, which represents current time (as a struct timeval).

**Figure 3.1:** PC clock hardware
$\begin{figure} \begin{center} \includegraphics {mp/clock.10} \end{center}\end{figure}$

Time can be queried via the gettimeofday function. If it would simply return the value of xtime, just the accuracy of the timer interrupt frequency could be provided. However, gettimeofday queries the hardware counter C that is used for interrupt generation and includes the time passed since the last update of xtime.

The alarm clock functionality, however, relies on the interrupts and cannot provide a higher accuracy than the interrupt frequency, which is 10ms. The next section discusses how this timer granularity can be improved. A different approach has been taken in the UTIME project at the University of Kansas [17]. In their system, for every event the hardware latch L is reprogrammed to generate the next interrupt exactly at the right time.

3.2 Changing Timer Granularity

Linux has a global definition

#define HZ 100

which determines the frequency of timer interrupts. Ideally, timer granularity could simply be changed by modifying this definition. However, several problems occur:

There are rounding errors in programming the hardware latch L and in updating system time. For 10ms ticks, these errors are acceptable but may be too large for other timer granularities.
Kernel timers are programmed in ticks. Some device drivers do not include HZ in calculating their timeout value, but simply assume HZ to be 100.
Utility programs such as top or ps take timing information from the kernel in ticks, also assuming 10ms ticks. This data is passed through the /proc filesystem interface, which had to be modified to hide changes of HZ.
The mechanism for clock synchronization needs to be adapted for different values of HZ. It does not work at all, if timer interrupts are more frequent than once in 1ms. For this case, some internal variables would require additional bits.

3.3 Performance

In the first experiment, the select call has been used to block for 10 $\mu$ s, 100 $\mu$ s, 1ms, 10ms, and 100ms for timer granularities of 100 $\mu$ s, 300 $\mu$ s, 1ms, 3ms, and 10ms. The actual time spent blocked on the select call has been measured using the gettimeofday function. For each configuration, the average of 500 runs has been taken to filter out delays caused by other processes. The difference of the time actually waited and the time requested is shown in Figure 3.2 in logarithmic scale.

**Figure 3.2:** Clock accuracy
$\begin{figure} \begin{center} \includegraphics {mp/clock.1} \end{center}\end{figure}$

Let us consider the graph for 1ms blocking time. For timer granularities of less than 1ms the error is about 2ms, for other granularities about 1ms. Assuming, the system could not block for a shorter time than the tick size, an error of 1ms and 0, respectively, would be expexted. The implementation of select explains the actual behavior:

$\begin{displaymath} \mbox{jiffies}_{\mbox{\small alarm}} = \mbox{jiffies}_{\mbox... ...l towait}}}{\mbox{time}_{\mbox{\small tick}}} \right\rceil + 1\end{displaymath}$

The reason for always rounding up and additionally adding one tick remains unclear. The graphs for tick sizes of 100 $\mu$ s and 10ms are similar. For 300 $\mu$ s and 3ms, the error only drops from 600 $\mu$ s to 500 $\mu$ s and from 6ms to 5ms, respectively, which is caused by rounding errors in the formula above.

Apart from these implementation peculiarities, the timer granularity is reflected in the accuracy provided to the user. This relation also exists inside the kernel, where events can be scheduled only in ticks, too.

**Figure 3.3:** Overhead of timer interrupts
$\begin{figure} \begin{center} \includegraphics {mp/clock.5} \end{center}\end{figure}$

The overhead introduced by more frequent timer interrupts is shown in Figure 3.3 for tick granularities of 100 $\mu$ s, 300 $\mu$ s, 1ms, 3ms, and 10ms. The solid line gives the average time of 100 runs of an empty loop executed one million times, the dashed line gives the time of a kernel make. At a tick granularity of 100 $\mu$ s there is an overhead of 10.2% compared to 10ms tick size for the loop, and 11.9% for the kernel make. With interrupts every 1ms the overhead is 3.1% and 3.2%, respectively.

The tick size is also used as the scheduling time slice. Hence, a higher interrupt frequency also introduces more context switches between processes. This overhead is not reflected in the experiment described. Nonetheless, it seems reasonable to choose a tick size of 1ms for our system. For instance, the token holding time of 1ms, which turned out to be a good choice in Chapter 2, would not be possible otherwise.

Footnotes

...synchronization: The interface for this mechanism is provided by the adjtimex system call.

Next: Clock Synchronization | Up: The BEAT Communication Service | Previous: Network Transmission

University of Kaiserslautern | Computer Science | Distributed Systems | Research | Squirrel

Rainer Koster, 6/18/1998