- algorithms

categories: algorithms

滑动窗口算法通过维护一个动态调整的窗口范围，高效解决子串、子数组、限流等场景问题。其核心逻辑可概括为以下步骤：

1. **初始化窗口** 使用双指针 `left` 和 `right` 定义窗口边界，初始状态均指向起点。

2. **扩展右边界** 移动 `right` 指针，将新元素加入窗口，并根据问题需求更新状态（如统计字符频率或请求计数）。

3. **收缩左边界** 当窗口满足特定条件（如达到限流阈值或包含冗余元素），逐步移动 `left` 指针缩小窗口，直至不满足条件为止。

4. **记录结果** 在窗口状态变化的每个阶段，捕获符合要求的解（如最长子串长度或限流通过状态）。

在 Linux 的 I/O 多路复用设计中，**select**、**poll** 和 **epoll** 是三种核心机制，它们在实现原理、性能特性和适用场景上有显著差异。以下从内核设计角度详细分析：

**一、select：基于轮询的原始模型**

1. **数据结构**

- 使用固定大小的位图（`fd_set`）管理文件描述符（FD），默认支持 1024 个 FD 。

- 每个 FD 对应一个 bit（如 `FD_SET(fd, &readfds)`），通过 `FD_ISSET` 检查就绪状态 。

2. **工作流程**

- 调用 `select` 时，内核将用户空间的 `fd_set` 拷贝到内核空间，遍历所有 FD 检查可读/可写状态（时间复杂度 **O(n)**）。

- 每次调用需重置 FD 集合，导致多次用户态-内核态拷贝开销 。

3. **局限性**

- **FD 数量限制**：受限于 `FD_SETSIZE`（通常 1024），无法扩展 。

- **性能瓶颈**：遍历所有 FD，高并发场景下效率低 。

**二、poll：链表结构的改进版**

1. **数据结构**

- 使用动态链表（`struct pollfd`数组）替代位图，支持无上限的 FD 数量 。

```C

struct pollfd {

int fd; // 文件描述符

short events; // 关注的事件（如 POLLIN）

short revents; // 实际发生的事件

};

```

2. **工作流程**

- 类似 select，内核遍历所有 FD 检查状态（时间复杂度仍为 **O(n)**）。

- 通过 `pollfd` 数组传递 FD，避免重复初始化 。

3. **优化与不足**

- **优势**：突破 FD 数量限制，适合中等并发场景 。

- **劣势**：大量 FD 时，遍历开销仍然显著；需频繁拷贝用户态-内核态数据 。

**三、epoll：事件驱动的高效模型**

1. **数据结构**

- **红黑树**：管理所有注册的 FD（`epoll_ctl` 添加），实现 O(log n) 的查找效率 。

- **就绪队列**：仅存储活跃 FD，`epoll_wait` 直接返回就绪列表（时间复杂度 **O(1)**）。

2. **核心机制**

- 注册-回调模式：

1. **`epoll_ctl`**：注册 FD 及其关注事件（如 `EPOLLIN`），内核通过回调函数跟踪状态变化 。

2. **`epoll_wait`**：阻塞等待就绪事件，仅返回活跃 FD 列表，无需遍历全部 FD 。

- **共享内存**：内核与用户空间共享就绪队列，避免数据拷贝 。

3. **触发模式**

- **水平触发（LT）**：只要 FD 可读/可写，持续通知（类似 select/poll 行为）。

- **边缘触发（ET）**：仅在 FD 状态变化时通知一次，需一次处理完所有数据（减少无效唤醒）。

4. **性能优势**

- **零拷贝**：通过 `mmap` 共享就绪队列，减少用户态-内核态切换 。

- **高效回调**：仅关注活跃 FD，避免无效遍历，适合数万级高并发场景 。

**四、对比总结**

| **特性** | select | poll | epoll |

| --------------- | -------------------- | --------------------- | --------------------------------- |

| **数据结构** | 位图（`fd_set`） | 链表（`pollfd` 数组） | 红黑树+就绪队列 |

| **FD 数量限制** | 1024（固定） | 无限制 | 无限制（受系统内存限制） |

| **时间复杂度** | O(n) | O(n) | O(1)（就绪队列） |

| **数据拷贝** | 每次调用拷贝 FD 集合 | 同 select | 注册时拷贝一次，后续共享内存 |

| **触发模式** | 仅水平触发 | 同 select | 支持 LT 和 ET 模式 |

| **适用场景** | 低并发、兼容性要求高 | 中低并发、FD 数量较多 | 高并发（如 Web 服务器、实时系统） |

**五、内核实现细节**

1. **select 的 `do_select`**

- 遍历所有 FD，调用每个 FD 的 `poll` 方法检查状态（如 socket 的 `tcp_poll`）。

- 若无就绪 FD，进程进入睡眠，被唤醒后重新遍历 。

2. **epoll 的回调机制**

- 每个 FD 注册时绑定回调函数（如 `ep_ptable_queue_proc`），状态变化时触发回调，将 FD 加入就绪队列 。

- 就绪队列通过 `ep_item_poll` 关联到红黑树节点 。

3. **性能瓶颈突破**

- **红黑树**：快速查找和插入（对比 select/poll 的线性结构）。

- **事件驱动**：避免轮询，仅处理活跃事件 。

**六、典型应用场景**

1. select/poll：旧系统兼容、FD 数量少（如嵌入式设备）。

2. epoll：

- Nginx（高并发连接）、Redis（高性能事件驱动）。

- 实时通信系统（如 WebSocket 服务器）。

通过以上设计差异，epoll 成为 Linux 高并发网络编程的核心工具，而 select/poll 因历史兼容性仍存在于特定场景中。