⚡ IO 多路复用 · 完整原理图

select / poll / epoll 全解析 · 内核数据结构 · 红黑树 · 就绪链表 · LT vs ET

🗺 三种机制一眼看全
select
最古老
📦 数据结构: 位图 fd_set
🔢 fd 上限: 1024（硬编码）
📋 内核操作: 线性轮询所有fd
📤 结果返回: 修改原 fd_set
🔁 每次调用: 重新从用户态拷贝
📈 时间复杂度: O(n)
🌐 跨平台: ✅ 所有系统
poll
改进版
📦 数据结构: pollfd 数组
🔢 fd 上限: 无限制
📋 内核操作: 线性轮询所有fd
📤 结果返回: revents 字段置位
🔁 每次调用: 仍然重新拷贝数组
📈 时间复杂度: O(n)
🌐 跨平台: ✅ POSIX 标准
epoll
Linux 最优
📦 数据结构: 红黑树 + 就绪链表
🔢 fd 上限: 系统文件描述符上限
📋 内核操作: 回调驱动，只处理活跃fd
📤 结果返回: 只拷贝就绪事件
🔁 每次调用: fd 注册一次即可
📈 时间复杂度: O(1) 触发，O(log n) 注册
🌐 跨平台: ⚠️ 仅 Linux
📊 性能对比表
维度 select poll epoll
监听 fd 数量 ≤ 1024 无限制 无限制
内核遍历方式 全量轮询 全量轮询 回调驱动
用户↔内核 拷贝 每次全量 每次全量 只拷贝就绪
连接数增加时性能 线性下降 线性下降 基本不变
内存使用 极少 少 少（内核管理）
典型使用场景 嵌入式/跨平台 少量连接场景 高并发服务器（Nginx/Redis）
🧠 核心问题：为什么需要 IO 多路复用？
❌ 方案1: 一连接一线程
• 1万个连接 = 1万个线程
• 内存：每线程≈8MB栈 → 80GB
• 上下文切换开销极大
• 大量线程在 等待IO阻塞
⚠️ 方案2: 非阻塞轮询
• 每个fd设为非阻塞
• 循环遍历所有fd
• CPU 100% 空转
• 无法区分 活跃vs空闲 fd
✅ 方案3: IO多路复用
• 一个线程监听所有fd
• 内核负责检测哪个fd就绪
• 只处理 真正有数据 的fd
• 等待期间线程可以睡眠
🔴 epoll 三大 API 调用链
用户程序
epoll_create(size) 系统调用
返回 epfd（一个特殊文件描述符，代表内核中的 epoll 实例）
↓
内核
创建 epoll 实例
分配 红黑树（存储所有监听的 fd）
分配 就绪链表（存储已就绪的 fd）
分配等待队列（存储阻塞在 epoll_wait 的进程）
↓ 注册 fd
用户程序
epoll_ctl(epfd, EPOLL_CTL_ADD, fd, &event) 系统调用
注册一个 fd 到 epoll，指定监听事件类型（EPOLLIN/EPOLLOUT/...）
↓
内核
红黑树插入节点 — O(log n)
为该 fd 注册 回调函数：当设备（网卡/磁盘）产生中断时，硬件→内核→回调→将 fd 加入就绪链表
↓ 等待事件
用户程序
epoll_wait(epfd, events[], maxevents, timeout) 系统调用
阻塞等待（或超时），将就绪链表中的事件拷贝到用户空间 events 数组
↓ 期间
硬件中断
网卡收到数据包 → 触发中断
1. 网卡 DMA 将数据写入内核缓冲区
2. 触发软中断（ksoftirqd）
3. 协议栈处理（TCP/IP 解包）
4. 调用 socket_data_ready 回调
5. 回调函数将该 socket fd 加入 就绪链表
6. 唤醒阻塞在 epoll_wait 的进程
↓ 唤醒
用户程序
epoll_wait 返回 返回就绪数量 n
只拷贝 n 个就绪事件到 events[] —— 不管注册了多少 fd，只处理有事件的
🧱 内核数据结构详解
🔴 红黑树（Red-Black Tree）— 存储所有监听 fd
以 fd 数值 为 key，节点存储该 fd 的监听配置（事件类型、回调等）
fd=8 fd=4 fd=12 fd=2 fd=6 fd=10 fd=15 红节点 黑节点 O(log n) 查找/插入/删除
每个节点存储：
  • fd（文件描述符，作为key）
  • events（监听的事件类型）
  • callback（就绪时调用的回调函数指针）
  • epitem（指向对应就绪链表节点）
🔗 就绪链表（rdllist）— 双向链表
fd 就绪时，回调函数把它加入这里。
epoll_wait 返回时，把链表内容拷贝到用户空间。
head →
fd=4 EPOLLIN
⇌
fd=12 EPOLLIN
⇌
fd=6 EPOLLOUT
→ NULL
⚡ 时间复杂度: O(1) 插入（链表头插）
😴 等待队列（wait queue）
进程调用 epoll_wait 阻塞时，进程描述符加入此队列，就绪时被唤醒。
进程 pid=1234 💤
← 睡眠等待事件
就绪链表非空时 → 唤醒此队列中的进程
📦 epoll_event 结构体
struct epoll_event {
  uint32_t events;  // EPOLLIN|EPOLLOUT|EPOLLET
  epoll_data_t data; // 用户自定义数据
};

