图解epoll原理

mark

poll翻译过来是轮询的意思, 可以看到poll和epoll都有轮询的过程, 不同点在于:poll轮询的是所有的socket,而epoll只轮询就绪的socket。 epoll是开发linux高性能服务器的必备技术至,epoll本质,是服务端程序员的必须掌握的知识。 本文主要是利用图文讲述了select的原理和epoll相对于做出的优化,以及epoll的部分细节问题。

从硬件理解网卡接收数据过程

下图是一个典型的计算机结构图,计算机由CPU、存储器(内存)、网络接口等部件组成。了解epoll本质的第一步,要从硬件的角度看计算机怎样接收网络数据。 下面这幅图在我的另一篇文章里也用到了,《冯诺依曼架构》

img

网卡收到网线传来的数据,通过硬件电路传输,网卡接收的数据存放到内存中,操作系统就可以去读取它们。

正确理解CPU中断

一般而言,由硬件产生的信号需要CPU立马做出处理,不然数据可能就丢失,所以它的优先级很高。CPU理应中断掉正在执行的程序,去做出响应;当CPU完成对硬件的响应后,再重新执行用户程序。 比如我们按下键盘上的按键,会触发中断即(键盘会给cpu的中断引脚发出一个高电平,CPU能够捕获这个信号,然后执行键盘中断程序。)网卡也是硬件设备,和键盘不同的是我们用键盘可以主动触发中断,而网卡是收到数据之后向CPU发出信号,触发中断程序,即CPU去处理网卡设备的数据!

mark

什么是一切皆文件

在Java的学习中,我们可以有深刻的体会,那就是一切皆对象;在Linux的学习中,一切皆文件的理念无处不在,文档、目录、磁盘驱动器、CD-ROM、调制解调器、键盘、打印机、显示器、终端,甚至是一些进程间通信和网络通信。所有这些资源拥有一个通用的抽象,在Linux中将其称为“文件”,其实Unix就是这种思想,所以Linux也借鉴了这个思想,因为每个“文件”都通过相同的 API 暴露出来,所以你可以使用同一组基本命令来读取和写入磁盘、键盘、文档或网络设备, “一切皆文件”的思想提供了一个强大而简单的抽象,那就是无论是硬件设备、还是网络连接、还是我们日常解除的文件,都是文件,这样使得API的设计可以化繁为简,用户可以使用通用的方式去访问任何资源,自有相应的中间件做好对底层的适配。 所以在Linux操作系统看来,一切都是文件,也就意味着,网卡设备也是文件,Socket连接也是文件,文件的统一抽象使得都有共同的属性,我们这里只谈最重要的文件属性——文件描述符(file descriptor,简写fd)!

mark

内核接收网络数据过程

数据经由网卡传送到内存,然后网卡通过中断信号通知CPU有数据到达,CPU执行中断程序。此处的中断程序主要有两项功能,先将网络数据写入到对应socket的接收缓冲区里面,再唤醒进程A,重新将进程A放入工作队列中。

mark

唤醒进程的过程如图所示:

mark

操作系统如何知道网络数据对应于哪个socket呢?因为一个socket对应着一个端口号,而网络数据包中包含了ip和端口的信息,内核可以通过端口号找到对应的socket。当然,为了提高处理速度,操作系统会维护端口号到socket的索引结构,以快速读取。

select如何同时监视多个socket

假如能够预先传入一个Socket列表,如果列表中的socket都没有数据,挂起进程,直到有一个socket收到数据,唤醒进程。这种方法很直接,也是select的设计思想。

先复习select的用法。在如下的代码中,先准备一个数组(下面代码中的fds),让fds存放着所有需要监视的socket。然后调用select,如果fds中的所有socket都没有数据,select会阻塞,直到有一个socket接收到数据,select返回,唤醒进程。用户可以遍历fds,通过FD_ISSET判断具体哪个socket收到数据,然后做出处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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]的数据处理
}
}
}

mark

select的实现思路很直接,假如程序同时监视如下图的sock1、sock2和sock3三个socket,那么在调用select之后,操作系统把进程A分别加入这三个socket的等待队列中。

mark

当任何一个socket收到数据后,中断程序将唤起进程。下图展示了socket2接收到了数据的处理流程。

mark

经由这些步骤,当进程A被唤醒后,它知道至少有一个socket接收了数据。程序只需遍历一遍socket列表,就可以得到就绪的socket。这种简单方式行之有效,在几乎所有操作系统都有对应的实现。

我们不难发现:每次调用select都需要将进程加入到所有监视socket的等待队列,每次唤醒都需要从每个队列中移除。这里涉及了两次遍历,而且每次都要将整个fds列表(即文件描述符列表,上图中写的是文件列表)传递给内核,有一定的开销。正是因为遍历操作开销大,出于效率的考量,才会规定select的最大监视数量,默认只能监视1024个socket。 进程被唤醒后,程序并不知道哪些socket收到数据,还需要遍历一次。

  • 当程序调用select时,内核会先遍历一遍socket,如果有一个以上的socket接收缓冲区有数据,那么select直接返回文件描述符状态已改变的个数,不会阻塞;
  • 如果没有socket有数据,且没有超过timeout时间,进程才会阻塞;
  • 如果返回0,代表在描述符状态改变前已超过timeout时间;
  • 如果有错误返回的是-1,错误原因存于errno。

