Linux Kernel Architecture

Chapter 15: Time Management

Again auxiliary functions convert back and forth between jiffies andtimespecs:timespec_to_jiffies

andjiffies_to_timespec.

15.2.4 Dynamic Timers

The kernel needs data structures to managealltimers registered in the system (these may be assigned

to a process or to the kernel itself). The structures must permit rapid and efficient checking for expired

timers so as not to consume too much CPU time. After all, such checks must be performed at each timer

interrupt.^6

Modeof Operation

Before taking a closer look at the existing data structures and the implementation of the algorithms, let’s

illustrate the principle of timer management by reference to a simplified example, since the algorithm

used by the kernel is more complicated than might be expected at first glance. (This complexity brings

its rewards in the form of greater performance that could not be achieved with simpler algorithms and

structures.) Not only must the data structure hold all the information needed to manage timers,^7 but it

must also be capable of being scanned easily at periodic intervals so that expired timers can execute and

then be removed. Figure 15-6 shows how timers are managed by the kernel.

tv1 tv2 tv3 tv4 tv5 tvec_base_t

struct timer_list

Figure 15-6: Data structures for managing timers.

The main difficulty lies in scanning the list for timers that are about to expire and that have just expired.

Because simply stringing together alltimer_listinstances is not satisfactory, the kernel creates different

groups into which timers are classified according to their expiry time. The basis for grouping is the main

array with five entries whose elements are again made up of arrays. The five positions of the main array

sort the existing timers roughly according to expiry times. The first group is a collection of all timers

whose expiry time is between 0 and 255 (or 2^8 ) ticks. The second group includes all timers with an expiry

time between 256 and 2^8 +^6 − 1 = 214 −1 ticks. The range for the third group is from 2^14 to 2^8 +^2 ×^6 −1,

and so on. The entries in the main table are known asgroupsand are sometimes referred to asbuckets.

Table 15-1 lists the intervals of the individual timer groups. I have used the bucket sizes for regular

systems as the basis of our calculations. The intervals differ on small systems with little memory.

Each group itself comprises an array in which the timers are sorted again. The array of the first group

consists of 256 elements, each position standing for a possibleexpiresvalue between 0 and 256. If there

(^6) Although the chosen data structure is well suited for the intended purpose, it is nevertheless too inefficient for high-resolution
timers that require even better organization.
(^7) For the moment, ignore the additional data required for process-specific interval timers.