I/O多路转接——select、poll 和 epoll
一、select
1. select() 函数
- select系统调用是用来让我们的程序监视多个文件描述符的状态变化的;
- 程序会停在select这里等待，直到被监视的文件描述符有一个或多个发生了状态改变。
select函数原型：
#include <sys/select.h>
int select( int nfds,
fd_set *readfds, fd_set *writefds, fd_set *exceptfds,
struct timeval *timeout);参数nfds：指定被监听的文件描述符的总数，通常被设置为select监听的所有文件描述符中最大的那个+1。
readfds, writefds 和 exceptfds 参数分别指向可读、可写和异常等事件对应的文件描述符。程序调 select 是通过这三个参数传入自己感兴趣的文件描述符，select 调用返回时，内核会修改他们，以便通知程序哪些文件描述符已经就绪。这是典型的输入输出型参数，他们都是 fd_set 结构体类型。
参数 timeout 为结构体 timeval，用来设置 select() 的等待时间
（1）参数timeout
- NULL：则表示 select() 没有 timeout，select 将一直被阻塞，直到某个文件描述符上发生了事件;
- 0：仅检测描述符集合的状态，然后立即返回，并不等待外部事件的发生。
- 特定的时间值：如果在指定的时间段里没有事件发⽣生，select() 将超时返回。
timeval结构体定义如下：
struct timeval
{
long tv_sec; // 秒
long tv_usec; // 微妙
}（2）fd_set结构体
第二个参数、第三个参数、第四个参数都是指向fd_set类型的指针，fd_set结构体内实质上就是一个位图。位图中每个元素的下标代表一个文件描述符。每个元素的取值只有0和1。
fd_set 的大小由 FD_SETSIZE 指定，这就限制了select 能同时处理的文件描述符的总数。
由于对位图的操作比较繁琐，所以系统已经封装好了一套函数供我们使用。
#include <sys/select.h>
FD_CLR(int fd, fd_set* fdset); //清除fdset的位fd
FD_SET(int fd, fd_set* fdset); //设置fdset的位fd
FD_ZERO(fd_set* fdset; //清除fdset所有的位
FD_ISSET(int fd, fd_set* fdset) //测试fdset的位fd是否被设置（3）函数返回值
select 函数成功时返回就绪（可读、可写和异常）文件描述符的总数。如果在超时时间内没有任何文件描述符就绪，select 返回0.select失败时返回-1并设置error。
如果在select等待期间，程序收到信号，则select立即返回-1，并设置error为EINTR。
2. socket就绪条件
（1）读就绪
socket内核中, 接收缓冲区中的字节数, 大于等于低水位标记SO_RCVLOWAT. 此时可以无阻塞的读该文件描述符, 并且返回值大于0;
socket TCP通信中, 对端关闭连接（收到了FIN的TCP连接）, 此时对该socket读, 将不会阻塞，而是直接返回0（也就是EOF）;
监听的socket上有新的连接请求；该套接字是一个listen的监听套接字，并且目前已经完成的连接数不为0。对这样的套接字进行accept操作通常不会阻塞。
socket上有未处理的错误;
（2）写就绪
socket内核中, 发送缓冲区中的可用字节数(发送缓冲区的空闲位置大小), 大于等于低水位标记SO_SNDLOWAT, 此时可以无阻塞的写, 并且返回值大于0;
socket的写操作被关闭(close或者shutdown或主动发送了FIN的TCP连接).对一个写操作被关闭的socket进行写操作, 会触发SIGPIPE信号;
socket使用非阻塞connect连接成功或失败之后;
socket上有未读取的错误。
（3）异常就绪
- socket上收到带外数据. 关于带外数据, 和TCP紧急模式相关(TCP协议头中, 有一个紧急指针的字段)。
3. select的特点
可监控的文件描述符个数取决与sizeof(fdset)的值。如果sizeof(fdset)＝512，那么支持的最大文件描述符是 512*8=4096.
-
将fd加入select监控集的同时，还要再使用一个数据结构array保存放到select监控集中的fd，
- 一是用于再select返回后，array作为源数据和fdset进行FDISSET判断。
- 二是select返回后会把以前加入的但并无事件发生的fd清空，则每次开始select前都要重新从array取得fd逐一加入(FD_ZERO最先)，扫描array的同时取得fd最大值maxfd，用于select的第一个参数。
4. select的缺点
每次调用select, 都需要手动设置fd集合,从接口使用角度来说非常不便.
每次调用select，都需要把fd集合从用户态拷贝到内核态，这个开销在fd很多时会很大
同时每次调用select都需要在内核遍历传递进来的所有fd，这个开销在fd很多时也很大
select支持的文件描述符数量太小.
二、poll
1. poll()函数
#include <poll.h>
int poll(struct pollfd *fds, nfds_t nfds, int timeout);
// pollfd结构
struct pollfd {
int fd; /* file descriptor */
short events; /* requested events */
short revents; /* returned events */
};（1）参数
fds是一个poll函数监听的结构列表. 每一个元素中, 包含了三部分内容:文件描述符, 监听的事件集合, 返回的事件集合.
nfds表示fds数组的长度.
timeout表示poll函数的超时时间, 单位是毫秒(ms).
（2）events和revents
（3）返回值
- 返回值小于0，表示出错；
- 返回值等于0，表示poll函数等待超时；
- 返回值大于0，表示poll由于监听的文件描述符就绪而返回。
2. poll的缺点
poll中监听的文件描述符数目增多时：
- 和select函数一样，poll返回后，需要轮询pollfd来获取就绪的描述符.
- 每次调用poll都需要把大量的pollfd结构从用户态拷贝到内核中.
- 同时连接的大量客户端在一时刻可能只有很少的处于就绪状态, 因此随着监视的描述符数量的增长,其效率也会线性下降.
三、epoll
1. epoll_create()函数
#include <sys/epoll.h>
int epoll_create(int size);
/*
* 功能：在内核中创建一个事件表
* 参数：告诉内核事件表需要多大
* 返回值：创建的事件表的文件描述符
*/2. epoll_ctl()函数
#include <sys/epoll.h>
int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);
/*
* 功能：操作epoll的内核事件表
* 参数：
* 1. epfd：epoll_create()函数的返回值，epoll内核事件表的文件描述符
* 2. op：要对事件表进行的操作，有以下三个选项：
①EPOLL_CTL_ADD 给fd文件描述符添加event事件
②EPOLL_CTL_MOD 将fd文件描述符上的事件修改成event事件
③EPOLL_CTL_DEL 删除fd文件描述符上的事件，event参数写NULL
* 3. fd：要操作的文件描述符
* 4. event：告诉内核需要监听什么事件，epoll_event结构体如下：
struct epoll_event {
uint32_t events; //可以取值EPOLLIN、EPOLLOUT、EPOLLET等
epoll_data_t data;
};
而其中的epoll_data_t 是一个联合体，其结构如下：
typedef union epoll_data {
void *ptr; // 指定与fd相关的用户数据（因为联合体，每次只能用其中一个）
int fd; // 事件所属的文件描述符
uint32_t u32;
uint64_t u64;
} epoll_data_t;
* 返回值：成功返回0，失败返回-1
*/3. epoll_wait()
#include <sys/epoll.h>
int epoll_wait(int epfd, struct epoll_event *events, int maxevents, int timeout);
/*
* 功能：在超时时间内等待一组文件描述符上的事件
* 参数：
* 1. epfd：epoll_create()函数的返回值，epoll内核事件表的文件描述符
* 2. events：分配好的epoll_event结构体数组，用于存储事件表中所有已发生的事件，即输出型参数，它使得epoll大大提高了效率
* 3. maxevents：最多监听多少个事件
* 4. timeout：和select的timeout一样。
*
* 返回值：和select返回值一样
*/关于struct epoll_event结构体：
- 第一个成员 events：代表用户关心的事件，值可以设成EPOLLIN、EPOLLOUT等
- 第二个成员 data：是一个union epoll_data 结构体，所以里面的 ptr 和 fd 不能同时使用。
4. epoll高效背后的秘密
在调用 epoll_create 时，Linux内核会创建一个 eventpoll 结构体，这个结构体中有两个成员就是epoll高效的秘密。
struct eventpoll{
...
/*红黑树的根节点，这颗树中存储着所有添加到epoll中的需要监控的事件*/
struct rb_root rbr;
/*双链表中则存放着将要通过epoll_wait返回给用户的满足条件的事件*/
struct list_head rdlist;
...
};每一个epoll对象都有一个独立的eventpoll结构体，用于存放通过epoll_ctl方法向epoll对象中添加进来的事件。这些事件都会挂载在红黑树中，如此，重复添加的事件就可以通过红黑树而高效的识别出来(红黑树的插入时间效率是lgn，其中n为树的高度)。
而所有添加到epoll中的事件都会与设备(网卡)驱动程序建立回调关系，也就是说，当相应的事件发生时会调用这个回调方法。这个回调方法在内核中叫ep_poll_callback，它会将发生的事件添加到rdlist双链表中。
在epoll中，对于每一个事件，都会建立一个epitem结构体，如下所示：
struct epitem{
struct rb_node rbn;//红黑树节点
struct list_head rdllink;//双向链表节点
struct epoll_filefd ffd; //事件句柄信息
struct eventpoll *ep; //指向其所属的eventpoll对象
struct epoll_event event; //期待发生的事件类型
} 当调用epoll_wait检查是否有事件发生时，只需要检查eventpoll对象中的rdlist双链表中是否有epitem元素即可。如果rdlist不为空，则把发生的事件复制到用户态，同时将事件数量返回给用户。
当调用
epoll_wait时就相当于以往调用select/poll，但是这时却不用传递socket句柄给内核，因为内核已经在epoll_ctl中拿到了要监控的句柄列表。在内核里，一切皆文件。所以，epoll 向内核注册了一个文件系统，用于存储上述的被监控socket。当你调用epoll_create时，就会在这个虚拟的epoll文件系统里创建一个file结点。当然这个file不是普通文件，它只服务于epoll。
epoll在被内核初始化时（操作系统启动），同时会开辟出epoll自己的内核高速cache区，用于安置每一个我们想监控的socket，这些socket会以红黑树的形式保存在内核cache里，以支持快速的查找、插入、删除。这个内核高速cache区，就是建立连续的物理内存页，然后在之上建立slab层，简单的说，就是物理上分配好你想要的size的内存对象，每次使用时都是使用空闲的已分配好的对象。
极其高效的原因：
我们在调用epoll_create时，内核除了帮我们在epoll文件系统里建了个file结点，在内核cache里建了个红黑树用于存储以后epoll_ctl传来的socket外，还会再建立一个list链表，用于存储准备就绪的事件，当epoll_wait调用时，仅仅观察这个list链表里有没有数据即可。有数据就返回，没有数据就sleep，等到timeout时间到后即使链表没数据也返回。所以，epoll_wait非常高效。
这个准备就绪list链表是怎么维护的呢？当我们执行epoll_ctl时，除了把socket放到epoll文件系统里file对象对应的红黑树上之外，还会给内核中断处理程序注册一个回调函数，告诉内核，如果这个句柄的中断到了，就把它放到准备就绪list链表里。所以，当一个socket上有数据到了，内核在把网卡上的数据copy到内核中，然后就把socket插入到准备就绪链表里了。
如此，一颗红黑树，一张准备就绪句柄链表，少量的内核cache，就帮我们解决了大并发下的socket处理问题。执行epoll_create时，创建了红黑树和就绪链表，执行epoll_ctl时，如果增加socket句柄，则检查在红黑树中是否存在，存在立即返回，不存在则添加到树干上，然后向内核注册回调函数，用于当中断事件来临时向准备就绪链表中插入数据。执行epoll_wait时立刻返回准备就绪链表里的数据即可。
5. LT 和 ET
EPOLL事件有两种模型 LT(Level Triggered 水平触发事件) 和 ET(Edge Triggered 边沿触发事件)
LT(level triggered，水平触发模式)是缺省的工作方式，并且同时支持 block 和 non-block socket。在这种做法中，内核告诉你一个文件描述符是否就绪了，然后你可以对这个就绪的fd进行IO操作。如果你不作任何操作，内核还是会继续通知你的，所以，这种模式编程出错误可能性要小一点。
ET(edge-triggered，边缘触发模式)是高速工作方式，只支持no-block socket。在这种模式下，当描述符从未就绪变为就绪时，内核通过epoll告诉你。然后它会假设你知道文件描述符已经就绪，并且不会再为那个文件描述符发送更多的就绪通知，等到下次有新的数据进来的时候才会再次出发就绪事件。
从操作系统角度看，当一个socket句柄上有事件时，内核会把该句柄插入上面所说的准备就绪list链表，这时我们调用epoll_wait，会把准备就绪的 socket 拷贝到用户态内存，然后清空准备就绪list链表，最后，epoll_wait干了件事，就是检查这些socket，如果是LT模式，并且这些socket上确实有未处理的事件时，又把该句柄放回到刚刚清空的准备就绪链表了。所以，LT的句柄，只要它上面还有事件，epoll_wait每次都会返回这个句柄。
四、select、poll 和 epoll 的优缺点对比
-
select优点：
- 一次可以等待多个文件描述符，减少了平均等待时间
- 客户越来越多时，减轻了进程调度的压力（相较于多进程多线程服务器）
-
select缺点：
- 能监听的文件描述符有上限，这个上限是由fd_set决定的。
- 它返回的只是就绪事件的个数，要判断是那个事件满足，需要遍历文件描述符。
- select监听的集合是输入输出参数，每次监听都需要重新初始化。
- 每次调用select，都需要把fd集合从用户态拷贝到内核态，这个开销在fd很多时会很大
- 内核采用轮询（遍历fd集合）的方式来检测就绪事件，这个开销在fd很多时也很大
- select和poll都只能工作在低效的LT（水平触发）模式
-
poll优点：
- poll监听的文件描述符没有最大数量的限制（65535）
- poll对于select来说包含了一个pollfd结构，pollfd结构包含了要监视的event和发生的revent，而不像select那样使用输入输出的传递方式。所以不需要每次监听都初始化
-
poll缺点：
- 数量过大以后其效率也会线性下降。
- poll和select一样也是返回就绪事件的个数，需要遍历文件描述符来判断是那个事件已经就绪，当数量很大时，开销也就很大。
- select和poll都只能工作在低效的LT（水平触发）模式
- 每次调用poll，都需要把pollfd数组从用户态拷贝到内核态，这个开销在fd很多时会很大
- 内核采用轮询（遍历pollfd数组）的方式来检测就绪事件，这个开销在fd很多时也很大
-
epoll 的优点
- 文件描述符数目无上限: 通过epoll_ctl()来注册一个文件描述符, 内核中使用红黑树的数据结构来管理所有需要监控的文件描述符.
- 基于事件的就绪通知方式: 一旦被监听的某个文件描述符就绪, 内核会采用类似于callback的回调机制, 迅速**这个文件描述符. 这样随着文件描述符数量的增加, 也不会影响判定就绪的性能;
- 维护就绪队列: 当文件描述符就绪, 就会被放到内核中的一个就绪队列中. 这样调用epoll_wait获取就绪文件描述符时，只需要去队列中的元素即可，操作时间复杂度是