typedef union epoll_data {
  void*    ptr;  // 可指向任意对象
  int      fd;  // fd 数值
  uint32_t u32;
  uint64_t u64;
} epoll_data_t;
📋 select 的位图（fd_set）机制
fd_set 本质是一个 1024 bit 的位图（128 字节），每一 bit 对应一个 fd。
bit=1 表示监听该 fd，bit=0 表示不监听。
fd_set（监听集合，示例：监听 fd 0,1,4,7,9）
⚠️ 痛点：每次 select() 调用后，内核会 修改 这个位图，应用必须重置后才能再次调用
select 的三重痛点
1️⃣ fd 上限 1024：FD_SETSIZE 硬编码，改内核才能突破
2️⃣ 每次重新拷贝：用户态→内核态全量位图拷贝，O(n) 开销
3️⃣ 结果破坏原集合：内核修改位图，调用方需保存原始集合备份
select() 系统调用签名
int select(
  int nfds,       // 最大fd+1
  fd_set *readfds, // 读监听集合
  fd_set *writefds, // 写监听集合
  fd_set *exceptfds,// 异常集合
  struct timeval *tv // 超时
);
返回后，readfds 中 bit=1 的 fd 表示有数据可读。
应用程序需要 遍历所有 fd（0 到 nfds-1）来找出哪些就绪。
即使只有 1 个 fd 就绪，也必须扫描整个位图。
🔍 典型用法：
FD_ZERO(&rfds); // 清空
FD_SET(sockfd, &rfds); // 加入
select(sockfd+1, &rfds, NULL, NULL, &tv);
if(FD_ISSET(sockfd, &rfds)) { /* 可读 */ }
📋 poll 的 pollfd 数组机制
poll 用 pollfd 结构体数组代替位图，解决了 fd 数量限制问题，但 仍需线性扫描。
struct pollfd {
  int    fd;      // 文件描述符
  short events;  // 监听事件(输入)
  short revents; // 就绪事件(输出)
};
✅ 优点：无 fd 上限，events/revents 分离，不需要每次备份
❌ 缺点：数组还是要全量拷贝到内核，内核仍然线性轮询
pollfd 数组可视化（就绪项高亮）
fd=3 events=POLLIN revents=POLLIN ✅
fd=5 events=POLLIN|POLLOUT revents=0
fd=8 events=POLLIN revents=0
fd=11 events=POLLOUT revents=POLLOUT ✅
fd=14 events=POLLIN revents=0
⚠️ poll() 返回后，应用仍需 遍历整个数组 检查 revents 是否非零
🎬 epoll 事件驱动动画演示
👤 客户端连接
fd=3未注册
fd=5未注册
fd=7未注册
fd=9未注册
🏛 内核 epoll 实例
红黑树（监听集合）
（空）
就绪链表 rdllist
（空）
等待队列
进程 1234：未阻塞
💻 用户程序状态
等待操作...
系统调用日志
// 点击上方按钮开始演示
⚡ 水平触发（LT）vs 边缘触发（ET）
🔑 触发时机的本质区别
LT（Level Triggered，水平触发）
• 只要缓冲区中 仍有数据（level ≠ 0），就持续通知
• 每次 epoll_wait 都会返回这个 fd
• 适合：允许分多次读取
• 默认模式，更安全，不会漏事件
ET（Edge Triggered，边缘触发）
• 只在 状态发生变化时（0→1 边缘）通知一次
• 通知后不再重复，直到下次有新数据
• 需要：循环读到 EAGAIN，否则会漏事件
• 设置 EPOLLET 标志，性能更高，减少系统调用
🔵 LT 水平触发演示
场景：100字节数据到达，每次只读 40 字节
内核缓冲区（100 bytes 到达）
100 bytes
📩 epoll_wait 返回: fd 就绪
   ➜ read(40 bytes)，缓冲区剩 60 bytes
60 bytes
📩 epoll_wait 返回: fd 仍就绪 ✅（LT 特性：缓冲区非空就通知）
   ➜ read(40 bytes)，缓冲区剩 20 bytes
20 bytes
📩 epoll_wait 返回: fd 仍就绪 ✅
   ➜ read(20 bytes)，缓冲区为空
0 bytes（空）
😴 缓冲区空 → epoll_wait 不再返回此 fd
✅ 优点：不需要一次读完，不会丢事件
❌ 缺点：可能产生多次系统调用
🟠 ET 边缘触发演示
场景：100字节数据到达，使用 EPOLLET
内核缓冲区（100 bytes 到达）
100 bytes
⚡ 状态变化: 0 → 100 bytes（边缘跳变）
📩 epoll_wait 返回: fd 就绪 （仅此一次！）
   ➜ 必须循环 read 直到 EAGAIN：
read(40 bytes) → 60 bytes 剩余
read(40 bytes) → 20 bytes 剩余
read(20 bytes) → 0 bytes 剩余
read() → EAGAIN（缓冲区空）← 停止循环
0 bytes
⚠️ 如果没读完 → 不会再次通知 → 数据丢失！
✅ 优点：通知次数少，性能高（Nginx 使用此模式）
❌ 缺点：必须非阻塞fd + 循环读到EAGAIN，否则漏事件
🏗 ET 模式正确用法（必须配合非阻塞 fd）
// 1. fd 必须设为非阻塞
int flags = fcntl(fd, F_GETFL, 0);
fcntl(fd, F_SETFL, flags | O_NONBLOCK);

// 2. 注册时加 EPOLLET
ev.events = EPOLLIN | EPOLLET;
epoll_ctl(epfd, EPOLL_CTL_ADD, fd, &ev);

// 3. 处理事件时循环读到 EAGAIN
while (1) {
  int n = read(fd, buf, sizeof(buf));
  if (n == -1 && errno == EAGAIN) break; // 读完了
  if (n <= 0) { close(fd); break; } // 错误/关闭
  process(buf, n);
}