首页 / 操作系统 / Linux / Linux的动态定时器--时间轮

Linux的定时器—有时也称为动态定时器或内核定时器—是管理内核时间的基础。定时器是一种软件功能，即允许在将来的某个时刻，函数在给定的时间间隔用完时被调用。注意的是定时器并不会周期运行，它在超时后就自行销毁，这也是定时器被称为动态定时器的一个原因。动态定时器不断地创建和销毁，而且它的运行次数也不受限制。定时器在内核代码中属于一个基础组件。要想完全弄清楚linux2.6中内核定时器的实现，得先从初始化开始。在start_kernel（void）-->init_timers（void）

1. void __init init_timers（void）  
2. {  
3.     int err = timer_cpu_notify（&timers_nb, （unsigned long）CPU_UP_PREPARE,  
4.                 （void *）（long）smp_processor_id（））;  
5.   
6.     init_timer_stats（）;  
7.   
8.     BUG_ON（err == NOTIFY_BAD）;  
9.     register_cpu_notifier（&timers_nb）;  
10.     open_softirq（TIMER_SOFTIRQ, run_timer_softirq）;  
11. }  

在timer_cpu_notify（&timers_nb,（unsigned long）CPU_UP_PREPARE,（void*）（long）smp_processor_id（））;中执行init_timers_cpu（cpu） //初始化本cpu中的timers初始化的主要代码是：

1. spin_lock_init（&base->lock）;  
2.   
3.     for （j = 0; j < TVN_SIZE; j++） {  
4.         INIT_LIST_HEAD（base->tv5.vec + j）;  
5.         INIT_LIST_HEAD（base->tv4.vec + j）;  
6.         INIT_LIST_HEAD（base->tv3.vec + j）;  
7.         INIT_LIST_HEAD（base->tv2.vec + j）;  
8.     }  
9.     for （j = 0; j < TVR_SIZE; j++）  
10.         INIT_LIST_HEAD（base->tv1.vec + j）;  
11.   
12.     base->timer_jiffies = jiffies;  
13.     base->next_timer = base->timer_jiffies;  

这段代码的主体是base，base的定义是：structtvec_base *base;这个tvec_base是动态定时器的主要数据结构，每个cpu上有一个，它包含相应cpu中处理动态定时器需要的所有数据。为简化分析仅考虑单cpu。给出这个数据机构：

1. struct tvec_base {  
2.     spinlock_t lock;  
3.     struct timer_list *running_timer;  
4.     unsigned long timer_jiffies;  
5.     unsigned long next_timer;  
6.     struct tvec_root tv1;  
7.     struct tvec tv2;  
8.     struct tvec tv3;  
9.     struct tvec tv4;  
10.     struct tvec tv5;  
11. } ____cacheline_aligned;  

其中，timer_list是具体定时器的结构体（后面再具体看timer_list结构体）；上面包含tv1，tv2，tv3，tv4，tv5；内核定时器的巧妙设计就在于此。

1. #define TVN_BITS （CONFIG_BASE_SMALL ？ 4 : 6）   
2. #define TVR_BITS （CONFIG_BASE_SMALL ？ 6 : 8）   
3. #define TVN_SIZE （1 << TVN_BITS）   
4. #define TVR_SIZE （1 << TVR_BITS）   
5. #define TVN_MASK （TVN_SIZE - 1）   
6. #define TVR_MASK （TVR_SIZE - 1）   
7.   
8. struct tvec {  
9.     struct list_head vec[TVN_SIZE];  
10. };  
11.   
12. struct tvec_root {  
13.     struct list_head vec[TVR_SIZE];  
14. };  

