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 O(n) time to start or main-
rain a timer, where n is the number of outstanding
timers: this is expensive for large n. This paper be-
gins by exploring the relationship between timer algo-
rithms, t i m e flow mechanisms used in discrete event
simulations, and sorting techniques. Next a timer
a l g o r i t h m for small timer intervals is presented t h a t
is similar to the timing wheel technique used in logic
sinmlators. By using a circular buffer or timing wheel,
it takes O(1) time to start, stop, and m a i n t a i n timers
within the range of the wheel.
T w o extensions for larger values of the interval are de-
scribed. 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. T h e performance of
these two schemes and various implementation trade-
offs are discussed.
传统的操作系统定时器模块的算法复杂度是O(n) ,其中n是定时器的数量：当n很大的时候代价会非常昂贵 。
这篇文章开始探讨定时器算法和时间流机制在离散的事件模拟和排序技术方面的关系.下面的小间隔的定时器算法很类似使用逻辑模拟的时间轮.
通过使用环状缓冲或者时间轮,我们可以在定时器的可维持运行的精度内使用O(1)的时间去开启,结束以及维持定时器
有两个额外的对于大的时间间隔的拓展.第一,定时器的间隔被哈希进去一个时间轮.第二,一个多层级的时间轮保证大于时间间隔的也能有位置存放.
下面会讨论这两张情况和不同实现的平衡.
Our model of a timer module has four component
routines:
START_TIMER(Interval, Request_ID, Expiry_
Action): The client calls this routine to start a timer
that will expire after “Interval” units of time. The
client supplies a Request_ID which is used to distinguish this timer from other timers that the client has
outstanding. Finally, the client can specify what action must be taken on expiry: for instance, calling a
client-specified routine, or setting an event flag.
STOP_TIMER(Request_ID): This routine uses its
knowledge of the client and Request_ID to locate the
timer and stop it.
PER_TICK_BOOKKEEPING: Let the granularity of
the timer-be T units. Then every T units this routine
checks whether any outstanding timers have expired;
if so, it calls STOP_TIMER, which in turn calls the
next routine.
EXPIRY_PROCESSING: This routine does the Expiry_Action specified in the START_TIMER call.
The first two routines are activated on client calls
while the last two are invoked on timer ticks. The
timer is often an external hardware clock.
The following two performance measures can be used
to choose between the various algorithms described
in the rest of this paper. Both of them are parameterized by n, the average (or worst-case) number of
outstanding timers.
我们的定时器模块有四个组件模块例程:
START_TIMER(Interval, Request_ID, Expiry_Action): 客户端会调用这个例程去启动(注册)一个会在Interval 时间后会过期的定时器.