Linux内核低精度定时器原理图解

基本概念

低精度定时器（也称为时间轮定时器）是Linux内核中用于管理相对时间较短的定时请求的机制，精度通常在毫秒级别。

核心数据结构

struct timer_list {
    struct list_head entry;
    unsigned long expires;
    void (*function)(unsigned long);
    unsigned long data;
    struct tvec_base *base;
    // ...
};

五级时间轮结构

(示意图)

1. TVR (Timer Vector Root)

   • 包含256个桶（0-255）
   • 每个桶表示一个jiffies（通常1 jiffy=1ms或4ms或10ms）
   • 覆盖范围：0-255 jiffies

2. TV1-TV4 (Timer Vector 1-4)

   • 每个包含64个桶
   • TV1: 256-16383 jiffies
   • TV2: 16384-1048575 jiffies
   • TV3: 1048576-67108863 jiffies
   • TV4: 67108864-4294967295 jiffies

工作原理

1. 添加定时器

   void add_timer(struct timer_list *timer);
   

   • 计算到期时间与当前jiffies的差值
   • 根据差值大小放入相应层级的桶中

2. 定时器到期处理

   • 每次时钟中断调用run_timer_softirq()
   • 从TVR开始检查到期定时器
   • 执行到期定时器的回调函数

3. 级联迁移

   • 当TVR处理完后，会从TV1迁移定时器到TVR
   • 类似地，高层级定时器会级联迁移到低层级

性能特点

1. O(1)时间复杂度

   • 添加、删除和到期处理都是O(1)操作

2. 适合短时定时器

   • 大多数定时器在TVR中处理
   • 长时定时器会逐渐迁移到高层级

3. 低内存开销

   • 固定大小的数组结构
   • 无动态内存分配

示例代码

#include <linux/module.h>
#include <linux/timer.h>

static struct timer_list my_timer;

void my_timer_callback(unsigned long data) {
    printk("Timer callback executed\n");
    /* 重新激活定时器 */
    mod_timer(&my_timer, jiffies + msecs_to_jiffies(2000));
}

static int __init my_init(void) {
    setup_timer(&my_timer, my_timer_callback, 0);
    mod_timer(&my_timer, jiffies + msecs_to_jiffies(2000));
    return 0;
}

static void __exit my_exit(void) {
    del_timer(&my_timer);
}

module_init(my_init);
module_exit(my_exit);

与高精度定时器对比

总结

低精度定时器通过巧妙的多级时间轮设计，在保持O(1)时间复杂度的同时，能够高效处理大量短时定时器请求，是Linux内核定时子系统的核心组件之一。