注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

还东国的博客

行之苟有恒,久久自芬芳

 
 
 

日志

 
 

Timing-Wheel定时器理解  

2015-07-02 15:41:33|  分类: LINUX编程 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Timing-Wheel定时器理解

在网络客户端的管理中,特别是大型的服务器的客户端的管理中,对客户端的失效必须要有一个高效的管理定时模块,来控制服务端不被撑爆和被僵尸链接干翻。

在以前写服务管理的时候儿,通过定时器来管理这些客户端链表,但是在小量连接(比如一千以下)的时候儿,遍历的时间成本是可以忽略的,如果几十万上百万怎么办呢?

还是国外的牛人给出了解决办法,比如“最小堆实现的定时器”和本文介绍的时间轮。

(根据George Varghese Tony Lauck 1996 年的论文<Hashed and Hierarchical Timing Wheels: data structures to efficiently implement a timer facility>http://cseweb.ucsd.edu/users/varghese/PAPERS/twheel.ps.Z))

今天当然重点是介绍后者,时间轮。这个东西有一个通俗的比喻,家里的水表,大家都看到过,千吨一个轮,百吨一个,依次类推。这样就可以实现很多种类型的大型的定时器(可以有几千几万几十万甚至更多,而且由于从2.6内核提供了timerfd,管理更方便,效率也更高)。简单的来说,就是循环队列+哈希+链表。这里要说明一个问题,如果只是用哈希循环,那么会造成对内存的极度渴求。所以要加上链表,这和MFC的内存管理的桶的机制是一样,希望大家记住,这种用法在内核和重要的库中都是一种非常均衡的算法+数据结构。应用非常广泛。

在前面讲过陈硕的MUDO中的这种时间轮的用法,它使用一个BOOST的循环数据结构实现的,非常方便,不用主动删除循环队列(或者说链表)的头尾,只要不断往尾部插入即可。同时他使用了智能指针,又会使很多工作被省略。优势还是比较明显的。更详细的可以看书。

但在其它的资料上,则大多得自己处理这个数据结构,结果不言而喻,就是增加了复杂度和难度,毕竟数据的处理对于一般的程序员来说,都还是比较复杂的。

http://www.ibm.com/developerworks/cn/linux/l-cn-timers/

http://blog.csdn.net/mindfloating/article/details/8033340

http://blog.csdn.net/cnlm2/article/details/6123126

网上的一个例程:

主要数据结构:

/*定时器节点*/

struct timer_node{

 

timer_id id;      /*定时器id*/      

 

int interval;      /*定时器超时值*/

 

int solt;    /*触发定时器需要的时间片*/

 

timer_expiry *cb;    /*定时器回调函数*/

 

void *user_data;      /*定时器传入参数*/

 

int len;      /*定时器传入参数长度*/

 

struct timer_node *next;    

 

};

 

/*定时器管理*/

 

struct timer{

 

int   time_solt;      /*定时器时间片大小*/

 

int   solt_num;      /*定时器最大数量*/     

 

int   cur_solt;         /*定时器当前时间片大小*/

 

int   solt_count;               /*定时器累计时间片大小*/

 

long  cur_time;      /*定时器当前时间*/

 

long  pre_time;      /*定时器上一个时间*/

 

get_time *gt;  /*定时器得到当前时间*/

 

struct timer_node **timer_list;

 

} T;

 

定时器回调函数

 

/*定时器超时函数*/

 

typedef int timer_expiry(timer_id id, void *user_data, int len);

 

/*获得当前时间*/

 

typedef long get_time(void);

 

timer_node结构中timer_expiry *cb为定时器超时调用的函数,返回0结束定时器,返回1继续循环定时器,这样定时器执行次数控制就非常方便了

 

timer结构体中get_time *gt为获得当前时间回调函数,如果返回秒即为秒定时器,返回毫秒即为毫秒定时器

 

具体代码如下:

 

time.h

 

[cpp] view plaincopy

#ifndef __TIMER_H__ 

#define __TIMER_H__ 

typedef unsigned int timer_id; 

/*定时器超时函数*/ 

typedef int timer_expiry(timer_id id, void *user_data, int len); 

/*获得当前时间*/ 

typedef long get_time(void); 

/*初始化定时器*/ 

int init_timer(int num, int solt, get_time *gt); 

/*销毁所有定时器*/ 

void destroy_timer(); 

/*增加一个定时器*/ 

int add_timer(timer_id id, int interval, timer_expiry *cb, void *user_data, int len); 

/*删除一个定时器*/ 

int delete_timer(timer_id id); 

/*运行定时器*/ 

void timer_runonce(); 

#endif  

 

 

time.c

 

[cpp] view plaincopy

#include "timer.h" 

#include <malloc.h> 

#include <string.h> 

/*定时器节点*/ 

struct timer_node{ 

    timer_id id;                /*定时器id*/        

    int interval;               /*定时器超时值*/ 

    int solt;                   /*触发定时器需要的时间片*/ 

    timer_expiry *cb;           /*定时器回调函数*/ 

    void *user_data;            /*定时器传入参数*/  

    int len;                    /*定时器传入参数长度*/ 

    struct timer_node *next;      

}; 

/*定时器管理*/ 

struct timer{ 

    int   time_solt;                /*定时器时间片大小*/ 

    int   solt_num;                 /*定时器最大数量*/       

    int   cur_solt;                 /*定时器当前时间片大小*/ 

    int   solt_count;               /*定时器累计时间片大小*/ 

    long  cur_time;                 /*定时器当前时间*/ 

    long  pre_time;                 /*定时器上一个时间*/ 

    get_time *gt;                   /*定时器得到当前时间*/ 

    struct timer_node **timer_list; 

} T; 

/*初始化定时器*/ 

/*num:定时器个数*/ 

/*solt:定时器时间片大小*/ 

/*gt:获得当前时间函数*/ 

/*返回值:0成功,-1失败*/ 

int  

init_timer(int num, int solt, get_time *gt){ 

     

    int i = 0; 

    memset(&T, 0, sizeof(struct timer)); 

    T.gt = gt; 

    T.timer_list = (struct timer_node **)malloc(num*sizeof(struct timer_node *)); 

    if (0 == T.timer_list){ 

        return -1; 

    } 

    while (i < num){ 

        T.timer_list[i] = 0; 

        i++; 

    } 

    T.time_solt = solt; 

    T.solt_num = num; 

    return 0; 

/*销毁所有定时器*/ 

/*返回值:*/ 

void 

destroy_timer(){ 

    int i = 0; 

    struct timer_node *p=0, *q=0; 

    while(i<T.solt_num){ 

        p = T.timer_list[i]; 

        if(p){ 

            while(p){    

                q = p; 

                p = p->next; 

                free(q); 

            } 

        } 

        i++; 

    } 

    free(T.timer_list); 

    return; 

/*添加一个定时器*/ 

/*p:定时器节点指针*/ 

/*返回值:*/ 

void add_timer(struct timer_node *p){ 

    int index = (T.cur_solt + p->interval/T.time_solt)%T.solt_num; 

    p->solt = T.solt_count +  p->interval/T.time_solt; 

    if (T.timer_list[index]){ 

        p->next = T.timer_list[index]; 

    } 

    T.timer_list[index] = p; 

    return; 

/*添加一个定时器*/ 

/*id:定时器id用户指定,程序不保证id唯一*/ 

/*interval:定时器超时值*/ 

/*cb:定时器超时回调函数*/ 

/*user_data:传入参数*/ 

/*len:传入参数长度*/ 

/*返回值:0成功,-1失败*/ 

int  

add_timer(timer_id id, int interval, timer_expiry *cb, void *user_data, int len){ 

    struct timer_node *p = (struct timer_node *)malloc(sizeof(struct timer_node)); 

    if (0 == p){ 

        return -1; 

    }        

    memset(p, 0, sizeof(struct timer_node)); 

    p->cb = cb; 

    p->id = id; 

    p->len = len; 

    p->interval = interval; 

    p->user_data = user_data; 

    add_timer(p); 

    return 0; 

/*删除一个定时器*/ 

/*id:定时器id*/ 

/*返回值:0成功,-1失败*/ 

int  

delete_timer(timer_id id){ 

    return -1; 

/*循环定时器*/ 

/*返回值:*/ 

void  

timer_runonce(){ 

    long diff; 

    struct timer_node *p=0, *q=0; 

    T.cur_time = T.gt(); 

    if (0 == T.pre_time){ 

        T.pre_time = T.cur_time; 

    } 

    diff = (T.cur_time-T.pre_time)/T.time_solt; 

    if (diff > 0){ 

        T.pre_time = T.cur_time; 

        T.cur_solt += diff; 

        T.solt_count += diff; 

        if (T.cur_solt>=T.solt_num){ 

            T.cur_solt = 0; 

        } 

    } 

    else{ 

        return; 

    } 

    q = T.timer_list[T.cur_solt]; 

    while (q){ 

        p = q; 

        q = q->next; 

        if (T.solt_count >= p->solt){ 

            T.timer_list[T.cur_solt] = q; 

            if (p->cb(p->id, p->user_data, p->len)){ 

                p->next = 0; 

                add_timer(p); 

            } 

            else{ 

                free(p); 

            } 

        } 

    } 

    return; 

 

 

测试代码testtimer

 

[cpp] view plaincopy

// timer.cpp : 定义控制台应用程序的入口点。 

// 

#include "stdafx.h" 

#include "timer.h" 

#include <stdio.h> 

#include <time.h> 

#include <windows.h> 

#include "stdlib.h" 

int g_counter = 0; 

long  

gt(){ 

    return time(0); 

int  

cb(timer_id id, void *user_data, int len){ 

    printf("%d", id); 

    return 1; 

void test_sleep() 

    init_timer(10, 1, gt); 

    add_timer(1, 5, cb, 0, 0); 

     

    while(1){ 

        timer_runonce(); 

        Sleep(2000); 

    } 

    destroy_timer(); 

int _tmain(int argc, _TCHAR* argv[]) 

    detect_memory_leaks(true); 

    int num = 1024*1024 - rand()%100; 

    init_timer(num, 1, gt); 

//  clock_ms tm; 

    for (int i=1; i<num; i++){ 

        int interval = rand()%30+1; 

        add_timer(i, interval, cb, 0, 0); 

    } 

//  printf("add_timer: %d/n", tm.elapsed()); 

    while (1){ 

        timer_runonce(); 

    } 

    destroy_timer(); 

    return 0; 

 

Linux高性能服务器编程》的代码:

#ifndef TIME_WHEEL_TIMER

#define TIME_WHEEL_TIMER

 

#include <time.h>

#include <netinet/in.h>

#include <stdio.h>

 

#define BUFFER_SIZE 64

class tw_timer;

struct client_data

{

    sockaddr_in address;

    int sockfd;

    char buf[ BUFFER_SIZE ];

    tw_timer* timer;

};

 

class tw_timer

{

public:

    tw_timer( int rot, int ts )

    : next( NULL ), prev( NULL ), rotation( rot ), time_slot( ts ){}

 

public:

    int rotation;

    int time_slot;

    void (*cb_func)( client_data* );

    client_data* user_data;

    tw_timer* next;

    tw_timer* prev;

};

 

class time_wheel

{

public:

    time_wheel() : cur_slot( 0 )

    {

        for( int i = 0; i < N; ++i )

        {

            slots[i] = NULL;

        }

    }

    ~time_wheel()

    {

        for( int i = 0; i < N; ++i )

        {

            tw_timer* tmp = slots[i];

            while( tmp )

            {

                slots[i] = tmp->next;

                delete tmp;

                tmp = slots[i];

            }

        }

    }

    tw_timer* add_timer( int timeout )

    {

        if( timeout < 0 )

        {

            return NULL;

        }

        int ticks = 0;

        if( timeout < TI )

        {

            ticks = 1;

        }

        else

        {

            ticks = timeout / TI;

        }

        int rotation = ticks / N;

        int ts = ( cur_slot + ( ticks % N ) ) % N;

        tw_timer* timer = new tw_timer( rotation, ts );

        if( !slots[ts] )

        {

            printf( "add timer, rotation is %d, ts is %d, cur_slot is %d\n", rotation, ts, cur_slot );

            slots[ts] = timer;

        }

        else

        {

            timer->next = slots[ts];

            slots[ts]->prev = timer;

            slots[ts] = timer;

        }

        return timer;

    }

    void del_timer( tw_timer* timer )

    {

        if( !timer )

        {

            return;

        }

        int ts = timer->time_slot;

        if( timer == slots[ts] )

        {

            slots[ts] = slots[ts]->next;

            if( slots[ts] )

            {

                slots[ts]->prev = NULL;

            }

            delete timer;

        }

        else

        {

            timer->prev->next = timer->next;

            if( timer->next )

            {

                timer->next->prev = timer->prev;

            }

            delete timer;

        }

    }

    void tick()

    {

        tw_timer* tmp = slots[cur_slot];

        printf( "current slot is %d\n", cur_slot );

        while( tmp )

        {

            printf( "tick the timer once\n" );

            if( tmp->rotation > 0 )

            {

                tmp->rotation--;

                tmp = tmp->next;

            }

            else

            {

                tmp->cb_func( tmp->user_data );

                if( tmp == slots[cur_slot] )

                {

                    printf( "delete header in cur_slot\n" );

                    slots[cur_slot] = tmp->next;

                    delete tmp;

                    if( slots[cur_slot] )

                    {

                        slots[cur_slot]->prev = NULL;

                    }

                    tmp = slots[cur_slot];

                }

                else

                {

                    tmp->prev->next = tmp->next;

                    if( tmp->next )

                    {

                        tmp->next->prev = tmp->prev;

                    }

                    tw_timer* tmp2 = tmp->next;

                    delete tmp;

                    tmp = tmp2;

                }

            }

        }

        cur_slot = ++cur_slot % N;

    }

 

private:

    static const int N = 60;

    static const int TI = 1;

    tw_timer* slots[N];

    int cur_slot;

};

 

#endif

陈硕的代码就不往上贴了,网上和书上都有。

这个定时器的计数器可以使用一部定时器,也可以使用方法得到当前的时间值,利用绝对值的差来判断。但个人晚倾向于前者,使用一部标准的定时器,触发循环队列运行的函数。

回头有时间写一个,跟网上的大侠们过过招,切磋一下。

补充一下:

循环队列的关键在于计时器在队列里的循环,一般来说,大家都会想到用一个计数器来计算当前定时器的销毁索引,但是那么做成本高,遍历和加减都需要控制。在陈硕的循环队列中,由于使用了BOOST中的循环队列,他会通过不断在尾部插入,自然的把最前面的顶出循环队列而造成计数器加减。

可是如果是自己写一个呢?那也好说,你如果有兴趣写成BOOST那种,当然不错,否则,你可以有一种简便的方法,那就是循环当前循环队列的索引,也就是说,你把当前需要释放或者说顶出的队列中的数据的当前的槽的索引不断向前加,如果达到最大就退回0.然后不断重复,这样成本就小很多了。

一些细节有的时候说出来怕啰嗦,不说又怕别人一时弄不清楚。

  评论这张
 
阅读(422)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017