I/O多路复用

1. 基本概念

        操作系统内核 ( $kernel$ ) 是操作系统的核心,独立于普通应用程序,可以访问受保护的内存空间,也有权访问所有底层硬件设备。为了保证用户进程不能直接操作内核,操作系统将内存空间划为两部分,内核空间和用户空间。对于linux系统,如果是 $32$ 位系统,虚拟内存中最高的 $1G$ 字节 ( $0xC0000000 \sim 0xFFFFFFFF$ ) 为内核空间;如果是 $64$ 位系统,指针的前 $16$ 位保留,从而只有 $48$ 位寻址空间,于是最高的 $128T$ 字节 ( $0x0000000000000000 \sim 0x00007FFFFFFFF000$ ) 作为系统空间,中间部分 ( $0x00007FFFFFFFFFFF \sim 0xFFFF800000000000$ ) 作为保留,其余部分为用户空间。
        正在执行的进程由于某些期待的事件未发生,如资源请求失败或者等待某些操作完成等,会自动执行阻塞原语,使自己由运行态变为阻塞态。进程的阻塞是一种主动行为,只有处于运行态的进程才可以触发,并且阻塞后不占用CPU资源。
        文件描述符 ( $fd$ ) 是一个指向文件引用的概念,在形式上是一个非负整数,实际上是一个索引值,指向内核打开文件表中的对应记录。打开文件表中记录了文件的属性,包括磁盘位置、访问权限、文件位置指针以及打开计数。
        缓存I/O又称为标准I/O,大多数文件系统的默认I/O操作都是缓存I/O。在Linux中,操作系统会将I/O数据缓存在文件系统的 $Page\ \ Cache$ 中,即数据会先被拷贝到操作系统内核的缓冲区中,然后才会从操作系统内核的缓冲区拷贝到应用程序的地址空间。
        在BIO模式下,当线程接收一个请求后,在等待I/O的时间内,调用会被阻塞,无法接受其他请求。在多线程环境下,如果想要接受大量请求,就需要创建大量线程,占用大量系统空间,并且线程切换会带来很大的开销。$10000$ 个线程真正发生读写的实际的线程数不会超过 $20\%$ 。
        在NIO模式下,当线程接收一个请求后,会加入 $fd_-set$ 集合,每次轮询集合接收数据,如果没有数据会返回错误。每次都要轮询所有集合,包括未发生实际读写的 $fd$ ,会浪费CPU资源。
        在I/O多路复用模式下,服务端通过 $select$ / $poll$ / $epoll$ 等系统调用获取 $fd$ 列表,遍历有事件的 $fd$ 进行数据接收,可以支持更多并发连接请求。

2. select

        $select$ 是仅仅知道了有I/O事件发生,但是无法确定是哪几个流 ( 一个或多个,甚至全部 ),只能无差别的轮询所有流,直到找出所有能读出或写入数据的流,具有 $O(n)$ 的无差别轮询复杂度。

  1. 使用 $copy_-from_-user$ 从用户空间拷贝 $fd_-set$ 到内核空间;
  2. 注册回调函数 $\_\_pollwait$ ,负责将当前进程挂载到设备的等待队列中,在设备收到一条消息或者完成磁盘写入后,会唤醒等待队列上等待的进程;
  3. 遍历所有 $fd$ ,调用其对应的 $poll$ 方法,$poll$ 方法的核心就是 $\_\_pollwait$ ,返回一个描述读写操作是否完成的 $mask$ ,根据这个 $mask$ 给 $fd\_set$ 赋值;
  4. 如果遍历完所有的 $fd$ 还没有返回一个可读写的 $mask$ ,调用 $schedule_-timeout$ 使调用 $select$ 的进程睡眠;
  5. 设备驱动发现自身资源可读写后,唤醒等待队列上的进程。如果超过了 $schedule_-timeout$ 设定的时间,调用 $select$ 的进程会被重新唤醒,重新开始遍历;
  6. 把 $fd_-set$ 从内核空间拷贝回用户空间。
