Skip to content


Posted on:October 10, 2021 at 09:54 PM

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 时间后会过期的定时器.