看看Libco的时间轮快和小编一起探秘Libco中的时间轮吧~"

Libco的作为一个协程库，相当于在用户态完成了逻辑流的切换，这里的调度便是一旦遇到阻塞的系统调用（如read）时，将其注册到epoll_wait中并切换逻辑流，等待其I/O事件的到达，一旦到达则进行处理，将同步阻塞I/O换成了I/O多路复用。

而这里便是将I/O事件当作定时事件来处理，将I/O事件设置超时事件，如果超时则直接处理，避免一直等待的情况。

Libco管理定时事件便是使用时间轮这种数据结构，通过一种hash的思想使得添加定时事件的时间复杂度降到O(1)，大大提高了效率。

什么是时间轮

如果我们通过链表，按照超时时间进行升序或者降序的排列，这样添加事件就需要O(N)的时间复杂度。

而时间轮则将多条链表组合起来，每条链表上的事件都是同样的超时时间，而两条链表超时时间的差值t就是处理超时事件的时间间隔。时间轮内部有一个指针指向当前的链表，t时间过去，t指向下一个链表，判断是否超时。

而当我们想要添加一个定时事件，只需要知道它的超时时间，再除以t，就是它应该插入的位置。

如图，当前指向1号链表，t为50ms，当需要添加一个定时为100ms的定时事件时，直接添加到3号链表即可（O(1)）。

libco的主循环分析

让我们看看这里的主循环，为了思路清晰，删除部分无关代码：

可以看到这个事件循环的思路是： epoll_wait监听→等待事件→处理I/O事件→得到现在时间，判断是否超时→处理超时事件。

获取现在的时间

这里比较有趣的是GetTickMS，这个用于获取现在时间的函数：

gettimeofday自然不用多说，它的好处是跨平台，不用切换到内核态。而上面的"法1"使用的函数如下：

如果你看不懂getCpuKhz这个函数，可以打开/proc/cpuinfo看一眼，就可以知道这里记载的是cpu的动态信息。而counter函数则主要是调用rdtscp这条汇编指令，将计数（来一个时钟脉冲+1）读出来。

我的理解是：counter()将总共的时钟脉冲数读出再除以CPU的频率（每秒时钟脉冲）就是时间。

本文转自：小组15级成员--康艺杰

原文地址：

http://blog.csdn.net/xiyoulinux_kangyijie/article/details/78494743

（更多详细内容，点击左下角【阅读原文】）