epoll如何改进效率的

措施一:功能分离

还记得select的输入输出型参数吗fd_set吗?fd_set是一个位图,使用位图中对应的位来表示要监视的文件描述符。所以select能监视的socket有上限,我的centos支持的描述符上限是1024个。

select低效的原因之一是将维护等待队列阻塞进程两个步骤合二为一。如下图所示,每次调用select都需要这两步操作

mark

如果上图看不懂,先复习本文中select用法的伪代码,然后复习下epoll的用法。如下的代码中,先用epoll_create创建一个epoll对象epfd,再通过epoll_ctl将需要监视的socket添加到epfd中,最后调用epoll_wait等待数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
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){
//处理
}
}

通过以上代码是不是可以看出,对于select来说,每次都要传入文件描述符列表(虽然是位图,但是信息表达的就是一个文件描述符列表),而对于epoll来说,只传入了一次文件描述符列表; 功能分离,使得epoll有了优化的可能。

措施二: 就绪列表

select低效的另一个原因在于程序不知道哪些socket收到数据,只能一个个遍历。如果内核维护一个“就绪列表”,引用收到数据的socket,就能避免遍历。

如下图所示,计算机共有三个socket,收到数据的sock2和sock3被rdlist(就绪列表)所引用。当进程被唤醒后,只要获取rdlist的内容,就能够知道哪些socket收到数据。

mark

epoll的原理的流程

创建epoll对象

如下图所示,当某个进程调用epoll_create方法时,内核会创建一个eventpoll对象(也就是程序中epfd所代表的对象)。eventpoll对象也是文件系统中的一员,和socket一样,它也会有等待队列。

mark

创建一个代表该epoll的eventpoll对象是必须的,因为内核要维护就绪列表等数据,就绪列表作为eventpoll的成员。

维护监视列表

创建epoll对象后,可以用epoll_ctl添加或删除所要监听的socket。以添加socket为例,如下图,如果通过epoll_ctl添加sock1、sock2和sock3的监视,内核会将eventpoll添加到这三个socket的等待队列中。

mark

当socket收到数据后,中断程序会操作eventpoll对象,而不是直接操作进程

接收数据

当socket收到数据后,中断程序会给eventpoll的就绪列表添加socket引用。如下图展示的是sock2和sock3收到数据后,中断程序让rdlist引用这两个socket

mark

eventpoll对象相当于是socket和进程之间的中介,socket的数据接收并不直接影响进程,而是通过改变eventpoll的就绪列表来改变进程状态。 当程序执行到epoll_wait时,如果rdlist已经引用了socket,那么epoll_wait直接返回,如果rdlist为空,阻塞进程。

阻塞和唤醒进程

假设计算机中正在运行进程A和进程B,在某时刻进程A运行到了epoll_wait语句。如下图所示,内核会将进程A放入eventpoll的等待队列中,阻塞进程。

mark

当socket接收到数据,中断程序一方面修改rdlist,另一方面唤醒eventpoll等待队列中的进程,进程A再次进入运行状态(如下图)。也因为rdlist的存在,进程A可以知道哪些socket发生了变化。

mark

epoll的实现细节

eventpoll的数据结构是什么样子? 就绪队列应该应使用什么数据结构?eventpoll应使用什么数据结构来管理通过epoll_ctl添加或删除的socket?

如下图所示,eventpoll包含了lock、mtx、wq(等待队列)、rdlist等成员。rdlist和rbr是我们所关心的。

mark

就绪列表引用着就绪的socket,所以它应能够快速的插入数据。 程序可能随时调用epoll_ctl添加监视socket,也可能随时删除。当删除时,若该socket已经存放在就绪列表中,它也应该被移除。

所以就绪列表应是一种能够快速插入和删除的数据结构。双向链表就是这样一种数据结构,epoll使用双向链表来实现就绪队列(对应上图的rdllist)

既然epoll将维护监视队列进程阻塞分离,也意味着需要有个数据结构来保存监视的socket。至少要方便的添加和移除,还要便于搜索,以避免重复添加。红黑树是一种自平衡二叉查找树,搜索、插入和删除时间复杂度都是O(log(N)),效率较好。epoll使用了红黑树作为索引结构(对应上图的rbr)。

因为操作系统要兼顾多种功能,以及由更多需要保存的数据,rdlist并非直接引用socket,而是通过epitem间接引用,红黑树的节点也是epitem对象。同样,文件系统也并非直接引用着socket。为方便理解,本文中省略了一些间接结构。

总结3种多路复用

mark

打赏
  • © 2018-2020 changlin zou
    • Page View:
    • Unique Visitor:

请我喝杯咖啡吧~

支付宝
微信