最近工作上遇到了一些和定时调度相关的问题。在 Google，类似这样的问题，往往已经有人帮我们造好轮子了。但是，作为正经程序员，我们还是会忍不住思考，如果我们自己做，会怎么做呢？已有的实现，又有什么特殊之处。今天这篇文章，我们来一起看一看 Linux 怎么解决这个问题的。

首先，我们先来试试分解这个问题。

  1. 数据结构: 我们需要设计一个数据结构来维护所有的任务，它需要支持快速的插入操作，和获取到期任务的操作。
  2. 任务执行：我们需要一个高效的手段，在到了指定的时间之后，执行已经到期的任务。

接下来，会尝试从这两个方面来分析 Linux 的实现。Linux 提供了多种执行定时任务的方式，我们这里主要来分析一下 timer_list。

数据结构

在 Linux 代码中，每一个定时任务都对应到一个 timer_list。下面是这个数据结构的定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct timer_list {
    // 侵入式的双向链表，Linux 代码中很常见
	struct list_head entry;

    // 什么时候到期，单位是 tick。
    // tick 可以理解成 CPU 的时钟周期。到底多久不影响理解。
	unsigned long expires;

	spinlock_t lock;
	unsigned long magic;

    // 到期之后要执行的函数
	void (*function)(unsigned long);
    // 函数的参数
	unsigned long data;

	struct tvec_t_base_s *base;
};

相信这个数据结构的定义，大家并不会觉得有什么惊讶的部分（除了这个名字…）。我们接下来看 Linux 怎么组织这些定时任务。

Linux 使用了 tvec_t_base_s 来维护（每个 CPU 对应的）所有的定时任务。它的定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
struct tvec_t_base_s {
	spinlock_t lock;

    // 目前已经处理到的时间点
    // 这个时间点之前应该到期的所有任务都已经处理完了。
	unsigned long timer_jiffies;

    // 当前正在执行的任务
	struct timer_list *running_timer;

    // 下面的几个字段是这个数据结构的核心。
    // 每个字段可以理解成一个使用链表来解决冲突的哈希表。
    // 哈希表的 key 是定时任务的 expires - current_time 的值。
    // 哈希表的 value 是定时任务本身。
    // 每个字段的 hash 函数不同。

    // 只包含 [0, 256) 个 tick 之后过期的任务
    // hash function: id -> id.
	tvec_root_t tv1;

    // 只包含 [256, 64 * 256) 个 tick 之后过期的任务
    // hash function: id -> id / 256
	tvec_t tv2;

    // 只包含 [64 * 256, 64 ^ 2 * 256) 个 tick 之后过期的任务
    // hash function: id -> id / 256 / 64
	tvec_t tv3;

    // 只包含 [64 ^2 * 256, 64 ^ 3 * 256) 个 tick 之后过期的任务
    // hash function: id -> id / 256 / 64 ^ 2
	tvec_t tv4;

    // 包含更未来的任务
	tvec_t tv5;
}

这个数据结构，某种程度上来看，和时间轮非常接近。随着时间的前进，当 tv1 中的任务完全处理完的时候，tv2 中的最小 slot 中的所有任务（tick 跨度是 256）会填补到 tv1 中。tv2 中的任务完成了之后，也会从 tv3 中获取任务，以此类推下去。这样的数据结构，可以支持快速的插入和查找的操作。

任务执行

Linux 执行定时任务的策略，某种程度上有点像 cron job。对于每个时钟中断（每个 tick），Linux 定义的中断处理函数都会更新当前时间，同时会触发一个软中断（TIMER_SOFTIRQ）。这个软中断的处理函数会查看 tvec_t_base_s.timer_jiffies 和当前时间的差距，然后处理所有到期的任务。之所以要使用软中断，是因为我们要保证每个硬件中断（这里的时钟中断）的处理函数执行的时间足够短，否则会阻塞其他的中断处理，降低系统的吞吐量。具体的代码的调用路径见下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 时钟中断处理函数
timer_interrupt() {
    do_timer_interrupt() {
        do_timer_interrupt_hook() {
            update_process_times() {
                run_local_timers() {
                    // 触发软中断
                    raise_softirq(TIMER_SOFTIRQ);
                }
            }
        }
    }
}

// 软中断处理函数
run_timer_softirq() {
    // 核心逻辑
    __run_timers();
}