操作系统 IO多路复用

多路复用指的是，由一个执行单元，同时对多个对象提供服务，形成一对多的服务关系。

• 多路：存在多个需要处理的 IO event 的 fd 文件句柄；

• 复用：复用一个循环线程同时为多个 FD 提供处理服务；

• IO：在操作系统中，数据在内核态和用户态之间的读写操作；

IO 多路复用是一种同步的IO模型，利用IO多路复用模型，可以实现一个线程监视多个文件句柄。一旦某个文件句柄就绪，就能够通知到对应的应用程序进行相应的读写操作；如果没有句柄就绪时，就会阻塞应用程序，从而释放出CPU资源。

网络中：一个或多个线程处理多个TCP连接，无需创建和维护过多的线程

实现IO多路复用的原型有三种，select、poll、epoll

IO多路复用的应用场景？

1. 网络编程： 在服务器端，当需要同时处理多个客户端连接时，可以使用IO多路复用来监听多个socket，以便及时响应客户端的请求。常见的IO多路复用技术包括select、poll、epoll（Linux系统中的特有机制）等

2. 高性能服务器： 对于高性能服务器，通过IO多路复用可以降低系统开销，提高服务器的并发处理能力。通过在单个线程中管理多个IO操作，避免了线程切换带来的开销，提高了系统的效率

3. 实时系统： 在实时系统中，需要及时响应外部事件，IO多路复用可以用于实时监视多个外部事件，以及时做出响应

4. 图形用户界面(GUI)编程： 在GUI编程中，常常需要同时处理多个用户输入或者异步事件，比如键盘输入、鼠标点击、定时器事件等，IO多路复用可以用于监听这些事件并及时做出响应

select

实现原理：轮询 + 遍历

select 实现多路复用的方式是，将已连接的 Socket 都放到一个文件描述符集合(通常是一个位图)，然后调用 select 函数将文件描述符集合拷贝到内核里，让内核来检查是否有网络事件产生，检查的方式很粗暴，就是通过遍历文件描述符集合的方式，当检查到有事件产生后，将此 Socket 标记为可读或可写， 接着再把整个文件描述符集合拷贝回用户态里，然后用户态还需要再通过遍历的方法找到可读或可写的 Socket，然后再对其处理。

select 的这种方式，需要进行 2 次 「遍历」 文件描述符集合，一次是在内核态里，一个次是在用户态里 ，而且还会发生 2 次 「拷贝」 文件描述符集合，先从用户空间传入内核空间，由内核修改后，再传出到用户空间中。

优点

select 应该是 POSIX 所规定，⼀般操作系统均有实现，几乎所有平台都支持；

缺点

1. 需要两次遍历文件描述集合和两次拷贝数据，性能开销大；
2. 由于文件描述集合采用位图实现，32位系统下默认最多支持1024个fd，64位系统下默认最多支持2048个fd；
3. 文件描述集合不可重用，每次调⽤ select 时，需要重新设置⽂件描述符集合，函数调⽤的开销大；
4. select的工作模式为水平触发(LT)，不支持边缘触发(ET)，效率较低；

select中无法精确感知到哪些fd就绪，需要遍历一轮fd列表，时间复杂度为O(N)；

poll

实现原理：轮询 + 遍历

poll 是为了克服 select 的限制⽽引⼊的⼀种I/O多路复⽤技术。 poll 使⽤⼀个⽂件描述符数组（⼀个结构体数组）来表示要监视的⽂件描述符。与 select 类似， poll 可以监视多个⽂件描述符的I/O状态。

优点

1. ⽂件描述符数量不受限制：由于 poll 使⽤⼀个动态数组来表示⽂件描述符，因此它可以处理任意数量的⽂件描述符；
2. 效率相对较⾼： poll 在查找就绪的⽂件描述符时，只需要遍历实际使⽤的⽂件描述符数组，⽽不是整个⽂件描述符集合；

缺点

1. 需要用户遍历监控的所有文件描述符，随着FD数量的增多而导致性能下降；
2. 存储文件描述符的链表不会保存在内核中，poll 每次调用时都要将链表从用户空间拷贝到内核空间，开销较大；
3. poll 的工作模式为水平触发(LT)，不支持边缘触发(ET)，效率低下；

epoll

实现原理：回调

epoll 中内核态和用户态共享 epfd文件描述集合 fds ，省去了切换开销，每次会将 fds 重排，并且会返回当前内部有n个 fds 被置位了，因此只需要遍历前n个就可以。epoll 只关心活跃的链接，不需要遍历全部集合。

epoll 模型修改主动轮询为被动通知，当有事件发生时，被动接收通知。所以 epoll 模型注册套接字后，主程序可做其他事情，当事件发生时，接收到通知后再去处理。

epoll 工作原理：

