定时器(timer)是Linux提供的一种定时服务的机制[1]。在使用定时器时，预先设置一个定时时间，并给定时时间到达时执行预先设定的任务。目前Linux系统本身提供了多种用户级定时器接口，其中精度较低的如Alarm函数，精度为秒级，能够满足一些定时精度低的应用场合。但由于同一进程中不能同时调用多个Alarm函数，因此应用场合有限。Setitimer克服不能重复使用的缺点，同时将精度提高到毫秒级，但是同一个进程中只能设置一个这种定时器。Timerfd是Linux为用户程序提供的另一个定时器接口，这个接口基于文件描述符，能够被用于select/poll的应用场景，其精度可以达到纳秒级，是用户空间高精度定时器的理想选择。本设计的定时器池基于时间轮原理,设定一个时间片大小作为时间间隔的基本单位，将时间轮分为固定时间片数，只需要一个Timerfd来管理该定时器池，设定超时时间间隔为时间片的大小，每次当超过一个时间片的时间时,系统将会通知定时器池的管理线程，管理线程做出相应的动作。综合以上优劣，本文提出一种定时器池的算法，用于管理大量定时器[2-3]。

1 设计原理以及工作流程
1.1 定时器池的结构
    本定时器池选用Timerfd作为添加和删除定时器的接口，使用Linux提供的函数timerfd_settime来设定定时的间隔时间大小。本定时器池的时间间隔为一个时间片time_slot大小。设定之后,管理线程等待系统的信号通知，系统每隔一个时间片就给定时器池发送一个信号，当收到此信号时，管理线程轮询定时器池，查看池中是否有超时的定时器，若有则按用户需求执行相关动作。定时器池的结构如图1所示。

    当用户想要添加或者删除定时器时，可直接调用添加或者删除函数，定时器池内部的管理线程将自动处理用户的需求，将用户所需的定时器加到定时器池相应的时间片链表中统一管理。定时器池中定时器的组织形式如图2所示。

    图2中模拟了时间轮原理：用一个结构体来保存一个时间片，以时间片作为定时器粒度的最小单位，以及该时间片下定时器的数量，同时该结构体包含该时间片下的定时器链表的链表头部，用来链接双向链表，链表选用Linux内核所采用的嵌入式双向链表结构，如式(1)所示：
    struct list_head{
    struct list_head *next, *prev}     (1)
1.2 定时器的添加
    用户根据其需求在定时器池中加入定时器，插入定时器之前所要做的工作有：
    (1)计算定时器插入时间片，每个定时器的插入时间片计算公式为：
    timer->slot =(pool->cur_slot+timer->interval/
    pool->time_slot )% pool->slot_num;        (2)
式(2)中timer为要插入的定时器结构，其中的timer->slot为定时器插入的时间片，pool->cur_slot为定时器池当前所轮询到的时间片，time->interval为所要添加的定时器的定时时间间隔，pool->time_slot为每个时间片的长度，pool->slot_num为定时器池的时间片总数。
    (2)计算定时器的时间轮数，每个定时器的时间轮数计算公式为：
    timer->round=timer->interval/
    (pool->time_slot*pool->slot_num)        (3)
其中的timer->round为该定时器的时间轮数，通过式(3)得出定时器的时间轮数。
    (3)用户在添加定时器到定时器池中时，需要指定定时器的超时时间,以及超时时间到达后所需要执行的函数。同时，必须指定该定时器是一次性定时还是周期性定时，以便管理线程删除或者重新添加该定时器。
1.3 定时器池的工作流程
    创建并初始化定时器池，此时内存中保存着一个定时器池动态管理单元，用户通过相应接口请求定时器池按其要求增加或者删除定时器。定时器池工作流程如图3所示。工作时，内部的定时器管理线程一直监听用户请求，同时管理线程等待系统的信号通知，当有信号通知到来时，管理线程轮询定时器池,查看池中已有的定时器池中是否有超时的定时器，若有则按照用户指定的动作来执行。原因是：(1)可直接调用函数，这种方法的优点是不用产生线程的开销;缺点是将占用定时器的时间，并且若该函数执行时间较长，将严重影响定时器的性能。(2)产生线程来执行该任务，这种方法的优点是不占用定时器池的时间，缺点是需要产生线程开销[4]。

    管理线程还将检查定时器的属性，即该定时器是一次性定时还是周期性定时，如果是一次性定时，当定时器超时后，管理线程将该定时器从链表结构中移除；如果是周期性定时，当超时后，管理线程首先将定时器从链表结构中移除，然后计算该定时器池再次插入的时间片以及时间轮数，得到以上数据后，按照时间片数将定时器重新插入到相应的链表中，实现用户的需求。
1.4 定时器的删除
    当定时器时间到时，若为一次性定时，当定时器超时后，管理线程自动地将定时器从链表中移除，释放相关内存。但是，当用户因为某种需要在中途删除未超时的一次性定时器或者删除周期性定时器时，此时需要调用定时器删除函数来删除定时器。但是从定时器链表中寻找特定的定时器并非一件容易的事情,本文采用基于红黑树的形式,相应的结构体设计如下：
    typedef int key_t;                    (4)
    typedef void* data_t;                (5)
    struct rb_node_t {
            struct rb_node_t *left, *right, *parent;
            key_t key; data_t data;    
        color_t color;}            (6)
    在添加定时器时，会给每个定时器分配一个唯一的id来标记定时器，该id存放在一张位图表中，将以O(1)的速度索取未用的id或者存储到期回收的定时器id。将该定时器id作为红黑树的键值key，将指向定时器的内存结构指针作为红黑树的data 数据。管理线程同时维护红黑树。当需要非正常删除某个定时器时,通过定时器的id找出其在红黑树中的位置，获取定时器结构在内存中所在位置的指针,以便从定时器链表中删除该定时器。红黑树的查找性能保持在O(logn)，从而快速找出定时器指针所在红黑树的单元。
