网站模板 博客,网站建设费用会计处理,做俄罗斯外贸的网站,dw软件主要做什么阻塞 IO 和 非阻塞 IO
阻塞 I/O 和 非阻塞 I/O 的主要区别#xff1a;
阻塞 I/O 执行用户程序操作是同步的#xff0c;调用线程会被阻塞挂起#xff0c;会一直等待内核的 I/O 操作完成才返回用户进程#xff0c;唤醒挂起线程非阻塞 I/O 执行用户程序操作是异步的#xf…阻塞 IO 和 非阻塞 IO
阻塞 I/O 和 非阻塞 I/O 的主要区别
阻塞 I/O 执行用户程序操作是同步的调用线程会被阻塞挂起会一直等待内核的 I/O 操作完成才返回用户进程唤醒挂起线程非阻塞 I/O 执行用户程序操作是异步的读写操作调用后内核会立即返回给用户一个状态值用户可以立即执行其他操作。
阻塞 IO 模型
应用程序调用一个 IO 函数导致应用程序阻塞等待数据准备好。 如果数据没有准备好一直等待….数据准备好了从内核拷贝到用户空间IO 函数返回成功指示。 当调用 read() 函数时系统首先查是否有准备好的数据。如果数据没有准备好那么系统就处于等待状态。当数据准备好后将数据从系统缓冲区复制到用户空间然后该函数返回。在套接应用程序中当调用 read() 函数时未必用户空间就已经存在数据那么此时 read() 函数就会处于等待状态。 非阻塞 IO 模型
我们把一个 SOCKET 接口设置为非阻塞就是告诉内核当所请求的 I/O 操作无法完成时不要将进程睡眠而是返回一个错误。这样我们的 I/O 操作函数将不断的测试数据是否已经准备好如果没有准备好继续测试直到数据准备好为止。在这个不断测试的过程中会大量的占用 CPU 的时间。该模型不被 推荐。 IO 复用模型
I/O 复用模型会用到 select、poll、epoll 函数这几个函数也会使进程阻塞但是和阻塞 I/O 所不同的的这两个函数可以同时阻塞多个 I/O 操作。而且可以同时对多个读操作多个写操作的 I/O 函数进行检测直到有数据可读或可写时才真正调用 I/O 操作函数。 当用户进程调用了 select那么整个进程会被 block而同时kernel 会“监视”所有 select 负责的 socket当任何一个 socket 中的数据准备好了select 就会返回。这个时候用户进程再调用 read 操作将数据从 kernel 拷贝到用户进程。
这个图和 blocking IO 的图其实并没有太大的不同事实上还更差一些。因为这里需要使用两个系统调用而 blocking IO 只调用了一个系统调用。但是用 select 的优势在于它可以同时处理多个 connection。
所以如果处理的连接数不是很高的话使用 select/epoll 的 web server 不一定比使用 multi-threading blocking IO 的 web server 性能更好可能延迟还更大。select/epoll 的优势并不是对于单个连接能处理得更快而是在于能处理更多的连接。
信号驱动 IO 模型
简介两次调用两次返回 首先我们允许套接口进行信号驱动 I/O并安装一个信号处理函数进程继续运行并不阻塞。当数据准备好时进程会收到一个 SIGIO 信号可以在信号处理函数中调用 I/O 操作函数处理数据。
异步 IO 模型 当一个异步过程调用发出后调用者不能立刻得到结果。实际处理这个调用的部件在完成后通过状态、通知和回调来通知调用者的输入输出操作。
多路复用的概念
先看一个例子 这里一旦使用 fgets() 方法等待标准输入就没有办法在 Socket 有数据的时候读出数据 I/O 多路复用把标准输入、Socket等都看做 I/O 的一路多路复用的意思就是在任何一路 I/O 有事件发生的情况下通知应用程序去处理相应的 I/O 事件 多路中的每一路本质上就是一个 fd 什么是 I/O 事件例如
I/O 事件一fd 对应的内核缓冲区来了数据可读I/O 事件二fd 对应的内核缓冲区空闲可写I/O 事件三fd 出现异常
多路复用技术的实现主要有
① select② poll③ epoll
I/O 多路复用就是通过一种机制一个进程可以监视多个描述符一旦某个描述符就绪一般是读就绪或者写就绪能够通知程序进行相应的读写操作。但 selectpollepoll 本质上都是同步 I/O因为他们都需要在读写事件就绪后自己负责进行读写也就是说这个读写过程是阻塞的而异步 I/O 则无需自己负责进行读写异步 I/O 的实现会负责把数据从内核拷贝到用户空间。
select 多路复用
首先应用进程需要告诉内核它感兴趣的 I/O 事件然后内核感知设备发生的 I/O 事件然后通知应用进程你感兴趣的 fd 发生了你感兴趣的 I/O 事件类型。 多路中的每一路本质上就是一个 fd。
select函数定义如下
/* According to POSIX.1-2001 */
#include sys/select.h
/* According to earlier standards */
#include sys/time.h
#include sys/types.h
#include unistd.hint select(int nfds, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout); fd_set
其中 fd_set 结构体定义如下
#define __FD_SETSIZE 1024 typedef struct {unsigned long fds_bits[__FD_SETSIZE / (8 * sizeof(long))];
} __kernel_fd_set; 这里一个 long 占 8 个字节64位系统一个字节占 8 位8 * sizeof(long) 总共占 64 位。
因此 __FD_SETSIZE / (8 * sizeof(long)) 的值是 1024/64 16即数组大小16个0-1516个 long 数组总共有 64*16 1024 位 。
所以fd_set 是长度为 1024 的比特位数组数组索引表示文件描述符。 如何设置这些描述符集合
void FD_CLR(int fd, fd_set *set);
int FD_ISSET(int fd, fd_set *set);
void FD_SET(int fd, fd_set *set);
void FD_ZERO(fd_set *set); FD_ZERO用来将这个 set 的所有元素都设置成0FD_SETset[fd] 1;FD_CLRset[fd] 0;FD_ISSETset[fd] 1 ? true : false
timeval
struct timeval {long tv_sec; /* seconds */ long tv_usec; /* microseconds */
};最后一个参数是 timeval 时间结构体
① 设置成空NULL表示如果没有 I/O 事件发生则 select 一直等待下去。② 设置一个非零的值这个表示等待固定的一段时间后从 select 阻塞调用中返回③ 将 tv_sec 和tv_usec都设置成0表示根本不等待检测完毕立即返回。这种情况使用得比较少。
select 执行流程
select 底层调用流程图https://www.processon.com/view/link/62d3fdfce401fd259605006d
下面是简要描述
int select (int n, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout);
select 函数监视的文件描述符分 3 类分别是 writefds、readfds 和 exceptfds。调用后 select 函数会阻塞直到有描述符就绪可读/可写/有except或者超时timeout 指定等待时间如果立即返回设为 null 即可函数返回。当 select 函数返回后可以通过遍历 fdset来找到就绪的描述符。fd_set是一个只包含长度为1024的比特位数组的结构体数组的索引表示文件描述符数组的值用1和0表示是否对当前索引的fd的 I/O 事件感兴趣。将这三个fd_set文件描述符拷贝到内核态的三个数组并创建三个对应的结果数组内核中for循环不断遍历 3 个fd_set数组中所有的fd看其是否有可读/可写 I/O 事件发生如果有将结果数组的对应比特位设置为1如果没有 I/O 事件发生将该fd对应进程放入等待队列中每个fd都有一个进程等待队列当fd发生 I/O 事件时会唤醒这个进程for循环结束后如果一个fd都没有 I/O 事件发生则当前调用select的进程进入休眠让出 CPU 使用权如果有某个fd发生 I/O 事件就将结果数组返回拷贝到用户态空间的三个fd_set的数组中
select 缺点 ① 支持的文件描述符的个数是有限的。在 Linux 系统中select 的默认最大值为 1024。 ② 内核会修改用户态传递的 readfds、writefds 参数的值
最佳实践多路复用 非阻塞 IO poll 多路复用
#include poll.hint poll(struct pollfd *fds, nfds_t nfds, int timeout); fdspollfd 数组存放应用进程所有感兴趣的fd及其相应的 IO 事件nfdspollfd 数组的大小可以大于1024突破文件描述符个数限制timeout超时时间 如果是一个 0 的数表示在有事件发生之前永远等待 如果是 0表示不阻塞进程立即返回 如果是一个 0 的数表示poll调用方等待指定的毫秒数后返回。
其中 pollfd 结构体定义如下
struct pollfd { int fd; /* file descriptor */ short events; /* requested events */ short revents; /* returned events */
};fd感兴趣的文件描述符events注册这个 fd 下感兴趣的 I/O 事件可读事件、可写事件等revents内核通知的这个fd下发生的 I/O 事件称为 returned events
poll 中感兴趣的 IO 事件有哪些
#define POLLIN Θx0001 /* any readable data available */
#define POLLPRI 0x0002 /* 00B/Urgent readable data */
#define POLLOUT 0x0004 /* file descriptor is writeable */#define POLLERR 0x0008 /* 一些错误发送 */
#define POLLHUP Θx0010 /* 描述符挂起 */
#define POLLNVAL Θx0020 /* 请求的事件无效 */poll 执行流程
poll 底层调用流程图https://www.processon.com/view/link/62d3fe350e3e74607274c241
其大致流程跟 select 相似
select vs poll
int poll (struct pollfd *fds, unsigned int nfds, int timeout);
不同于 select 使用三个位图来表示三个 fdset 的方式poll 使用一个 pollfd 数组实现。pollfd 结构体包含了要监视的文件描述符 fd, 对该fd感兴趣的 IO 事件 events 和内核通知 fd 下发生的 IO 事件 revents。使用nfds设置数组pollfd的大小没有最大数量限制。和 select 函数一样poll 返回后需要轮询 pollfd 来获取就绪的描述符。
最主要的区别是以下两点
select 支持最大的 fds 是 1024poll 则没有这个限制select 还需要遍历不感兴趣的 fd, 但是 poll 只关心感兴趣的 fd (不感兴趣的fd不存在pollfd数组中)
select/poll 的缺点
每次调用 select/poll 时都需要在用户态和内核态之间拷贝数据在内核中select/poll 在检测 IO 事件时只要有一个 fd 有事件发生就会线性扫描所有的 fds时间复杂度 O(n)
epoll 多路复用
epoll 是在 Linux 2.6 内核中提出的是之前的 select 和 poll 的增强版本。相对于 select 和 poll 来说epoll 更加灵活没有描述符限制。 从图中可以明显地看到epoll 的性能是最好的即使在多达 10000 个文件描述的情况下其性能的下降和有10个文件描述符的情况相比差别也不是很大。而随着文件描述符的增大常规的 select 和 poll 方法性能逐渐变得很差。
epoll 的使用
epoll_create创建 epoll 实例
#include sys/epoll.h int epoll_create(int size); 创建一个 epoll 实例从 Linux 2.6.8 开始参数 size 被忽略但是必须大于0
关于这个参数size在一开始的 epoll_create 实现中是用来告知内核期望监控fd的数量然后内核使用这部分的信息来初始化内核数据结构在新的实现中这个参数不再被需要因为内核可以动态分配需要的内核数据结构。
我们只需要注意每次将 size 设置成一个大于0的整数就可以了。
epoll_create() 返回一个文件描述符这个文件描述符对应着这个epoll实例。Linux 中一切皆文件epoll 也被看成是一个文件在内核中也有 file 实例与之对应。
epoll_ctl操作 epoll 实例中的 IO 事件
#include sys/epoll.hint epoll_ctl(int epfd, int op, int fd, struct epoll_event *event); ① epfdepoll_create 创建的 epoll 实例对应的文件描述符② op对 IO 事件的操作类型 EPOLL_CTL_ADD 向 epoll 实例添加 fd 对应的事件 EPOLL_CTL_DEL 向 epoll 实例删除 fd 对应的事件 EPOLL_CTL_MOD修改 fd 对应的事件。③ fd注册的事件的文件描述符比如一个监听套接字socket④ event表示注册的事件类型
其中 epoll_event 结构体定义如下
struct epoll_event { uint32_t events; /* Epoll events */epoll_data_t data; /* User data variable*/
};events 就表示事件类型Epoll 中的 IO 事件类型主要有以下几种
EPOLLIN表示对应的文件描述字可以读EPOLLOUT表示对应的文件描述字可以写EPOLLRDHUP表示套接字的一端已经关闭或者半关闭EPOLLHUP表示对应的文件描述字被挂起EPOLLET设置为edge-triggered默认为 level-triggered
epoll_wait等待内核 I/O 事件的分发
#include sys/epoll.hint epoll_wait(int epfd, struct epoll_event *events, int maxevents, int timeout);① epfdepoll_create 创建的 epoll 实例对应的文件描述符 ② events 接口的返回参数内核返回给用户态应用进程所有需要处理的 I/O 事件这是一个数组数组中的每个元素都是一个需要待处理的 I/O 事件。epoll 会把发生的事件的集合从内核复制到 events 数组中。 events数组是一个用户分配好大小的数组数组长度大于等于maxevents。events不可以是空指针内核只负责把数据复制到这个 events 数组中不会去帮助我们在用户态中分配内存 其中 events 表示具体的事件类型事件类型取值和 epoll_ctl 可设置的值一样 ③ maxevents一个大于0的整数表示本次 epoll_wait 可以返回的最大事件值。通常maxevents参数与预分配的events数组的大小是相等的。 ④ timeout超时事件如果这个值设置为-1表示不超时如果设置为0则立即返回即使没有任何 I/O 事件发生。设置 0 的数值则表示等待一段时间内没有事件发生则超时。
范例程序
参见目录 linux-C-net\nio 下的 C 代码这份代码未经调试不保证能正常运行意在表述 Linux 下 IO 复用网络通信代码的基本模式。
epoll 执行流程
epoll 原理图https://www.processon.com/view/link/62d3fe5a7d9c08119ce3bbbc epoll_cteate() : 内核会创建一个 eventpoll 结构体实例返回一个文件描述符与 eventpoll 实例相对应 epoll_ctl()注册感兴趣的 fd以及对该 fd 感兴趣的事件类型 epoll_wait()等待内核 IO 事件分发返回值表示要处理 IO 事件的数量最大不超过 maxevents需要返回给用户态的所有需要处理的 IO 事件存放在events数组中events数组的大小由epoll_wait()返回值决定。 用户注册的fd有 IO 事件发生时就会将其对应的 epitem 挂到一个双向链表rdllist中位于eventpoll 结构体中 epoll_wait 就是在一个循环中不断查看这个rdllist链表中是否有就绪事件如果有就将就绪事件返回拷贝到用户空间中如果没有当前进程就进入休眠CPU 被调度给其他进程使用 进程被唤醒的条件 1进程超时 2进程收到一个signal信号 3某个fd上有事件发生 4当前进程被CPU重新调度
epoll vs select/poll
select/poll 的缺点 ① 每次调用 select/poll 时都需要在用户态/内核态之间进行拷贝数据 ② 在内核中select/poll 在检测 IO 事件时只要有一个 fd 有事件发生就会线性扫描所有的 fds时间复杂度 O(n)
与 select/poll 的缺点相比epoll 的高效之处是
① 将应用进程关心的 fd 直接维护在内核中不再进行用户态和内核态间的拷贝使用红黑树维护高效增删改② epoll 只处理有 IO 事件发生的 fd不会扫描所有的 fds时间复杂度 O(1) 条件触发 和 边缘触发
条件触发Level_triggered又叫水平触发当被监控的文件描述符上有可读写事件发生时epoll_wait()会通知处理程序去读写。如果这次没有把数据一次性全部读写完如读写缓冲区太小那么下次调用 epoll_wait() 时它还会通知你在上没读写完的文件描述符上继续读写当然如果你一直不去读写它会一直通知你如果系统中有大量你不需要读写的就绪文件描述符而它们每次都会返回这样会大大降低处理程序检索自己关心的就绪文件描述符的效率
边缘触发Edge_triggered当被监控的文件描述符上有可读写事件发生时epoll_wait() 会通知处理程序去读写。如果这次没有把数据全部读写完如读写缓冲区太小那么下次调用 epoll_wait() 时它不会通知你也就是它只会通知你一次直到该文件描述符上出现第二次可读写事件才会通知你这种模式比水平触发效率高系统不会充斥大量你不关心的就绪文件描述符
总结
条件触发只要满足事件的条件比如有数据需要读就一直不断的把这个事件传递给用户边缘触发只有第一次满足条件的时候才触发之后就不会再传递同样的事件了边缘触发的效率比条件触发的效率高epoll 支持边缘触发和条件触发默认是条件触发select 和 poll 都是条件触发
epoll 高效原理和底层机制详细分析
总述 当某一进程调用 epoll_create() 方法时Linux 内核会创建一个 eventpoll 结构体在内核 cache 里建了个红黑树用于存储以后 epoll_ctl() 传来的 socket 外还会再建立一个 rdllist 双向链表用于存储准备就绪的事件当 epoll_wait() 调用时仅仅观察这个 rdllist 双向链表里有没有数据即可。有数据就返回没有数据就 sleep等到 timeout 时间到后即使链表没数据也返回。 同时所有添加到 epoll 中的事件都会与设备如网卡驱动程序建立回调关系也就是说相应事件的发生时会调用这里的回调方法。这个回调方法在内核中叫做 ep_poll_callback它会把这样的事件放到上面的 rdllist 双向链表中。 当调用 epoll_wait() 检查是否有发生事件的连接时只是检查 eventpoll 对象中的 rdllist 双向链表是否有 epitem 元素而已如果 rdllist 链表不为空则这里的事件复制到用户态内存使用共享内存提高效率中同时将事件数量返回给用户。因此 epoll_wait() 效率非常高可以轻易地处理百万级别的并发连接。
从网卡接收数据说起
一个典型的计算机结构图计算机由 CPU、存储器内存、网络接口等部件组成。了解 epoll 本质的第一步要从硬件的角度看计算机怎样接收网络数据。 网卡接收数据的过程网卡收到网线传来的数据经过硬件电路的传输最终将数据写入到内存中的某个地址上。这个过程涉及到 DMA 传输、IO 通路选择等硬件有关的知识但我们只需知道网卡会把接收到的数据写入内存。操作系统就可以去读取它们。
如何知道接收了数据
CPU 的如何知道网络上有数据要接收很简单使用中断机制。
进程阻塞
了解 epoll 本质要从操作系统进程调度的角度来看数据接收。阻塞是进程调度的关键一环指的是进程在等待某事件如接收到网络数据发生之前的等待状态recv、select 和 epoll 都是阻塞方法。了解“进程阻塞为什么不占用 cpu资源”也就能够了解这一步。
为简单起见我们从普通的 recv 接收开始分析先看看下面代码
int s socket(AF_INET, SOCK_STREAM, 0); // 创建 socket
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 执行到创建 socket 的语句时操作系统会创建一个由文件系统管理的 socket 对象。这个 socket 对象包含了发送缓冲区、接收缓冲区、等待队列等成员。等待队列是个非常重要的结构它指向所有需要等待该 socket 事件的进程。
当程序执行到 recv 时操作系统会将进程 A 从工作队列移动到该 socket 的等待队列中如下图。由于工作队列只剩下了进程 B 和 C依据进程调度cpu 会轮流执行这两个进程的程序不会执行进程 A 的程序。所以进程 A 被阻塞不会往下执行代码也不会占用 cpu 资源。 操作系统添加等待队列只是添加了对这个“等待中”进程的引用以便在接收到数据时获取进程对象、将其唤醒而非直接将进程管理纳入自己之下。上图为了方便说明直接将进程挂到等待队列之下。
当 socket 接收到数据后操作系统将该 socket 等待队列上的进程重新放回到工作队列该进程变成运行状态继续执行代码。也由于 socket 的接收缓冲区已经有了数据recv 可以返回接收到的数据。
内核接收网络数据全过程 进程在 recv 阻塞期间计算机收到了对端传送的数据步骤①。数据经由网卡传送到内存步骤②然后网卡通过中断信号通知 cpu 有数据到达cpu 执行中断程序步骤③。此处的中断程序主要有两项功能先将网络数据写入到对应 socket 的接收缓冲区里面步骤④再唤醒进程 A步骤⑤重新将 进程 A 放入工作队列中。
思考下操作系统如何知道网络数据对应于哪个 socket
因为一个 socket 对应着一个端口号而网络数据包中包含了 ip 和端口的信息内核可以通过端口号找到对应的 socket。当然为了提高处理速度操作系统会维护端口号到 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 fds[] 存放需要监听的 socket
while(1) {int n select(..., fds, ...)for(int i0; i fds.count; i) {if (FD_ISSET(fds[i], ...)) {// fds[i]的数据处理}}
}select 的实现思路很直接。假如程序同时监视 sock1、sock2 和 sock3 三个socket那么在调用 select 之后操作系统把进程 A 分别加入这三个 socket 的等待队列中。 当任何一个 socket 收到数据后中断程序将唤起进程。所谓唤起进程就是将进程从所有的等待队列中移除加入到工作队列里面。
经由这些步骤当进程 A 被唤醒后它知道至少有一个 socket 接收了数据。程序只需遍历一遍 socket 列表就可以得到就绪的 socket。
这种简单方式行之有效在几乎所有操作系统都有对应的实现。
但是简单的方法往往有缺点主要是 其一每次调用 select 都需要将进程加入到所有被监视 socket 的等待队列每次唤醒都需要从每个队列中移除都必须要进行遍历。而且每次都要将整个 fds 列表传递给内核有一定的开销。正是因为遍历操作开销大出于效率的考量才会规定 select 的最大监视数量默认只能监视 1024 个 socket。 其二进程被唤醒后程序并不知道哪些 socket 收到数据还需要遍历一次。
那么有没有减少遍历的方法有没有保存就绪 socket 的方法这两个问题便是 epoll 技术要解决的。
当然当程序调用 select 时内核会先遍历一遍 socket如果有一个以上的 socket 接收缓冲区有数据那么 select 直接返回不会阻塞。这也是为什么 select 的返回值有可能大于 1 的原因之一。如果没有 socket 有数据进程才会阻塞。
epoll 的设计思路
epoll 是在 select 出现 N 多年后才被发明的是 select 和 poll 的增强版本。
epoll 通过以下一些措施来改进效率 措施一功能分离 select 低效的原因之一是将“维护等待队列”和“阻塞进程”两个步骤合二为一。每次调用 select 都需要这两步操作然而大多数应用场景中需要监视的 socket 相对固定并不需要每次都修改。epoll 将这两个操作分开先用 epoll_ctl 维护等待队列再调用 epoll_wait 阻塞进程。显而易见的效率就能得到提升。
相比 selectepoll 拆分了功能。
为方便理解后续的内容我们先复习下 epoll 的用法。如下的代码中先用 epoll_create 创建一个 epoll 对象 epfd再通过 epoll_ctl 将需要监视的 socket 添加到 epfd 中最后调用 epoll_wait 等待数据。
int epfd epoll_create(...);
epoll_ctl(epfd, ...); // 将所有需要监听的 socket 添加到 epfd 中
while(1) {int n epoll_wait(...)for (接收到数据的 socket) {// 处理}
}功能分离使得 epoll 有了优化的可能。 措施二就绪列表 select 低效的另一个原因在于程序不知道哪些 socket 收到数据只能一个个遍历。如果内核维护一个“就绪列表”引用收到数据的 socket就能避免遍历。
epoll 的原理和流程
当某个进程调用 epoll_create 方法时内核会创建一个 eventpoll 对象也就是程序中 epfd 所代表的对象。eventpoll 对象也是文件系统中的一员和 socket 一样它也会有等待队列。
创建 epoll 对象后可以用 epoll_ctl 添加或删除所要监听的 socket。以添加 socket 为例如下图如果通过 epoll_ctl 添加 sock1、sock2 和 sock3 的监视内核会将 eventpoll 添加到这三个 socket 的等待队列中。 当 socket 收到数据后中断程序会操作 eventpoll 对象而不是直接操作进程。中断程序会给 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
struct eventpoll {/** This mutex is used to ensure that files are not removed* while epoll is using them. This is held during the event * collection loop, the file cleanup path, the epoll file exit* code and the ctl operations. */struct mutex mtx;/* Wait queue used by sys_epoll_wait()*/ wait_queue_head_t wq;/* Wait queue used by file-pol1()*/ wait_queue_head_t poll_wait;/* List of ready file descriptors */ struct list_head rdllist;/* Lock which protects rdllist and ovflist */ rwlock_t lock;/* RB tree root used to store monitored fd structs */ struct rb_root_cached rbr;/** This is a single linked list that chains all the struct epitem that* happened while transferring ready events to userspace w/out* holding -lock.*/struct epitem *ovflist;/* wakeup_source used when ep_scan_ready_list is running */ struct wakeup_source *wsj/* The user that created the eventpoll descriptor */ struct user_struct *user;struct file *file;/* used to optimize loop detection check */ u64 gen;
}就绪列表引用着就绪的 socket所以它应能够快速的插入数据。
程序可能随时调用 epoll_ctl 添加监视 socket也可能随时删除。当删除时若该 socket 已经存放在就绪列表中它也应该被移除。
所以就绪列表应是一种能够快速插入和删除的数据结构。双向链表就是这样一种数据结构epoll 使用双向链表来实现就绪队列也就是 Linux 源码中的rdllist
/* List of ready file descriptors */
struct list_head rdllist;既然 epoll 将“维护监视队列”和“进程阻塞”分离也意味着需要有个数据结构来保存监视的 socket。至少要方便的添加和移除还要便于搜索以避免重复添加。红黑树是一种自平衡二叉查找树搜索、插入和删除时间复杂度都是 O(log(N))效率较好。epoll 使用了红黑树作为索引结构也就是 Linux 源码中的rbr
/* RB tree root used to store monitored fd structs */
struct rb_root_cached rbr;eventpoll中的rbr成员变量指向红黑树的根节点而rdlist成员变量指向双链表的头结点。
因为操作系统要兼顾多种功能以及由更多需要保存的数据rdlist 并非直接引用 socket而是通过 epitem 间接引用红黑树的节点也是 epitem 对象。
struct epitem {RB_ENTRY(epitem) rbn;/* RB_ENTRY(epitem) rbn等价于struct { struct type *rbe_left; //指向左子树struct type *rbe_right; //指向右子树struct type *rbe_parent; //指向父节点int rbe_color; //该节点的颜色} rbn*/LIST_ENTRY(epitem) rdlink;/* LIST_ENTRY(epitem) rdlink等价于struct { struct type *le_next; //指向下个元素struct type **le_prev; //前一个元素的地址}*/int rdy; //判断该节点是否同时存在与红黑树和双向链表中int sockfd; //socket句柄struct epoll_event event; //存放用户填充的事件
};结论
epoll 在 select 和 pollpoll 和 select 基本一样有少量改进的基础引入了 eventpoll 作为中间层使用了红黑树和双向链表等先进的数据结构是一种高效的多路复用技术。
