原文：https://zhuanlan.zhihu.com/p/63179839 从网卡接收数据开始
下图是典型的计算机结构图，由计算机组成CPU、由存储器(内存)、网络接口等组成。epoll本质的第一步是从硬件的角度看计算机如何接收网络数据。
计算机结构图(图片来源:linux微型计算机组成结构内核完全注释)
下图显示了网卡接收数据的过程。①在这个阶段，网卡收到网线的数据；经过②硬件电路传输阶段；最后将数据写入内存中的地址（③阶段)。这个过程涉及到。DMA传输、IO与硬件相关的知识，如通路选择，但我们只需要知道：网卡将接收到的数据写入内存。
网卡接收数据的过程
网卡接收的数据通过硬件传输存储在内存中。操作系统可以读取它们。 如何知道接收数据？
了解epoll本质的第二步，要从CPU从数据接收的角度来看。要理解这个问题，首先要理解一个概念-中断。
计算机执行程序时，会有优先级要求。例如，当计算机收到断电信号时(电容器可以保存一点电源CPU短时间运行)，应立即保存数据，保存数据的程序优先级较高。
一般来说，硬件产生的信号需要cpu立即做出回应(否则数据可能会丢失)，因此其优先级很高。cpu应中断正在执行的程序并做出响应；当cpu完成对硬件的响应后，再重新执行用户程序。中断的过程如下图，和函数调用差不多。只不过函数调用是事先定好位置，而中断的位置由“信号”决定。
调用中断程序
以键盘为例，当用户按下键盘时，键盘会给出cpu中断引脚产生高电平。cpu它可以捕获信号，然后执行键盘中断程序。下图显示了各种硬件通过中断和中断cpu交互。
cpu中断(图片来源:net.pku.edu.cn）
本节提出的问题现在可以回答了：当网卡将数据写入内存时，网卡会向前移动cpu通过发出中断信号，操作系统可以知道新数据的到来，然后通过网卡中断程序处理数据。 三、为什么过程堵塞不占用cpu资源？
了解epoll本质的第三步，要从操作系统进程调度的角度来看数据接收。阻塞是进程调度的关键一环，指的是进程在等待某事件（如接收到网络数据）发生之前的等待状态，recv、select和epoll都是阻塞方法。了解“进程阻塞为什么不占用cpu资源？，也能理解这一步。
为了简单起见，我们来自普通人recv接收开始分析，先看下面的代码:
//创建socket int s = socket(AF_INET, SOCK_STREAM, 0); //绑定 bind(s, ...) //监听 listen(s, ...) //接受客户端连接 int c = accept(s, ...) //接收客户端数据 recv(c, ...); //打印数据 printf(...) 这是最基本的网络编程代码，先新建socket依次调用对象bind、listen、accept，最后调用recv接收数据。recv当程序运行到达时，这是一种阻塞方法recv它会一直等待，直到收到数据。
插入：如果您不熟悉网络编程，请阅读我编写的内容《Unity3D详细介绍网络游戏实战(第二版)。 阻塞的原理是什么？
工作队列
为了支持多任务，实现过程调度的功能，操作系统将过程分为几种状态和等待。运行状态是进程获得cpu使用权，正在执行代码的状态；等待状态是阻塞状态，比如上述程序运行到recv程序将从运行状态转变为等待状态，接收到数据后再转换为运行状态。由于速度快，操作系统会分时执行各种操作状态的过程，看起来像是同时执行多个任务。
运行在下图中的计算机中A、B、C三个过程，其中A执行上述基本网络程序。一开始，这三个过程都被操作系统的工作队列引用，处于运行状态，分时执行。
有工作队列A、B和C三个过程
等待队列
当过程A执行到创建时socket操作系统将创建由文件系统管理的语句socket对象(下图)。socket对象包括发送缓冲区、接收缓冲区、等待队列等。等待队列是一个非常重要的结构，它指向所有需要等待的人socket事件的过程。
创建socket
当程序执行时recv当操作系统将过程A从工作队列移动到此时socket等待队列(如下图所示)。由于工作队列只剩下过程B和C，根据进程调度，cpu这两个过程的程序将轮流执行，不会执行过程A的程序。因此，过程A被阻塞，不会执行代码，也不会占用cpu资源。
socket的等待队列
ps：在操作系统中添加等待队列只是对等待过程的参考，以获取过程对象并在收到数据时唤醒它，而不是直接将过程管理纳入自己为了方便说明，上图直接将过程挂在等待列下。
唤醒进程
当socket操作系统接收到数据后，会socket等待队列上的过程回到工作队列，过程变成运行状态，继续执行代码。socket接收缓冲区已有数据，recv收到的数据可以返回。 四、网络数据全过程内核接收
这一步，贯穿网卡、中断、过程调度的知识，描述阻塞recv内核接收数据的全过程。
如下图所示，进程在recv在阻塞期间，计算机收到对端传输的数据(步骤)①）。数据通过网卡传输到内存(步骤)②），然后网卡通过中断信号通知cpu数据到达，cpu执行中断程序(步骤)③）。这里的中断程序主要有两个功能，首先将网络数据写入对应socket在接收缓冲区(步骤④），再唤醒进程A（步骤⑤），将过程A重新放入工作队列。
内核接收数据的全过程
唤醒过程如下图所示。
唤醒进程
以上是核接收数据的全过程
这里有两个思考题。让我们先想想。
首先，操作系统如何知道网络数据对应哪个？socket？
二是如何同时监控多个socket的数据？
第一个问题:因为一个socket与端口号相对应，包含在网络数据包中ip与端口信息相对应的内核可以通过端口号找到socket。当然，为了提高处理速度，操作系统将保持端口号到socket快速读取索引结构。
第二个问题是多路复用的重中之重，是本文后半部分的重点！
五、同时监控多个socket的简单方法
服务端需要管理多个客户端连接，recv只能监控单个socket，在这种矛盾下，人们开始寻求监视socket的方法。epoll本质是高效监控多重监控socket。从历史发展的角度来看，必种不太有效的方法必然会出现，人们会改进。只有先了解不太有效的方法，才能理解epoll的本质。
如果能提前进入一个socket如果列表中有列表socket没有数据，直到有一个挂起过程socket收到数据，唤醒过程。这种方法非常直接，也是select设计理念。
为了便于理解，我们先复习select的用法。在以下代码中，首先准备一个数组(以下代码中fds），让fds存储所有需要监控的存储，存储所有需要监控的存储socket。然后调用select，如果fds中的所有socket没有数据，select直到有一个socket接收到数据，select返回，唤醒过程。用户可以遍历fds，通过FD_ISSET判断具体哪一个socket收到数据，然后进行处理。
int s = socket(AF_INET, SOCK_STREAM, 0); bind(s, ...) listen(s, ...) int fds[] = 存储需要监控socket while(1){ int n = select(..., fds, ...) for(int i=0; i < fds.count; i ){ if(FD_ISSET(fds[i], ...)){ //fds[i]的数据处理 } } } select的流程
select实现的想法非常直接。如果程序同时监控下图sock1、sock2和sock3三个socket，那么在调用select之后，操作系统将过程A分别添加到这三个中socket在等待队列中。
操作系统将过程A分别添加到这三个中socket在等待队列中
当任何一个socket中断程序将在收到数据后唤起过程。下图显示sock接收数据的处理过程。
ps：recv和select中断回调可以设置为不同的内容。 sock2接收数据，中断程序唤起过程A
所谓唤起过程，就是将过程从所有等待队列中删除，加入工作队列。如下图所示。
将过程A从所有等待队列中删除，然后加入工作队列
通过这些步骤，当过程A被唤醒时，它知道至少有一个socket接收数据。程序只需要重复一遍socket列表可以得到就绪socket。
在几乎所有的操作系统中，这种简单的方法都是有效的。
但简单的方法往往有缺点，主要是：
一、每次调用select所有监控都需要添加过程socket等待队列，每次唤醒都需要从每个队列中删除。这里涉及两次遍历，每次都需要整个队列。fds列表传递给核心，有一定的费用。正是因为遍历运营费用大，出于效率考虑，才会规定select默认情况下，最大监控数量只能监控1024个socket。
其二，进程被唤醒后，程序并不知道哪些socket收到数据，还需要经历一次。
那么，有没有办法减少遍历呢？有没有就绪保存？socket方法？这两个问题是epoll技术要解决。
补充说明： 本节只解释了select一种情况。当程序调用时selec时，内核会先遍历一遍socket，如果有一个以上的socket接收缓冲区有数据，那么select直接返回，不会阻塞。这也是为什么select的返回值有可能大于1的原因之一。如果没有socket有数据，进程才会阻塞。
六、epoll的设计思路
epoll是在select出现N多年后才被发明的，是select和poll的增强版本。epoll通过以下一些措施来改进效率。
措施一：功能分离
select低效的原因之一是将“维护等待队列”和“阻塞进程”两个步骤合二为一。如下图所示，每次调用select都需要这两步操作，然而大多数应用场景中，需要监视的socket相对固定，并不需要每次都修改。epoll将这两个操作分开，先用epoll_ctl维护等待队列，再调用epoll_wait阻塞进程。显而易见的，效率就能得到提升。
相比select，epoll拆分了功能
为方便理解后续的内容，我们先复习下epoll的用法。如下的代码中，先用epoll_create创建一个epoll对象epfd，再通过epoll_ctl将需要监视的socket添加到epfd中，最后调用epoll_wait等待数据。
int s = socket(AF_INET, SOCK_STREAM, 0);
bind(s, ...)
listen(s, ...)
int epfd = epoll_create(...);
epoll_ctl(epfd, ...); //将所有需要监听的socket添加到epfd中
while(1){
int n = epoll_wait(...)
for(接收到数据的socket){
//处理
}
}
功能分离，使得epoll有了优化的可能。
措施二：就绪列表
select低效的另一个原因在于程序不知道哪些socket收到数据，只能一个个遍历。如果内核维护一个“就绪列表”，引用收到数据的socket，就能避免遍历。如下图所示，计算机共有三个socket，收到数据的sock2和sock3被rdlist（就绪列表）所引用。当进程被唤醒后，只要获取rdlist的内容，就能够知道哪些socket收到数据。
就绪列表示意图 七、epoll的原理和流程
本节会以示例和图表来讲解epoll的原理和流程。
创建epoll对象
如下图所示，当某个进程调用epoll_create方法时，内核会创建一个eventpoll对象（也就是程序中epfd所代表的对象）。eventpoll对象也是文件系统中的一员，和socket一样，它也会有等待队列。
内核创建eventpoll对象
创建一个代表该epoll的eventpoll对象是必须的，因为内核要维护“就绪列表”等数据，“就绪列表”可以作为eventpoll的成员。
维护监视列表
创建epoll对象后，可以用epoll_ctl添加或删除所要监听的socket。以添加socket为例，如下图，如果通过epoll_ctl添加sock1、sock2和sock3的监视，内核会将eventpoll添加到这三个socket的等待队列中。
添加所要监听的socket
当socket收到数据后，中断程序会操作eventpoll对象，而不是直接操作进程。
接收数据
当socket收到数据后，中断程序会给eventpoll的“就绪列表”添加socket引用。如下图展示的是sock2和sock3收到数据后，中断程序让rdlist引用这两个socket。
给就绪列表添加引用
eventpoll对象相当于是socket和进程之间的中介，socket的数据接收并不直接影响进程，而是通过改变eventpoll的就绪列表来改变进程状态。
当程序执行到epoll_wait时，如果rdlist已经引用了socket，那么epoll_wait直接返回，如果rdlist为空，阻塞进程。
阻塞和唤醒进程
假设计算机中正在运行进程A和进程B，在某时刻进程A运行到了epoll_wait语句。如下图所示，内核会将进程A放入eventpoll的等待队列中，阻塞进程。
epoll_wait阻塞进程
当socket接收到数据，中断程序一方面修改rdlist，另一方面唤醒eventpoll等待队列中的进程，进程A再次进入运行状态（如下图）。也因为rdlist的存在，进程A可以知道哪些socket发生了变化。
epoll唤醒进程 八、epoll的实现细节
至此，相信读者对epoll的本质已经有一定的了解。但我们还留有一个问题，eventpoll的数据结构是什么样子？
再留两个问题，就绪队列应该应使用什么数据结构？eventpoll应使用什么数据结构来管理通过epoll_ctl添加或删除的socket？
（——我是分割线，想好了才能往下看哦~）
如下图所示，eventpoll包含了lock、mtx、wq（等待队列）、rdlist等成员。rdlist和rbr是我们所关心的。
epoll原理示意图，图片来源：《深入理解Nginx：模块开发与架构解析(第二版)》，陶辉
就绪列表的数据结构
就绪列表引用着就绪的socket，所以它应能够快速的插入数据。
程序可能随时调用epoll_ctl添加监视socket，也可能随时删除。当删除时，若该socket已经存放在就绪列表中，它也应该被移除。
所以就绪列表应是一种能够快速插入和删除的数据结构。双向链表就是这样一种数据结构，epoll使用双向链表来实现就绪队列（对应上图的rdllist）。
索引结构
既然epoll将“维护监视队列”和“进程阻塞”分离，也意味着需要有个数据结构来保存监视的socket。至少要方便的添加和移除，还要便于搜索，以避免重复添加。红黑树是一种自平衡二叉查找树，搜索、插入和删除时间复杂度都是O(log(N))，效率较好。epoll使用了红黑树作为索引结构（对应上图的rbr）。
ps：因为操作系统要兼顾多种功能，以及由更多需要保存的数据，rdlist并非直接引用socket，而是通过epitem间接引用，红黑树的节点也是epitem对象。同样，文件系统也并非直接引用着socket。为方便理解，本文中省略了一些间接结构。
九、结论
epoll在select和poll（poll和select基本一样，有少量改进）的基础引入了eventpoll作为中间层，使用了先进的数据结构，是一种高效的多路复用技术。
再留一点作业！
下表是个很常见的表，描述了select、poll和epoll的区别。读完本文，读者能否解释select和epoll的时间复杂度为什么是O(n)和O(1)？
select、poll和epoll的区别。图片来源《Linux高性能服务器编程》