定时器(timer)与时间轮(timewheel)

1 定时器(timer)

1.1 定时器使用场景

通常,定时是系统一个比较常用的事件。定时器要解决的问题是,隔一定时间(short-one)或者每隔一段时间(repeated)触发一个定时事件。

无论是系统还是应用,都会用到定时功能,例如,
系统层面: 屏幕刷新,TCP等
应用层面: 网络库实现的定时功能比如libuv

1.2 应用层定时器

应用层的定时通常有几种方式:

可以在某个循环(比如Windows GetMessage, DispatchMessage后面)判断时间,通常循环里可能会sleep一下,或者有类似poll,wait之类的超时设置;

借助操作系统提供的timer函数(POSIX timer函数或者windows timer消息),或者系统提供的定时任务如crond;

利用poll相关函数,借助timerfd等(linux);

数据结构方面,可以使用链表或者堆。

1.3 系统层定时器

系统定时器有低分辨率定时器,也有高分辨率定时器。

低分辨率定时器一般为毫秒级,典型分辨率为4毫秒。通常采用timer wheel实现。

高分辨率定时器可以达到纳秒级。通常采用红黑树实现。

底层使用时钟硬件(如HPET)提供的时钟中断来提供tick。

2 时间轮(timewheel)

timewheel思想十分简单。想象我们的时钟,分辨率为秒,能实现从1秒到43200(12*60*60)秒的定时。然而定时轮并不需要12*60*60大小的数组,只需要用到12+60+60=132个大小的数组。

3 参考

《Professional Linux Kernel Architechure》

Leave a Reply

Your email address will not be published. Required fields are marked *