内核利用 epoll_create 创建一个 epfd 文件描述符，并利用红黑树数据结构将其存储到根结点上，再用 epoll_ctl 从红黑树中添加、修改或移除文件描述符，最后内核调用 epoll_wait 函数开始监听，。

epoll 处于阻塞状态，当有事件发生或设置的等待时间 timeout 到了就会返回，返回时传出有事件发生文件描述符的结构体数组。与 select、poll 不一样的是， epoll 直接传出有事件发生的文件描述符数组，不用遍历查询。

• epoll_create

1. 在内核开辟空间，创建一个 epoll 池子用于批量存储管理 fd，后续可以通过 epoll_ctl 往池子中增删改 fd
2. 在内核创建一颗红黑树的根节点。，保证了所有增、删、改操作的平均时间复杂度维持在 O(logN) 的对数级水平
3. 就绪队列： 针对于 fd 的就绪 io event，由于通常数量有限，且每个事件都需要逐一处理，没有优先级之分，采用简单的双向链表实现

• epoll_ctl

在某个 epoll 池子中进行一个 fd 的增删改操作. 正是由于 epoll 中将 epoll_ctl 与 epoll_create 操作进行了解耦，才实现了对 epoll_create 时传递的 fd 数据的复用，减少了用户态和内核台之间对 fd 数据的重复传递。此外，在 epoll_ctl 实现时，也需要通过 epollevent 设置好回调事件，当 fd 有指定事件到达时，会被添加到就绪队列中，最终将 loop thread 唤醒

• epoll_wait

从对应 epoll 池子中获取就绪的 epollevent，从中可以关联到对应的 fd 和 loop thread 信息

epoll 编程结构

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

int epfd = epoll_crete(1000);

//将 listen_fd 添加进 epoll 中
epoll_ctl(epfd, EPOLL_CTL_ADD, listen_fd,&listen_event);

while (1) {
	//阻塞等待 epoll 中 的fd 触发
	int active_cnt = epoll_wait(epfd, events, 1000, -1);

	for (i = 0 ; i < active_cnt; i++) {
		if (evnets[i].data.fd == listen_fd) {
			//accept. 并且将新accept 的fd 加进epoll中.
		}
		else if (events[i].events & EPOLLIN) {
			//对此fd 进行读操作
		}
		else if (events[i].events & EPOLLOUT) {
			//对此fd 进行写操作
		}
	}
}

优点

1. 将 select、poll中的 轮询改成了回调，大大提高了CPU的执行效率，也不会随着FD的数量增加而导致效率下降；
2. epoll 由一组函数实现，epoll_create 创建的红黑树保存在内核中，epoll_ctl 只需从红黑树中添加、删除或修改节点，无需重复将已有的文件描述符拷贝到内核态中，开销较小；
3. 与 poll 类似， epoll 可以处理任意数量的⽂件描述符，因为它使⽤⼀个动态数据结构来表示⽂件描述符；
4. epoll 使⽤⼀个内核事件表来记录要监视的⽂件描述符和事件，因此在每次调⽤ epoll 时⽆需重新设置⽂件描述符集合。这可以减少函数调⽤的开销，并提⾼实时性；
5. epoll 支持边缘触发和水平触发(默认工作方式)，边缘触发可减少 epoll_wait 调用次数，提高效率；

缺点

只能在 Linux 平台上使用

水平触发和边缘触发的区别？

水平触发

当被监控的 Socket 上有可读事件发⽣时，服务器不断地从阻塞中苏醒，直到内核缓冲区数据被 read 函数读完才结束，⽬的是告诉我们有数据，只要满⾜事件的条件，⽐如内核中有数据需要读，就⼀直不断地把这个事件传递给⽤户

边缘触发

当被监控的 Socket 描述符上有可读事件发⽣时，服务器只会从阻塞中苏醒⼀次，即使进程没有调⽤ read 函数从内核读取数据，也依然只苏醒⼀次，因此我们程序要保证⼀次性将内核缓冲区的数据读取完，只有第⼀次满⾜条件的时候才触发，之后就不会再传递同样的事件了

select和 epoll 的区别？

• select 和 poll 采⽤轮询的⽅式检查就绪事件，每次都要扫描整个⽂件描述符，复杂度O(N);

• epoll 采⽤回调⽅式检查就绪事件，只会返回有事件发⽣的⽂件描述符的个数，复杂度O(1);

• select 只⼯作在低效的LT模式，epoll 可以在 ET ⾼效模式⼯作;

• epoll 是 Linux 所特有，⽽ select 则应该是 POSIX 所规定，⼀般操作系统均有实现;

• select 单个进程可监视的fd数量有限，即能监听端⼝的⼤⼩有限，64位是2048；epoll 没有最⼤并发连接的限制，能打开的 fd 的上限远⼤于2048；

• select 内核需要将消息传递到⽤户空间，都需要内核拷⻉动作；epoll 通过内核和⽤户空间共享⼀块内存来实现的