linux 定时器的工作原理_linux 内核定时器原理 - CSDN
精华内容
参与话题
  • 定时器的实现依赖的是CPU时钟中断,时钟中断的精度就决定定时器精度的极限。一个时钟中断源如何实现多个定时器呢?对于内核,简单来说就是用特定的数据结构管理众多的定时器,在时钟中断处理中判断哪些定时器超时,...

    定时器的实现原理

    定时器的实现依赖的是CPU时钟中断,时钟中断的精度就决定定时器精度的极限。一个时钟中断源如何实现多个定时器呢?对于内核,简单来说就是用特定的数据结构管理众多的定时器,在时钟中断处理中判断哪些定时器超时,然后执行超时处理动作。而用户空间程序不直接感知CPU时钟中断,通过感知内核的信号、IO事件、调度,间接依赖时钟中断。用软件来实现动态定时器常用数据结构有:时间轮、最小堆和红黑树。下面就是一些知名的实现:

    Linux内核定时器相关(Linux v4.9.7, x86体系架构)的一些相关代码:

    内核启动注册时钟中断

    // @file: arch/x86/kernel/time.c - Linux 4.9.7
    // 内核init阶段注册时钟中断处理函数
    static struct irqaction irq0  = {
        .handler = timer_interrupt,
        .flags = IRQF_NOBALANCING | IRQF_IRQPOLL | IRQF_TIMER,
        .name = "timer"
    };
    
    void __init setup_default_timer_irq(void)
    {
        if (!nr_legacy_irqs())
            return;
        setup_irq(0, &irq0);
    }
    
    // Default timer interrupt handler for PIT/HPET
    static irqreturn_t timer_interrupt(int irq, void *dev_id)
    {
        // 调用体系架构无关的时钟处理流程
        global_clock_event->event_handler(global_clock_event);
        return IRQ_HANDLED;
    }
    

    内核时钟中断处理流程

    // @file: kernel/time/timer.c - Linux 4.9.7
    /*
     * Called from the timer interrupt handler to charge one tick to the current
     * process.  user_tick is 1 if the tick is user time, 0 for system.
     */
    void update_process_times(int user_tick)
    {
        struct task_struct *p = current;
    
        /* Note: this timer irq context must be accounted for as well. */
        account_process_tick(p, user_tick);
        run_local_timers();
        rcu_check_callbacks(user_tick);
    #ifdef CONFIG_IRQ_WORK
        if (in_irq())
            irq_work_tick();
    #endif
        scheduler_tick();
        run_posix_cpu_timers(p);
    }
    
    /*
     * Called by the local, per-CPU timer interrupt on SMP.
     */
    void run_local_timers(void)
    {
        struct timer_base *base = this_cpu_ptr(&timer_bases[BASE_STD]);
    
        hrtimer_run_queues();
        /* Raise the softirq only if required. */
        if (time_before(jiffies, base->clk)) {
            if (!IS_ENABLED(CONFIG_NO_HZ_COMMON) || !base->nohz_active)
                return;
            /* CPU is awake, so check the deferrable base. */
            base++;
            if (time_before(jiffies, base->clk))
                return;
        }
        raise_softirq(TIMER_SOFTIRQ); // 标记一个软中断去处理所有到期的定时器
    }
    

    内核定时器时间轮算法

    单层时间轮算法的原理比较简单:用一个数组表示时间轮,每个时钟周期,时间轮 current 往后走一个格,并处理挂在这个格子的定时器链表,如果超时则进行超时动作处理,然后删除定时器,没有则剩余轮数减一。原理如图:
    这里写图片描述
    Linux 内核则采用的是 Hierarchy 时间轮算法,Hierarchy 时间轮将单一的 bucket 数组分成了几个不同的数组,每个数组表示不同的时间精度,Linux 内核中用 jiffies 记录时间,jiffies记录了系统启动以来经过了多少tick。下面是Linux 4.9的一些代码:

    // @file: kernel/time/timer.c - Linux 4.9.7
    /*
     * The timer wheel has LVL_DEPTH array levels. Each level provides an array of
     * LVL_SIZE buckets. Each level is driven by its own clock and therefor each
     * level has a different granularity.
     */
    
    /* Size of each clock level */
    #define LVL_BITS    6
    #define LVL_SIZE    (1UL << LVL_BITS)
    
    /* Level depth */
    #if HZ > 100
    # define LVL_DEPTH  9
    # else
    # define LVL_DEPTH  8
    #endif
    
    #define WHEEL_SIZE  (LVL_SIZE * LVL_DEPTH)
    
    struct timer_base {
        spinlock_t      lock;
        struct timer_list   *running_timer;
        unsigned long       clk;
        unsigned long       next_expiry;
        unsigned int        cpu;
        bool            migration_enabled;
        bool            nohz_active;
        bool            is_idle;
        DECLARE_BITMAP(pending_map, WHEEL_SIZE);
        struct hlist_head   vectors[WHEEL_SIZE];
    } ____cacheline_aligned;
    

    Hierarchy 时间轮的原理大致如下,下面是一个时分秒的Hierarchy时间轮,不同于Linux内核的实现,但原理类似。对于时分秒三级时间轮,每个时间轮都维护一个cursor,新建一个timer时,要挂在合适的格子,剩余轮数以及时间都要记录,到期判断超时并调整位置。原理图大致如下:
    这里写图片描述

    定时器的使用方法

    在Linux 用户空间程序开发中,常用的定期器可以分为两类:

    1. 执行一次的单次定时器 single-short;
    2. 循环执行的周期定时器 Repeating Timer;

    其中,Repeating Timer 可以通过在Single-Shot Timer 终止之后,重新再注册到定时器系统里来实现。当一个进程需要使用大量定时器时,同样利用时间轮、最小堆或红黑树等结构来管理定时器。而时钟周期来源则需要借助系统调用,最终还是从时钟中断。Linux用户空间程序的定时器可用下面方法来实现:

    • 通过alarm()setitimer()系统调用,非阻塞异步,配合SIGALRM信号处理;
    • 通过select()nanosleep()系统调用,阻塞调用,往往需要新建一个线程;
    • 通过timefd()调用,基于文件描述符,可以被用于 select/poll 的应用场景;
    • 通过RTC机制, 利用系统硬件提供的Real Time Clock机制, 计时非常精确;

    上面方法没提sleep(),因为Linux中并没有系统调用sleep(),sleep()是在库函数中实现,是通过调用alarm()来设定报警时间,调用sigsuspend()将进程挂起在信号SIGALARM上,而且sleep()也只能精确到秒级上,精度不行。当使用阻塞调用作为定时周期来源时,可以单独启一个线程用来管理所有定时器,当定时器超时的时候,向业务线程发送定时器消息即可。

    一个基于时间轮的定时器简单实现

    #include <stdio.h>
    #include <signal.h>
    #include <stdlib.h>
    #include <unistd.h>
    
    #define TIME_WHEEL_SIZE 8
    
    typedef void (*func)(int data);
    
    struct timer_node {
        struct timer_node *next;
        int rotation;
        func proc;
        int data;
    };
    
    struct timer_wheel {
        struct timer_node *slot[TIME_WHEEL_SIZE];
        int current;
    };
    
    struct timer_wheel timer = {{0}, 0};
    
    void tick(int signo)
    {
        // 使用二级指针删进行单链表的删除
        struct timer_node **cur = &timer.slot[timer.current];
        while (*cur) {
            struct timer_node *curr = *cur;
            if (curr->rotation > 0) {
                curr->rotation--;
                cur = &curr->next;
            } else {
                curr->proc(curr->data);  // bug-fix: 与下面一样交换位置
                *cur = curr->next;
                free(curr);
            }
        }
        timer.current = (timer.current + 1) % TIME_WHEEL_SIZE;
        alarm(1);
    }
    
    void add_timer(int len, func action)
    {
        int pos = (len + timer.current) % TIME_WHEEL_SIZE;
        struct timer_node *node = malloc(sizeof(struct timer_node));
    
        // 插入到对应格子的链表头部即可, O(1)复杂度
        node->next = timer.slot[pos];
        timer.slot[pos] = node;
        node->rotation = len / TIME_WHEEL_SIZE;
        node->data = 0;
        node->proc = action;
    }
    
     // test case1: 1s循环定时器
    int g_sec = 0;
    void do_time1(int data)
    {
        printf("timer %s, %d\n", __FUNCTION__, g_sec++);
        add_timer(1, do_time1);
    }
    
    // test case2: 2s单次定时器
    void do_time2(int data)
    {
        printf("timer %s\n", __FUNCTION__);
    }
    
    // test case3: 9s循环定时器
    void do_time9(int data)
    {
        printf("timer %s\n", __FUNCTION__);
        add_timer(9, do_time9);
    }
    
    int main()
    {
        signal(SIGALRM, tick);
        alarm(1); // 1s的周期心跳
    
        // test
        add_timer(1, do_time1);
        add_timer(2, do_time2);
        add_timer(9, do_time9);
    
        while(1) pause();
        return 0;
    }
    

    在实际项目中,一个常用的做法是新起一个线程,专门管理定时器,定时来源使用rtc、select等比较精确的来源,定时器超时后向主要的work线程发消息即可,或者使用timefd接口。

    参考:

    展开全文
  • linux 定时器原理

    2019-08-03 10:23:26
    内核定时器: unsigned long timeout = jiffies + (x * HZ); while(1) { // Check the condition. // Take a schedule. if (time_after(jiffies, timeout)) { printk("Timeout\n");...

    内核定时器:
        unsigned long timeout = jiffies + (x * HZ);
        while(1) {
            // Check the condition.
            // Take a schedule.
            if (time_after(jiffies, timeout)) {
                printk("Timeout\n");
                break;
            }
        }
    转换到秒:    
    s = (jiffies - last_jiffies)/HZ;
    jiffies(约50天溢出)为jiffies_64的后32位,因此直接读取jiffies_64不具备原子性,使用get_jiffies_64,
    函数原理:[平台为32位则需要保护读取,否则直接读取]
    顺序锁:        读读/读写并发,写写互斥
    读写自旋锁:    读读并发,读写/写写互斥
    自旋锁:        不允许任何操作并发
    u64 get_jiffies_64(void)
    {
        unsigned long seq;
        u64 ret;
        do {
            seq = read_seqbegin(&xtime_lock);
            ret = jiffies_64;
        } while (read_seqretry(&xtime_lock, seq)); // 若读的过程中发生写,则重读
        return ret;
    }
    这里涉及一个顺序锁的读写规则:
    读不会更改lock的seq,写会++,这里就会发现到值被写覆盖,于是重新读。

    write_seqlock(&lock);
    ...... //写操作代码
    write_sequnlock(&lock);
    顺序锁的使用场景是必须默认保持写互斥后,才能使用顺序锁.


    睡眠延时:
    这种睡眠再调度的精度要低于jiffies的精度:
    schedule_timeout(xx);
    函数原理:
        expire = timeout + jiffies;            // 超时截至时间
        setup_timer_on_stack(&timer, process_timeout, (unsigned long)current);
        __mod_timer(&timer, expire, false, TIMER_NOT_PINNED);
        schedule();
        del_singleshot_timer_sync(&timer);
        destroy_timer_on_stack(&timer);
        timeout = expire - jiffies;
     out:
        return timeout < 0 ? 0 : timeout;
        
    从这里看出,这个函数实际上是基于timer来实现的

    标准的延时调度接口 timer_list:[如果需要循环调度,则在timer_func中递归init/add]
    struct timer_list my_timer;
    init_timer(&my_timer);
    my_timer.expire = jiffies + n*HZ;
    my_timer.function = timer_func;
    my_timer.data = func_parameter;
    add_timer(&my_timer);


    短延时(基于指令级忙等,不基于jiffy机制的方法):
    mdelay/udelay/ndelay
    基于一个全局的变量:loops_per_jiffy,变量初始化位于:
    calibrate_delay()
    基本原理是,先从4096 以*2的倍数找到第一个范围 4096*x < t < 4096*2x
    然后逐渐开始细化,从4096*x 开始,逐渐递增4096*x>>2(而不是减半),直到到达对应的精度要求
    10000000
    11000000
    10100000
    ....

    static inline void __udelay(unsigned long usecs)
    {
        unsigned long loops_per_usec;
        loops_per_usec = (loops_per_jiffy * HZ) / 1000000;        //一秒中能够执行的指令数目/1000000(ms)
        __delay(usecs * loops_per_usec);                        //Delay 几毫秒的可以执行的指令
    }


    注:rdtsc这个指令是得到CPU自启动以后的运行周期,不适合超线程和多核CPU

    墙上时钟:RTC
    static struct timeval curr_time;
    do_gettimeofday(&curr_time);


    timer_list原理:
    初始化timer时,首先取一个cpu变量【timer在哪个cpu注册,就在哪个cpu触发】
    作为本cpu上所有timer的控制结构,根据超时程度将timers进行分级管理,其中base->timer_jiffies为最短的那个计时器的时间:
    0 - 1<<8       tv1  index = expires
      - 1<<(8+6)   tv2    index = expires >> 8()
      - 1<<(8+2*6) tv3  index = expires >> 8+6()
      - 1<<(8+3*6) tv4  index = expires >> 8+2*6()
      ...          tv5  [不是直接根据索引来决定在数组的地方,因为数组的地方是有限的]
     

    在tv2中,需要把 2^8 - 2^14之间的timers均匀放到一个2^6的数组中,只能2^8对齐,每个数组链中最多放置2^8个timers.
    往后类推..


    tv1
    1  2  3  4  5  6 ....    vec
    a1 b1 c1 d1 e1 f1
    a2 b2 c2
    a3    c3
    a4
    最后一步,添加timer到目标队列的尾部.

    timer_list执行调度:
    初始化:init_timers_cpu,主要是分配cpu变量,(除了启动cpu0是固定的静态空间),后再初始化tv1-tv5所有的timer header.
    调用:这里从时钟irq中开始执行,增加jiffies.
    run_timer_softirq(timer.c)
       ->  __run_timers
       
    在函数update_process_times调用run_local_timers后触发软中断:
    raise_softirq(TIMER_SOFTIRQ);  

    遍历过程:
    static inline void __run_timers(struct tvec_base *base)
    {
        struct timer_list *timer;

        spin_lock_irq(&base->lock);
        while (time_after_eq(jiffies, base->timer_jiffies)) {            //遍历所有超时的列表
            struct list_head work_list;
            struct list_head *head = &work_list;
            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);        //清空这个列表,并处理
            while (!list_empty(head)) {                                    //遍历这个列表下的所有timer
                void (*fn)(unsigned long);
                unsigned long data;
                bool irqsafe;
                timer = list_first_entry(head, struct timer_list,entry);//取出timer
                fn = timer->function;
                data = timer->data;
                irqsafe = tbase_get_irqsafe(timer->base);

                timer_stats_account_timer(timer);

                base->running_timer = timer;
                detach_expired_timer(timer, base);                        //timer脱链

                if (irqsafe) {
                    spin_unlock(&base->lock);
                    call_timer_fn(timer, fn, data);                        //调用实际的函数
                    spin_lock(&base->lock);
                } else {
                    spin_unlock_irq(&base->lock);
                    call_timer_fn(timer, fn, data);
                    spin_lock_irq(&base->lock);
                }
            }
        }
        base->running_timer = NULL;
        spin_unlock_irq(&base->lock);
    }

    核心的降级处理函数:
    #define INDEX(N) ((base->timer_jiffies >> (TVR_BITS + (N) * TVN_BITS)) & TVN_MASK)

    static int cascade(struct tvec_base *base, struct tvec *tv, int index)
    {
        struct timer_list *timer, *tmp;
        struct list_head tv_list;
        list_replace_init(tv->vec + index, &tv_list);            //获取
        list_for_each_entry_safe(timer, tmp, &tv_list, entry) {
            __internal_add_timer(base, timer);
        }
        return index;
    }

    index=0 说明当前的tv1已经为空,这个时候base->timer_jiffies应该已经 >256, INDEX(N)的作用就是减去基数获取实际所在的
    链表位置,在tv2中timer_jiffies逐渐增加,每次取tv2的一个数组链表然后释放到tv1中(256),逐渐释放,当tv2结束时,同理从tv3
    释放到tv2.

    转载于:https://www.cnblogs.com/wenhuisun/p/3158625.html

    展开全文
  • 所谓低分辨率定时器,是指这种定时器的计时单位基于jiffies值的计数,也就是说,它的精度只有1/HZ,假如你的内核配置的HZ是1000,那意味着系统中的低分辨率定时器的精度就是1ms。早期的内核版本中,内核并不支持高...

    http://blog.csdn.net/droidphone/article/details/8051405

    利用定时器,我们可以设定在未来的某一时刻,触发一个特定的事件。所谓低分辨率定时器,是指这种定时器的计时单位基于jiffies值的计数,也就是说,它的精度只有1/HZ,假如你的内核配置的HZ是1000,那意味着系统中的低分辨率定时器的精度就是1ms。早期的内核版本中,内核并不支持高精度定时器,理所当然只能使用这种低分辨率定时器,我们有时候把这种基于HZ的定时器机制成为时间轮:time wheel。虽然后来出现了高分辨率定时器,但它只是内核的一个可选配置项,所以直到目前最新的内核版本,这种低分辨率定时器依然被大量地使用着。

    定时器的使用方法

    在讨论定时器的实现原理之前,我们先看看如何使用定时器。要在内核编程中使用定时器,首先我们要定义一个time_list结构,该结构在include/linux/timer.h中定义:

    struct timer_list {
        /*
         * All fields that change during normal runtime grouped to the
         * same cacheline
         */
        struct list_head entry;
        unsigned long expires;
        struct tvec_base *base;
    
        void (*function)(unsigned long);
        unsigned long data;
    
        int slack;
            ......
    };

    entry 字段用于把一组定时器组成一个链表,至于内核如何对定时器进行分组,我们会在后面进行解释。
    expires 字段指出了该定时器的到期时刻,也就是期望定时器到期时刻的jiffies计数值。

    base 每个cpu拥有一个自己的用于管理定时器的tvec_base结构,该字段指向该定时器所属的cpu所对应tvec_base结构。

    function 字段是一个函数指针,定时器到期时,系统将会调用该回调函数,用于响应该定时器的到期事件。

    data 该字段用于上述回调函数的参数。

    slack 对有些对到期时间精度不太敏感的定时器,到期时刻允许适当地延迟一小段时间,该字段用于计算每次延迟的HZ数。

    要定义一个timer_list,我们可以使用静态和动态两种办法,静态方法使用DEFINE_TIMER宏:

    #define DEFINE_TIMER(_name, _function, _expires, _data)

    该宏将得到一个名字为_name,并分别用_function,_expires,_data参数填充timer_list的相关字段。

    如果要使用动态的方法,则可以自己声明一个timer_list结构,然后手动初始化它的各个字段:

    struct timer_list timer;  
    ......  
    init_timer(&timer);  
    timer.function = _function;  
    timer.expires = _expires;  
    timer.data = _data;  

    要激活一个定时器,我们只要调用add_timer即可:

    add_timer(&timer); 

    要修改定时器的到期时间,我们只要调用mod_timer即可:

    mod_timer(&timer, jiffies+50); 

    要移除一个定时器,我们只要调用del_timer即可:

    del_timer(&timer);  

    定时器系统还提供了以下这些API供我们使用:

    • void add_timer_on(struct timer_list *timer, int cpu); // 在指定的cpu上添加定时器
    • int mod_timer_pending(struct timer_list *timer, unsigned long expires); // 只有当timer已经处在激活状态时,才修改timer的到期时刻
    • int mod_timer_pinned(struct timer_list *timer, unsigned long expires);
    • void set_timer_slack(struct timer_list *time, int slack_hz); // 设定timer允许的到期时刻的最大延迟,用于对精度不敏感的定时器
    • int del_timer_sync(struct timer_list *timer); // 如果该timer正在被处理中,则等待timer处理完成才移除该timer

    定时器的软件架构

    低分辨率定时器是基于HZ来实现的,也就是说,每个tick周期,都有可能有定时器到期,关于tick如何产生,请参考:Linux时间子系统之四:定时器的引擎:clock_event_device。系统中有可能有成百上千个定时器,难道在每个tick中断中遍历一下所有的定时器,检查它们是否到期?内核当然不会使用这么笨的办法,它使用了一个更聪明的办法:按定时器的到期时间对定时器进行分组。因为目前的多核处理器使用越来越广泛,连智能手机的处理器动不动就是4核心,内核对多核处理器有较好的支持,低分辨率定时器在实现时也充分地考虑了多核处理器的支持和优化。为了较好地利用cache line,也为了避免cpu之间的互锁,内核为多核处理器中的每个cpu单独分配了管理定时器的相关数据结构和资源,每个cpu独立地管理属于自己的定时器。

    定时器的分组

    首先,内核为每个cpu定义了一个tvec_base结构指针:

    static DEFINE_PER_CPU(struct tvec_base *, tvec_bases) = &boot_tvec_bases;  

    tvec_base结构的定义如下:

    struct tvec_base {  
        spinlock_t lock;  
        struct timer_list *running_timer;  
        unsigned long timer_jiffies;  
        unsigned long next_timer;  
        struct tvec_root tv1;  
        struct tvec tv2;  
        struct tvec tv3;  
        struct tvec tv4;  
        struct tvec tv5;  
    } ____cacheline_aligned;  

    running_timer 该字段指向当前cpu正在处理的定时器所对应的timer_list结构。
    timer_jiffies 该字段表示当前cpu定时器所经历过的jiffies数,大多数情况下,该值和jiffies计数值相等,当cpu的idle状态连续持续了多个jiffies时间时,当退出idle状态时,jiffies计数值就会大于该字段,在接下来的tick中断后,定时器系统会让该字段的值追赶上jiffies值。

    next_timer 该字段指向该cpu下一个即将到期的定时器。

    tv1–tv5 这5个字段用于对定时器进行分组,实际上,tv1–tv5都是一个链表数组,其中tv1的数组大小为TVR_SIZE, tv2 tv3 tv4 tv5的数组大小为TVN_SIZE,根据CONFIG_BASE_SMALL配置项的不同,它们有不同的大小:

    #define TVN_BITS (CONFIG_BASE_SMALL ? 4 : 6)  
    #define TVR_BITS (CONFIG_BASE_SMALL ? 6 : 8)  
    #define TVN_SIZE (1 << TVN_BITS)  
    #define TVR_SIZE (1 << TVR_BITS)  
    #define TVN_MASK (TVN_SIZE - 1)  
    #define TVR_MASK (TVR_SIZE - 1)  
    
    struct tvec {  
        struct list_head vec[TVN_SIZE];  
    };  
    
    struct tvec_root {  
        struct list_head vec[TVR_SIZE];  
    };  

    默认情况下,没有使能CONFIG_BASE_SMALL,TVR_SIZE的大小是256,TVN_SIZE的大小则是64,当需要节省内存空间时,也可以使能CONFIG_BASE_SMALL,这时TVR_SIZE的大小是64,TVN_SIZE的大小则是16,以下的讨论我都是基于没有使能CONFIG_BASE_SMALL的情况。当有一个新的定时器要加入时,系统根据定时器到期的jiffies值和timer_jiffies字段的差值来决定该定时器被放入tv1至tv5中的哪一个数组中,最终,系统中所有的定时器的组织结构如下图所示:
    这里写图片描述

    定时器的添加

    要加入一个新的定时器,我们可以通过api函数add_timer或mod_timer来完成,最终的工作会交由internal_add_timer函数来处理。该函数按以下步骤进行处理:

    • 计算定时器到期时间和所属cpu的tvec_base结构中的timer_jiffies字段的差值,记为idx;
    • 根据idx的值,选择该定时器应该被放到tv1–tv5中的哪一个链表数组中,可以认为tv1-tv5分别占据一个32位数的不同比特位,tv1占据最低的8位,tv2占据紧接着的6位,然后tv3再占位,以此类推,最高的6位分配给tv5。最终的选择规则如下表所示:
    链表数组 idx范围
    tv1 0-255(2^8)
    tv2 256–16383(2^14)
    tv3 16384–1048575(2^20)
    tv4 1048576–67108863(2^26)
    tv5 67108864–4294967295(2^32)

    确定链表数组后,接着要确定把该定时器放入数组中的哪一个链表中,如果时间差idx小于256,按规则要放入tv1中,因为tv1包含了256个链表,所以可以简单地使用timer_list.expires的低8位作为数组的索引下标,把定时器链接到tv1中相应的链表中即可。如果时间差idx的值在256–18383之间,则需要把定时器放入tv2中,同样的,使用timer_list.expires的8–14位作为数组的索引下标,把定时器链接到tv2中相应的链表中,。定时器要加入tv3 tv4 tv5使用同样的原理。经过这样分组后的定时器,在后续的tick事件中,系统可以很方便地定位并取出相应的到期定时器进行处理。以上的讨论都体现在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;  
        struct list_head *vec;  
    
        if (idx < TVR_SIZE) {  
            int i = expires & TVR_MASK;  
            vec = base->tv1.vec + i;  
        } else if (idx < 1 << (TVR_BITS + TVN_BITS)) {  
            int i = (expires >> TVR_BITS) & TVN_MASK;  
            vec = base->tv2.vec + i;  
        } else if (idx < 1 << (TVR_BITS + 2 * TVN_BITS)) {  
            int i = (expires >> (TVR_BITS + TVN_BITS)) & TVN_MASK;  
            vec = base->tv3.vec + i;  
        } else if (idx < 1 << (TVR_BITS + 3 * TVN_BITS)) {  
            int i = (expires >> (TVR_BITS + 2 * TVN_BITS)) & TVN_MASK;  
            vec = base->tv4.vec + i;  
        } else if ((signed long) idx < 0) {  
                    ......  
        } else {  
                    ......  
            i = (expires >> (TVR_BITS + 3 * TVN_BITS)) & TVN_MASK;  
            vec = base->tv5.vec + i;  
        }  
        list_add_tail(&timer->entry, vec);  
    }  

    定时器的到期处理

    经过2.1节的处理后,系统中的定时器按到期时间有规律地放置在tv1–tv5各个链表数组中,其中tv1中放置着在接下来的256个jiffies即将到期的定时器列表,需要注意的是,并不是tv1.vec[0]中放置着马上到期的定时器列表,tv1.vec[1]中放置着将在jiffies+1到期的定时器列表。因为base.timer_jiffies的值一直在随着系统的运行而动态地增加,原则上是每个tick事件会加1,base.timer_jiffies代表者该cpu定时器系统当前时刻,定时器也是动态地加入头256个链表tv1中,按2.1节的讨论,定时器加入tv1中使用的下标索引是定时器到期时间expires的低8位,所以假设当前的base.timer_jiffies值是0x34567826,则马上到期的定时器是在tv1.vec[0x26]中,如果这时候系统加入一个在jiffies值0x34567828到期的定时器,他将会加入到tv1.vec[0x28]中,运行两个tick后,base.timer_jiffies的值会变为0x34567828,很显然,在每次tick事件中,定时器系统只要以base.timer_jiffies的低8位作为索引,取出tv1中相应的链表,里面正好包含了所有在该jiffies值到期的定时器列表。

    那什么时候处理tv2–tv5中的定时器?每当base.timer_jiffies的低8位为0值时,这表明base.timer_jiffies的第8-13位有进位发生,这6位正好代表着tv2,这时只要按base.timer_jiffies的第8-13位的值作为下标,移出tv2中对应的定时器链表,然后用internal_add_timer把它们从新加入到定时器系统中来,因为这些定时器一定会在接下来的256个tick期间到期,所以它们肯定会被加入到tv1数组中,这样就完成了tv2往tv1迁移的过程。同样地,当base.timer_jiffies的第8-13位为0时,这表明base.timer_jiffies的第14-19位有进位发生,这6位正好代表着tv3,按base.timer_jiffies的第14-19位的值作为下标,移出tv3中对应的定时器链表,然后用internal_add_timer把它们从新加入到定时器系统中来,显然它们会被加入到tv2中,从而完成tv3到tv2的迁移,tv4,tv5的处理可以以此作类推。具体迁移的代码如下,参数index为事先计算好的高一级tv的需要迁移的数组索引:

    static int cascade(struct tvec_base *base, struct tvec *tv, int index)  
    {  
        /* cascade all the timers from tv up one level */  
        struct timer_list *timer, *tmp;  
        struct list_head tv_list;  
    
        list_replace_init(tv->vec + index, &tv_list);  //  移除需要迁移的链表  
    
        /* 
         * We are removing _all_ timers from the list, so we 
         * don't have to detach them individually. 
         */  
        list_for_each_entry_safe(timer, tmp, &tv_list, entry) {  
            BUG_ON(tbase_get_base(timer->base) != base);  
                    //  重新加入到定时器系统中,实际上将会迁移到下一级的tv数组中  
            internal_add_timer(base, timer);    
        }  
    
        return index;  
    }  

    每个tick事件到来时,内核会在tick定时中断处理期间激活定时器软中断:TIMER_SOFTIRQ,关于软件中断,请参考另一篇博文:Linux中断(interrupt)子系统之五:软件中断(softIRQ。TIMER_SOFTIRQ的执行函数是__run_timers,它实现了本节讨论的逻辑,取出tv1中到期的定时器,执行定时器的回调函数,由此可见,低分辨率定时器的回调函数是执行在软件中断上下文中的,这点在写定时器的回调函数时需要注意。__run_timers的代码如下:

    static inline void __run_timers(struct tvec_base *base)  
    {  
        struct timer_list *timer;  
    
        spin_lock_irq(&base->lock);  
            /* 同步jiffies,在NO_HZ情况下,base->timer_jiffies可能落后不止一个tick  */  
        while (time_after_eq(jiffies, base->timer_jiffies)) {    
            struct list_head work_list;  
            struct list_head *head = &work_list;  
                    /*  计算到期定时器链表在tv1中的索引  */  
            int index = base->timer_jiffies & TVR_MASK;    
    
            /* 
             * /*  tv2--tv5定时器列表迁移处理  */  
             */  
            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));    
                    /*  该cpu定时器系统运行时间递增一个tick  */                   
            ++base->timer_jiffies;    
                    /*  取出到期的定时器链表  */                                         
            list_replace_init(base->tv1.vec + index, &work_list);  
                    /*  遍历所有的到期定时器  */            
            while (!list_empty(head)) {                                      
                void (*fn)(unsigned long);  
                unsigned long data;  
    
                timer = list_first_entry(head, struct timer_list,entry);  
                fn = timer->function;  
                data = timer->data;  
    
                timer_stats_account_timer(timer);  
    
                base->running_timer = timer;    /*  标记正在处理的定时器  */  
                detach_timer(timer, 1);  
    
                spin_unlock_irq(&base->lock);  
                call_timer_fn(timer, fn, data);  /*  调用定时器的回调函数  */  
                spin_lock_irq(&base->lock);  
            }  
        }  
        base->running_timer = NULL;  
        spin_unlock_irq(&base->lock);  
    }  

    通过上面的讨论,我们可以发现,内核的低分辨率定时器的实现非常精妙,既实现了大量定时器的管理,又实现了快速的O(1)查找到期定时器的能力,利用巧妙的数组结构,使得只需在间隔256个tick时间才处理一次迁移操作,5个数组就好比是5个齿轮,它们随着base->timer_jifffies的增长而不停地转动,每次只需处理第一个齿轮的某一个齿节,低一级的齿轮转动一圈,高一级的齿轮转动一个齿,同时自动把即将到期的定时器迁移到上一个齿轮中,所以低分辨率定时器通常又被叫做时间轮:time wheel。事实上,它的实现是一个很好的空间换时间软件算法。

    定时器软件中断

    系统初始化时,start_kernel会调用定时器系统的初始化函数init_timers:

    void __init init_timers(void)  
    {        
        int err = timer_cpu_notify(&timers_nb, (unsigned long)CPU_UP_PREPARE,   
                    (void *)(long)smp_processor_id());  
    
        init_timer_stats();  
    
        BUG_ON(err != NOTIFY_OK);  
        register_cpu_notifier(&timers_nb);  /* 注册cpu notify,以便在hotplug时在cpu之间进行定时器的迁移 */  
        open_softirq(TIMER_SOFTIRQ, run_timer_softirq);  
    }  

    可见,open_softirq把run_timer_softirq注册为TIMER_SOFTIRQ的处理函数,另外,当cpu的每个tick事件到来时,在事件处理中断中,update_process_times会被调用,该函数会进一步调用run_local_timers,run_local_timers会触发TIMER_SOFTIRQ软中断:

    void run_local_timers(void)  
    {  
        hrtimer_run_queues();  
        raise_softirq(TIMER_SOFTIRQ);  
    }  

    TIMER_SOFTIRQ的处理函数是run_timer_softirq:

    static void run_timer_softirq(struct softirq_action *h)  
    {  
        struct tvec_base *base = __this_cpu_read(tvec_bases);  
    
        hrtimer_run_pending();  
    
        if (time_after_eq(jiffies, base->timer_jiffies))  
            __run_timers(base);  
    }  

    好啦,终于看到__run_timers函数了,2.2节已经介绍过,正是这个函数完成了对到期定时器的处理工作,也完成了时间轮的不停转动。

    展开全文
  • 上一篇文章,我介绍了传统的低分辨率定时器的实现原理。而随着内核的不断演进,大牛们已经对这种低分辨率定时器的精度不再满足,而且,硬件也在不断地发展,系统中的定时器硬件的精度也越来越高,这也给高分辨率...

    上一篇文章,我介绍了传统的低分辨率定时器的实现原理。而随着内核的不断演进,大牛们已经对这种低分辨率定时器的精度不再满足,而且,硬件也在不断地发展,系统中的定时器硬件的精度也越来越高,这也给高分辨率定时器的出现创造了条件。内核从2.6.16开始加入了高精度定时器架构。在实现方式上,内核的高分辨率定时器的实现代码几乎没有借用低分辨率定时器的数据结构和代码,内核文档给出的解释主要有以下几点:

    • 低分辨率定时器的代码和jiffies的关系太过紧密,并且默认按32位进行设计,并且它的代码已经经过长时间的优化,目前的使用也是没有任何错误,如果硬要基于它来实现高分辨率定时器,势必会打破原有的时间轮概念,并且会引入一大堆#if--#else判断;
    • 虽然大部分时间里,时间轮可以实现O(1)时间复杂度,但是当有进位发生时,不可预测的O(N)定时器级联迁移时间,这对于低分辨率定时器来说问题不大,可是它大大地影响了定时器的精度;
    • 低分辨率定时器几乎是为“超时”而设计的,并为此对它进行了大量的优化,对于这些以“超时”未目的而使用定时器,它们大多数期望在超时到来之前获得正确的结果,然后删除定时器,精确时间并不是它们主要的目的,例如网络通信、设备IO等等。

    为此,内核为高精度定时器重新设计了一套软件架构,它可以为我们提供纳秒级的定时精度,以满足对精确时间有迫切需求的应用程序或内核驱动,例如多媒体应用,音频设备的驱动程序等等。以下的讨论用hrtimer(high resolution timer)表示高精度定时器。
    /*****************************************************************************************************/
    声明:本博内容均由http://blog.csdn.net/droidphone原创,转载请注明出处,谢谢!
    /*****************************************************************************************************/

    1.  如何组织hrtimer?

    我们知道,低分辨率定时器使用5个链表数组来组织timer_list结构,形成了著名的时间轮概念,对于高分辨率定时器,我们期望组织它们的数据结构至少具备以下条件:

    • 稳定而且快速的查找能力;
    • 快速地插入和删除定时器的能力;
    • 排序功能;

    内核的开发者考察了多种数据结构,例如基数树、哈希表等等,最终他们选择了红黑树(rbtree)来组织hrtimer,红黑树已经以库的形式存在于内核中,并被成功地使用在内存管理子系统和文件系统中,随着系统的运行,hrtimer不停地被创建和销毁,新的hrtimer按顺序被插入到红黑树中,树的最左边的节点就是最快到期的定时器,内核用一个hrtimer结构来表示一个高精度定时器:

    struct hrtimer {
    	struct timerqueue_node		node;
    	ktime_t				_softexpires;
    	enum hrtimer_restart		(*function)(struct hrtimer *);
    	struct hrtimer_clock_base	*base;
    	unsigned long			state;
            ......
    };
    定时器的到期时间用ktime_t来表示,_softexpires字段记录了时间,定时器一旦到期,function字段指定的回调函数会被调用,该函数的返回值为一个枚举值,它决定了该hrtimer是否需要被重新激活:

    enum hrtimer_restart {
    	HRTIMER_NORESTART,	/* Timer is not restarted */
    	HRTIMER_RESTART,	/* Timer must be restarted */
    };
    state字段用于表示hrtimer当前的状态,有几下几种位组合:

    #define HRTIMER_STATE_INACTIVE	0x00  // 定时器未激活
    #define HRTIMER_STATE_ENQUEUED	0x01  // 定时器已经被排入红黑树中
    #define HRTIMER_STATE_CALLBACK	0x02  // 定时器的回调函数正在被调用
    #define HRTIMER_STATE_MIGRATE	0x04  // 定时器正在CPU之间做迁移
    hrtimer的到期时间可以基于以下几种时间基准系统:

    enum  hrtimer_base_type {
    	HRTIMER_BASE_MONOTONIC,  // 单调递增的monotonic时间,不包含休眠时间
    	HRTIMER_BASE_REALTIME,   // 平常使用的墙上真实时间
    	HRTIMER_BASE_BOOTTIME,   // 单调递增的boottime,包含休眠时间
    	HRTIMER_MAX_CLOCK_BASES, // 用于后续数组的定义
    };
    和低分辨率定时器一样,处于效率和上锁的考虑,每个cpu单独管理属于自己的hrtimer,为此,专门定义了一个结构hrtimer_cpu_base:

    struct hrtimer_cpu_base {
            ......
    	struct hrtimer_clock_base	clock_base[HRTIMER_MAX_CLOCK_BASES];
    };
    其中,clock_base数组为每种时间基准系统都定义了一个hrtimer_clock_base结构,它的定义如下:

    struct hrtimer_clock_base {
    	struct hrtimer_cpu_base	*cpu_base;  // 指向所属cpu的hrtimer_cpu_base结构
            ......
    	struct timerqueue_head	active;     // 红黑树,包含了所有使用该时间基准系统的hrtimer
    	ktime_t			resolution; // 时间基准系统的分辨率
    	ktime_t			(*get_time)(void); // 获取该基准系统的时间函数
    	ktime_t			softirq_time;// 当用jiffies
    	ktime_t			offset;      // 
    };
    active字段是一个timerqueue_head结构,它实际上是对rbtree的进一步封装:
    struct timerqueue_node {
    	struct rb_node node;  // 红黑树的节点
    	ktime_t expires;      // 该节点代表队hrtimer的到期时间,与hrtimer结构中的_softexpires稍有不同
    };
    
    struct timerqueue_head {
    	struct rb_root head;          // 红黑树的根节点
    	struct timerqueue_node *next; // 该红黑树中最早到期的节点,也就是最左下的节点
    };
    timerqueue_head结构在红黑树的基础上,增加了一个next字段,用于保存树中最先到期的定时器节点,实际上就是树的最左下方的节点,有了next字段,当到期事件到来时,系统不必遍历整个红黑树,只要取出next字段对应的节点进行处理即可。timerqueue_node用于表示一个hrtimer节点,它在标准红黑树节点rb_node的基础上增加了expires字段,该字段和hrtimer中的_softexpires字段一起,设定了hrtimer的到期时间的一个范围,hrtimer可以在hrtimer._softexpires至timerqueue_node.expires之间的任何时刻到期,我们也称timerqueue_node.expires为硬过期时间(hard),意思很明显:到了此时刻,定时器一定会到期,有了这个范围可以选择,定时器系统可以让范围接近的多个定时器在同一时刻同时到期,这种设计可以降低进程频繁地被hrtimer进行唤醒。经过以上的讨论,我们可以得出以下的图示,它表明了每个cpu上的hrtimer是如何被组织在一起的:

                                                           图 1.1  每个cpu的hrtimer组织结构

    总结一下:

    • 每个cpu有一个hrtimer_cpu_base结构;
    • hrtimer_cpu_base结构管理着3种不同的时间基准系统的hrtimer,分别是:实时时间,启动时间和单调时间;
    • 每种时间基准系统通过它的active字段(timerqueue_head结构指针),指向它们各自的红黑树;
    • 红黑树上,按到期时间进行排序,最先到期的hrtimer位于最左下的节点,并被记录在active.next字段中;
    • 3中时间基准的最先到期时间可能不同,所以,它们之中最先到期的时间被记录在hrtimer_cpu_base的expires_next字段中。

    2.  hrtimer如何运转

    hrtimer的实现需要一定的硬件基础,它的实现依赖于我们前几章介绍的timekeeper和clock_event_device,如果你对timekeeper和clock_event_device不了解请参考以下文章:Linux时间子系统之三:时间的维护者:timekeeperLinux时间子系统之四:定时器的引擎:clock_event_device。hrtimer系统需要通过timekeeper获取当前的时间,计算与到期时间的差值,并根据该差值,设定该cpu的tick_device(clock_event_device)的下一次的到期时间,时间一到,在clock_event_device的事件回调函数中处理到期的hrtimer。现在你或许有疑问:前面在介绍clock_event_device时,我们知道,每个cpu有自己的tick_device,通常用于周期性地产生进程调度和时间统计的tick事件,这里又说要用tick_device调度hrtimer系统,通常cpu只有一个tick_device,那他们如何协调工作?这个问题也一度困扰着我,如果再加上NO_HZ配置带来tickless特性,你可能会更晕。这里我们先把这个疑问放下,我将在后面的章节中来讨论这个问题,现在我们只要先知道,一旦开启了hrtimer,tick_device所关联的clock_event_device的事件回调函数会被修改为:hrtimer_interrupt,并且会被设置成工作于CLOCK_EVT_MODE_ONESHOT单触发模式。

    2.1  添加一个hrtimer

    要添加一个hrtimer,系统提供了一些api供我们使用,首先我们需要定义一个hrtimer结构的实例,然后用hrtimer_init函数对它进行初始化,它的原型如下:

    void hrtimer_init(struct hrtimer *timer, clockid_t which_clock,
    			 enum hrtimer_mode mode);
    which_clock可以是CLOCK_REALTIME、CLOCK_MONOTONIC、CLOCK_BOOTTIME中的一种,mode则可以是相对时间HRTIMER_MODE_REL,也可以是绝对时间HRTIMER_MODE_ABS。设定回调函数:
    timer.function = hr_callback;

    如果定时器无需指定一个到期范围,可以在设定回调函数后直接使用hrtimer_start激活该定时器:

    int hrtimer_start(struct hrtimer *timer, ktime_t tim,
    			 const enum hrtimer_mode mode);
    如果需要指定到期范围,则可以使用hrtimer_start_range_ns激活定时器:

    hrtimer_start_range_ns(struct hrtimer *timer, ktime_t tim,
    			unsigned long range_ns, const enum hrtimer_mode mode);
    要取消一个hrtimer,使用hrtimer_cancel:

    int hrtimer_cancel(struct hrtimer *timer);
    以下两个函数用于推后定时器的到期时间:

    extern u64
    hrtimer_forward(struct hrtimer *timer, ktime_t now, ktime_t interval);
    
    /* Forward a hrtimer so it expires after the hrtimer's current now */
    static inline u64 hrtimer_forward_now(struct hrtimer *timer,
    				      ktime_t interval)
    {
    	return hrtimer_forward(timer, timer->base->get_time(), interval);
    }
    以下几个函数用于获取定时器的当前状态:

    static inline int hrtimer_active(const struct hrtimer *timer)
    {
    	return timer->state != HRTIMER_STATE_INACTIVE;
    }
    
    static inline int hrtimer_is_queued(struct hrtimer *timer)
    {
    	return timer->state & HRTIMER_STATE_ENQUEUED;
    }
    
    static inline int hrtimer_callback_running(struct hrtimer *timer)
    {
    	return timer->state & HRTIMER_STATE_CALLBACK;
    }
    hrtimer_init最终会进入__hrtimer_init函数,该函数的主要目的是初始化hrtimer的base字段,同时初始化作为红黑树的节点的node字段:

    static void __hrtimer_init(struct hrtimer *timer, clockid_t clock_id,
    			   enum hrtimer_mode mode)
    {
    	struct hrtimer_cpu_base *cpu_base;
    	int base;
    
    	memset(timer, 0, sizeof(struct hrtimer));
    
    	cpu_base = &__raw_get_cpu_var(hrtimer_bases);
    
    	if (clock_id == CLOCK_REALTIME && mode != HRTIMER_MODE_ABS)
    		clock_id = CLOCK_MONOTONIC;
    
    	base = hrtimer_clockid_to_base(clock_id);
    	timer->base = &cpu_base->clock_base[base];
    	timerqueue_init(&timer->node);
            ......
    }

    hrtimer_start和hrtimer_start_range_ns最终会把实际的工作交由__hrtimer_start_range_ns来完成:

    int __hrtimer_start_range_ns(struct hrtimer *timer, ktime_t tim,
    		unsigned long delta_ns, const enum hrtimer_mode mode,
    		int wakeup)
    {
            ......        
            /* 取得hrtimer_clock_base指针 */
            base = lock_hrtimer_base(timer, &flags); 
            /* 如果已经在红黑树中,先移除它: */
            ret = remove_hrtimer(timer, base); ......
            /* 如果是相对时间,则需要加上当前时间,因为内部是使用绝对时间 */
            if (mode & HRTIMER_MODE_REL) {
                    tim = ktime_add_safe(tim, new_base->get_time());
                    ......
            } 
            /* 设置到期的时间范围 */
            hrtimer_set_expires_range_ns(timer, tim, delta_ns);
            ...... 
            /* 把hrtime按到期时间排序,加入到对应时间基准系统的红黑树中 */
            /* 如果该定时器的是最早到期的,将会返回true */
            leftmost = enqueue_hrtimer(timer, new_base);
            /* 
            * Only allow reprogramming if the new base is on this CPU. 
            * (it might still be on another CPU if the timer was pending) 
            * 
            * XXX send_remote_softirq() ?
            * 定时器比之前的到期时间要早,所以需要重新对tick_device进行编程,重新设定的的到期时间
            */
            if (leftmost && new_base->cpu_base == &__get_cpu_var(hrtimer_bases))
                    hrtimer_enqueue_reprogram(timer, new_base, wakeup);
            unlock_hrtimer_base(timer, &flags);
            return ret;
    }
    <p style="box-sizing: border-box; margin-top: 0px; margin-bottom: 0px; padding-top: 0.2rem; padding-bottom: 0.3rem; font-size: 0.7rem; line-height: 0.875rem; word-break: break-all;">
    </p>
    
    2.2  hrtimer的到期处理

    高精度定时器系统有3个入口可以对到期定时器进行处理,它们分别是:

    • 没有切换到高精度模式时,在每个jiffie的tick事件中断中进行查询和处理;
    • 在HRTIMER_SOFTIRQ软中断中进行查询和处理;
    • 切换到高精度模式后,在每个clock_event_device的到期事件中断中进行查询和处理;

    低精度模式  因为系统并不是一开始就会支持高精度模式,而是在系统启动后的某个阶段,等待所有的条件都满足后,才会切换到高精度模式,当系统还没有切换到高精度模式时,所有的高精度定时器运行在低精度模式下,在每个jiffie的tick事件中断中进行到期定时器的查询和处理,显然这时候的精度和低分辨率定时器是一样的(HZ级别)。低精度模式下,每个tick事件中断中,hrtimer_run_queues函数会被调用,由它完成定时器的到期处理。hrtimer_run_queues首先判断目前高精度模式是否已经启用,如果已经切换到了高精度模式,什么也不做,直接返回:

    void hrtimer_run_queues(void)
    {
    
    	if (hrtimer_hres_active())
    		return;
    
    如果hrtimer_hres_active返回false,说明目前处于低精度模式下,则继续处理,它用一个for循环遍历各个时间基准系统,查询每个hrtimer_clock_base对应红黑树的左下节点,判断它的时间是否到期,如果到期,通过__run_hrtimer函数,对到期定时器进行处理,包括:调用定时器的回调函数、从红黑树中移除该定时器、根据回调函数的返回值决定是否重新启动该定时器等等:

    	for (index = 0; index < HRTIMER_MAX_CLOCK_BASES; index++) {
    		base = &cpu_base->clock_base[index];
    		if (!timerqueue_getnext(&base->active))
    			continue;
    
    		if (gettime) {
    			hrtimer_get_softirq_time(cpu_base);
    			gettime = 0;
    		}
    
    		raw_spin_lock(&cpu_base->lock);
    
    		while ((node = timerqueue_getnext(&base->active))) {
    			struct hrtimer *timer;
    
    			timer = container_of(node, struct hrtimer, node);
    			if (base->softirq_time.tv64 <=
    					hrtimer_get_expires_tv64(timer))
    				break;
    
    			__run_hrtimer(timer, &base->softirq_time);
    		}
    		raw_spin_unlock(&cpu_base->lock);
    	}
    上面的timerqueue_getnext函数返回红黑树中的左下节点,之所以可以在while循环中使用该函数,是因为__run_hrtimer会在移除旧的左下节点时,新的左下节点会被更新到base->active->next字段中,使得循环可以继续执行,直到没有新的到期定时器为止。

    高精度模式  切换到高精度模式后,原来给cpu提供tick事件的tick_device(clock_event_device)会被高精度定时器系统接管,它的中断事件回调函数被设置为hrtimer_interrupt,红黑树中最左下的节点的定时器的到期时间被编程到该clock_event_device中,这样每次clock_event_device的中断意味着至少有一个高精度定时器到期。另外,当timekeeper系统中的时间需要修正,或者clock_event_device的到期事件时间被重新编程时,系统会发出HRTIMER_SOFTIRQ软中断,软中断的处理函数run_hrtimer_softirq最终也会调用hrtimer_interrupt函数对到期定时器进行处理,所以在这里我们只要讨论hrtimer_interrupt函数的实现即可。

    hrtimer_interrupt函数的前半部分和低精度模式下的hrtimer_run_queues函数完成相同的事情:它用一个for循环遍历各个时间基准系统,查询每个hrtimer_clock_base对应红黑树的左下节点,判断它的时间是否到期,如果到期,通过__run_hrtimer函数,对到期定时器进行处理,所以我们只讨论后半部分,在处理完所有到期定时器后,下一个到期定时器的到期时间保存在变量expires_next中,接下来的工作就是把这个到期时间编程到tick_device中:

    void hrtimer_interrupt(struct clock_event_device *dev)
    {
            ......
    	for (i = 0; i < HRTIMER_MAX_CLOCK_BASES; i++) {
                    ......
    		while ((node = timerqueue_getnext(&base->active))) {
                            ......
    			if (basenow.tv64 < hrtimer_get_softexpires_tv64(timer)) {
    				ktime_t expires;
    
    				expires = ktime_sub(hrtimer_get_expires(timer),
    						    base->offset);
    				if (expires.tv64 < expires_next.tv64)
    					expires_next = expires;
    				break;
    			}
    
    			__run_hrtimer(timer, &basenow);
    		}
    	}
    
    	/*
    	 * Store the new expiry value so the migration code can verify
    	 * against it.
    	 */
    	cpu_base->expires_next = expires_next;
    	raw_spin_unlock(&cpu_base->lock);
    
    	/* Reprogramming necessary ? */
    	if (expires_next.tv64 == KTIME_MAX ||
    	    !tick_program_event(expires_next, 0)) {
    		cpu_base->hang_detected = 0;
    		return;
    	}
    如果这时的tick_program_event返回了非0值,表示过期时间已经在当前时间的前面,这通常由以下原因造成:

    • 系统正在被调试跟踪,导致时间在走,程序不走;
    • 定时器的回调函数花了太长的时间;
    • 系统运行在虚拟机中,而虚拟机被调度导致停止运行;
    为了避免这些情况的发生,接下来系统提供3次机会,重新执行前面的循环,处理到期的定时器:

    	raw_spin_lock(&cpu_base->lock);
    	now = hrtimer_update_base(cpu_base);
    	cpu_base->nr_retries++;
    	if (++retries < 3)
    		goto retry;
    如果3次循环后还无法完成到期处理,系统不再循环,转为计算本次总循环的时间,然后把tick_device的到期时间强制设置为当前时间加上本次的总循环时间,不过推后的时间被限制在100ms以内:

    	delta = ktime_sub(now, entry_time);
    	if (delta.tv64 > cpu_base->max_hang_time.tv64)
    		cpu_base->max_hang_time = delta;
    	/*
    	 * Limit it to a sensible value as we enforce a longer
    	 * delay. Give the CPU at least 100ms to catch up.
    	 */
    	if (delta.tv64 > 100 * NSEC_PER_MSEC)
    		expires_next = ktime_add_ns(now, 100 * NSEC_PER_MSEC);
    	else
    		expires_next = ktime_add(now, delta);
    	tick_program_event(expires_next, 1);
    	printk_once(KERN_WARNING "hrtimer: interrupt took %llu ns\n",
    		    ktime_to_ns(delta));
    }

    3.  切换到高精度模式

    上面提到,尽管内核配置成支持高精度定时器,但并不是一开始就工作于高精度模式,系统在启动的开始阶段,还是按照传统的模式在运行:tick_device按HZ频率定期地产生tick事件,这时的hrtimer工作在低分辨率模式,到期事件在每个tick事件中断中由hrtimer_run_queues函数处理,同时,在低分辨率定时器(时间轮)的软件中断TIMER_SOFTIRQ中,hrtimer_run_pending会被调用,系统在这个函数中判断系统的条件是否满足切换到高精度模式,如果条件满足,则会切换至高分辨率模式,另外提一下,NO_HZ模式也是在该函数中判断并切换。

    void hrtimer_run_pending(void)
    {
    	if (hrtimer_hres_active())
    		return;
            ......
    	if (tick_check_oneshot_change(!hrtimer_is_hres_enabled()))
    		hrtimer_switch_to_hres();
    }
    因为不管系统是否工作于高精度模式,每个TIMER_SOFTIRQ期间,该函数都会被调用,所以函数一开始先用hrtimer_hres_active判断目前高精度模式是否已经激活,如果已经激活,则说明之前的调用中已经切换了工作模式,不必再次切换,直接返回。hrtimer_hres_active很简单:

    DEFINE_PER_CPU(struct hrtimer_cpu_base, hrtimer_bases) = {
            ......
    }
    
    static inline int hrtimer_hres_active(void)
    {
    	return __this_cpu_read(hrtimer_bases.hres_active);
    }
    hrtimer_run_pending函数接着通过tick_check_oneshot_change判断系统是否可以切换到高精度模式,

    int tick_check_oneshot_change(int allow_nohz)
    {
    	struct tick_sched *ts = &__get_cpu_var(tick_cpu_sched);
    
    	if (!test_and_clear_bit(0, &ts->check_clocks))
    		return 0;
    
    	if (ts->nohz_mode != NOHZ_MODE_INACTIVE)
    		return 0;
    
    	if (!timekeeping_valid_for_hres() || !tick_is_oneshot_available())
    		return 0;
    
    	if (!allow_nohz)
    		return 1;
    
    	tick_nohz_switch_to_nohz();
    	return 0;
    }
    函数的一开始先判断check_clock标志的第0位是否被置位,如果没有置位,说明系统中没有注册符合要求的时钟事件设备,函数直接返回,check_clock标志由clocksource和clock_event_device系统的notify系统置位,当系统中有更高精度的clocksource被注册和选择后,或者有更精确的支持CLOCK_EVT_MODE_ONESHOT模式的clock_event_device被注册时,通过它们的notify函数,check_clock标志的第0为会置位。

    如果tick_sched结构中的nohz_mode字段不是NOHZ_MODE_INACTIVE,表明系统已经切换到其它模式,直接返回。nohz_mode的取值有3种:

    • NOHZ_MODE_INACTIVE    // 未启用NO_HZ模式
    • NOHZ_MODE_LOWRES    // 启用NO_HZ模式,hrtimer工作于低精度模式下
    • NOHZ_MODE_HIGHRES   // 启用NO_HZ模式,hrtimer工作于高精度模式下
    接下来的timerkeeping_valid_for_hres判断timekeeper系统是否支持高精度模式,tick_is_oneshot_available判断tick_device是否支持CLOCK_EVT_MODE_ONESHOT模式。如果都满足要求,则继续往下判断。allow_nohz是函数的参数,为true表明可以切换到NOHZ_MODE_LOWRES 模式,函数将进入tick_nohz_switch_to_nohz,切换至NOHZ_MODE_LOWRES 模式,这里我们传入的allow_nohz是表达式:

    (!hrtimer_is_hres_enabled())

    所以当系统不允许高精度模式时,将会在tick_check_oneshot_change函数内,通过tick_nohz_switch_to_nohz切换至NOHZ_MODE_LOWRES 模式,如果系统允许高精度模式,传入的allow_nohz参数为false,tick_check_oneshot_change函数返回1,回到上面的hrtimer_run_pending函数,hrtimer_switch_to_hres函数将会被调用,已完成切换到NOHZ_MODE_HIGHRES高精度模式。好啦,真正的切换函数找到了,我们看一看它如何切换:

    首先,它通过hrtimer_cpu_base中的hres_active字段判断该cpu是否已经切换至高精度模式,如果是则直接返回:

    static int hrtimer_switch_to_hres(void)
    {
    	int i, cpu = smp_processor_id();
    	struct hrtimer_cpu_base *base = &per_cpu(hrtimer_bases, cpu);
    	unsigned long flags;
    
    	if (base->hres_active)
    		return 1;
    接着,通过tick_init_highres函数接管tick_device关联的clock_event_device:

    	local_irq_save(flags);
    
    	if (tick_init_highres()) {
    		local_irq_restore(flags);
    		printk(KERN_WARNING "Could not switch to high resolution "
    				    "mode on CPU %d\n", cpu);
    		return 0;
    	}
    tick_init_highres函数把tick_device切换到CLOCK_EVT_FEAT_ONESHOT模式,同时把clock_event_device的回调handler设置为hrtimer_interrupt,这样设置以后,tick_device的中断回调将由hrtimer_interrupt接管,hrtimer_interrupt在上面已经讨论过,它将完成高精度定时器的调度和到期处理。

    接着,设置hres_active标志,以表明高精度模式已经切换,然后把3个时间基准系统的resolution字段设为KTIME_HIGH_RES:

    	base->hres_active = 1;
    	for (i = 0; i < HRTIMER_MAX_CLOCK_BASES; i++)
    		base->clock_base[i].resolution = KTIME_HIGH_RES;
    最后,因为tick_device被高精度定时器接管,它将不会再提供原有的tick事件机制,所以需要由高精度定时器系统模拟一个tick事件设备,继续为系统提供tick事件能力,这个工作由tick_setup_sched_timer函数完成。因为刚刚完成切换,tick_device的到期时间并没有被正确地设置为下一个到期定时器的时间,这里使用retrigger_next_event函数,传入参数NULL,使得tick_device立刻产生到期中断,hrtimer_interrupt被调用一次,然后下一个到期的定时器的时间会编程到tick_device中,从而完成了到高精度模式的切换:
    	tick_setup_sched_timer();
    	/* "Retrigger" the interrupt to get things going */
    	retrigger_next_event(NULL);
    	local_irq_restore(flags);
    	return 1;
    }

    整个切换过程可以用下图表示:


                                                                                 图3.1  低精度模式切换至高精度模式

    4.  模拟tick事件

    根据上一节的讨论,当系统切换到高精度模式后,tick_device被高精度定时器系统接管,不再定期地产生tick事件,我们知道,到目前的版本为止(V3.4),内核还没有彻底废除jiffies机制,系统还是依赖定期到来的tick事件,供进程调度系统和时间更新等操作,大量存在的低精度定时器也仍然依赖于jiffies的计数,所以,尽管tick_device被接管,高精度定时器系统还是要想办法继续提供定期的tick事件。为了达到这一目的,内核使用了一个取巧的办法:既然高精度模式已经启用,可以定义一个hrtimer,把它的到期时间设定为一个jiffy的时间,当这个hrtimer到期时,在这个hrtimer的到期回调函数中,进行和原来的tick_device同样的操作,然后把该hrtimer的到期时间顺延一个jiffy周期,如此反复循环,完美地模拟了原有tick_device的功能。下面我们看看具体点代码是如何实现的。

    在kernel/time/tick-sched.c中,内核定义了一个per_cpu全局变量:tick_cpu_sched,从而为每个cpu提供了一个tick_sched结构, 该结构主要用于管理NO_HZ配置下的tickless处理,因为模拟tick事件与tickless有很强的相关性,所以高精度定时器系统也利用了该结构的以下字段,用于完成模拟tick事件的操作:

    struct tick_sched {
    	struct hrtimer			sched_timer;
    	unsigned long			check_clocks;
    	enum tick_nohz_mode		nohz_mode;
            ......
    };
    
    sched_timer就是要用于模拟tick事件的hrtimer,check_clock上面几节已经讨论过,用于notify系统通知hrtimer系统需要检查是否切换到高精度模式,nohz_mode则用于表示当前的工作模式。

    上一节提到,用于切换至高精度模式的函数是hrtimer_switch_to_hres,在它的最后,调用了函数tick_setup_sched_timer,该函数的作用就是设置一个用于模拟tick事件的hrtimer:

    void tick_setup_sched_timer(void)
    {
    	struct tick_sched *ts = &__get_cpu_var(tick_cpu_sched);
    	ktime_t now = ktime_get();
    
    	/*
    	 * Emulate tick processing via per-CPU hrtimers:
    	 */
    	hrtimer_init(&ts->sched_timer, CLOCK_MONOTONIC, HRTIMER_MODE_ABS);
    	ts->sched_timer.function = tick_sched_timer;
    
    	/* Get the next period (per cpu) */
    	hrtimer_set_expires(&ts->sched_timer, tick_init_jiffy_update());
    
    	for (;;) {
    		hrtimer_forward(&ts->sched_timer, now, tick_period);
    		hrtimer_start_expires(&ts->sched_timer,
    				      HRTIMER_MODE_ABS_PINNED);
    		/* Check, if the timer was already in the past */
    		if (hrtimer_active(&ts->sched_timer))
    			break;
    		now = ktime_get();
    	}
    
    #ifdef CONFIG_NO_HZ
    	if (tick_nohz_enabled)
    		ts->nohz_mode = NOHZ_MODE_HIGHRES;
    #endif
    }
    
    该函数首先初始化该cpu所属的tick_sched结构中sched_timer字段,把该hrtimer的回调函数设置为tick_sched_timer,然后把它的到期时间设定为下一个jiffy时刻,返回前把工作模式设置为NOHZ_MODE_HIGHRES,表明是利用高精度模式实现NO_HZ。

    接着我们关注一下hrtimer的回调函数tick_sched_timer,我们知道,系统中的jiffies计数,时间更新等是全局操作,在smp系统中,只有一个cpu负责该工作,所以在tick_sched_timer的一开始,先判断当前cpu是否负责更新jiffies和时间,如果是,则执行更新操作:

    static enum hrtimer_restart tick_sched_timer(struct hrtimer *timer)
    {
            ......
    
    #ifdef CONFIG_NO_HZ
    	if (unlikely(tick_do_timer_cpu == TICK_DO_TIMER_NONE))
    		tick_do_timer_cpu = cpu;
    #endif
    
    	/* Check, if the jiffies need an update */
    	if (tick_do_timer_cpu == cpu)
    		tick_do_update_jiffies64(now);
    
    然后,利用regs指针确保当前是在中断上下文中,然后调用update_process_timer:

    	if (regs) {
                    ......
    		update_process_times(user_mode(regs));
    		......
    	}
    最后,把hrtimer的到期时间推进一个tick周期,返回HRTIMER_RESTART表明该hrtimer需要再次启动,以便产生下一个tick事件。

    	hrtimer_forward(timer, now, tick_period);
    
    	return HRTIMER_RESTART;
    }
    关于update_process_times,如果你你感兴趣,回看一下本系列关于clock_event_device的那一章:Linux时间子系统之四:定时器的引擎:clock_event_device中的第5小节,对比一下模拟tick事件的hrtimer的回调函数tick_sched_timer和切换前tick_device的回调函数tick_handle_periodic,它们是如此地相像,实际上,它们几乎完成了一样的工作。
    展开全文
  • 上一篇文章,我介绍了传统的低分辨率定时器的实现原理。而随着内核的不断演进,大牛们已经对这种低分辨率定时器的精度不再满足,而且,硬件也在不断地发展,系统中的定时器硬件的精度也越来越高,这也给高分辨率...
  • linux内核定时器使用及原理

    万次阅读 2011-05-09 11:40:00
    内核定时器使用   <br />内核定时器是内核用来控制在未来某个时间点(基于jiffies)调度执行某个函数的一种机制,其实现位于 <linux/timer.h> 和 kernel/timer.c 文件中。 被调度的函数...
  • linux 定时器简单使用例程

    千次阅读 2019-05-31 14:27:21
    我们常常有设置系统在某一时间执行相应动作的需求,比如设置电脑什么时候自动锁屏,什么时候自动关机,设置应用程序... linux定时器的使用原理很简单,你只需设置一个超时时间和相应的执行函数,系统就会在超时...
  • Linux内核定时器原理

    2013-04-12 14:21:18
    转自:... 一、定义: /include/linux/timer.h struct timer_list { struct list_head entry; unsigned long expires; void (*function)(unsign
  • Linux内核定时器 一、定义: /include/linux/timer.h struct timer_list { struct list_head entry; unsigned long expires; void (*function)(unsigned long); unsigned long data; struct tvec_t_base_s...
  • Linux时间子系统之七:定时器的应用--...我们已经在前面几章介绍了低分辨率定时器和高精度定时器的实现原理,内核为了方便其它子系统,在时间子系统中提供了一些用于延时或调度的API,例如msleep,hrtimer_nan...
  • linux定时器串行执行原因 背景: 按键多次抖动激活的未运行定时器会覆盖 当按键中断触发时激活定时器,此时定时器正在运行且持有锁,若原先的定时器不能运行,则会造成死锁。 问题1: 定时器运行中被中断抢占...
  • 深入剖析Linux内核定时器实现机制

    千次阅读 2013-03-22 16:55:21
    【摘要】本文详解了Linux内核的定时器实现机制。具体分析了定时器的分级组织结构,以及在此基础之上的插入、更新、扫描执行等过程。其动态刷新维护的机制值得借鉴。然后介绍了内核定时器相关的API。 【关键字】内核...
  • Linux下一种高效多定时器实现

    万次阅读 2018-08-29 12:15:59
    Linux下一种高效多定时器实现 作者:LouisozZ 日期:2018.08.29 运行环境说明 由于在 Linux 系统下一个进程只能设置一个时钟定时器,所以当应用需要有...多定时器原理 在一个进程只能有一个定时器的前提条件下...
  • Linux内核时钟系统和定时器实现

    万次阅读 2016-10-19 11:20:32
    1. Linux内核时钟系统和定时器实现Linux 2.6.16之前,内核只支持低精度时钟,内核定时器工作方式: 系统启动后,会读取时钟源设备(RTC, HPET,PIT…),初始化当前系统时间; 内核会根据HZ(系统定时器频率,节拍率)...
  • linux下的C语言开发(定时器

    万次阅读 多人点赞 2012-01-17 20:37:00
    linux下面的定时器又是怎么一回事呢?其实,在linux里面有一种进程中信息传递的方法,那就是信号。这里的定时器就相当于系统每隔一段时间给进程发一个定时信号,我们所要做的就是定义一个信号处理函数。 #...
  • Linux高精度定时器

    千次阅读 2018-10-21 00:34:09
    Linux时间子系统之六:高精度定时器(HRTIMER)的原理和实现 https://blog.csdn.net/droidphone/article/details/8074892 上一篇文章,我介绍了传统的低分辨率定时器的实现原理。而随着内核的不断演进,大牛们已经...
  • Linux内核定时器

    千次阅读 2019-05-23 20:21:48
    时间系统的工作需要软硬件以及操作系统的互相协作,在上一部分,我们已经看到大多数时间函数都依赖内核系统调用,GlibC 仅仅做了一次请求的转发。因此必须深入内核代码以便了解更多的细节。 内核自身的正常运行也...
  • 版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声...
  • Linux定时器的实现

    千次阅读 2017-03-02 23:14:32
    方法1. 使用sleep或者usleep这种方法很简单,这里就不具体描述,它的缺点也很明确:精度不够,特别是在系统负载比较大时,会发生超时现象。方法2. 使用信号量SIGALRM + alarm()alarm也称为闹钟函数,alarm()用来设置...
  • LInux下几种定时器的比较和使用

    千次阅读 2019-01-17 13:55:53
    所以要在应用中根据实际要求选择不同的定时器,就要考虑到几种应用定时器的特点。 定时器文章参考  一般而言有, 1、sleep,usleep和nanosleep sleep()和nanosleep()都是使进程睡眠一段时间后被唤醒,但是二者...
1 2 3 4 5 ... 20
收藏数 13,378
精华内容 5,351
关键字:

linux 定时器的工作原理