感谢支持
我们一直在努力

Linux内核系统定时器TIMER实现过程分析

Linux系统定时器,在内核中扮演着重要角色。内核的许多重要实现如任务调度,工作队列等均以系统定时器关系密切。系统定时器能以可编程的频率中断处理,这一中断叫做软中断。此频率即为每秒的定时器节拍数HZ。HZ的越大,说明定时器节拍越小,线程调度的准确性会越高。但HZ设得过大,对一个系统来说并不好,会导CPU开销过大,反而造成任务调度效率降低。滴答jiffies 变量记录系统启动以来,系统定时器已经触发的次数。也就是说每过一秒jiffies的增量为HZ,一般HZ=100,HZ是可以配置的,在S3C2440 arm linux中配置为200.


下面基于Linux2.6.30.4源码来探讨其实现原理及其过程。


要理解系统定时器实现原理,先来看看关系到系统定时器的各种数据结构,其具体的描述参数。


结构体structtimer_list来描述timer的参数,其数据结构如下:


[cpp]


  1. struct timer_list {  

  2.        structlist_head entry;              //timer双向链表   

  3.        unsignedlong expires;             //timer超时变量   

  4.    

  5.        void(*function)(unsigned long);   //timer超时回调函数  www.linuxidc.com 

  6.        unsignedlong data;                  //传递给回调函数的数据,也就是定时器数据   

  7.       struct tvec_base *base;            //timer base向量表用于timer_list的挂载和链表管理   

  8.                                               //timer的一些扩展参数   

  9. #ifdef CONFIG_TIMER_STATS          

  10.        void*start_site;  

  11.        charstart_comm[16];  

  12.        intstart_pid;  

  13. #endif   

  14. #ifdef CONFIG_LOCKDEP   

  15.        structlockdep_map lockdep_map;  

  16. #endif   

  17. };  


其中:


[cpp]


  1. list_entry结构:  

  2. struct list_head {  

  3.        structlist_head *next, *prev;  

  4. };  

  5. tevc_base的结构:  

  6. struct tvec_base {  

  7.        spinlock_tlock;                         //自旋锁lock   

  8.        structtimer_list *running_timer;   //指向已经挂载进来的timer_list   

  9.        unsignedlong timer_jiffies;          //timer jiffies用于记录定时器当前jiffies   

  10.        structtvec_root tv1;                  //5组tvec_base,从tv1~tv5,成员数各不相同   

  11.        structtvec tv2;                        //其成员数TVR_SIZE,TVN_SIZE决定   

  12.        structtvec tv3;  

  13.        structtvec tv4;  

  14.        structtvec tv5;  

  15. } ____cacheline_aligned;  

  16.   

  17. #define TVN_BITS (CONFIG_BASE_SMALL ? 4 :6)   

  18. #define TVR_BITS (CONFIG_BASE_SMALL ? 6 :8)   

  19. #define TVN_SIZE (1 << TVN_BITS)   

  20. #define TVR_SIZE (1 << TVR_BITS)   

  21. #define TVN_MASK (TVN_SIZE – 1)   

  22. #define TVR_MASK (TVR_SIZE – 1)   

  23.    

  24. struct tvec {  

  25.        structlist_head vec[TVN_SIZE];   // tv2~t5个数为64的数组   

  26. };                              

  27.    

  28. struct tvec_root {  

  29.        structlist_head vec[TVR_SIZE];  //tv1个数为256的数组   

  30. };  

可见涉及到系统定时器的数据结构并不多,那么:对于一个linux系统中,定时器个数可能会很多,而且每个定时器的超时事件时间并不相同,所以如何管理和处理定时器超时事件,关系到内核性能的高低。它根据不同的定时事件,按时间间分组,将新增的timer定时器建成双向链表,然后按照一定方式存放于5组tv1~tv5变量中称为tec_base。对于对称式多理器(SMP)系统还考虑到了TIMER从一个CPU迁移到另一个CPU的情况,相应的tev_base也跟着更改。那它在系统是怎样实现的呢?现在先从一个简单的系统定时器应用例子来看看它的实现过程:


[cpp]


  1. #include <linux/init.h>   

  2. #include <linux/module.h>   

  3. #include <linux/timer.h>   

  4.    

  5. struct  timer_list   my_timer;  

  6.    

  7. static void my_function(unsigned   long  data)  

  8. {  

  9.           static int i = 0;  

  10.            printk( “timer’s callback function\n”);  

  11.            printk( “timer’s data = %lu\n”,data);  

  12.            return;  

  13. }  

  14.    

  15. static int my_timer_init(void)  

  16. {  

  17.               printk(“timerinit…\n”);  

  18.            my_timer.data = 0xff;  

  19.            my_timer.function = my_function;  

  20.            my_timer.expires = jiffies + 3*HZ;  

  21.            init_timer(&my_timer);  

  22.            add_timer(&my_timer);  

  23.            return  0;  

  24. }  

  25.    

  26. static void my_timer_exit(void)  

  27. {  

  28.               printk( “timer exit…\n”);  

  29. }  

  30.    

  31. module_init(my_timer_init);  

  32. module_exit(my_timer_exit);  

  33. MODULE_AUTHOR( “itspy”);  

  34. MODULE_LICENSE( “GPL”);  

  35. MODULE_DESCRIPTION(“linux kernel timerprogramming”);  

