嵌入式

linux下多定时器的实现（经典）

2019-07-13 09:04发布

站内文章 / 嵌入式Linux
14854 0 1462
class="markdown_views prism-atom-one-light"> linux下多定时器的实现
一、已有的定时器接口
   时空管理是计算机系统的主要任务。在时间管理中，我们经常利用定时器处理事情：比如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<

热门文章