// fd_set为数组,通过FD_SETSIZE定义
// readfds、writefds和exceptfds分别对应读、写和异常条件fd
// timeout为超时时间,select会一直阻塞到有事件到达或者等待时间超过timeout
int select(int nfds, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout);

        $select$ 本质上是通过设置或者检查存放 $fd$ 标志位的数据结构来进行下一步处理,缺点是:

4. poll

        $poll$ 本质和 $select$ 一样,也是将 $fd$ 拷贝到内核空间并轮询设备状态,但是没有最大连接数的限制。与 $select$ 的不同之处在于:

struct pollfd {
    int fd;

    // 期待事件
    short events;

    // 监听到的事件
    short revents;
}

int poll(struct pollfd *fds, unsigned int nfds, int timeout);

        缺点是:

5. epoll

        $epoll$ 可以理解为 $event\ \ poll$ ,不同于忙轮询和无差别轮询,每个流发生了怎样的I/O事件都会通知 $epoll$ ,也就是说 $epoll$ 是事件驱动的,从而将复杂度降低到了 $O(1)$ 。
        当进程调用 $epoll_-create$ 时,Linux内核会创建 $eventpoll$ 结构体,如下:

#include <sys/epoll.h>

// 每个epoll对象都有一个独立的eventpoll结构体
struct eventpoll {
    // 红黑树根节点,存储所有事件
    struct rb_root rbr;

    // 双链表存储发生事件
    struct list_head rdlist;
}

// 创建epoll对象
int epoll_create(int size);

// 添加/删除事件
int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);

// 检查事件集合,没有可读流则阻塞进程
int epoll_wait(int epfd, struct epoll_event *events, int maxevents, int timeout);

// 事件结构
struct epitem {
    // 红黑树节点
    struct rb_node rbn;

    // 双向链表节点
    struct list_head rdllink;

    // 事件句柄
    struct epoll_filefd ffd;

    // 所属eventpoll对象
    struct eventpoll *ep;

    // 期待发生的事件类型
    struct epoll_event event;
}

        通过 $epoll_-ctl$ 向 $eventpoll$ 对象中添加的事件都会存储在红黑树中,红黑树的高效性保证了重复事件可以被快速识别出来。所有添加到了 $epoll$ 的事件都会与设备 ( 网卡 ) 驱动程序建立回调关系,当相应事件发生时就会回调 $ep_-poll_-callback$ ,将发生的事件添加到双链表中。$epoll_-wait$ 检查是否有事件发生,即链表是否存在节点,如果存在,则复制回用户空间,并返回事件数量。
        $epoll$ 的优点有:

        $epoll$ 有 $EPOLLLT$ 和 $EPOLLET$ 两种触发模式,$LT$ ( $level-triggered$ ) 是默认模式,$ET$ ( $edge-triggered$ ) 是高速模式。

6. 应用场景

6.1 对比

$select$ $poll$ $epoll$
方式 轮询 轮询 回调
数据结构 $bitmap$ 数组 红黑树
最大连接数 $1024$ ( $x86$ )/ $2048$ ( $x64$ ) 无上限 无上限
拷贝 每次调用都需要进行拷贝 每次调用都需要进行拷贝 内核空间和用户空间共享一块内存
工作模式 $LT$ $LT$ $LT$ / $ET$
复杂度 $O(n)$ $O(n)$ $O(1)$

6.2 Nginx

        Nginx支持多种并发模型,具体实现根据系统平台而有所不同,在支持多种并发模型的平台上会自动选择最高效的模型,也可以通过 $use$ 指令在配置文件中显示指定。

6.3 Redis

        Redis采用I/O多路复用保证在多连接时候的吞吐量,主要是基于 $epoll$ 实现的,也提供了 $select$ 和 $kqueue$ 实现,默认采用 $epoll$ 。

I/O多路复用