Data Structures

High-resolution timers can be based on two different types of clocks (which are referred to as clock bases). The monotonic clock starts at 0 when the system is booted (clock_monotonic). The other clock (clock_realtime) represents the real time of the system. The latter clock may exhibit skips if, for instance, the system time is changed, but the monotonic clock runs, well, monotonously all the time.

For each CPU in the system, a data structure with both clock bases is available. Each clock base is equipped with a red-black tree that sorts all pending high-resolution timers. Figure 15-12 summarizes the situation graphically. Two clock bases (monotonic and real time) are available per CPU. All timers are sorted by expiration time on a red-black tree, and expired timers whose callback handlers still need to be executed are moved from the red-black tree to a linked list.

CPU 1

CPU 2

clock_base[0] clock_base[1]

Callback pending list active clock_base[0] clock_base[1]

Status info cb_pending hrtimer_bases

Expired timers pending to be processed struct hrtimer_clock_base

Callback pending list

Continue reading here: Figure 1512 Overview of the data structures used to implement highresolution timers

Was this article helpful?

0 0