通常来讲,就是利用 select 的空余时间,来进行时钟检查,不管是 select / poll / epoll/ kevent,以下统称 select,它有一个等待时间作为参数,即没有事件时,最多 wait 多少时间,我们把这个作为网络库的基准频率,比如 10MS,或者 20MS, 25MS, 50MS,都是常用的几个值。
就是说网络库调用 select 等待事件时如果没有事件,那么最长等待 10MS 就返回了,这时再处理完所有网络事件后,就可以来处理时钟数据了。事件处理函数就是这样:
def update_events(milisec = 10):
result = selector.select(milisec)
for fd, event in result:
do something with socket event
current = time.time()
update_timer(current)while 1:
WAIT_MILLISEC = 10
update_events(WAIT_MILLISEC)
关键就是这个两次 select 中间 update_timer 的任务:集合中检查需要唤醒的时钟,并且调用它们的回调函数,来驱动整个服务器的时钟运行,以最简单的扫描法为例:
def update_timer (current):
for timer in available_timers:
while current >= timer.expires:
timer.callback(current)
timer.expires += timer.period
available_timers 记录着当前可用的所有 timer 的集合,expires 是他们需要被触发的时间,如果当前时间大于等于这个 expires,认为该 timer 需要被触发到。注意 timer.expires 更新的时候是 += 周期,而不是 = current + 周期,后者会导致误差积累,长时间运行后偏差越来越大。同时这里需要 while,因为可能跨越两个以上周期,当然只运行一次的 timer 就不需要了,这里只是简化下。
比如 libevent 里面的主循环 event_base_loop 每次 select 完毕后就调用一次 timeout_process。
这就是 Timer 调度的基本原理。
可能你会发现每次 select 结束都要扫描整个 available_timers 集合,是一个非常费时间的事情,那么首先想到的就是优先队列了:将 Timer 节点按照 expires 的先后顺序,将最快要发生的超时节点放在前面,每次检测队列头就可以判断是否超时了。
比如 libevent 里面的 timerout_process 函数,就是用最小堆来存储超时事件,每次检测堆的第一个节点如果超时则删除并继续检测下一个,否则跳出循环(此时没有任何节点到期)。
还有一种固定超时队列,就是里面的节点的超时周期都是相同的,那么每次增加都在最后,每次检测都只检测头部。比如所有链接都要检测60秒无事件超时这个事情,就可以用它,因为60秒是固定的,新增时放到队列最后,检测时只检测头部是否超时,如果有事件来到,就删除并重新加入队列末尾,这是固定超时队列。
还有上面专门说的系统提供的 timerfd,创建后加入 select, 但是受限于 linux 系统,跨平台就用不了了,不能太依赖。
然而这些都不算最完美的解决方案,一旦超时节点多达上万个,每个时间都不同,又考虑通用实现(非特定平台实现)的话,这几种调度方式是要吃亏的,目前最好的算法是 Linux Kernel 的时间轮算法,几乎保证不管有多少个时钟对象要处理,每次 update_timer 的时间都几乎是常数。
具体可以看代码 kernel/timer.c ,时间轮的应用层实现见我写的:
Asyn.NET/itimer.h at master · skywind3000/AsyncNet · Github
AsyncNet/itimer.c at master · skywind3000/AsyncNet · GitHub
两个文件,拷贝走就得了,没有任何第三个文件的依赖,更没有全局唯一的时钟管理器。
一般来讲 “侵入式” 的网络库,都会把这个事情给管理了,因为他们接管你的主循环,比如 libevent, skynet 之类,你进入一个 event_loop 就只有程序结束才能出来了,而非侵入式的网络库不会接管你的主循环,可以让你自己主动去触发。
比如某同事想在 libevent 上跑一套自己的时钟系统,而 event_base_dispatch 属于进去就出不来的 “侵入式” 设计。为了能在 select 前后加入自己的时钟调度,不得不把 libevent 改出一个 branch 来,所以 侵入式 是比较恶劣的设计。libevent 应该学习一下 win32,把 GetMessage, DispatchMessage 放出来,比如叫做:
int event_base_update(struct event_base *base, int max_wait_time);
让你主动去触发它,然后灵活的在前后做点事情,还可以用 event_base_wakeup 从另外一个现成唤醒它,这样就会灵活很多了,完全取代 event_base_dispatch 这个进去出不来的死循环。
每次 select wait 的时间一般用一个固定值,称为一个 TICK,固定值选大了,时钟基准周期就会很长,短时误差就会增大,选小了,又会占用额外 cpu,可以模拟 Linux 使用 100Hz的值,即 10ms来做,这也是通行做法。
不嫌麻烦还可以每次从 timer 集合里面选择最先要超时的事件,计算还有多长时间就会超时,作为 select wait 的值,每次都不一样,每次都基本精确,同时不会占用多余 cpu,这叫 tickless,Linux 的 3.x以上版本也支持 tickless 的模式来驱动各种系统级时钟,号称更省电更精确,不过需要你手动打开,FreeBSD 9 以后也引入了 tickless。
TICKLESS 模式可以说是一个新的方向,但是目前处于默认关闭的测试状态,那么你的网络库到底是用 TICK 还是 TICKLESS,看你根据具体情况来评估了。