定时器(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》