上面例子,实现了一个定时器事件,将在3 HZ(秒)发生。my_imer_init函数中调用到的定时器API只有:


init_timer(&my_timer);   //用于定时器初始化


add_timer(&my_timer);    //增加一个新的定时器到tev_base向量表中


其中init_timer中调用了__init_timer(),这个函数才是真正初始化定时器的:


[cpp]


  1. static void __init_timer(struct timer_list*timer,  

  2.                       const char *name,  

  3.                       struct lock_class_key *key)  

  4. {  

  5.        timer->entry.next= NULL;                           //对于新增的timer实例,其下一各总是指向NULL。   

  6.        timer->base= __raw_get_cpu_var(tvec_bases); //SMP中,获得当前处理器的tev_base   

  7.                                                                    //这个tev_bases是根据一定规律变化的,稍后会将到   

  8.     …  

  9. }  

新增的定时器初始化,就是完成了一个timer_list结构初始化过程。


add_timer()  –> mod_timer()  –>  __mod_timer()

其中:

[cpp]


  1. static inline int  

  2. __mod_timer(struct timer_list *timer,unsigned long expires, bool pending_only)  

  3. {  

  4.        structtvec_base *base, *new_base;  

  5.        unsignedlong flags;  

  6.        intret;  

  7.    

  8.        ret= 0;  

  9.        BUG_ON(!timer->function);                 // BUG检测,确保回调函数为非空NULL   

  10.        base= lock_timer_base(timer, &flags); //获取本地cpu的tev_base,这是一个临   

  11.                                                           //界资源,里边是一个for(;;)循环,如果找不到说明已经迁移到了别的CPU   

  12.        if (timer_pending(timer)) {                  //当已挂载的timer 定时超时发生后,会被卸载摘除   

  13.               detach_timer(timer,0);             

  14.               ret= 1;  

  15.        }else {  

  16.               if(pending_only)                        //新增一个定时器时,pending_only 为 false   

  17.                      gotoout_unlock;  

  18.        }  

  19.    

  20. …  

  21.        new_base= __get_cpu_var(tvec_bases);   //获取本地cpu中的tevc_bases   

  22.        if(base != new_base) {     //由于之前base 可能已被迁移到其他CPU的 tev_base向量表,会造成 base != new_base   

  23.               if(likely(base->running_timer != timer)) { //由于在timer正在运行时,我们不能直接更改base,位与一个叫做DEFERRABLE(可延后标志)后处理   

  24.                      /*See the comment in lock_timer_base() */      

  25.                      timer_set_base(timer,NULL);  

  26.                      spin_unlock(&base->lock);  

  27.                      base= new_base;  

  28.                      spin_lock(&base->lock);  

  29.                      timer_set_base(timer,base);  

  30.               }  

  31.        }  

  32.    

  33.        timer->expires= expires;                  

  34.        internal_add_timer(base,timer);       //分析timer expires及建表过程   

  35.    

  36. out_unlock:  

  37.        spin_unlock_irqrestore(&base->lock,flags);  

  38.    

  39.        return ret;  

  40. }  

对于新增的timer最后调用internal_add_timer(base, timer)加入到相应的timer_list中以完成初始化过程。,这是一个建表的过程,表的建立情况,关系到表的管理效率。之前我们说到它共有tv1~tv5 组,tv1是一个很特别的组。每个tv中有各个组员,每个timer是如何添加的呢,看看internal_add_timer()的实现过程:


[cpp]


  1. static void internal_add_timer(structtvec_base *base, struct timer_list *timer)  

  2. {  

  3.        unsignedlong expires = timer->expires;  

  4.        unsignedlong idx = expires – base->timer_jiffies;  

  5.        structlist_head *vec;  

  6.    

  7.        if(idx < TVR_SIZE) {  

  8.               inti = expires & TVR_MASK;  

  9.               vec= base->tv1.vec + i;  

  10.        }else if (idx < 1 << (TVR_BITS + TVN_BITS)) {  

  11.               inti = (expires >> TVR_BITS) & TVN_MASK;  

  12.               vec= base->tv2.vec + i;  

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

  14.               inti = (expires >> (TVR_BITS + TVN_BITS)) & TVN_MASK;  

  15.               vec= base->tv3.vec + i;  

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

  17.               inti = (expires >> (TVR_BITS + 2 * TVN_BITS)) & TVN_MASK;  

  18.               vec= base->tv4.vec + i;  

  19.        }else if ((signed long) idx < 0) {  

  20.               /* 

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

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

  23.                */  

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

  25.        }else {  

  26.               inti;  

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

  28.                * architectures then we use the maximumtimeout: 

  29.                */  

  30.               if(idx > 0xffffffffUL) {  

  31.                      idx= 0xffffffffUL;  

  32.                      expires= idx + base->timer_jiffies;  

  33.               }  

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

  35.               vec= base->tv5.vec + i;  

  36.        }  

  37.        /* 

  38.         * Timers are FIFO: 

  39.         */  

  40.        list_add_tail(&timer->entry,vec);  

  41. }  

