EPOLL原理详解（图⽂并茂）
⽂章核⼼思想是：
要清晰明⽩EPOLL为什么性能好。
⼀、从⽹卡接收数据说起
下图是⼀个典型的计算机结构图，计算机由CPU、存储器（内存）、⽹络接⼝等部件组成。了解epoll本质的第⼀步，要从硬件的⾓度看计算机怎样接收⽹络数据。
下图展⽰了⽹卡接收数据的过程。在①阶段，⽹卡收到⽹线传来的数据；经过②阶段的硬件电路的传输；最终将数据写⼊到内存中的某个地址上（③阶段）。这个过程涉及到DMA传输、IO通路选择等硬件有关的知识，但我们只需知道：⽹卡会把接收到的数据写⼊内存。
通过硬件传输，⽹卡接收的数据存放到内存中。操作系统就可以去读取它们。
⼆、如何知道接收了数据？
了解epoll本质的第⼆步，要从CPU的⾓度来看数据接收。要理解这个问题，要先了解⼀个概念——中断。
计算机执⾏程序时，会有优先级的需求。⽐如，当计算机收到断电信号时（电容可以保存少许电量，供CPU运⾏很短的⼀⼩段时间），它应⽴即去保存数据，保存数据的程序具有较⾼的优先级。
⼀般⽽⾔，由硬件产⽣的信号需要cpu⽴马做出回应（不然数据可能就丢失），所以它的优先级很⾼。cpu理应中断掉正在执⾏的程序，去做出响应；当cpu完成对硬件的响应后，再重新执⾏⽤户程序。中断的过程如下图，和函数调⽤差不多。只不过函数调⽤是事先定好位置，⽽中断的位置由“信号”决定。
以键盘为例，当⽤户按下键盘某个按键时，键盘会给cpu的中断引脚发出⼀个⾼电平。cpu能够捕获这个信号，然后执⾏键盘中断程序。下图展⽰了各种硬件通过中断与cpu交互。
现在可以回答本节提出的问题了：当⽹卡把数据写⼊到内存后，⽹卡向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时，它会⼀直等待，直到接收到数据才往下执⾏。
那么阻塞的原理是什么？
⼯作队列
操作系统为了⽀持多任务，实现了进程调度的功能，会把进程分为“运⾏”和“等待”等⼏种状态。运⾏状态是进程获得cpu使⽤权，正在执⾏代码的状态；等待状态是阻塞状态，⽐如上述程序运⾏到recv时，程序会从运⾏状态变为等待状态，接收到数据后⼜变回运⾏状态。操作系统会分时执⾏各个运⾏状态的进程，由于速度很快，看上去就像是同时执⾏多个任务。
下图中的计算机中运⾏着A、B、C三个进程，其中进程A执⾏着上述基础⽹络程序，⼀开始，这3个进程都被操作系统的⼯作队列所引⽤，处于运⾏状态，会分时执⾏。
⼯作队列中有A、B和C三个进程
等待队列
当进程A执⾏到创建socket的语句时，操作系统会创建⼀个由⽂件系统管理的socket对象（如下图）。这个socket对象包含了发送缓冲区、接收缓冲区、等待队列等成员。等待队列是个⾮常重要的结构，它指向所有需要等待该socket事件的进程。
当程序执⾏到recv时，操作系统会将进程A从⼯作队列移动到该socket的等待队列中（如下图）。由于⼯作队列只剩下了进程B和C，依据进程调度，cpu会轮流执⾏这两个进程的程序，不会执⾏进程A的程序。所以进程A被阻塞，不会往下执⾏代码，也不会占⽤cpu资源。
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 < unt; i++){
if(FD_ISSET(fds[i], ...)){
//fds[i]的数据处理
}
}
}
select的流程
select的实现思路很直接。假如程序同时监视如下图的sock1、sock2和sock3三个socket，那么在调⽤select之后，操作系统把进程A分别加⼊这三个socket的等待队列中。
当任何⼀个socket收到数据后，中断程序将唤起进程。下图展⽰了sock2接收到了数据的处理流程。
ps：recv和select的中断回调可以设置成不同的内容。
所谓唤起进程，就是将进程从所有的等待队列中移除，加⼊到⼯作队列⾥⾯。如下图所⽰。
经由这些步骤，当进程A被唤醒后，它知道⾄少有⼀个socket接收了数据。程序只需遍历⼀遍socket列表，就可以得到就绪的socket。
这种简单⽅式⾏之有效，在⼏乎所有操作系统都有对应的实现。
但是简单的⽅法往往有缺点，主要是：
其⼀，每次调⽤select都需要将进程加⼊到所有监视socket的等待队列，每次唤醒都需要从每个队列中移除。这⾥涉及了两次遍历，⽽且每次都要将整个fds列表传递给内核，有⼀定的开销。正是因为遍历操作开销⼤，出于效率的考量，才会规定select的最⼤监视数量，默认只能监视1024个socket。
其⼆，进程被唤醒后，程序并不知道哪些socket收到数据，还需要遍历⼀次。
那么，有没有减少遍历的⽅法？有没有保存就绪socket的⽅法？这两个问题便是epoll技术要解决的。
补充说明：本节只解释了select的⼀种情形。当程序调⽤select时，内核会先遍历⼀遍socket，如果有⼀个以上的socket接收缓冲区有数据，那么select直接返回，不会阻塞。这也是为什么select的返回值有可能⼤于1的原因之⼀。如果没有socket有数据，进程才会阻塞。
六、epoll的设计思路
epoll是在select出现N多年后才被发明的，是select和poll的增强版本。epoll通过以下⼀些措施来改进效率。
措施⼀：功能分离
select低效的原因之⼀是将“维护等待队列”和“阻塞进程”两个步骤合⼆为⼀。如下图所⽰，每次调⽤select都需要这两步操作，然⽽⼤多数应⽤场景中，需要监视的socket相对固定，并不需要每次都修改。epoll将这两个操作分开，先⽤epoll_ctl维护等待队列，再调⽤epoll_wait阻塞进程。显⽽易见的，效率就能得到提升。
为⽅便理解后续的内容，我们先复习下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⼀样，它也会有等待队列。
创建⼀个代表该epoll的eventpoll对象是必须的，因为内核要维护“就绪列表”等数据，“就绪列表”可以作为eventpoll的成员。
维护监视列表
创建epoll对象后，可以⽤epoll_ctl添加或删除所要监听的socket。以添加socket为例，如下图，如果通过epoll_ctl添加sock1、sock2和sock3的监视，内核会将eventpoll添加到这三个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的等待队列中，阻塞进程。
当socket接收到数据，中断程序⼀⽅⾯修改rdlist，另⼀⽅⾯唤醒eventpoll等待队列中的进程，进程A再次进⼊运⾏状态（如下图）。也因为rdlist的存在，进程A可以知道哪些socket发⽣了变化。
⼋、epoll的实现细节
⾄此，相信读者对epoll的本质已经有⼀定的了解。但我们还留有⼀个问题，eventpoll的数据结构是什么样⼦？
再留两个问题，就绪队列应该应使⽤什么数据结构？eventpoll应使⽤什么数据结构来管理通过epoll_ctl添加或删除的socket？
如下图所⽰，eventpoll包含了lock、mtx、wq（等待队列）、rdlist等成员。rdlist和rbr是我们所关⼼的。
就绪列表的数据结构
就绪列表引⽤着就绪的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作为中间层，使⽤了先进的数据结构，是⼀种⾼效的多路复⽤技术。
发布评论