转载地址：如果本文说不清楚epoll来掐死我吧！ （1） - 知乎
下图是典型的计算机结构图，由计算机组成CPU、由存储器(内存)、网络接口等组成。epoll本质的，要从从计算机如何接收网络数据的角度来看。
计算机结构图(图片来源:linux微型计算机组成结构内核完全注释)
下图显示了网卡接收数据的过程。①在这个阶段，网卡收到网线的数据；经过②硬件电路传输阶段；最后将数据写入内存中的地址（③阶段)。这个过程涉及到。DMA传输、IO硬件相关知识，如通道选择，但我们只需要知道：
网卡接收数据的过程
网卡接收的数据通过硬件传输存储在内存中。操作系统可以读取它们。
了解epoll本质的，要从从数据接收的角度来看。要理解这个问题，首先要理解一个概念-中断。
计算机执行程序时，会有优先级要求。例如，当计算机收到断电信号时(电容器可以保存一点电源CPU短时间运行)，应立即保存数据，保存数据的程序优先级较高。
一般来说，硬件产生的信号需要cpu立即做出回应(否则数据可能会丢失)，因此其优先级很高。cpu应中断正在执行的程序并做出响应；当cpu在完成对硬件的响应后，重新执行用户程序。中断过程如下图所示，类似于函数调用。但函数调用是提前设置位置，中断位置由信号决定。
调用中断程序
以键盘为例，当用户按下键盘时，键盘会给出cpu中断引脚产生高电平。cpu它可以捕获信号，然后执行键盘中断程序。下图显示了各种硬件通过中断和中断cpu交互。
cpu中断(图片来源:net.pku.edu.cn）
本节提出的问题现在可以回答了：当网卡将数据写入内存时，，再通过网卡处理数据。
了解epoll本质的，要从从数据接收的角度来看。阻塞是过程调度的关键环节，是指等待事件（如接收网络数据）发生前的等待状态，recv、select和epoll都是阻塞方法。。
为了简单起见，我们来自普通人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的程序。。
socket的等待队列
ps：在操作系统中添加等待队列只是对等待过程的参考，以获取过程对象并在收到数据时唤醒它，而不是直接将过程管理纳入自己为了方便说明，上图直接将过程挂在等待列下。
当socket操作系统接收到数据后，会socket等待队列上的过程回到工作队列，过程变成运行状态，继续执行代码。socket接收缓冲区已有数据，recv收到的数据可以返回。
如下图所示，进程在recv在阻塞期间，计算机收到对端传输的数据(步骤)①）。数据通过网卡传输到内存(步骤)②），然后网卡通过中断信号通知cpu数据到达，cpu执行中断程序(步骤)③）。这里的中断程序主要有两个功能，首先将网络数据写入对应socket在接收缓冲区(步骤④），再唤醒进程A（步骤⑤），将过程A重新放入工作队列。
内核接收数据的全过程
唤醒过程如下图所示。
唤醒进程
这里有两个思考题。让我们先想想。
首先，操作系统如何知道网络数据对应哪个？socket？
二是如何同时监控多个socket的数据？
第一个问题:因为一个socket与端口号相对应，包含在网络数据包中ip与端口信息相对应的内核可以通过端口号找到socket。当然，为了提高处理速度，操作系统将保持端口号到socket快速读取索引结构。
第二个问题是是本文后半部分的重点！
服务端需要管理多个客户端连接，recv只能监控单个socket，在这种矛盾下，人们开始寻求监视socket的方法。epoll的要义是的监视多个socket。从历史发展的角度来看，必种不太有效的方法必然会出现，人们会改进。只有先了解不太有效的方法，才能理解epoll的本质。
如果能提前进入一个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的实现思路很直接。假如程序同时监视如下图的sock1、sock2和sock3三个socket，那么在调用select之后，操作系统把进程A分别加入这三个socket的等待队列中。
操作系统把进程A分别加入这三个socket的等待队列中
当任何一个socket收到数据后，中断程序将唤起进程。下图展示了sock2接收到了数据的处理流程。
ps：recv和select的中断回调可以设置成不同的内容。
sock2接收到了数据，中断程序唤起进程A
所谓唤起进程，就是将进程从所有的等待队列中移除，加入到工作队列里面。如下图所示。
将进程A从所有等待队列中移除，再加入到工作队列里面
经由这些步骤，当进程A被唤醒后，它知道至少有一个socket接收了数据。程序只需遍历一遍socket列表，就可以得到就绪的socket。
这种简单方式，在几乎所有操作系统都有对应的实现。
其一，每次调用select都需要将进程加入到所有监视socket的等待队列，每次唤醒都需要从每个队列中移除。这里涉及了两次遍历，而且每次都要将整个fds列表传递给内核，有一定的开销。正是因为遍历操作开销大，出于效率的考量，才会规定select的最大监视数量，默认只能监视1024个socket。
其二，进程被唤醒后，程序并不知道哪些socket收到数据，还需要遍历一次。
那么，有没有减少遍历的方法？有没有保存就绪socket的方法？这两个问题便是epoll技术要解决的。
补充说明： 本节只解释了select的一种情形。当程序调用select时，内核会先遍历一遍socket，如果有一个以上的socket接收缓冲区有数据，那么select直接返回，不会阻塞。这也是为什么select的返回值有可能大于1的原因之一。如果没有socket有数据，进程才会阻塞。
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_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的本质已经有一定的了解。但我们还留有一个问题，是什么样子？
再留两个问题，应该应使用什么数据结构？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高性能服务器编程》