通过代码我们知道它的过程是这样的:首先它根据每个timer中的超时差值idx来决定timer所处的tev_base组别tv1~tv5.所以超时事件越后发生,那么它所处的组位置越靠后。对于tv1组,超时插值idx为0~255之间。差值idx即为所属组tv1中的数组下标。从中可知tv1组中相邻定时器的超时事件间隔1 jiffies发生。对于tv2组,超时差值idx为 256~2^14(16386)  之间,组中相邻定时时器超事件时间隔256^1 = 256 jiffies发生。以此类推,tv3 组超时差值idx为(16387~2^20)之间,组中相邻定时器超时时间间隔256^2 = 65536 jiffies发生 … 最后,新增的timer加入到当前节点(超时差值相等)的尾部list_add_tail()形成一个双向链表。这样分组timer双向链表方便了后面对定时器的迁移更新管理过程,以及最终提高了CPU的处理效率,因为在__run_timers()时,我们只需扫描tv1组中即将到来的定时器事件就行了。


我们知道启动过程时start_kernel()对定时器的初始化是这样的 :


init_timers() -> run_timer_softirq()  -> __run_timers()…


timer_interrupt() -> update_process_times() ->run_local_timers() -> raise_softirq(TIMER_SOFTIRQ);


之前我写的一篇《内核窥秘之一:start_kernel()运行过程记录》也有提到过.


       __run_timers()是系统定时器超时事件的服务程序。这是run_timer_softirq()中一部分,是通过软中断的实现的,它是在软中断下半部处理的。


[cpp]


  1. static inline void __run_timers(structtvec_base *base)  

  2. {  

  3.        …  

  4.        while(time_after_eq(jiffies, base->timer_jiffies)) {      //确定当前tvec_base->timer_jiffies是否有效   

  5.               structlist_head work_list;  

  6.               structlist_head *head = &work_list;  

  7.               intindex = base->timer_jiffies & TVR_MASK;               //只需扫描tv1组,看当前jiffies时刻是否有超时发生   

  8.               if(!index &&                                                         //cascade()定时器队列级联函数实现了   

  9.                      (!cascade(base,&base->tv2, INDEX(0))) &&         //tv5~tv2组迁移过程   

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

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

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

  13.               ++base->timer_jiffies;                                            //更新当前tvec_base->timer_jiffies   

  14.               list_replace_init(base->tv1.vec+ index, &work_list);        //链表更新新、旧取代   

  15.               while(!list_empty(head)) { //判定是否有定时器超时事件发生,非空为有,知道处理完链表中所有相同的定时器事件为止   

  16.                      void(*fn)(unsigned long);  

  17.                      unsignedlong data;  

  18.    

  19.                      timer= list_first_entry(head, struct timer_list,entry);  // 这是一个宏,获取第一个实体(对应的是入口的下一个)的地址   

  20.                      fn= timer->function;                                      

  21.                      data= timer->data;              

  22.            …  

  23.                      fn(data);                                                        //timer超时时回调函数入口   

  24.            …  

  25.         }  

  26.        }  

  27.      …  

  28. }  

对于cascade()函数它是确保之前定时器建立时internal_add_timer()定时器队列以及队列租得迁移更新工作,为什么要迁移,因为,系统在处理定时器时,比较的只是tv1组而已,也就是说,原来的tv1执行完之后,那么剩下的tv2,tv3,tv4,tv5将会先后迁移到tv1组:tv5 -> tv4 -> tv3 -> tv2-> tv1,这样定时器超时事件服务程序并不需要对每组的tv的超时事件进行检测,相比而言,也就提高了CPU的处理效率。那么这样一来timer 链表将发生变化,所以需要重新计算,重新实现internal_add_timer(),所以cascade ()函数代码如下:


[cpp]


  1. tatic int cascade(struct tvec_base *base,struct tvec *tv, int index)  

  2. {  

  3.        /*cascade all the timers from tv up one level */  

  4.        structtimer_list *timer, *tmp;  

  5.        structlist_head tv_list;  

  6.    

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

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

  9.               BUG_ON(tbase_get_base(timer->base)!= base);    //确保本地cpu 的tvec_base没   

  10.               internal_add_timer(base,timer);                         //有发生改变   

  11.        }  

  12.    

  13.        return index;  

  14. }  

通过以上分析,我们对Linux中系统定时器TIMER实现过程有所了解了。

赞(0) 打赏
转载请注明出处:服务器评测 » Linux内核系统定时器TIMER实现过程分析
分享到: 更多 (0)

听说打赏我的人,都进福布斯排行榜啦!

支付宝扫一扫打赏

微信扫一扫打赏