Chinaunix首页 | 论坛 | 博客
  • 博客访问: 22292
  • 博文数量: 7
  • 博客积分: 10
  • 博客等级: 民兵
  • 技术积分: 50
  • 用 户 组: 普通用户
  • 注册时间: 2012-02-21 01:23
个人简介

This is pipilucn.

文章分类

全部博文(7)

文章存档

2013年(7)

我的朋友

分类: LINUX

2013-02-26 00:20:31

2010-12-27 22:11 1393人阅读 评论(0) 举报

目录(?)[+]

1.     Overview

常用的定时器实现算法有两种:红黑树和时间轮(timing wheel)。

Linux2.6的代码中,kernel/timer.c文件实现了一个通用定时器机制,使用的是时间轮算法。

 

每一个CPU都有一个struct tvec_base结构,代表这个CPU使用的时间轮。

struct tvec_base

{

       spinlock_t lock;                                  // 同步锁

       struct timer_list * running_timer;         // 当前正在运行的定时器

       unsigned long timer_jiffies;                  // 当前运行到的jiffies

       struct tvec_root tv1;                          

       struct tvec tv2;

       struct tvec tv3;

       struct tvec tv4;

       struct tvec tv5;

}

 

struct tvec_rootstruct tvec都是数组,数组中的每一项都指定一个链表。struct tvec_root定义的数组大小是256(28次方)struct tvec_root定义的数组大小是6426次方)。所以,tv1~6定义的数组总大小是2的(8 + 4*6 = 32)次方,正好对应32位处理器中jiffies的定义(unsigned long)。

 

因为使用的是wheel算法,tv1~5就代表5wheel

tv1是转速最快的wheel,所有在256jiffies内到期的定时器都会挂在tv1的某个链表头中。

tv2是转速第二快的wheel,里面挂的定时器超时jiffies2^8 ~ 2^(8+6)之间。

tv3是转速第三快的wheel,超时jiffies2^(8+6) ~ 2^(8+2*6)之间。

tv4tv5类似。

 

2.     增加timer

增加timer分两步,先是调用init_timer初始化一个struct timer_list结构,然后调用add_timertimer挂到5wheel中包含的某一个定时器队列中。

init_timer函数初始化timer_list中的一些域。

static void __init_timer(struct timer_list *timer)

{

       timer->entry.next = NULL;

       timer->base = __raw_get_cpu_var(tvec_bases);

#ifdef CONFIG_TIMER_STATS

       timer->start_site = NULL;

       timer->start_pid = -1;

       memset(timer->start_comm, 0, TASK_COMM_LEN);

#endif

}

 

add_timer__mod_timer函数的一个封装,__mod_timer最终会调用internal_add_timer

static void internal_add_timer(struct tvec_base *base, struct timer_list *timer)

{

       unsigned long expires = timer->expires;

       unsigned long idx = expires - base->timer_jiffies; // idx为定时器距离超时还有多少jiffies

       struct list_head *vec;

 

       // 如果idx少于TVR_SIZE(256),把定时器加入tv1

       if (idx < TVR_SIZE) {                       

              int i = expires & TVR_MASK;

              vec = base->tv1.vec + i;

       }

    // 如果idx少于2^(8+6)次方,加入tv2

    else if (idx < 1 << (TVR_BITS + TVN_BITS)) {

              int i = (expires >> TVR_BITS) & TVN_MASK;

              vec = base->tv2.vec + i;

       }

    // 类推,加入tv3

    else if (idx < 1 << (TVR_BITS + 2 * TVN_BITS)) {

              int i = (expires >> (TVR_BITS + TVN_BITS)) & TVN_MASK;

              vec = base->tv3.vec + i;

       }

    // 类推,加入tv4

    else if (idx < 1 << (TVR_BITS + 3 * TVN_BITS)) {

              int i = (expires >> (TVR_BITS + 2 * TVN_BITS)) & TVN_MASK;

              vec = base->tv4.vec + i;

       }

    // 如果idx < 0,说明定时器已经超时,应该马上被调度,把它加入base->timer_jiffies                                         // base的当前jiffies对应的队列。这里要注意的是,这个函数在spin_lock_irq被调           // 用之后调用,所以不会与定时器调度函数产生竞态。

    else if ((signed long) idx < 0) {

              /*

               * Can happen if you add a timer with expires == jiffies,

               * or you set a timer to go off in the past

               */

              vec = base->tv1.vec + (base->timer_jiffies & TVR_MASK);

       }

       // 加入tv5队列。

       else {

              int i;

              /* If the timeout is larger than 0xffffffff on 64-bit

               * architectures then we use the maximum timeout:

               */

              if (idx > 0xffffffffUL) {

                     idx = 0xffffffffUL;

                     expires = idx + base->timer_jiffies;

              }

              i = (expires >> (TVR_BITS + 3 * TVN_BITS)) & TVN_MASK;

              vec = base->tv5.vec + i;

       }

       trace_timer_set(timer);

       /*

        * Timers are FIFO:

        */

       list_add_tail(&timer->entry, vec);

}

 

