libevent源码深度剖析九 集成定时器事件

系列目录

(1)libevent源码深度剖析一 序 (2)libevent源码深度剖析二 Reactor模式 (3)libevent源码深度剖析三 libevent基本使用场景和事件流程 (4)libevent源码深度剖析四 libevent源代码文件组织 (5)libevent源码深度剖析五 libevent的核心:事件event (6)libevent源码深度剖析六 初见事件处理框架 (7)libevent源码深度剖析七 事件主循环 (8)libevent源码深度剖析八 集成信号处理 (9)libevent源码深度剖析九 集成定时器事件 (10)libevent源码深度剖析十 支持I/O多路复用技术 (11)libevent源码深度剖析十一 时间管理 (12)libevent源码深度剖析十二 让libevent支持多线程 (13)libevent源码深度剖析十三 libevent信号处理注意点

现在再来详细分析libevent中I/O事件和Timer事件的集成,与Signal相比,Timer事件的集成会直观和简单很多。Libevent对堆的调整操作做了一些优化,本节还会描述这些优化方法。

1.集成到事件主循环

因为系统的I/O机制像select()和epoll_wait()都允许程序制定一个最大等待时间(也称为最大超时时间)timeout,即使没有I/O事件发生,它们也保证能在timeout时间内返回。 那么根据所有Timer事件的最小超时时间来设置系统I/O的timeout时间;当系统I/O返回时,再激活所有就绪的Timer事件就可以了,这样就能将Timer事件完美的融合到系统的I/O机制中了。 具体的代码在源文件event.c的event_base_loop()中,现在就对比代码来看看这一处理方法:

 1if (!base->event_count_active && !(flags & EVLOOP_NONBLOCK)) {
 2          // 根据Timer事件计算evsel->dispatch的最大等待时间
 3          timeout_next(base, &tv_p);
 4      } else { 
 5          // 如果还有活动事件,就不要等待,让evsel->dispatch立即返回
 6          evutil_timerclear(&tv);
 7      }
 8      // ...
 9      // 调用select() or epoll_wait() 等待就绪I/O事件
10      res = evsel->dispatch(base, evbase, tv_p);
11      // ...
12      // 处理超时事件,将超时事件插入到激活链表中
13      timeout_process(base);

timeout_next()函数根据堆中具有最小超时值的事件和当前时间来计算等待时间,下面看看代码:

 1static int timeout_next(struct event_base *base, struct timeval **tv_p){
 2    struct timeval now;
 3    struct event *ev;
 4    struct timeval *tv = *tv_p;
 5    // 堆的首元素具有最小的超时值
 6    if ((ev = min_heap_top(&base->timeheap)) == NULL) {
 7        // 如果没有定时事件,将等待时间设置为NULL,表示一直阻塞直到有I/O事件发生
 8        *tv_p = NULL;
 9        return (0);
10    }
11    // 取得当前时间
12    gettime(base, &now);
13    // 如果超时时间<=当前值,不能等待,需要立即返回
14    if (evutil_timercmp(&ev->ev_timeout, &now, <=)) {
15        evutil_timerclear(tv);
16        return (0);
17    }
18    // 计算等待的时间=当前时间-最小的超时时间
19    evutil_timersub(&ev->ev_timeout, &now, tv);
20    return (0);
21}

2.Timer小根堆

libevent使用堆来管理Timer事件,其key值就是事件的超时时间,源代码位于文件min_heap.h中。 所有的数据结构书中都有关于堆的详细介绍,向堆中插入、删除元素时间复杂度都是O(lgN),N为堆中元素的个数,而获取最小key值(小根堆)的复杂度为O(1)。堆是一个完全二叉树,基本存储方式是一个数组。 libevent实现的堆还是比较轻巧的,虽然我不喜欢这种编码方式(搞一些复杂的表达式)。轻巧到什么地方呢,就以插入元素为例,来对比说明,下面伪代码中的size表示当前堆的元素个数:

