Chapter 15: Time Management
are several timers in the system with the sameexpiresvalue, they are linked by means of a doubly
linked standard list (and via theentryelement oftimer_list).
Table 15-1: Interval Lengths for Timers
Group Intervaltv1 0 –255tv2 28 =256 –2^14 − 1tv3 214 –2^20 − 1tv4 220 –2^26 − 1tv5 226 –2^32 − 1The remaining groups also consist of arrays but with fewer entries, namely, 64. The array entries also
accepttimer_listinstances linked in a doubly linked list. However, each array entry no longer holds
just one possible value ofexpiresbut an entire interval. The length of the interval depends on the group.
While the second group permits 256= 28 consecutive time values per array element, this figure is 2^14 in
the third group, 2^20 in the fourth, and 2^26 in the fifth and final group. Why these interval sizes make
sense will become clear when we consider how timers are executed in the course of time and how the
associated data structure is changed.
How are timers executed? The kernel is responsible primarily for looking after the first of the above
groups because this includes all timers due to expire shortly. For simplicity’s sake, let us assume that
each group has a counter that stores the number of an array position (actual kernel implementation is the
same in functional terms but is far less clearly structured as you will see shortly).
The index entry of the first group points to the array element that holds thetimer_listinstances of the
timers shortly due to be executed. The kernel scans this list every time there is a timer interrupt, executes
all timer functions, and increments the index position by 1. The timers just executed are removed from the
data structure. The next time a timer interrupt occurs, the timers at the new array position are executed
and deleted from the data structure, and the index is again incremented by 1, and so on. Once all entries
have been processed, the value of the index is 255. Because addition is modulo 256, the index reverts to
its initial position (position 0).
Because the contents of the first group are exhausted after at most 256 ticks, timers of the higher groups
must be pushed forward successively in order to replenish the first group. Once the index position of the
first group has reverted to its initial position, the group is replenished with all timers of asinglearray
entry of the second group. This explains the interval size selection in the individual groups. Because 256
different expiry times per array element are possible in the first group, the data of asingleentry in the
second group are sufficient to replenish the complete array of the first group. The same applies for higher
groups. The data in an array element of the third group are sufficient to replenish the entire second group;
an element of the fourth group is sufficient for the entire third group, and an element of the fifth group is
sufficient for the entire fourth group.