3.     timer的调度

timer的调度在软中断中完成,在init_timers函数中调用

       open_softirq(TIMER_SOFTIRQ, run_timer_softirq)

注册定时器对应的软中断处理函数。

static void run_timer_softirq(struct softirq_action *h)

{

       struct tvec_base *base = __get_cpu_var(tvec_bases);

       hrtimer_run_pending();              // 高精度时钟的处理

       // 如果jiffies超过了base->timer_jiffies,那么调用时钟处理函数

       if (time_after_eq(jiffies, base->timer_jiffies))

              __run_timers(base);

}

 

static inline void __run_timers(struct tvec_base *base)

       spin_lock_irq  加锁,关中断,保证与定时器添加函数之间不会产生竞态

       while (time_after_eq(jiffies, base->timer_jiffies))

              // index代表这个循环需要处理的定时器在数组tv1中的下标

              int index = base->timer_jiffies & TVR_MASK;

              // 定时器的重新排列,下文详细讨论

              if (!index &&

                     (!cascade(base, &base->tv2, INDEX(0))) &&

                            (!cascade(base, &base->tv3, INDEX(1))) &&

                                   !cascade(base, &base->tv4, INDEX(2)))

                  cascade(base, &base->tv5, INDEX(3));

             

              ++base->timer_jiffies;

              // 取出这次循环需要处理的定时器队列

              list_replace_init(base->tv1.vec + index, &work_list);

              // 处理队列中的每一个定时器。注意在调用定时器中的timer->function之前,会先        // 调用spin_unlock_irq,调用完之后再重新用spin_lock_irq加锁。这是为了提高CPU的效率。另外,在处理某个定时器时,              // 会调用set_running_timer把当前正在运行的定时器标记到base->running_timer              // 中。

              ……

       // 函数退出,标记现在base中没有正在运行的定时器

       set_running_timer(base, NULL);         

       spin_unlock_irq                                  // 解锁

 

4.     定时器的重新排列

在 时间轮算法中,随着时间推移,定时器到期的时间越来越近,时间轮也随着时间不停转动。当最快的轮转到某一个触发点,就将次快轮的某一队列搬到最快轮。次块 轮转到某一触发点,把下一级时间轮的某一队列再往上搬到次快轮。依此类推。所以排队中的定时器就是这样一级一级往上,直到在最快轮中被处理。

在这里,这些搬移由上节描述的__run_timers函数的下列代码体现:

              // index代表这个循环需要处理的定时器在数组tv1中的下标

              int index = base->timer_jiffies & TVR_MASK;

              // 定时器的重新排列

              if (!index &&

                     (!cascade(base, &base->tv2, INDEX(0))) &&

                            (!cascade(base, &base->tv3, INDEX(1))) &&

                                   !cascade(base, &base->tv4, INDEX(2)))

                  cascade(base, &base->tv5, INDEX(3));

jiffies的低8位为0时,tv1到了触发点,调用cascade函数把tv2的某一格定时器搬到tv1tv2cascade函数返回0时,代表tv2也到了触发点,于是又触发下一级时间轮tv3。依此类推。

这里INDEX的定义为:

#define INDEX(N) ((base->timer_jiffies >> (TVR_BITS + (N) * TVN_BITS)) & TVN_MASK)

可以看出这个宏返回的是时间轮中某一格的索引:

       INDEX(0)返回tv2的索引。

       INDEX(1)返回tv3的索引。

       INDEX(2)返回tv4的索引。

       INDEX(3)返回tv5的索引。

 

static int cascade(struct tvec_base *base, struct tvec *tv, int index)

       // tv数组中以index为下标的定时器队列取出,准备搬移

       list_replace_init(tv->vec + index, &tv_list);

       // 根据超时时间,将队列中的定时器重新排队。定时器往上一级时间轮排队的过程就          // 在这里发生。

       list_for_each_entry_safe(timer, tmp, &tv_list, entry) {

              BUG_ON(tbase_get_base(timer->base) != base);

              internal_add_timer(base, timer);

       }


阅读(1349) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~