【Linux】IO多路复用
什么是IO多路复用？
多路是指多个socket网络连接
复用是指复用一个线程，使用一个线程来检查所有文件描述符的就绪状态
多路复用的实现主要有三种技术：select poll epoll
select
系统提供的接口
可以让我们的程序同时监听多个文件描述符上的事件是否就绪
当有一个文件描述符事件就绪，select就会返回，并将已就绪的事件告诉调用者
函数：
nfds: 需要监听的文件描述符中，最大的文件描述符值+1
readfds：输入输出型参数，调用者用户告知内核需要监听哪些文件描述符上的读事件，返回时返回已就绪的文件描述符
writefds：输入输出型参数，调用者用户告知内核需要监听哪些文件描述符上的写事件，返回时返回已就绪的文件描述符
exceptfds：输入输出型参数，调用者用户告知内核需要监听哪些文件描述符上的异常事件是否就绪，返回时返回已就绪的文件描述符
timeout：输入输出型参数，调用时由用户指定select函数的等待时间，返回时表示timeout剩余时间
如果设置NULL则进行阻塞等待，直到有事件就绪
如果设置特定时间，在特定时间内没有事件就绪就会返回
如果设置为0，代表如果没事件就绪直接返回
返回值：
如果调用成功返回就绪的文件描述符个数
如果timeout到了，返回0
如果调用失败返回-1，并设置错误码
fd_set结构
本质是一个位图
select 函数监视的文件描述符分3类，分别是writefds、readfds、和exceptfds
当用户程序调用select的时候，select会将需要监控的readfds集合拷贝到内核空间（假设监控的仅仅是socket可读）
然后遍历自己监控的skb(SocketBuffer)，挨个调用skb的poll逻辑以便检查该socket是否有可读事件，遍历完所有的skb后，如果没有任何一个socket可读，那么select会调用schedule_timeout进入schedule循环，使得process进入睡眠
如果在timeout时间内某个socket上有数据可读了，或者等待timeout了，则调用select的程序会被唤醒，接下来select就是遍历监控的集合，挨个收集可读事件并返回给用户了
每次调用select，都需要把被监控的fds集合从用户态空间拷贝到内核态空间，高并发场景下这样的拷贝会使得消耗的资源是很大的
能监听端口的数量有限，单个进程所能打开的最大连接数由FD_SETSIZE宏定义，监听上限就等于fds_bits位数组中所有元素的二进制位总数
select的优点：同时等待多个文件描述符，只负责等待，其他操作交给其他接口，提高IO效率
selete的缺点：每次调用手动设置fd集合，每次都需要用户态到内核态的拷贝，每次调用都需要在内核里遍历一遍，开销大，可监控的文件描述符数量太少
poll
fds：一个监控的结构体列表，里面包括文件描述符，监控事件集合，就绪事件集合
nfds：表示fds的数组长度
timeout：表示超时等待时间
-1：poll调用后进行阻塞等待，直到被监视的某个文件描述符上的某个事件就绪。
0：poll调用后进行非阻塞等待，无论被监视的文件描述符上的事件是否就绪，poll检测后都
立即返回。
特定的时间值：poll调用后在指定的时间内进行阻塞等待，如果被监视的文件描述符上一直没
有事件就绪，则在该时间后poll进行超时返回
返回值：
成功返回就绪文件描述符个数
超时返回0
失败返回-1，设置错误码
poll解决了select集合大小限制和已经不需要重新设置集合的问题，但是还需要用户态到内核态的大量拷贝，随着监听数量增大，性能也随之降低，不适合高并发场景
epoll
在linux的网络编程中，很长的时间都在使用select来做事件触发。在linux新的内核中，有了一种替换它的机制，就是epoll
相比于select，epoll最大的好处在于它不会随着监听fd数目的增长而降低效率
在内核中的select实现中，它是采用轮询来处理的，轮询的fd数目越多，自然耗时越多,并且，在linux/posix_types.h头文件有这样的声明：
#define __FD_SETSIZE 1024
表示select最多同时监听1024个fd，当然，可以通过修改头文件再重编译内核来扩大这个数目，但这似乎并不治本。
创建一个epoll的句柄，size用来告诉内核这个监听的数目一共有多大
这个参数不同于select()中的第一个参数，给出最大监听的fd+1的值
需要注意的是，当创建好epoll句柄后，它就是会占用一个fd值，在linux下如果查看/proc/进程id/fd/，是能够看到这个fd的，所以在使用完epoll后，必须调用close()关闭，否则可能导致fd被耗尽
int epoll_create(int size);功能：该函数生成一个 epoll 专用的文件描述符
参数size: 用来告诉内核这个监听的数目一共有多大，参数 size 并不是限制了 epoll 所能监听的描述符最大个数，只是对内核初始分配内部数据结构的一个建议。自从 linux 2.6.8 之后，size 参数是被忽略的，也就是说可以填只有大于 0 的任意值。
返回值：如果成功，返回poll 专用的文件描述符，否者失败，返回-1
int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event); 功能：epoll 的事件注册函数，它不同于 select() 是在监听事件时告诉内核要监听什么类型的事件，而是在这里先注册要监听的事件类型
参数epfd: epoll 专用的文件描述符，epoll_create()的返回值
参数op: 表示动作，用三个宏来表示：
EPOLL_CTL_ADD：注册新的 fd 到 epfd 中
EPOLL_CTL_MOD：修改已经注册的fd的监听事件
EPOLL_CTL_DEL：从 epfd 中删除一个 fd
参数fd: 需要监听的文件描述符
参数event: 告诉内核要监听什么事件，struct epoll_event 结构如:
events可以是以下几个宏的集合：
EPOLLIN ：表示对应的文件描述符可以读（包括对端 SOCKET 正常关闭）
EPOLLOUT：表示对应的文件描述符可以写
EPOLLPRI：表示对应的文件描述符有紧急的数据可读（这里应该表示有带外数据到来）
EPOLLERR：表示对应的文件描述符发生错误
EPOLLHUP：表示对应的文件描述符被挂断
EPOLLET ：将 EPOLL 设为边缘触发(Edge Trigger)模式，这是相对于水平触发(Level Trigger)来说的
EPOLLONESHOT：只监听一次事件，当监听完这次事件之后，如果还需要继续监听这个 socket 的话，需要再次把这个 socket 加入到 EPOLL 队列里
返回值：0表示成功，-1表示失败。
int epoll_wait(int epfd, struct epoll_event * events, int maxevents, int timeout); 功能：等待事件的产生，收集在 epoll 监控的事件中已经发送的事件，类似于 select() 调用
参数epfd: epoll 专用的文件描述符，epoll_create()的返回值
参数events: 分配好的 epoll_event 结构体数组，epoll 将会把发生的事件赋值到events 数组中（events 不可以是空指针，内核只负责把数据复制到这个 events 数组中，不会去帮助我们在用户态中分配内存）
参数maxevents: maxevents 告之内核这个 events 有多少个
参数timeout: 超时时间，单位为毫秒，为 -1 时，函数为阻塞
返回值：
如果成功，表示返回需要处理的事件数目
如果返回0，表示已超时
如果返回-1，表示失败
epoll工作原理
红黑树和就绪队列
epoll模型当中的红黑树本质就是告诉内核，需要监视哪些文件描述符上的哪些事件，调用epll_ctl函数实际就是在对这颗红黑树进行对应的增删改操作
epoll模型当中的就绪队列本质就是告诉内核，哪些文件描述符上的哪些事件已经就绪了，调用epoll_wait函数实际就是在从就绪队列当中获取已经就绪的事件
所有添加到红黑树当中的事件，都会与设备（网卡）驱动程序建立回调方法，这个回调方法在内核中叫ep_poll_callback
对于select和poll来说，操作系统在监视多个文件描述符上的事件是否就绪时，需要让操作系统主动对这多个文件描述符进行轮询检测，这一定会增加操作系统的负担
而对于epoll来说，操作系统不需要主动进行事件的检测，当红黑树中监视的事件就绪时，会自动调用对应的回调方法，将就绪的事件添加到就绪队列当中
当用户调用epoll_wait函数获取就绪事件时，只需要关注底层就绪队列是否为空，如果不为空则将就绪队列当中的就绪事件拷贝给用户即可
采用回调机制最大的好处，就是不再需要操作系统主动对就绪事件进行检测了，当事件就绪时会自动调用对应的回调函数进行处理
epoll的边缘触发与水平触发
水平触发(LT)
关注点是数据是否有无，只要读缓冲区不为空，写缓冲区不满，那么epoll_wait就会一直返回就绪，水平触发是epoll的默认工作方式
边缘触发(ET)
关注点是变化，只要缓冲区的数据有变化，epoll_wait就会返回就绪
这里的数据变化并不单纯指缓冲区从有数据变为没有数据，或者从没有数据变为有数据，还包括了数据变多或者变少。即当buffer长度有变化时，就会触发
假设epoll被设置为了边缘触发，当客户端写入了100个字符，由于缓冲区从0变为了100，于是服务端epoll_wait触发一次就绪，服务端读取了2个字节后不再读取
这个时候再去调用epoll_wait会发现不会就绪，只有当客户端再次写入数据后，才会触发就绪
这就导致如果使用ET模式，那就必须保证要「一次性把数据读取&写入完」，否则会导致数据长期无法读取/写入
epoll 为什么比select、poll更高效？
epoll 采用红黑树管理文件描述符
从上图可以看出，epoll使用红黑树管理文件描述符，红黑树插入和删除的都是时间复杂度 O(logN)，不会随着文件描述符数量增加而改变。
select、poll采用数组或者链表的形式管理文件描述符，那么在遍历文件描述符时，时间复杂度会随着文件描述的增加而增加。
epoll 将文件描述符添加和检测分离，减少了文件描述符拷贝的消耗
select&poll 调用时会将全部监听的 fd 从用户态空间拷贝至内核态空间并线性扫描一遍找出就绪的 fd 再返回到用户态。下次需要监听时，又需要把之前已经传递过的文件描述符再读传递进去，增加了拷贝文件的无效消耗，当文件描述很多时，性能瓶颈更加明显。
而epoll只需要使用epoll_ctl添加一次，后续的检查使用epoll_wait，减少了文件拷贝的消耗
四、总结
select，poll，epoll都是IO多路复用机制，即可以监视多个描述符，一旦某个描述符就绪（读或写就绪），能够通知程序进行相应读写操作，但select，poll，epoll本质上都是同步I/O，因为他们都需要在读写事件就绪后自己负责进行读写，也就是说这个读写过程是阻塞的，而异步I/O则无需自己负责进行读写，异步I/O的实现会负责把数据从内核拷贝到用户空间
select，poll实现需要自己不断轮询所有fd集合，直到设备就绪，期间可能要睡眠和唤醒多次交替。而epoll其实也需要调用epoll_wait不断轮询就绪链表，期间也可能多次睡眠和唤醒交替，但是它是设备就绪时，调用回调函数，把就绪fd放入就绪链表中，并唤醒在epoll_wait中进入睡眠的进程。虽然都要睡眠和交替，但是select和poll在“醒着”的时候要遍历整个fd集合，而epoll在“醒着”的时候只要判断一下就绪链表是否为空就行了，这节省了大量的CPU时间。这就是回调机制带来的性能提升
select，poll每次调用都要把fd集合从用户态往内核态拷贝一次，并且要把current往设备等待队列中挂一次，而epoll只要一次拷贝，而且把current往等待队列上挂也只挂一次（在epoll_wait的开始，注意这里的等待队列并不是设备等待队列，只是一个epoll内部定义的等待队列），这也能节省不少的开销
