清单 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
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 中,有基于最小堆实现的定时器,它主要提供了以下的几个接口: