0%

epoll和kqueue

macos没有epoll机制,而是使用kqueue,二者功能类似,特此记录!

一、引入

  1. 缓冲区的引入是为了减少频繁I/O操作而引起频繁的系统调用,当你操作一个流时,更多的是以缓冲区为单位进行操作,这是相对于用户空间而言。
    • 对于内核来说,也需要缓冲区,即内核缓冲区。
  2. 假设有一个管道,进程A为管道的写入方,B为管道的读出方:
    • 假设一开始内核缓冲区是空的,B作为读出方,被阻塞着。然后首先A往管道写入,这时候内核缓冲区由空的状态变到非空状态,内核就会产生一个事件告诉B该醒来了,这个事件称之为“缓冲区非空”。
    • “缓冲区非空”事件通知B后,B却还没有读出数据,且内核许诺了不能把写入管道中的数据丢掉,这个时候A写入的数据会滞留在内核缓冲区中。如果内核缓冲区也满了,B仍未开始读数据,这个时候会产生一个I/O事件,告诉进程A你该等等(阻塞)了,这个事件定义为“缓冲区满”。
    • 假设后来B终于开始读数据了,于是内核的缓冲区空了出来,这时候内核会告诉A,内核缓冲区有空位了,你可以从长眠中醒来继续写数据了,这个事件定义为“缓冲区非满”
    • 也许事件“缓冲区非满”已经通知了A,但是A也没有数据写入了,而B继续读出数据,知道内核缓冲区空了。这个时候内核就告诉B,你需要阻塞了,这个事件定义为“缓冲区空”。

这四个情形涵盖了四个I/O事件:缓冲区满,缓冲区空,缓冲区非空,缓冲区非满,这四个I/O事件是进行阻塞同步的根本。

阻塞I/O模式下,一个线程只能处理一个流的I/O事件。如果想要同时处理多个流,要么多进程(fork),要么多线程(pthread_create),这两种方法效率都不高。

  1. 于是再来考虑非阻塞忙轮询的I/O方式,我们发现可以同时处理多个流了:
1
2
3
4
5
6
while true {
for i in stream[]; {
if i has data
read until unavailable
}
}

我们只要不停的把所有流从头到尾问一遍,周而复始,这样就可以处理多个流了。但这样的做法显然不好,因为如果所有的流都没有数据,那么只会白白浪费CPU。

阻塞模式下,内核对于I/O事件的处理是阻塞或者唤醒,而非阻塞模式下则把I/O事件交给其他对象。

为了避免CPU空转,可以引进了一个代理(select),这个代理可以同时观察许多流的I/O事件,在空闲的时候会把当前线程阻塞掉,当有一个或多个流有I/O事件时就从阻塞态中醒来,于是我们的程序就会轮询一遍所有的流。

1
2
3
4
5
6
7
while true {
select(streams[])
for i in streams[] {
if i has data
read until unavailable
}
}

如果没有I/O事件产生,我们的程序就会阻塞在select处。但是依然有个问题,我们从select那里仅仅知道了有I/O事件发生了,但却并不知道是哪几个流(可能有一个,多个,甚至全部),我们只能无差别轮询所有流,找出能读出数据或写入数据的流,对他们进行操作。使用select有O(n)的无差别轮询复杂度,同时处理的流越多,每一次无差别轮询时间就越长。

select/poll是通过轮询的方法来获得就绪的状态,调用select/poll后就阻塞住,直到有就绪的文件描述符,或者超时,或者被中断。返回值是就绪的文件描述符的个数,需要遍历作为参数传入的文件描述符的位域或数组获得哪个文件描述符。

Banga et al的论文(发布于USENIX ATC 1999)提供了一个新的建议:状态相关兴趣集。通过在内核内部维护兴趣集的状态,来取代每次调用都要提供整个兴趣集这样的方式。在decalre_interest()调用之上,内核持续的更新兴趣集。用户程序通过调用get_next_event()函数来分发事件。Linux和Free BSD都有它们自己的实现,分别是epoll和kqueue。

二、epoll

  1. epoll的核心是3个API,核心数据结构是:1个红黑树和1个链表。

