概述
epoll也是一种IO多路复用技术,是在2.6内核中提出的,是之前的select和poll的增强版本。相对于select和poll来说,epoll更加灵活,没有描述符限制。epoll使用一个文件描述符管理多个描述符,将用户关系的文件描述符的事件存放到内核的一个事件表中,这样在用户空间和内核空间的copy只需一次。
操作过程
epoll操作过程需要三个接口,分别如下:1
2
3int epoll_create(int size);//创建一个epoll的句柄,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);
int epoll_create(int size)
创建一个epoll的句柄,size用来告诉内核这个监听的数目一共有多大,这个参数不同于select()中的第一个参数,给出最大监听的fd+1的值,参数size并不是限制了epoll所能监听的描述符最大个数,只是对内核初始分配内部数据结构的一个建议。
当创建好epoll句柄后,它就会占用一个fd值,在linux下如果查看/proc/进程id/fd/,是能够看到这个fd的,所以在使用完epoll后,必须调用close()关闭,否则可能导致fd被耗尽。
int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event)
函数是对指定描述符fd执行op操作。
- epfd:是epoll_create()的返回值。
- op:表示op操作,用三个宏来表示:
添加EPOLL_CTL_ADD,
删除EPOLL_CTL_DEL,
修改EPOLL_CTL_MOD。
分别添加、删除和修改对fd的监听事件。 - fd:是需要监听的fd(文件描述符)
- epoll_event:是告诉内核需要监听什么事,struct epoll_event结构如下:
1
2
3
4
5
6
7
8
9
10
11typedef union epoll_data {
void *ptr;
int fd;
__uint32_t u32;
__uint64_t u64;
} epoll_data_t;
struct epoll_event {
__uint32_t events; /* Epoll events */
epoll_data_t data; /* User data variable */
};
events可以是以下宏的集合1
2
3
4
5
6
7
8EPOLLIN :表示对应的文件描述符可以读(包括对端SOCKET正常关闭);
EPOLLOUT:表示对应的文件描述符可以写;
EPOLLPRI:表示对应的文件描述符有紧急的数据可读(这里应该表示有带外数据到来);
EPOLLERR:表示对应的文件描述符发生错误;
EPOLLHUP:表示对应的文件描述符被挂断;
EPOLLET: 将EPOLL设为边缘触发(Edge Triggered)模式,这是相对于水平触发(Level Triggered)来说的。
EPOLLONESHOT:只监听一次事件,当监听完这次事件之后,
如果还需要继续监听这个socket的话,需要再次把这个socket加入到EPOLL队列里
int epoll_wait(int epfd, struct epoll_event * events, int maxevents, int timeout)
等待epfd上的io事件,最多返回maxevents个事件。
参数events用来从内核得到事件的集合,maxevents告之内核这个events有多大,这个maxevents的值不能大于创建epoll_create()时的size,参数timeout是超时时间(毫秒,0会立即返回,-1将不确定,也有说法说是永久阻塞)。该函数返回需要处理的事件数目,如返回0表示已超时。
工作原理
为什么epoll比select/poll高效?简单的说,是因为三个技术的使用:内存映射(mmap),红黑树,链表。
mmap将用户空间的一块虚拟地址和内核空间的一块虚拟地址映射到同一块物理内存地址,如此一来,这块物理内存对内核和用户均可见(类似共享内存),减少了epoll监听的句柄从用户态拷贝到内核态,内核可以直接看到epoll监听的句柄,效率高。
上面mmap出来的内存如何保存epoll所监听的套接字?就是使用的红黑树去存储所有的套接字,当添加或者删除一个套接字时,都在红黑树上去处理,红黑树本身的插入和删除性能比较好(O(logn))。
epoll在返回时,只处理就绪的套接字,非就绪的套接字会直接跳过,这是怎么回事嘞?其实这就是最后那个技术:链表。当某个套接字就绪,则将套接字插入到就绪链表中,所以每次epoll返回时,只需要遍历那个就绪链表就可以获取所有就绪的套接字进行处理。
那这个链表是怎么维护的嘞?epoll在插入一个新的套接字时,同时向内核注册回调函数,告诉内核:如果这个套接字的中断到了,就调用回调函数把这个套接字插入到就绪链表里。
总结下:
在调用epoll_create时,建立一个epoll对象,使用mmap将一块用户虚拟地址和内核虚拟地址映射到同一块物理内存,在该物理内存创建一个红黑树,用于后续的描述符的插入和查询,还会在该内存中创建一个链表,用于存储就绪的描述符。
在调用epoll_ctl函数时,将一个指定的描述符插入到红黑树中(如果已经有了则不会插入,立即返回),或者从红黑树中删除,插入的同时还会注册该描述符的回调函数,告诉内核,当该描述符的中断到达时,将该描述符插入到就绪链表。
在调用epoll_wait时,如果就绪链表非空,则将就绪链表中的描述符拷贝到用户空间指定的集合中。如果链表为空,则阻塞(取决于timeout参数)。
epoll还有两个工作模式:水平触发LT(level trigger)和边缘触发ET(edge trigger)。
在内核发现有句柄的IO准备就绪时,将该句柄插入到就绪链表,当调用epoll_wait时,将该链表拷贝到用户空间,清空该链表,此时epoll_wait还做了一件事情,判断这些句柄是不是ET模式(默认是LT模式),如果不是ET,并且该句柄上还有没有处理完的事件,则将该句柄再插入到链表中。所以,非ET的句柄,只要它上面还有事件,epoll_wait每次都会返回。而ET模式的句柄,除非有新中断到,即使socket上的事件没有处理完,也是不会次次从epoll_wait返回的。
举个例子:
- 我们已经把一个用来从管道中读取数据的文件句柄(RFD)添加到epoll描述符
- 这个时候从管道的另一端被写入了2KB的数据
- 调用epoll_wait(2),并且它会返回RFD,说明它已经准备好读取操作
- 然后我们读取了1KB的数据
- 调用epoll_wait(2)……
如果该句柄被设置为EPOLLET,则下一次调用epoll_wait时会挂起,等待新的中断到达,第5步没有读取完的数据会被丢弃。
如果是EPOLLLT(默认),下一次调用epoll_wait时该句柄还会返回,直到将该句柄中的数据全部读取完毕。
对比
epoll也是IO多路复用的一种,还有一种典型代表就是select。回忆一下select 的工作方式:
- 创建一个句柄集合,用于保存将要监视的描述符,其默认最大为1024个。
- 将该集合从用户空间拷贝到内核空间(一次拷贝),用于内核监视。
- 内核检测到集合中有描述符就绪时,将就绪的数量返回,并且将集合再次拷贝到用户空间(两次拷贝)。
- 使用FD_ISSET宏函数来检测哪些文件I/O可读可写(遍历)
- select对于句柄的监控是建立在内核的修改之上的,也就是说经过一次监控之后,内核会修改位,因此再次监控时需要再次从用户态向内核态进行拷贝(第N次拷贝)。
相比之下,epoll的优势就非常明显了:
- 句柄直接建立在内核中,减少了用户空间和内核空间之间的拷贝次数。
- 减少对就绪句柄的遍历
其他
更新于2018 04 11
为什么要用红黑树呢?为什么不用AVL树或者hash表呢?
疑惑了挺长一段时间吧,这几天忙于啃《深度探索C++对象模型》(久负盛名,啃不动的说),今天下午忙里偷闲(翘课)各种搜索,最后总结如下:
首先hash表示肯定是不行的,它的O(1)的威力体现在完全静态的数据中进行查找操作,也就是少数的插入操作,然后无数次的查找操作。而此处需要频繁的进行插入与删除。
AVL树和红黑树的查询时间复杂度相同,甚至比红黑树要高,那为什么不用AVL树呢?首先可以肯定的是AVL树的平衡性非常好,它保证每一个结点的子树高度差不超过1, 而红黑树并不追求“完全平衡”——它只要求部分地达到平衡要求,降低了对旋转的要求,从而提高了性能。也就是说,每次插入或者删除一个结点,AVL要进行多次的结点调整,而红黑树最多三次调整就可以(可以变色),这就导致了红黑树的插入删除性能比AVL要好很多。
总结的说:AVL更平衡,结构上更加直观,时间效能针对读取而言更高;维护稍慢,时间开销较大。
红黑树,读取略逊于AVL,维护强于AVL,空间开销与AVL类似,内容极多时略优于AVL,维护优于AVL。
如果需求是搜索次数远大于插入和删除,则用AVL更佳。如果搜索,插入和删除操作差不多,则用红黑树更佳。
所以结果就很明确啦
参考资料:
《linux/UNIX系统编程手册》
《UNIX网络编程》
epoll详细工作原理
Linux IO模式及 select、poll、epoll详解
epoll的原理
epoll详解