hashed and hierarchical timing wheels: data structures for the efficient implementation of a timer facility
Conventional algorithms to implement an Operating System timer module take &Ogr; ( n ) time to start or maintain a timer, where n is the number of outstanding timers: this is expensive for large n . This paper begins by exploring the relationship between timer algorithms, time flow mechanisms used in discrete event simulations, and sorting techniques. Next a timer algorithm for small timer intervals is presented that is similar to the timing wheel technique used in logic simulators. By using a circular buffer or timing wheel, it takes &Ogr; (1) time to start, stop, and maintain timers within the range of the wheel. Two extensions for larger values of the interval are described. In the first, the timer interval is hashed into a slot on the timing wheel. In the second, a hierarchy of timing wheels with different granularities is used to span a greater range of intervals. The performance of these two schemes and various implementation trade-offs are discussed.
hierarchic timing data structures efficiency implementation algorithm operating system module maintainability paper exploration relationships flow event simulation sorting interval logic buffers extensibility values hierarchies performance scheme