epoll

  1. 三个步骤

    • 首先,需要调用epoll_create来创建一个epoll的文件描述符,内核会同时创建一个eventpoll的数据结构。这个数据结构里面会包含两个东西,一个是红黑树,专门用于存储epoll_ctl注册进来的fd文件描述符;另外一个是就绪链表,用来存储epoll_wait调用相关的,已经就绪的那些fd文件描述符。
    • 其次,因为epoll中的所有事件,都与网卡驱动程序建立回调关系,当相应的事件发生的时候,会通过这个回调函数,将发生的事件添加到就绪链表当中。
    • 最后,当调用epoll_wait检查是否有事件发生时,只需要检查eventpoll对象中的rdlist双链表中是否有需要处理的事件。如果rdlist不为空,则把发生的事件复制到用户态,同时将事件数量返回给用户。
  2. epoll是通过后台中断的方式来获得就绪的状态,调用epoll_create创建实例,调用epoll_ctl添加或删除监控的文件描述符,调用epoll_wait阻塞住,直到有就绪的文件描述符,通过epoll_event参数返回就绪状态的文件描述符和事件。

    • epoll_create 创建一个epoll对象,一般epollfd = epoll_create()
    • epoll_ctl(epoll_add/epoll_del的合体),往epoll对象中增加/删除某一个流的某一个事件
      • epoll_ctl(epollfd, EPOLL_CTL_ADD, socket, EPOLLIN);//有缓冲区内有数据时epoll_wait返回
      • epoll_ctl(epollfd, EPOLL_CTL_DEL, socket, EPOLLOUT);//缓冲区可写入时epoll_wait返回
    • epoll_wait(epollfd,…)等待直到注册的事件发生
  3. 两种触发方式

    • 边缘触发(edge trigger,ET)
      • 对于读操作
        • 当缓冲区由不可读变为可读的时候,即缓冲区由空变为不空的时候
        • 当有新数据到达时,即缓冲区中的待读数据变多的时候
        • 当缓冲区有数据可读,且应用进程对相应的描述符进行EPOLL_CTL_MOD修改EPOLLIN事件时
      • 对于写操作
        • 当缓冲区由不可写变为可写时
        • 当有旧数据被发送走,即缓冲区中的内容变少的时候
        • 当缓冲区有空间可写,且应用进程对相应的描述符进行EPOLL_CTL_MOD修改EPOLLOUT事件时。
    • 水平触发(level trigger,LT),默认
      • 对于读操作,只要缓冲内容不为空,LT模式返回读就绪。
      • 对于写操作,只要缓冲区还不满,LT模式会返回写就绪。

三、kqueue

  1. kqueue是 FreeBSD上的一种的多路复用机制,它是针对传统的select/poll处理大量的文件描述符性能较低效而开发出来的。kqueue与epoll非常相似,最初是2000年Jonathan Lemon在FreeBSD系统上开发的一个高性能的事件通知接口。

  2. 原理:注册一批socket描述符到kqueue以后,当其中的描述符状态发生变化时,kqueue将一次性通知应用程序哪些描述符可读、可写或出错了。

  3. kqueue支持多种类型的文件描述符,包括socket、信号、定时器、AIO、VNODE、PIPE。

  4. kqueue的接口包括kqueue()、kevent()两个系统调用和一个struct kevent结构:

    • kqueue()生成一个内核事件队列,返回该队列的文件描述符,其它 API 通过该描述符操作这个kqueue,如:注册,反注册,获取通知等。
    • kevent()提供向内核注册/反注册事件和返回就绪事件或错误事件。
      • 注册/撤销:kevent()中的neventlist参数将其设为0且传入合法的changelist和nchangelist,就会将changelist中的事件注册到kqueue中。当关闭某文件描述符时,与之关联的事件会被自动地从kqueue移除。
      • 启用禁用/禁止过滤器事件:通过flags EV_ENABLE和EV_DISABLE使过滤器事件有效或无效。这个功能在利用 EVFILT_WRITE 发送数据时非常有用。
      • 获取已触发事件:将nchangelist设置成0及其他参数,当kevent非错误和超时返回时,在eventlist和neventlist中就保存可用事件集合。
    • struct kevent就是kevent()操作的最基本的事件结构:
1
2
3
4
5
6
7
8
struct kevent { 
uintptr_t ident; /* 事件 ID */
short filter; /* 事件过滤器 */
u_short flags; /* 行为标识 */
u_int fflags; /* 过滤器标识值 */
intptr_t data; /* 过滤器数据 */
void *udata; /* 应用透传数据 */
};
  • ident:事件的id,一般设置为文件描述符。

  • filter:可以将kqueue filter看作事件。内核检测ident上注册的filter的状态,状态发生了变化,就通知应用程序。

    在一个 kqueue 中,{ident, filter} 确定一个唯一的事件

  • 行为标志flags:

    • EV_ADD:指示加入事件到 kqueue
    • EV_DELETE:指示将传入的事件从 kqueue 中移除
  •  过滤器标识值:

    • EV_ENABLE:过滤器事件可用,注册一个事件时,默认是可用的。
    • EV_DISABLE:过滤器事件不可用,当内部描述可读或可写时,将不通知应用程序。

四、参考

  1. epoll详解
  2. epoll和kqueue