【第128期】一道搜狗面试题：IO复用中select、poll、epoll的区别

(1)select==>时间复杂度O(n) 它只知道发生了一个I/O事件，但不知道是哪些流（可能有一个、多个、甚至全部）。我们只能不加区别地轮询所有流来找出哪些流可以读取。数据，或写入数据并对其进行操作的流。因此 select 的无差别轮询复杂度为 O(n)。同时处理的流越多，乱轮询时间就越长。 (2)poll==>时间复杂度O(n) poll 本质上与 select 相同。它将用户传入的数组复制到内核空间，然后查询每个fd对应的设备状态。但它对最大连接数没有限制，因为它是基于链表存储的。 (3)epoll==>时间复杂度O(1) epoll可以理解为事件轮询。与忙轮询和无差别轮询不同，epoll 会通知我们哪个流中发生了哪个 I/O 事件。所以我们说epoll实际上是事件驱动的（每个事件都与fd相关联）。这个时候我们对这些流的操作就有意义了。 （复杂度降低至O(1)） select、poll、epoll都是IO复用机制。 I/O 多路复用使用一种机制来监视多个描述符。一旦某个描述符准备好（通常是读准备好或者写准备好），就可以通知程序执行相应的读写操作。但select、poll、epoll本质上都是同步I/O，因为它们都需要在读写事件就绪后负责读写，也就是说读写过程是阻塞的，而异步I/O不要求他们自己这样做。负责读写，异步I/O的实现会负责将数据从内核复制到用户空间。 epoll和select都可以提供多路I/O复用解决方案。所有这些都可以在当前的 Linux 内核中得到支持。其中，epoll是Linux特有的，而select则应该由POSIX规定，在通用操作系统中实现。 选择： Select本质上是通过设置或检查存储fd标志的数据结构来执行下一步处理。这样做的缺点是： 1、单个进程可以监听的fd数量有限，即监听端口大小有限。 一般来说，这个数字与系统内存有很大关系。具体数量可以通过cat /proc/sys/fs/file-max查看。 32 位机器的默认值为 1024。64 位机器的默认值为 2048。 2、扫描socket时，采用线性扫描，即采用轮询方式，效率较低：当socket较多时，每个select()都要通过遍历FD_SETSIZE个Socket来完成调度。无论哪个Socket处于活动状态，都会被遍历一次。这浪费了大量的CPU时间。如果可以为套接字注册回调函数，并在相关操作处于活动状态时自动完成相关操作，则可以避免轮询。这就是 epoll 和 kqueue 的作用。 3.需要维护一个数据结构来存储大量的FD，这会在用户空间和内核空间之间传输该结构时导致较高的复制开销。 轮询： poll 本质上与 select 相同。它将用户传入的数组复制到内核空间，然后查询每个fd对应的设备状态。如果设备就绪，则向设备等待队列添加一个项目并继续遍历。如果遍历完所有fd后都没有找到就绪设备，则当前进程会被挂起，直到设备就绪或者主动超时。被唤醒后，会再次遍历fd。这个过程经历了很多不必要的遍历。 它对最大连接数没有限制，因为它是基于链表存储的，但它也有一个缺点： 大量的fd数组在用户态和内核地址空间之间作为一个整体进行复制，而不管这种复制是否有意义。 民意调查的另一个特点是“横向触发”。如果上报了一个fd但没有被处理，则下次轮询时会再次上报该fd。 电子轮询： epoll有两种触发方式：EPOLLLT和EPOLLET。 LT 是默认模式，ET 是“高速”模式。 LT模式下，只要fd还有数据可读，epoll_wait每次都会返回它的事件，提醒用户程序进行操作。 ET（边沿触发）模式下，只会提示一次，直到下次有数据为止。无论fd中是否还有可读数据，流入之前都不会再有任何提示。 因此，在ET模式下，读取一个fd时，必须将其缓冲区读出，也就是说，直到read的返回值小于请求的值，或者遇到EAGAIN错误。另一个特点是epoll使用“事件”就绪通知方法通过epoll_ctl来注册fd。一旦fd准备好，内核就会使用类似callback的回调机制来激活fd，epoll_wait就可以收到通知。 为什么epoll有EPOLLET触发模式？如果使用EPOLLLT模式，一旦系统中有大量不需要读写的就绪文件描述符，每次调用epoll_wait都会返回，这会大大降低handler检索的效率它关心的就绪文件描述符。如果使用EPOLLET的边沿触发方式，当监控的文件描述符上发生读写事件时，epoll_wait()会通知handler进行读写。 如果这次没有全部数据被读写（比如读写缓冲区太小），那么下次调用epoll_wait()时它不会通知你，即只会通知你一次，直到文件描述符是直到第二个可读可写事件发生时你才会收到通知！ ！ ！这种模式比水平触发效率更高，而且系统不会被大量你不关心的就绪文件描述符淹没。 epoll的优点： 最大并发连接数没有限制，可打开的FD上限远大于1024（1G内存可监控约10万个端口）； 效率是提高的，不是通过轮询的方式，并且效率不会随着FD数量的增加而降低。只有活跃且可用的FD才会调用回调函数；也就是说，epoll最大的优点就是它只关心你的“活跃”连接，与连接总数无关。因此，在实际的网络环境中，Epoll的效率会比select和poll高很多。 内存复制使用mmap()文件映射内存来加速与内核空间的消息传递；即epoll使用mmap来减少复制开销。 select、poll、epoll的区别总结： 1.支持一个进程可以打开的最大连接数 选择 单个进程可以打开的最大连接数由FD_SETSIZE宏定义，其大小为32个整数的大小（在32位机器上，大小为3232，在64位机器上类似） ，FD_SETSIZE 为 3264)。当然，我们可以修改然后重新编译内核，但性能可能会受到影响，这需要进一步测试。 轮询 poll本质上和select是一样的，但是它没有最大连接数的限制，因为它是基于链表存储的。 epoll 连接数虽然有上限，但是非常大。 1G内存的机器大约可以打开10万个连接，2G内存的机器大约可以打开20万个连接。 2、FD急剧增加带来的IO效率问题 选择 因为每次调用时都会线性遍历连接，随着FD的增大，会造成遍历速度慢的“线性退化性能问题”。 轮询 与上面相同 epoll因为epoll内核中的实现是基于每个fd上的回调函数，所以只有活跃的socket才会主动调用回调。因此，当活动套接字较少时，使用epoll不会出现前两者的线性下降性能问题。 ，但是当所有套接字都处于活动状态时，可能会出现性能问题。 3.消息传递方式 选择 内核需要将消息传递到用户空间，这需要内核复制动作。 轮询 与上面相同 epoll epoll是通过内核和用户空间共享一块内存来实现的。 上期：100道面试题汇总 总结： 综上所述，在选择select、poll、epoll时，要考虑具体的使用场合以及这三种方法的特点。 1、表面上看，epoll性能最好，但是当连接数较少且连接非常活跃时，select和poll的性能可能会比epoll更好。毕竟epoll的通知机制需要很多函数回调。 2. select效率低下，因为每次都需要轮询。但效率低下是相对的，可以根据情况通过良好的设计来改善。 今天我们就对这三种IO复用进行比较，参考了网上和书籍上的资料，整理如下： 1. 选择实施 select的调用过程如下： 使用copy_from_user将fd_set从用户空间复制到内核空间 注册回调函数__pollwait 遍历所有的fd，调用其对应的poll方法（对于socket来说，这个poll方法是sock_poll，sock_poll会根据情况调用tcp_poll、udp_poll或者datagram_poll）——以tcp_poll为例，它的核心实现是__pollwait，上面注册了Callback 。 __pollwait的主要工作是将current（当前进程）挂入设备的等待队列中。不同的设备有不同的等待队列。对于tcp_poll来说，等待队列是sk->sk_sleep（注意，进程被挂到等待队列中并不意味着进程已经休眠）。设备收到消息（网络设备）或者填写文件数据（磁盘设备）后，会唤醒设备并等待队列上休眠的进程。此时，电流将被唤醒。 poll方法返回时，会返回一个描述读写操作是否就绪的掩码，并根据这个掩码给fd_set赋值。如果遍历完所有的fd，没有返回可读写的掩码，就会调用schedule_timeout，调用select的进程（也就是current）就会进入睡眠状态。当设备驱动程序能够读写自己的资源时，它将唤醒在等待队列中休眠的进程。如果经过一定的超时时间（schedule_timeout指定）没有人被唤醒，调用select的进程就会再次被唤醒，获得CPU，然后再次遍历fd，判断是否有就绪的fd。 将 fd_set 从内核空间复制到用户空间。 上期：100道面试题汇总 总结： select的几大缺点： 每次调用select时，都需要将fd集合从用户态复制到内核态。当fd很多的时候这个开销会很大。 同时，每次调用select时，都需要遍历内核中所有传递过来的FD。当FD很多的时候这个开销也是非常大的。 select支持的文件描述符数量太少，默认为1024 2. 投票实施 poll的实现与select非常相似，只是描述fd集合的方式不同。 poll 使用 pollfd 结构，而不是 select 的 fd_set 结构。其他一切都是相似的。多个描述符的管理还涉及根据描述符的状态进行轮询和处理。但 poll 对文件描述符的最大数量没有限制。 poll和select的一个缺点是，包含大量文件描述符的数组会在用户态和内核的地址空间之间作为一个整体进行复制，而不管这些文件描述符是否准备好。它的开销随着文件描述符的数量而增加。并且呈线性增加。 3.epoll 既然epoll是对select和poll的改进，那么它应该能够避免上述三个缺点。那么epoll怎么解决呢？在此之前，我们先看一下epoll、select、poll的调用接口的区别。 select和poll都只提供一种功能——select或poll功能。 epoll提供了三个函数，epoll_create、epoll_ctl和epoll_wait。 epoll_create是创建epoll句柄； epoll_ctl是注册要监听的事件类型； epoll_wait是等待事件产生。对于第一个缺点，epoll的解决方案是在epoll_ctl函数中。每次在epoll句柄中注册一个新事件（在epoll_ctl中指定EPOLL_CTL_ADD）时，所有的fd都会被复制到内核中，而不是在epoll_wait期间重复复制。 epoll保证每个fd在整个过程中只会被复制一次。 对于第二个缺点，epoll的解决方案不像select或poll那样每次都将current添加到fd对应的设备等待队列中。而是在epoll_ctl期间只挂起一次current（这一次是必须的），并且每次都将current添加到fd对应的设备等待队列中。每个fd指定一个回调函数。当设备就绪并唤醒等待队列上的服务员时，会调用该回调函数，该回调函数会将就绪的fd添加到就绪链表中）。 epoll_wait的工作其实就是检查就绪链表中是否有就绪的fd（使用schedule_timeout()休眠一段时间，判断效果，与select实现中的第7步类似）。 关于第三个缺点，epoll没有这个限制。它支持的FD上限是可以打开的最大文件数。这个数字一般远大于2048。例如，在1GB内存的机器上，大约是100,000。具体数量可以通过cat /proc/sys/fs/file-max查看。一般来说，这个数字与系统内存有很大关系。 上期：100道面试题汇总 总结： （1）select和poll实现需要不断轮询所有fd集合，直到设备准备好。在此期间，睡眠和醒来可能要交替多次。其实epoll也需要调用epoll_wait来不断轮询就绪链表。在此期间，可能会多次交替睡眠和醒来。然而，当设备就绪时，它会调用回调函数，将就绪的fd放入就绪链表中，并在epoll_wait中唤醒进入睡眠状态。过程。 虽然无论是sleep还是alternate，select和poll在“awake”时都需要遍历整个fd集合，而epoll在“awake”时只需要判断就绪链表是否为空，这样就节省了大量的CPU时间。这就是回调机制带来的性能提升。（2）每次调用select和poll时，都要将fd集合从用户态复制到内核态，并且将current放入设备等待队列一次，而epoll只需要复制一次，将current放入设备等待队列中被放入等待队列中。只挂一次（在epoll_wait开始处，注意这里的等待队列不是设备等待队列，而是epoll内部定义的等待队列）。这样也能节省不少开支。 参考 https://www.sychzs.cn/zhaodahai/p/6831456.html https://www.sychzs.cn/sky-heaven/p/7011684.html