典型的代码逻辑如下:

 1Heap[size++] = new; // 先放到数组末尾,元素个数+1
 2// 下面就是shift_up()的代码逻辑,不断的将new向上调整
 3_child = size;
 4while(_child>0) // 循环
 5{
 6   _parent = (_child-1)/2; // 计算parent
 7   if(Heap[_parent].key < Heap[_child].key)
 8      break; // 调整结束,跳出循环
 9   swap(_parent, _child); // 交换parent和child
10}

而libevent的heap代码对这一过程做了优化,在插入新元素时,只是为新元素预留了一个位置hole(初始时hole位于数组尾部),但并不立刻将新元素插入到hole上,而是不断向上调整hole的值,将父节点向下调整,最后确认hole就是新元素的所在位置时,才会真正的将新元素插入到hole上,因此在调整过程中就比上面的代码少了一次赋值的操作,代码逻辑是:

 1// 下面就是shift_up()的代码逻辑,不断的将new的“预留位置”向上调整
 2_hole = size; // _hole就是为new预留的位置,但并不立刻将new放上
 3while(_hole>0) // 循环
 4{
 5    _parent = (_hole-1)/2; // 计算parent
 6    if(Heap[_parent].key < new.key)
 7        break; // 调整结束,跳出循环
 8    Heap[_hole] = Heap[_parent]; // 将parent向下调整
 9    _hole = _parent; // 将_hole调整到_parent
10}
11Heap[_hole] = new; // 调整结束,将new插入到_hole指示的位置
12size++; // 元素个数+1

由于每次调整都少做一次赋值操作,在调整路径比较长时,调整效率会比第一种有所提高。libevent中的min_heap_shift_up_()函数就是上面逻辑的具体实现,对应的向下调整函数是min_heap_shift_down_()

举个例子,向一个小根堆3, 5, 8, 7, 12中插入新元素2,使用第一中典型的代码逻辑,其调整过程如下图所示:

使用libevent中的堆调整逻辑,调整过程如下图所示:

对于删除和元素修改操作,也遵从相同的逻辑,就不再罗嗦了。

3.小节

通过设置系统I/O机制的wait时间,从而简洁的集成Timer事件;主要分析了libevent对堆调整操作的优化。

原文发布于微信公众号 - 高性能服务器开发(easyserverdev)

原文发表时间:2018-05-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏尾尾部落

[剑指offer] 矩形覆盖

我们可以用2 * 1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2 * 1的小矩形无重叠地覆盖一个2 * n的大矩形,总共有多少种方法?

10520
来自专栏木头编程 - moTzxx

JQuery 遍历被选中的checkbox元素

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u011415782/article/de...

39130
来自专栏吴伟祥

Velocity语法大全 转

本文转载自:http://www.cnblogs.com/codingsilence/archive/2011/03/29/2146580.html

7340
来自专栏JavaEE

thumbnails图像处理库的使用前言:thumbnails的使用:

53630
来自专栏nice_每一天

教你开发jQuery插件(转) 教你开发jQuery插件(转)

原文:http://www.cnblogs.com/Wayou/p/jquery_plugin_tutorial.html

19610
来自专栏difcareer的技术笔记

关于EGL与示例代码[转]

OpenGL ES的javax.microedition.khronos.opengles 包定义了平台无关的GL绘图指令,EGL(javax.microedi...

9430
来自专栏柠檬先生

sass 基础——回顾

1.webstorm 自动编译SASS   下载安装包 http://rubyinstaller.org/downloads/   然后点击安装,路径为默认路...

24670
来自专栏程序员互动联盟

【答疑解惑】getchar()与EOF

先看下面的代码: while((c = getchar()) != EOF){ putchar(c); } 这一段代码是The C Programming ...

38390
来自专栏CDA数据分析师

技能 | Excel将文本型数字转为数值型的8种方法

问题描述 问:文本型数字不能参与运算怎么办? ? 该问题的进一步解读: 文本型的数字常出现在一些软件数据导出,或是某些由left、right、text等函数转换...

21890
来自专栏GreenLeaves

JS框架设计之加载器所在路径的探知一模块加载系统

1、要加载一个模块,我们需要一个URL作为加载地址,一个script作为加载媒介,但用户在require是都用ID,我们需要一个将ID转换为URL的方法,思路很...

21950

扫码关注云+社区

领取腾讯云代金券