3G Eden
RSS注册的信号处理函数则用来驱动定时器系统：
清单 7. 信号处理函数驱动定时器
/* Tick Bookkeeping */
static void sig_func(int signo)
{
struct timer *node = timer_list.header.lh_first;
for ( ; node != NULL; node = node->entries.le_next) {
node->elapse++;
if(node->elapse >= node->interval) {
node->elapse = 0;
node->cb(node->id, node->user_data, node->len);
}
}
}
|
它主要是在每次收到 SIGALRM 信号时，执行定时器链表中的每个定时器 elapse 的自增操作，并与 interval 相比较，如果相等，代表注册的定时器已经超时，这时则调用注册的回调函数。
上面的实现，有很多可以优化的地方：考虑另外一种思路，在定时器系统内部将维护的相对 interval 转换成绝对时间，这样，在每 PerTickBookkeeping 时，只需将当前时间与定时器的绝对时间相比较，就可以知道是否该定时器是否到期。这种方法，把递增操作变为了比较操作。并且上面的实现方式，效率也不高，在执行 StartTimer，StopTimer，PerTickBookkeeping 时，算法复杂度分别为 O(1)，O(n)，O(n)，可以对上面的实现做一个简单的改进，在 StartTimer 时，即在添加 Timer 实例时，对链表进行排序，这样的改进，可以使得在执行 StartTimer，StopTimer，PerTickBookkeeping 时，算法复杂度分别为 O(n)，O(1)，O(1) 。改进后的定时器系统如下图 1：
图 1. 基于排序链表的定时器
基于 2.6 版本内核定时器的实现 (Posix 实时定时器 )
Linux 自 2.6 开始，已经开始支持 POSIX timer ［ 2 ］所定义的定时器，它主要由下面的接口构成 :
清单 8. POSIX timer 接口
#include <signal.h> #include <time.h> int timer_create(clockid_t clockid, struct sigevent *evp, timer_t *timerid); int timer_settime(timer_t timerid, int flags, const struct itimerspec *new_value, struct itimerspec * old_value); int timer_gettime(timer_t timerid, struct itimerspec *curr_value); int timer_getoverrun(timer_t timerid); int timer_delete(timer_t timerid); |
这套接口是为了让操作系统对实时有更好的支持，在链接时需要指定 -lrt 。
timer_create(2): 创建了一个定时器。
timer_settime(2): 启动或者停止一个定时器。
timer_gettime(2): 返回到下一次到期的剩余时间值和定时器定义的时间间隔。出现该接口的原因是，如果用户定义了一个 1ms 的定时器，可能当时系统负荷很重，导致该定时器实际山 10ms 后才超时，这种情况下，overrun=9ms 。
timer_getoverrun(2): 返回上次定时器到期时超限值。
timer_delete(2): 停止并删除一个定时器。
上面最重要的接口是 timer_create(2)，其中，clockid 表明了要使用的时钟类型，在 POSIX 中要求必须实现 CLOCK_REALTIME 类型的时钟。 evp 参数指明了在定时到期后，调用者被通知的方式。该结构体定义如下 :
清单 9. POSIX timer 接口中的信号和事件定义
union sigval {
int sival_int;
void *sival_ptr;
};
struct sigevent {
int sigev_notify; /* Notification method */
int sigev_signo; /* Timer expiration signal */
union sigval sigev_value; /* Value accompanying signal or
passed to thread function */
void (*sigev_notify_function) (union sigval);
/* Function used for thread
notifications (SIGEV_THREAD) */
void *sigev_notify_attributes;
/* Attributes for notification thread
(SIGEV_THREAD) */
pid_t sigev_notify_thread_id;
/* ID of thread to signal (SIGEV_THREAD_ID) */
};
|
其中，sigev_notify 指明了通知的方式 :
SIGEV_NONE
当定时器到期时，不发送异步通知，但该定时器的运行进度可以使用 timer_gettime(2) 监测。
SIGEV_SIGNAL
当定时器到期时，发送 sigev_signo 指定的信号。
SIGEV_THREAD
当定时器到期时，以 sigev_notify_function 开始一个新的线程。该函数使用 sigev_value 作为其参数，当 sigev_notify_attributes 非空，则制定该线程的属性。注意，由于 Linux 上线程的特殊性，这个功能实际上是由 glibc 和内核一起实现的。
SIGEV_THREAD_ID (Linux-specific)
仅推荐在实现线程库时候使用。
如果 evp 为空的话，则该函数的行为等效于：sigev_notify = SIGEV_SIGNAL，sigev_signo = SIGVTALRM，sigev_value.sival_int = timer ID 。
由于 POSIX timer ［ 2 ］接口支持在一个进程中同时拥有多个定时器实例，所以在上面的基于 setitimer() 和链表的 PerTickBookkeeping 动作就交由 Linux 内核来维护，这大大减轻了实现定时器的负担。由于 POSIX timer ［ 2 ］接口在定时器到期时，有更多的控制能力，因此，可以使用实时信号避免信号的丢失问题，并将 sigev_value.sival_int 值指定为 timer ID，这样，就可以将多个定时器一起管理了。需要注意的是，POSIX timer ［ 2 ］接口只在进程环境下才有意义 (fork(2) 和 exec(2) 也需要特殊对待 )，并不适合多线程环境。与此相类似的，Linux 提供了基于文件描述符的相关定时器接口：
清单 10. Linux 提供的基于文件描述符的定时器接口
#include <sys/timerfd.h> int timerfd_create(int clockid, int flags); int timerfd_settime(int fd, int flags, const struct itimerspec *new_value, struct itimerspec *old_value); int timerfd_gettime(int fd, struct itimerspec *curr_value); |
这样，由于基于文件描述符，使得该接口可以支持 select(2)，poll(2) 等异步接口，使得定时器的实现和使用更加的方便，更重要的是，支持 fork(2)，exec(2) 这样多进程的语义，因此，可以用在多线程环境之中，它们的使用比 POSIX timer ［ 2 ］更加的灵活，其根本原因在于定时器的管理统一到了 unix/linux 基本哲学之一 ---- “一切皆文件”之下。
最小堆指的是满足除了根节点以外的每个节点都不小于其父节点的堆。这样，堆中的最小值就存放在根节点中，并且在以某个结点为根的子树中，各节点的值都不小于该子树根节点的值。一个最小堆的例子如下图 2：
图 2. 最小堆
一个最小堆，一般支持以下几种操作：
Insert(TimerHeap, Timer): 在堆中插入一个值，并保持最小堆性质，具体对应于定时器的实现，则是把定时器插入到定时器堆中。根据最小堆的插入算法分析，可以知道该操作的时间复杂度为 O(lgn) 。
Minimum(TimerHeap): 获取最小堆的中最小值；在定时器系统中，则是返回定时器堆中最先可能终止的定时器。由于是最小堆，只需返回堆的 root 即可。此时的算法复杂度为 O(1) 。
ExtractMin(TimerHeap): 在定时器到期后，执行相关的动作，它的算法复杂度为 O(1) 。
最小堆本质上是一种最小优先级队列 (min-priority queue) 。定时可以作为最小优先级队列的一个应用，该优先级队列把定时器的时间间隔值转化为一个绝对时间来处理，ExtractMin 操则是在所有等待的定时器中，找出最先超时的定时器。在任何时候，一个新的定时器实例都可通过 Insert 操作加入到定时器队列中去。
在 pjsip 项目的基础库 pjlib 中，有基于最小堆实现的定时器，它主要提供了以下的几个接口：
清单 10. pjlib 提供的基于最小堆的定时器接口
/**
* Create a timer heap.
*/
PJ_DECL(pj_status_t) pj_timer_heap_create( pj_pool_t *pool,
pj_size_t count,
pj_timer_heap_t **ht);
/**
* Destroy the timer heap.
*/
PJ_DECL(void) pj_timer_heap_destroy( pj_timer_heap_t *ht );
/**
* Initialize a timer entry. Application should call this function at least
* once before scheduling the entry to the timer heap, to properly initialize
* the timer entry.
*/
PJ_DECL(pj_timer_entry*) pj_timer_entry_init( pj_timer_entry *entry,
int id,
void *user_data,
pj_timer_heap_callback *cb );
/**
* Schedule a timer entry which will expire AFTER the specified delay.
*/
PJ_DECL(pj_status_t) pj_timer_heap_schedule( pj_timer_heap_t *ht,
pj_timer_entry *entry,
const pj_time_val *delay);
/**
* Cancel a previously registered timer.
*/
PJ_DECL(int) pj_timer_heap_cancel( pj_timer_heap_t *ht,
pj_timer_entry *entry);
/**
* Poll the timer heap, check for expired timers and call the callback for
* each of the expired timers.
*/
PJ_DECL(unsigned) pj_timer_heap_poll( pj_timer_heap_t *ht,
pj_time_val *next_delay);
|
pjlib 中的定时器在内部使用数组的方式实现堆，这样对于内存空间的使用将更加的紧凑；它的实现还可在定时器的数量超过预先设定的最大数量时会自己增加最大定时器数量。文件 pjlib/src/pjlib-test/timer.c 是它的一个单元测试。与基于链表方式的实现相比较，明显它的时间复杂度要低一些，这样可以支持更多的定时器实例。
基于时间轮 (Timing-Wheel) 方式实现的定时器
