一、已有的定时器接口
时空管理是计算机系统的主要任务。在时间管理中，我们经常利用定时器处理事情：比如tcp协议中利用定时器管理包超时，视频显示中利用定时器来定时显示视 频帧，web服务中利用定时器来管理用户的超时。windows系统提供了SetTimer和timeSetEvent等定时器接口，linux中则提供 了setitimer等接口。这些函数的接口很类似，大体上都是用户提供回调函数和超时时间向OS注册一个定时器事件，OS在超时时间到了的时候，调用用 户提供的回调函数来完成用户想要做的事情。windows下的接口支持单进程中拥有多个定时器，而linux则只允许单进程拥有一个定时器，因此在 linux下的单进程中要使用多个定时器，则需要自己维护管理，这是本文写作的出发点。另外，OS提供的定时器管理算法在大规模定时器的管理方面可能还不 尽人意，这时候就需要用户去优化管理算法了，本文在这方面提供了一点素材。
二、一个最简单的多定时器的实现（linux版）
1、实现细节
这个实现允许用户使用多个自定义的定时器，每个自定义的定时器将周期地被触发直到其被删除。实现的主要思路是：
i）首先在初始化多定时器（init_mul_timer）时利用setitimer注册一个基本的时间单位（如1s）的定时事件；
ii）用户需要set_a_timer注册自定义定时器时，在timer_manage管理结构中记录这个定时器的回调函数和定时周期等参数；
iii）当基本的时间单位到期后（如SIGALRM信号到达时），遍历整个timer_manage，如果有自定义定时器的超时时间到了，就执行相应的回调函数，并将自定义定时器的超时时间置为最初值；否则将自定义定时器的超时时间相应地减一个基本的时间单位；
iv）用户通过del_a_timer来删除某个定时器，通 过destroy_mul_timer来删除整个多定时器。
2、代码
i) mul_timer.h
|
/* This file provides an interface of multiple timers. for convenience, it simplify signal processing.
* Also, it can't be used in multithreading environment.
* Author:bripengandre
* Date:2009-04-29
*/
#ifndef _MUL_TIMER_H_
#define _MUL_TIMER_H_
#include <sys/time.h>
#define MAX_TIMER_CNT 10
#define MUL_TIMER_RESET_SEC 10
#define TIMER_UNIT 60
#define MAX_FUNC_ARG_LEN 100
#define INVALID_TIMER_HANDLE (-1)
typedef int timer_handle_t;
typedef struct _timer_manage
{
struct _timer_info
{
int state; /* on or off */
int interval;
int elapse; /* 0~interval */
int (* timer_proc) (void *arg, int arg_len);
char func_arg[MAX_FUNC_ARG_LEN];
int arg_len;
}timer_info[MAX_TIMER_CNT];
void (* old_sigfunc)(int);
void (* new_sigfunc)(int);
struct itimerval value, ovalue;
}_timer_manage_t;
/* success, return 0; failed, return -1 */
int init_mul_timer(void);
/* success, return 0; failed, return -1 */
int destroy_mul_timer(void);
/* success, return timer handle(>=0); failed, return -1 */
timer_handle_t set_a_timer(int interval, int (* timer_proc) (void *arg, int arg_len), void *arg, int arg_len);
/* success, return 0; failed, return -1 */
int del_a_timer(timer_handle_t handle);
#endif /* _MUL_TIMER_H_ */
|
ii)mul_timer.c
|
#include <stdio.h>
#include <string.h>
#include <signal.h>
#include <time.h>
#include "mul_timer.h"
static struct _timer_manage timer_manage;
static void sig_func(int signo);
/* success, return 0; failed, return -1 */
int init_mul_timer(void)
{
int ret;
memset(&timer_manage, 0, sizeof(struct _timer_manage));
if( (timer_manage.old_sigfunc = signal(SIGALRM, sig_func)) == SIG_ERR)
{
return (-1);
}
timer_manage.new_sigfunc = sig_func;
timer_manage.value.it_value.tv_sec = MUL_TIMER_RESET_SEC;
timer_manage.value.it_value.tv_usec = 0;
timer_manage.value.it_interval.tv_sec = TIMER_UNIT;
timer_manage.value.it_interval.tv_usec = 0;
ret = setitimer(ITIMER_REAL, &timer_manage.value, &timer_manage.ovalue);
return (ret);
}
/* success, return 0; failed, return -1 */
int destroy_mul_timer(void)
{
int ret;
if( (signal(SIGALRM, timer_manage.old_sigfunc)) == SIG_ERR)
{
return (-1);
}
ret = setitimer(ITIMER_REAL, &timer_manage.ovalue, &timer_manage.value);
if(ret < 0)
{
return (-1);
}
memset(&timer_manage, 0, sizeof(struct _timer_manage));
return(0);
}
/* success, return timer handle(>=0); failed, return -1 */
timer_handle_t set_a_timer(int interval, int (* timer_proc) (void *arg, int arg_len), void *arg, int arg_len)
{
int i;
if(timer_proc == NULL || interval <= 0)
{
return (-1);
}
for(i = 0; i < MAX_TIMER_CNT; i++)
{
if(timer_manage.timer_info[i].state == 1)
{
continue;
}
memset(&timer_manage.timer_info[i], 0, sizeof(timer_manage.timer_info[i]));
timer_manage.timer_info[i].timer_proc = timer_proc;
if(arg != NULL)
{
if(arg_len > MAX_FUNC_ARG_LEN)
{
return (-1);
}
memcpy(timer_manage.timer_info[i].func_arg, arg, arg_len);
timer_manage.timer_info[i].arg_len = arg_len;
}
timer_manage.timer_info[i].interval = interval;
timer_manage.timer_info[i].elapse = 0;
timer_manage.timer_info[i].state = 1;
break;
}
if(i >= MAX_TIMER_CNT)
{
return (-1);
}
return (i);
}
/* success, return 0; failed, return -1 */
int del_a_timer(timer_handle_t handle)
{
if(handle < 0 || handle >= MAX_TIMER_CNT)
{
return (-1);
}
memset(&timer_manage.timer_info[handle], 0, sizeof(timer_manage.timer_info[handle]));
return (0);
}
static void sig_func(int signo)
{
int i;
for(i = 0; i < MAX_TIMER_CNT; i++)
{
if(timer_manage.timer_info[i].state == 0)
{
continue;
}
timer_manage.timer_info[i].elapse++;
if(timer_manage.timer_info[i].elapse == timer_manage.timer_info[i].interval)
{
timer_manage.timer_info[i].elapse = 0;
timer_manage.timer_info[i].timer_proc(timer_manage.timer_info[i].func_arg, timer_manage.timer_info[i].arg_len);
}
}
}
#define _MUL_TIMER_MAIN
#ifdef _MUL_TIMER_MAIN
static void get_format_time(char *tstr)
{
time_t t;
t = time(NULL);
strcpy(tstr, ctime(&t));
tstr[strlen(tstr)-1] = '\0';
return;
}
timer_handle_t hdl[3], call_cnt = 0;
int timer_proc1(void *arg, int len)
{
char tstr[200];
static int i, ret;
get_format_time(tstr);
printf("hello %s: timer_proc1 is here.\n", tstr);
if(i >= 5)
{
get_format_time(tstr);
ret = del_a_timer(hdl[0]);
printf("timer_proc1: %s del_a_timer::ret=%d\n", tstr, ret);
}
i++;
call_cnt++;
return (1);
}
int timer_proc2(void * arg, int len)
{
char tstr[200];
static int i, ret;
get_format_time(tstr);
printf("hello %s: timer_proc2 is here.\n", tstr);
if(i >= 5)
{
get_format_time(tstr);
ret = del_a_timer(hdl[2]);
printf("timer_proc2: %s del_a_timer::ret=%d\n", tstr, ret);
}
i++;
call_cnt++;
return (1);
}
int main(void)
{
char arg[50];
char tstr[200];
int ret;
init_mul_timer();
hdl[0] = set_a_timer(2, timer_proc1, NULL, 0);
printf("hdl[0]=%d\n", hdl[0]);
hdl[1] = set_a_timer(3, timer_proc2, arg, 50);
printf("hdl[1]=%d\n", hdl[1]);
hdl[2] = set_a_timer(3, timer_proc2, arg, 101);
printf("hdl[1]=%d\n", hdl[2]);
while(1)
{
if(call_cnt >= 12)
{
get_format_time(tstr);
ret = destroy_mul_timer();
printf("main: %s destroy_mul_timer, ret=%d\n", tstr, ret);
call_cnt++;
}
if(call_cnt >= 20)
{
break;
}
}
return 0;
}
#endif
|
3、缺陷
i)新建定时器、遍历定时器和删除定时器（查找哪个定时器超时）时时间复杂度都为O(n)（n是定时器的个数）;
ii)适用环境是单线程环境，如要用于多线程，需添加同步操作。
iii)程序中有些小bug，如对新建超时时间为0的定时器没有妥善的处理。
三、多定时器的改进版
1、思路
改进定时器的实现，即是改善二种所指出的几个缺陷，如下是一个改进版,主要是将遍历超时时间的时间复杂度降为了O(1).
改善思路:各定时器以一个链表的形式组织起来,除链表头定时器的超时时间是用绝对时间纪录的外,其它定时器的超时时间均用相对时间(即超时时间-前一个定时器的超时时间)纪录.
注意,各定时器都是一次性的,当定时器的超时被处理后,定时器将被自动删除.另外如果将定时器的结点改为双向结构,可以将删除定时器的时间复杂度降为O(1).
2、数据结构
每个定时器都有一个唯一的ID,这个ID是如下的结构体:
|
typedef struct _timer_handle
{
unsigned long ptr;
unsigned long entry_id;
}*timer_handle_t;
|
ptr纪录的是定时器结点的地址,entry_id则是一个自多定时器初始化后自增的id.ptr和entry_id一起组成定时器结点的key,一方面使得新建定时器时生成key的过程大为简化,另一方面使得删除定时器的时间复杂度降为O(1)（前提是定时器结点采用双向结构）。
定时器结点的数据结构如下：
|
/* timer entry */
typedef struct _mul_timer_entry
{
char is_use; /* 0, not; 1, yes */
struct _timer_handle handle;
unsigned int timeout;
unsigned int elapse; /* */
int (* timer_proc) (void *arg, unsigned int *arg_len); /* callback function */
void *arg;
unsigned int *arg_len;
struct _mul_timer_entry *etr_next;
}mul_timer_entry_t;
|
其中的is_use是用来防止这样一种情况：用户在回调函数中调用kill_timer来删除定时器，这个时候kill_timer和遍历定时器中都有删 除结点的操作，有可能将整个链表搞混乱。所以在调用用户的回调函数前先将is_use置1，在kill_timer中需检查is_use，只有在 is_use为0的情况下，才执行清理定时器结点的操作。
3、代码（windows版）
i)mul_timer.h
|
/* This file provides an interface of multiple timers. it can't be used in multithreading environment.
* Author:bripengandre
* Date:2009-07-19
*/
#ifndef _MUL_TIMER_H_
#define _MUL_TIMER_H_
#include <windows.h>
typedef struct _timer_handle
{
unsigned long ptr;
unsigned long entry_id;
}*timer_handle_t;
/* timer entry */
typedef struct _mul_timer_entry
{
char is_use; /* 0, not; 1, yes */
struct _timer_handle handle;
unsigned int timeout;
unsigned int elapse; /* */
int (* timer_proc) (void *arg, unsigned int *arg_len); /* callback function */
void *arg;
unsigned int *arg_len;
struct _mul_timer_entry *etr_next;
}mul_timer_entry_t;
typedef struct _mul_timer_manage
{
unsigned long entry_id;
unsigned int timer_cnt;
unsigned int time_unit;
struct _mul_timer_entry *etr_head;
UINT timer_id;
};
struct _mul_timer_manage *init_mul_timer(unsigned int time_unit);
timer_handle_t set_timer(struct _mul_timer_manage *ptimer, unsigned int time_out, int (* timer_proc) (void *arg, unsigned int *arg_len), void *arg, unsigned int *arg_len);
int kill_timer(struct _mul_timer_manage *ptimer, timer_handle_t hdl);
int get_timeout_byhdl(struct _mul_timer_manage *ptimer, timer_handle_t hdl);
int get_timeout_bytimeproc(struct _mul_timer_manage *ptimer, int (* timer_proc) (void *arg, unsigned int *arg_len));
int release_mul_timer(struct _mul_timer_manage *ptimer);
int is_valid_time_hdl(timer_handle_t hdl);
#endif /* _MUL_TIMER_H_ */
|
ii)mul_timer.c
|
#include "mul_timer.h"
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void CALLBACK traverse_mul_timer(UINT uTimerID, UINT uMsg, DWORD dwUser, DWORD dw1, DWORD dw2);
static int print_mul_timer(struct _mul_timer_manage *ptimer);
struct _mul_timer_manage *init_mul_timer(unsigned int time_unit)
{
struct _mul_timer_manage *p;
if( (p = malloc(sizeof(struct _mul_timer_manage))) == NULL)
{
return (NULL);
}
p->etr_head = NULL;
p->timer_cnt = 0;
p->time_unit = time_unit;
p->entry_id = 0;
p->timer_id = timeSetEvent(time_unit, 0, (LPTIMECALLBACK )traverse_mul_timer, (DWORD)p, TIME_PERIODIC);
return(p);
}
timer_handle_t set_timer(struct _mul_timer_manage *ptimer, unsigned int time_out, int (* timer_proc) (void *arg, unsigned int *arg_len), void *arg, unsigned int *arg_len)
{
struct _mul_timer_entry *p, *prev, *pnew;
if(ptimer == NULL || time_out == 0)
{
return (NULL);
}
if( (pnew = malloc(sizeof(struct _mul_timer_entry))) == NULL)
{
return (NULL);
}
pnew->is_use = 0;
pnew->arg = arg;
pnew->arg_len = arg_len;
pnew->elapse = 0;
pnew->timer_proc = timer_proc;
p = ptimer->etr_head;
prev = NULL;
while(p != NULL)
{
if(p->timeout < time_out) /* assume the latest time_proc has higher priority */
{
time_out = time_out-p->timeout;
prev = p;
p = p->etr_next;
}
else
{
p->timeout -= time_out;
break;
}
}
pnew->timeout = time_out;
pnew->etr_next = p;
pnew->handle.ptr = (unsigned long )pnew;
pnew->handle.entry_id = ptimer->entry_id;
ptimer->entry_id++;
if(prev == NULL)
{
ptimer->etr_head = pnew;
}
else
{
prev->etr_next = pnew;
}
ptimer->timer_cnt++;
return (&pnew->handle);
}
int kill_timer(struct _mul_timer_manage *ptimer, timer_handle_t hdl)
{
struct _mul_timer_entry *p, *prev;
if(ptimer == NULL)
{
return (0);
}
p = ptimer->etr_head;
prev = NULL;
while(p != NULL)
{
if(p->handle.ptr == hdl->ptr && p->handle.entry_id == hdl->entry_id)
{
break;
}
prev = p;
p = p->etr_next;
}
/* no such timer or timer is in use, return 0 */
if(p == NULL || (p != NULL && p->is_use == 1))
{
return (0);
}
/* has found the timer */
if(prev == NULL)
{
ptimer->etr_head = p->etr_next;
}
else
{
prev->etr_next = p->etr_next;
}
/* revise timeout */
if(p->etr_next != NULL)
{
p->etr_next->timeout += p->timeout;
}
/* delete the timer */
free(p);
p = NULL;
ptimer->timer_cnt--;
return (1);
}
int get_timeout_byhdl(struct _mul_timer_manage *ptimer, timer_handle_t hdl)
{
struct _mul_timer_entry *p;
unsigned int timeout;
if(ptimer == NULL || (struct _mul_timer_entry *)(hdl) == NULL)
{
return (-1);
}
timeout = 0;
p = ptimer->etr_head;
while(p != NULL)
{
if(p->handle.ptr == hdl->ptr && p->handle.entry_id == hdl->entry_id)
{
break;
}
timeout += p->timeout;
p = p->etr_next;
}
if(p == NULL)
{
return (-1);
}
else
{
return ((int)timeout+p->timeout);
}
}
int get_timeout_bytimeproc(struct _mul_timer_manage *ptimer, int (* timer_proc) (void *arg, unsigned int *arg_len))
{
struct _mul_timer_entry *p;
unsigned int timeout;
if(ptimer == NULL || timer_proc == NULL)
{
return (-1);
}
p = ptimer->etr_head;
while((p != NULL) && (p->timer_proc != timer_proc))
{
timeout += p->timeout;
p = p->etr_next;
}
if(p == NULL)
{
return (-1);
}
else
{
return (timeout+p->timeout);
}
}
int release_mul_timer(struct _mul_timer_manage *ptimer)
{
struct _mul_timer_entry *p, *ptmp;
if(ptimer == NULL)
{
return (0);
}
timeKillEvent(ptimer->timer_id);
/* delete all timers */
p = ptimer->etr_head;
while(p != NULL)
{
ptmp = p;
p = p->etr_next;
free(ptmp);
}
/* delete timer_manage */
free(ptimer);
ptimer = NULL;
return (1);
}
int is_valid_time_hdl(timer_handle_t hdl)
{
if(hdl == NULL)
{
return (0);
}
else
{
return (1);
}
}
void CALLBACK traverse_mul_timer(UINT uTimerID, UINT uMsg, DWORD dwUser, DWORD dw1, DWORD dw2)
{
struct _mul_timer_manage *ptimer;
struct _mul_timer_entry *p, *ptmp;
unsigned int timeout;
ptimer = (struct _mul_timer_manage *)dwUser;
if(ptimer == NULL)
{
return;
}
timeout = ptimer->time_unit;
p = ptimer->etr_head;
while(p != NULL)
{
if(p->timeout <= timeout)
{
p->is_use = 1;
p->timer_proc(p->arg, p->arg_len);
ptmp = p;
timeout -= p->timeout;
p = p->etr_next;
free(ptmp);
ptimer->etr_head = p;
}
else
{
p->timeout -= timeout;
p->elapse += timeout;
ptimer->etr_head = p;
break;
}
}
if(p == NULL)
{
ptimer->etr_head = NULL;
}
return;
}
static int print_mul_timer(struct _mul_timer_manage *ptimer)
{
struct _mul_timer_entry *p;
int i;
if(ptimer == NULL)
{
return (0);
}
printf("***************************mul_timer statistics start************************\n");
printf("this mul_timer's time_unit=%u, etr_head=%p and has %d timers:\n", ptimer->time_unit, ptimer->etr_head, ptimer->timer_cnt);
p = ptimer->etr_head;
i = 0;
while(p != NULL)
{
printf("the %d timer: timeout=%u, elapse=%u, timer_proc=%p, arg=%p, arg_len=%p, etr_next=%p\n"
, i+1, p->timeout, p->elapse, p->timer_proc, p->arg, p->arg_len, p->etr_next);
p = p->etr_next;
i++;
}
printf("***************************mul_timer statistics end************************\n");
return (1);
}
#define _MUL_TIMER_MAIN
#ifdef _MUL_TIMER_MAIN
static void get_format_time(char *tstr)
{
time_t t;
t = time(NULL);
strcpy(tstr, ctime(&t));
tstr[strlen(tstr)-1] = '\0';
return;
}
timer_handle_t hdl[100];
int call_cnt = 0;
struct _mul_timer_manage *ptimer;
int timer_proc1(void *arg, unsigned int *len)
{
char tstr[200];
static int i, ret;
get_format_time(tstr);
printf("call_cnt=%d, hello %s: timer_proc1 is here.\n", call_cnt, tstr);
i++;
call_cnt++;
return (1);
}
int timer_proc2(void * arg, unsigned int *len)
{
char tstr[200];
static int i, ret;
get_format_time(tstr);
printf("call_cnt=%d, hello %s: timer_proc2 is here: arg = %s, len = %d.\n", call_cnt, tstr, arg, *len);
i++;
call_cnt++;
return (1);
}
int main(void)
{
char arg[50] = "hello, multiple timers";
char tstr[200];
int ret;
int len = 50, i;
ptimer = init_mul_timer(1000);
for(i = 0; i < 10; i++)
{
hdl[i<<1] = set_timer(ptimer, 1000*(i+1), timer_proc1, NULL, NULL);
printf("hdl[0i<<1=%d, is_valid_hdl=%d\n", hdl[i<<1], is_valid_time_hdl(hdl[i<<1]));
hdl[(i<<1)+1] = set_timer(ptimer, 3000*(i+1), timer_proc2, arg, &len);
printf("hdl[i<<1+1]=%d, is_valid_hdl=%d\n", hdl[(i<<1)+1], is_valid_time_hdl(hdl[(i<<1)+1]));
print_mul_timer(ptimer);
}
ret = kill_timer(ptimer, hdl[17]);
printf("ret=kill_timer=%d\n", ret);
print_mul_timer(ptimer);
printf("hd[19]->timout=%d\n", get_timeout_byhdl(ptimer, hdl[19]));
while(1)
{
if(call_cnt == 15)
{
get_format_time(tstr);
ret = release_mul_timer(ptimer);
printf("call_cnt=%d, main: %s destroy_mul_timer, ret=%d\n", call_cnt, tstr, ret);
call_cnt++;
}
}
return 0;
}
#endif
|
(bripengandre) |