2 定时器池算法的实现
    采用面向对象的思想，头文件.h中只包含用户可以查看到基本的结构，.c文件中包含实际的定时器池的内部数据结构，这样可以避免用户操作结构体中的数据成员[7]。
2.1 定时器池的函数接口

    定时器的结构数据如下：
    struct timer_pool_s {
　　bool(*init)(struct timer_pool_s *pool, struct timer_pool_
        conf *conf );  //初始化定时器结构
     timer_id(*add)(sturct timer_pool_s *this, struct timer
        *timer, TIMER_TYPE type);  //添加定时器
        bool(*del )(struct timer_pool_s *pool, timer_id id);
    //删除定时器
        void( *enable )( struct timer_pool_s *pool );
                                         //使能定时器池
        void(*disable )( struct timer_pool_s *pool);
                                       //禁用定时器池
        void(*start )(struct timer_pool_s *pool);   //开启定时器池
         void ( *stop )( struct timer_pool_s *pool);
                                       //关闭定时器池
    };
2.2 定时器池的使用方法
    struct timter_pool_s  *timer_pool = create_timer_pool();
    timer_pool->init(timer_pool, timer_conf);
    timer_pool->add(timer_pool, your_timer，timer_type);
    timer_pool->start(timer_pool);
    timer_pool->del(timer_pool, timer_id)l
    destroy_timer_pool( timer_pool );
　    其中的your_timer代表用户想要添加的定时器，在该定时器结构中设置了当定时器超时后所要执行的函数地址以及是用线程启动执行该函数,或是直接调用启动该函数。
3 性能测试
    本定时器池使用双向链表来管理各个定时器，每次轮询所有时间片所链接的定时器链表下的定时器将占用一些系统时间，故定时器池的最小时间片应该大于轮询链表中所有定时器的时间，以及到期的定时器执行相关动作所需要的时间的总和，因此定时器池不能无限地加入定时器。对于一个给定的时间片大小，通过不断对比测试可以找出该时间片大小下，定时器池中最佳的定时器数量，定时器池中定时器的数量最少不应少于5个，否则就与定时器池设计的初衷相左。
    (1)测试环境： Intel(R) Core(TM) i3-2100 CPU @ 2.8 GHz，2 GB内存; Fedora 14(内核2.6.35.14-106.fc14.i686 )。
    (2)测试设计：测试时采用时间片粒度分别为40 ms, 80 ms、200。每次测试时,在系统尚未执行timer_pool->start前将定时器加入到定时器池中，在定时器池开启后，立刻获取当前时间，定时器超时后，触发超时执行函数获取当时的时间，记录保存。对于每个时间片都记录两组数据，分别为定时器数目为5个、10个，每个定时器的定时时间分别为定时器时间片大小的1~N倍，N代表定时器数目。测试的结果为某个时间片下定时器的相对误差以及按时响应的概率，其中按时响应概率为准时响应的定时器个数占定时器总数（测试次数100次）的百分比，相对误差代表前后两次定时任务的绝对误差的差值，体现定时器的稳定性。每种情况测试100次，同时包括了本文90%以上的测试结果，并剔除了某些因为系统原因导致结果偏差太大的数据。定时器触发方式分为部分周期性触发、部分一次性触发，定时器超时后，超时执行方式为直接调用执行[5-7]。测试结果如表1所示。

    由表1可见，当定时器池的时间片较小时，池中定时器数目越少，定时器池性能越好。随着定时器数目的增加，管理线程轮询所需要的时间可能会超过一个时间片的长度，造成定时器池在接收下一个时间片超时的信号延迟，从而导致定时器的性能急剧下降。从表1中可以看到，当定时器池时间片≥40 ms时，能够较好地满足性能需求。因此选择该定时器池的时间片最小不能低于40 ms，并且定时器个数要控制在5个以内，否则定时器将不能保证及时被管理线程轮询，从而影响定时器池的效率。另外，对于一些执行时间特别长的执行函数，此时应该选用的执行方式为线程执行，即定时器到时后，产生一个线程来执行超时执行函数。如果执行函数需要较长时间，则应选用线程方式执行；如果时间相对较短，则可以采用直接调用方式，但前提是不能影响到定时器池的性能。
    本文设计并实现了一种基于时间轮以及红黑树的定时器池算法，可方便用户统一管理大量的定时器。对于定时器的添加、删除、查找，以及轮询等技术进行了细致地分析，提高了定时器池的响应速度，以满足不同场合的需求。
参考文献
[1] 赵汝聪，谢维信. 一种新的嵌入式Linux高性能定时器实现方法[J].信号处理，2009,25(3)：439-443.
[2] 赵红武，金瑜，刘云生.一种改进的定时器实现算法及其性能分析[J].微计算机应用,2006,27(3)：343-345.
[3] 唐靓. Linux 2．6细粒度定时器的设计[J].电脑知识与技术, 2009,36(5):10259-10261.
[4] 晋磊，陈昌鹏，陈凯，等.Linux平台下增强型定时器服务的研究[J]. 微型电脑应用,2005,21(11)：41-43.
[5] 林绍太，张会.Linux定时器及其在网络安全中的应用[J].计算机系统应用,2004(10)：63-64.
[6] 杨焓，毛玉明. Linux用户空间一种微秒级定时器的实现[C]. 2007中国西部青年通信学术会议,2007.
[7] STEVENS W R. UNIX网路编程(第2卷)[M].北京：人民邮电出版社,2010.