从这个定义看到，tv1就是长度为256的数组，数组成员是list_head；同样的，tv2，tv3，tv4和tv5都是长度为64的数组，数组成员是list_head。List_head就是linux内核代码中广泛使用的双向链表。在阻塞和非阻塞中的等待队列时就看到了list_head的应用。那么，tv1-tv5都是数组+链表的实现，其实hash的有一种简单实现就是数组+链表的组合，那么这几个就有些hash的味道，具体是不是，还要分析道后面才知道。再回到前面的初始化中，for（j = 0; j < TVN_SIZE; j++） {INIT_LIST_HEAD（base->tv5.vec+ j）;INIT_LIST_HEAD（base->tv4.vec+ j）;INIT_LIST_HEAD（base->tv3.vec+ j）;INIT_LIST_HEAD（base->tv2.vec+ j）;}for（j = 0; j < TVR_SIZE; j++）INIT_LIST_HEAD（base->tv1.vec+ j）;就tv1-tv5这5个结构体中的数组中每个list_head进行初始化。base->timer_jiffies= jiffies;base->next_timer= base->timer_jiffies;将base中的timer_jiffies和next_timer都初始化为jiffies。
初始化完成后，在init_timers函数的第二个重要的步骤是：open_softirq（TIMER_SOFTIRQ,run_timer_softirq）;这个函数注册定时器软中断，简单的软中断分析见《Linux的软中断》 见 http://www.linuxidc.com/Linux/2012-04/57918.htm；
下面来看具体定时器的初始化和添加操作：初始化的函数：

1. #define init_timer（timer）                          
2.     do {                                  
3.         static struct lock_class_key __key;           
4.         init_timer_key（（timer）, #timer, &__key）;          
5.     } while （0）  
6.   
7. void init_timer_key（struct timer_list *timer,  
8.             const char *name,  
9.             struct lock_class_key *key）  
10. {  
11.     debug_init（timer）;  
12.     __init_timer（timer, name, key）;  
13. }  
14.   
15. static void __init_timer（struct timer_list *timer,  
16.              const char *name,  
17.              struct lock_class_key *key）  
18. {  
19.     timer->entry.next = NULL;  
20.     timer->base = __raw_get_cpu_var（tvec_bases）;  
21. #ifdef CONFIG_TIMER_STATS   
22.     timer->start_site = NULL;  
23.     timer->start_pid = -1;  
24.     memset（timer->start_comm, 0, TASK_COMM_LEN）;  
25. #endif   
26.     lockdep_init_map（&timer->lockdep_map, name, key, 0）;  
27. }  

初始化的宏定义：

1. #define TIMER_INITIALIZER（_function, _expires, _data） {        
2.         .entry = { .prev = TIMER_ENTRY_STATIC },      
3.         .function = （_function）,              
4.         .expires = （_expires）,                
5.         .data = （_data）,                  
6.         .base = &boot_tvec_bases,             
7.         __TIMER_LOCKDEP_MAP_INITIALIZER（          
8.             __FILE__ ":" __stringify（__LINE__））   
9.     }  

定时器的添加：

1. void add_timer（struct timer_list *timer）  
2. {  
3.     BUG_ON（timer_pending（timer））;  
4.     mod_timer（timer, timer->expires）;  
5. }  

Timer_list结构体的定义：

1. struct timer_list {  
2.     struct list_head entry;  
3.     unsigned long expires;  
4.   
5.     void （*function）（unsigned long）;  
6.     unsigned long data;  
7.   
8.     struct tvec_base *base;  
9. #ifdef CONFIG_TIMER_STATS   
10.     void *start_site;  
11.     char start_comm[16];  
12.     int start_pid;  
13. #endif   
14. #ifdef CONFIG_LOCKDEP   
15.     struct lockdep_map lockdep_map;  
16. #endif   
17. };  

 

1. int mod_timer（struct timer_list *timer, unsigned long expires）  
2. {  
3.     /* 
4.      * This is a common optimization triggered by the 
5.      * networking code - if the timer is re-modified 
6.      * to be the same thing then just return: 
7.      */  
8.     if （timer_pending（timer） && timer->expires == expires）  
9.         return 1;  
10.   
11.     return __mod_timer（timer, expires, false, TIMER_NOT_PINNED）;  
12. }