虚拟内存 & I/O & 零拷贝( 五 ) _虚拟内存

epoll 有效规避了将 fd 频繁的从用户态拷贝到内核态，通过使用红黑树(RB-tree)搜索被监视的文件描述符(file deor) 。在 epoll 实例上注册事件时，epoll 会将该事件添加到epoll 实例的红黑树上并注册一个回调函数，当事件发生时会将事件添加到就绪链表中。
3.3.1 epoll 数据结构 + 算法
epoll 的核心数据结构是：1 个红黑树和 1 个双向链表，还有 3个核心API 。

文章插图
3.3.2 监视 socket 索引-红黑树
为什么采用红黑树呢？因为和 epoll 的工作机制有关。epoll 在添加一个 socket 或者删除一个 socket 或者修改一个 socket 的时候，它需要查询速度更快，操作效率最高，因此需要一个更加优秀的数据结构能够管理这些 socket 。我们想到的比如链表，数组，二叉搜索树，B+树等都无法满足要求，

因为链表在查询，删除的时候毫无疑问时间复杂度是 O(n)；
数组查询很快，但是删除和新增时间复杂度是 O(n)；
二叉搜索树虽然查询效率是 lgn，但是如果不是平衡的，那么就会退化为线性查找，复杂度直接来到 O(n)；
B+树是平衡多路查找树，主要是通过降低树的高度来存储上亿级别的数据，但是它的应用场景是内存放不下的时候能够用最少的 IO 访问次数从磁盘获取数据。比如数据库聚簇索引，成百上千万的数据内存无法满足查找就需要到内存查找，而因为 B+树层高很低，只需要几次磁盘 IO 就能获取数据到内存，所以在这种磁盘到内存访问上 B+树更适合。

因为我们处理上万级的 fd，它们本身的存储空间并不会很大，所以倾向于在内存中去实现管理，而红黑树是一种非常优秀的平衡树，它完全是在内存中操作，而且查找，删除和新增时间复杂度都是 lgn，效率非常高，因此选择用红黑树实现 epoll 是最佳的选择。当然不选择用 AVL 树是因为红黑树是不符合 AVL 树的平衡条件的，红黑是用非严格的平衡来换取增删节点时候旋转次数的降低，任何不平衡都会在三次旋转之内解决；而 AVL 树是严格平衡树，在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多。所以红黑树的插入效率更高。
3.3.2 就绪 socket 列表-双向链表
就绪列表存储的是就绪的 socket，所以它应能够快速的插入数据。程序可能随时调用 epoll_ctl 添加监视 socket，也可能随时删除。当删除时，若该 socket 已经存放在就绪列表中，它也应该被移除。（事实上，每个 epoll_item 既是红黑树节点，也是链表节点，删除红黑树节点，自然删除了链表节点）所以就绪列表应是一种能够快速插入和删除的数据结构。双向链表就是这样一种数据结构，epoll 使用双向链表来实现就绪队列（rdllist）
3.3.3 三个 API 3.3.3.1 int epoll_create(int size)
功能：内核会产生一个 epoll 实例数据结构并返回一个文件描述符 epfd，这个特殊的描述符就是 epoll 实例的句柄，后面的两个接口都以它为中心。同时也会创建红黑树和就绪列表，红黑树来管理注册 fd，就绪列表来收集所有就绪 fd 。size 参数表示所要监视文件描述符的最大值，不过在后来的 Linux 版本中已经被弃用（同时，size 不要传 0，会报 invalid argument 错误）
3.3.3.2 int epoll_ctl(int epfd，int op，int fd，struct epoll_event *event)
功能：将被监听的 socket 文件描述符添加到红黑树或从红黑树中删除或者对监听事件进行修改；同时向内核中断处理程序注册一个回调函数，内核在检测到某文件描述符可读/可写时会调用回调函数，该回调函数将文件描述符放在就绪链表中。
3.3.3.3 int epoll_wait(int epfd，struct epoll_event *events，int maxevents，int timeout);
功能：阻塞等待注册的事件发生，返回事件的数目，并将触发的事件写入 events 数组中。events: 用来记录被触发的 events，其大小应该和 maxevents 一致 maxevents: 返回的 events 的最大个数处于 ready 状态的那些文件描述符会被复制进 ready list 中，epoll_wait 用于向用户进程返回 ready list(就绪列表) 。events 和 maxevents 两个参数描述一个由用户分配的 struct epoll event 数组，调用返回时，内核将就绪列表(双向链表)复制到这个数组中，并将实际复制的个数作为返回值。注意，如果就绪列表比 maxevents 长，则只能复制前 maxevents 个成员；反之，则能够完全复制就绪列表。另外，struct epoll event 结构中的 events 域在这里的解释是：在被监测的文件描述符上实际发生的事件。
3.3.4 工作模式