Chapter 15: Time Management
The array positions of the higher groups are not, of course, selected randomly — the index entry again
has a role to play. However, the index entry value is no longer incremented by 1 after each timer tick but
only after each 256i−^1 tick, whereistands for the number of the group.Let’s examine this behavior by reference to a concrete example: 256 jiffies have expired since processing
of the first group was started, which is why the index is reset to 0. At the same time, the contents of the
first array element of the second group are used to replenish the data of the first group. Let us assume
that thejiffiessystem timer has the value 10,000 at the time of reset. In the first element of the second
group, there is a linked list of timers due to expire at 10,001, 10,015, 10,015, and 10,254 ticks. These are
distributed over array positions 1, 15, and 254 of the first group, and a linked list made up of two pointers
is created at position 15 — after all, both expire at the same time. Once copying is complete, the index
position of the second group is incremented by 1.The cycle then starts afresh. The timers of the first group are processed one after the other until index
position 255 is reached. All timers in the second array element of the second group are used to replenish
the first group. When the index position of thesecondgroup has reached 63 (from the second group
onward the groups contain only 64 entries), the contents of the first element of thethirdgroup are used
to replenish the data of the second group. Finally, when the index of the third group has reached its
maximum value, data are fetched from the fourth group; the same applies for the transfer of data between
the fifth and the fourth groups.To determine which timers have expired, the kernel need not scan through an enormous list of timers but
can limit itself to checking asinglearray position in the first group. Because this position is usually empty
or contains only a single timer, this check can be performed very quickly. Even the occasional copying of
timers from the higher groups requires little CPU time, because copying can be carried out efficiently by
means of pointer manipulation (the kernel is not required to copy memory blocks but need only supply
pointers with new values as is usually the case in standard list functions).Data Structures
The contents of the above groups are generated by two simple data structures that differ minimally:kernel/timer.c
typedef struct tvec_s {
struct list_head vec[TVN_SIZE];
} tvec_t;typedef struct tvec_root_s {
struct list_head vec[TVR_SIZE];
} tvec_root_t;Whiletvec_root_tcorresponds to the first group,tvec_trepresents higher groups. The two struc-
tures differ only in the size of the array elements; for the first group,TVR_SIZEis defined as 256. All
other groups useTVN_SIZEentries with a default value of 64. Systems where memory is scarce set the
configuration optionBASE_SMALL; in this case, 64 entries are reserved for the first and 16 for all other
groups.