epoll是Linux下多路复用IO接口select/poll的增强版本，它能显著减少程序在大量并发连接中只有少量活跃的情况下的系统CPU利用率，因为它不会复用文件描述符集合来传递结果而迫使开发者每次等待事件之前都必须重新准备要被侦听的文件描述符集合，另一点原因就是获取事件的时候，它无须遍历整个被侦听的描述符集，只要遍历那些被内核IO事件异步唤醒而加入Ready队列的描述符集合就行了。epoll的除了提供select/poll那种IO事件的电平触发（Level Triggered）外，还提供了边沿触发（Edge Triggered），这就使得用户空间程序有可能缓存IO状态，减少epoll_wait/epoll_pwait的调用，提高应用程序效率。
epoll相关的系统调用有:epoll_create, epoll_ctl和epoll_wait。Linux-2.6.19又引入了可以屏蔽指定信号的epoll_wait: epoll_pwait。至此epoll家族已全。其中epoll_create用来创建一个epoll文件描述符，epoll_ctl用来添加/修改/删除需要侦听的文件描述符及其事件，epoll_wait/epoll_pwait接收发生在被侦听的描述符上的，用户感兴趣的IO事件。epoll文件描述符用完后，直接用close关闭即可，非常方便。事实上，任何被侦听的文件符只要其被关闭，那么它也会自动从被侦听的文件描述符集合中删除，很是智能。
每次添加/修改/删除被侦听文件描述符都需要调用epoll_ctl，所以要尽量少地调用epoll_ctl，防止其所引来的开销抵消其带来的好处。有的时候，应用中可能存在大量的短连接（比如说Web服务器），epoll_ctl将被频繁地调用，可能成为这个系统的瓶颈。
我查看了内核中的侦听描述符集合的组织形式，发现其所采用的数据结构是红黑树（rbtree），这种树的插入/删除/查找的平均时间复杂度都是O(log2(N))，可以说已经达到了“理论”上的极限。但是，数据结构的选择应该是因地制宜的，应该充分考虑到其所处环境：
- 他所操作的对象是文件描述符，文件描述符的一个重要的特性就是总分配最小可用的文件描述符，换句话说就是：他们一般密集地分部在数值较小的区间。
- 考虑到只有PIPE/Socket等管道类的文件描述符才能被侦听可读、可写等事件，一般的文件操作的异步事件都是读完、写完等，所以，实际上可侦听的文件描述符的密度可能只有50%（Web服务器），但还是有能接近100%的（代理网关），即使是50%，也依然很高。
所以，插入/删除/查找的时间复杂度都是O(1)的数据结构--数组应该更适合，为此，我专门给内核做了一个，用数组替代了以前的红黑树，并用一个简单的做了测试，结果显示epoll操作的时间复杂度确实从O(log2(N))降到了O(1)，效果明显。
尝试着向官方内核补丁，不幸地，理由是“we aren't going back"，因为红黑树就是从最初的哈希表来的，至于改的理由“might exhaust memory badly”，个人感觉有些牵强。
把这个补丁索引在这里了，希望可能对大家有用！
阅读(4445) | 评论(10) | 转发(0) |
