[toc]

kernel/sched/deadline.c 截止时间调度器(Deadline Scheduler, SCHED_DEADLINE) 面向硬实时的可预测调度

历史与背景

这项技术是为了解决什么特定问题而诞生的？

kernel/sched/deadline.c 实现了SCHED_DEADLINE调度策略，它的诞生是为了解决传统实时调度器（SCHED_FIFO/RR）在硬实时（Hard Real-time）和复杂系统中所面临的局限性。

SCHED_FIFO/RR基于静态优先级，虽然模型简单，但在复杂系统中存在两个主要问题：

  1. 缺乏可分析性（Analyzability）：在一个包含几十个实时任务的系统中，仅仅依靠手动分配静态优先级来保证所有任务都能满足各自的截止时间，是一项极其困难且易错的工作。当任务间存在复杂的依赖关系时，几乎无法从理论上证明系统的可调度性。
  2. 任务间无隔离：SCHED_FIFO是“赢家通吃”模型。一个有bug或行为不当的高优先级任务可以无限期地运行，完全饿死所有低优先级任务，导致系统服务完全中断。它不提供任何形式的“带宽”或“资源”保证。

SCHED_DEADLINE通过引入一种基于**截止时间（Deadline）**的、更现代的实时调度理论——**最早截止时间优先（Earliest Deadline First, EDF）算法，并结合恒定带宽服务器（Constant Bandwidth Server, CBS）**算法，来解决这些问题。

其核心目标是：

  • 提供可形式化分析的调度模型：开发者只需为每个任务指定三个参数（runtime, period, deadline），系统就可以通过一个简单的“接纳控制（Admission Control）”测试来判断这组任务是否是可调度的，即是否所有任务都能满足其截止时间。
  • 提供任务间的隔离：每个SCHED_DEADLINE任务都像拥有一个自己的“虚拟CPU”，其算力由runtime/period决定。一个任务即使进入死循环，也只能耗尽自己的runtime预算，而不会影响到其他任务。

它的发展经历了哪些重要的里程碑或版本迭代？

SCHED_DEADLINE是Linux实时能力演进的一个重要里程碑。

  • 学术研究与原型：EDF和CBS算法在实时系统学术界已经有很长的研究历史。
  • 引入内核 (Kernel 3.14)：由意大利比萨圣安娜高等学校（SSSUP）的实时系统实验室（ReTiS Lab）主导，经过多年的开发和RFC（请求意见稿）过程，SCHED_DEADLINE在Linux 3.14版本中被正式合并。
  • 集成到调度类框架：它被实现为一个新的调度类（dl_sched_class），优先级介于StopTask和Real-Time类之间，是内核中优先级最高的、可供用户空间使用的调度策略。
  • 持续的增强：后续版本对其进行了多方面的增强，包括对多核系统的支持（如分片EDF - GRUB算法）、接纳控制的改进，以及与cgroups的集成，以支持对一组任务进行截止时间调度。

目前该技术的社区活跃度和主流应用情况如何？

SCHED_DEADLINE是Linux在硬实时领域的一项前沿技术，社区活跃度高，尤其是在学术界和对实时性有极高要求的工业界。

  • 主流应用：虽然它不如CFS或传统RT那样“普遍”，但其应用场景非常关键：
    • 实时虚拟化：在KVM等虚拟化环境中，可以为一个虚拟机（或其关键vCPU线程）设置SCHED_DEADLINE策略，为其提供可保证的、隔离的CPU时间，以在虚拟机内部运行实时操作系统或应用。
    • 复杂的工业自动化与机器人：在存在大量周期性、有严格时间要求的控制任务的场景。
    • 多媒体流处理：在需要对多个视频或音频流进行同步和处理，且每个流都有不同处理要求的场景。
    • 资源预留：可以精确地为某个关键服务预留一定比例的CPU算力。

核心原理与设计

它的核心工作原理是什么？

SCHED_DEADLINE的核心是基于EDF和CBS算法。

  1. 任务模型（The Three Parameters）：

    • Runtime (Worst-case execution time)：任务在每个周期内，最多需要运行的CPU时间。
    • Period：任务被周期性激活的时间间隔。
    • Deadline：相对于任务的激活时间点，runtime必须在此之前完成。通常情况下，deadline等于period。

  2. 调度策略：最早截止时间优先 (EDF)：

    • 这是一个非常简单的抢占式策略：在任何时刻，调度器总是选择绝对截止时间（absolute deadline）最早的那个可运行任务来执行。
    • 一个任务的绝对截止时间 = 它的激活时间 + 它的相对deadline参数。

  3. 数据结构：红黑树：

    • 与CFS类似，每个CPU的截止时间运行队列（struct dl_rq）也使用一棵红黑树。
    • 但这棵树是以任务的绝对截止时间为键值排序的。
    • 因此，选择下一个要运行的任务，就是简单地选取红黑树最左边的节点，这个操作的复杂度是O(1)（因为指针已经被缓存）。

  4. 资源隔离：恒定带宽服务器 (CBS)：

    • CBS算法确保每个任务都不会超出其声明的runtime。
    • 当一个任务被激活时，它会被赋予runtime的“CPU预算”。
    • 当它运行时，预算会消耗；当它阻塞时，预算保持不变。
    • 如果一个任务耗尽了它的runtime预算，但它的周期（period）还没结束，它就会被**“节流”（throttled）**，即被暂时挂起，不允许再运行。
    • 直到它的下一个周期开始时，它的runtime预算和绝对截止时间才会被重新设置，然后它才能再次变为可运行状态。
    • 这个机制有效地将任务的行为约束在其声明的参数内，实现了强大的隔离。

它的主要优势体现在哪些方面？

  • 可分析性（Schedulability Analysis）：这是其最大优势。对于一组独立的周期性任务，只要所有任务的 runtime_i / period_i 的总和（即总CPU利用率）小于等于CPU核心数，系统就是可调度的。这为系统设计者提供了强大的理论工具。
  • 任务间隔离：CBS机制提供了“防火墙”，防止一个任务的行为影响到其他任务的时间保证。
  • 更高的CPU利用率：理论上，EDF可以达到100%的CPU利用率，而基于静态优先级的调度算法（如RM - 速率单调）则有更低的理论上限。

它存在哪些已知的劣势、局限性或在特定场景下的不适用性？

  • 瞬时过载处理能力差：在EDF中，如果系统发生瞬时过载（例如，一个事件风暴导致多个任务同时需要运行），最先错过截止时间的往往是截止时间最长的任务，这可能是反直觉的。而在静态优先级系统中，牺牲的总是优先级最低的任务。
  • 配置复杂：开发者必须准确地知道或估算出任务的runtime、period和deadline，这通常需要深入的系统分析和测量。
  • 不适合非周期性任务：虽然可以适配非周期性任务（通过所谓的“sporadic servers”），但其模型天生就是为周期性任务设计的。

使用场景

在哪些具体的业务或技术场景下，它是首选解决方案？

当系统需要可验证的、可组合的硬实时保证时，SCHED_DEADLINE是首选解决方案。

  • 实时虚拟化：为一个vCPU线程设置runtime=5ms, period=10ms，相当于为这个虚拟机提供了一个独占的、有50%算力保证的CPU，并且不受宿主机上其他任务的干扰。
  • 复杂的多媒体系统：一个视频解码器需要每40ms处理一帧，最多花费10ms；一个音频处理器需要每5ms处理一个缓冲区，最多花费1ms。使用SCHED_DEADLINE可以清晰地描述这些需求并验证系统是否能满足它们。

是否有不推荐使用该技术的场景？为什么？

  • 通用计算：完全不适用。它的目标是满足截止时间，而不是公平或响应性。
  • 简单的实时系统：如果系统只有一个或两个关键的实时任务，使用SCHED_FIFO并手动为它们分配合适的静态优先级，通常更简单、更直观。

对比分析

请将其 与 其他相似技术 进行详细对比。

特性 SCHED_DEADLINE (EDF+CBS) SCHED_FIFO/RR (静态优先级) CFS (SCHED_NORMAL)
核心调度目标 保证截止时间 可预测性 公平性
决策依据 任务的绝对截止时间 任务的静态优先级 任务的虚拟运行时间
任务间隔离 强 (通过CBS节流) 弱 (高优先级可饿死低优先级) 强 (通过vruntime保证公平份额)
可分析性 强 (基于CPU利用率的接纳控制) 弱 (依赖于复杂的速率单调分析或手动验证) 不适用 (非实时)
配置复杂度 高 (需要runtime, period, deadline三元组) 中 (需要分配0-99的优先级) 低 (nice值用于微调)
过载行为 不可预测，可能导致“多米诺骨牌”式的截止时间错过。 可预测，总是牺牲优先级最低的任务。 优雅地降低所有任务的性能。
适用场景 需要可验证的硬实时保证的复杂系统。 传统的、基于优先级的软实时或简单硬实时系统。 所有通用计算负载。

include/linux/sched/deadline.h

dl_prio 检查截止任务优先级

1
2
3
4
static inline bool dl_prio(int prio)
{
	return unlikely(prio < MAX_DL_PRIO);
}

kernel/sched/deadline.c

init_dl_rq 初始化截止运行队列

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
36
37
38
39
40
41
42
43
44
static void init_dl_rq_bw_ratio(struct dl_rq *dl_rq)
{
	if (global_rt_runtime() == RUNTIME_INF) {
		//带宽比例为最大值,最大带宽和额外带宽也为最大值
		dl_rq->bw_ratio = 1 << RATIO_SHIFT;
		dl_rq->max_bw = dl_rq->extra_bw = 1 << BW_SHIFT;
	} else {
		dl_rq->bw_ratio = to_ratio(global_rt_runtime(),
			  global_rt_period()) >> (BW_SHIFT - RATIO_SHIFT);
		dl_rq->max_bw = dl_rq->extra_bw =
			to_ratio(global_rt_period(), global_rt_runtime());
	}
}

void init_dl_bw(struct dl_bw *dl_b)
{
	raw_spin_lock_init(&dl_b->lock);
	//根据全局实时运行时（global_rt_runtime）的值来计算带宽（bw）
	if (global_rt_runtime() == RUNTIME_INF)	//实时运行时是无限的（即没有限制），此时将 dl_b->bw 设置为 -1，用作特殊标记
		dl_b->bw = -1;
	else
		//将实时周期（global_rt_period）和运行时（global_rt_runtime）的比值转换为带宽值
		dl_b->bw = to_ratio(global_rt_period(), global_rt_runtime());
	dl_b->total_bw = 0;
}

void init_dl_rq(struct dl_rq *dl_rq)
{
	dl_rq->root = RB_ROOT_CACHED;

#ifdef CONFIG_SMP
	/* zero means no -deadline tasks */
	dl_rq->earliest_dl.curr = dl_rq->earliest_dl.next = 0;

	dl_rq->overloaded = 0;
	dl_rq->pushable_dl_tasks_root = RB_ROOT_CACHED;
#else
	init_dl_bw(&dl_rq->dl_bw);
#endif

	dl_rq->running_bw = 0;
	dl_rq->this_bw = 0;
	init_dl_rq_bw_ratio(dl_rq);
}

init_dl_entity 初始化截止任务实体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
static void init_dl_task_timer(struct sched_dl_entity *dl_se)
{
	struct hrtimer *timer = &dl_se->dl_timer;

	hrtimer_setup(timer, dl_task_timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL_HARD);
}

static void init_dl_inactive_task_timer(struct sched_dl_entity *dl_se)
{
	struct hrtimer *timer = &dl_se->inactive_timer;

	hrtimer_setup(timer, inactive_task_timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL_HARD);
}

void init_dl_entity(struct sched_dl_entity *dl_se)
{
	RB_CLEAR_NODE(&dl_se->rb_node);
	init_dl_task_timer(dl_se);
	init_dl_inactive_task_timer(dl_se);
	__dl_clear_params(dl_se);
}

dl_server_init 初始化截止服务器

1
2
3
4
5
6
7
8
void dl_server_init(struct sched_dl_entity *dl_se, struct rq *rq,
		    dl_server_has_tasks_f has_tasks,
		    dl_server_pick_f pick_task)
{
	dl_se->rq = rq;
	dl_se->server_has_tasks = has_tasks;
	dl_se->server_pick_task = pick_task;
}

DEFINE_SCHED_CLASS(dl) 定义截止调度类

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
DEFINE_SCHED_CLASS(dl) = {

	.enqueue_task		= enqueue_task_dl,
	.dequeue_task		= dequeue_task_dl,
	.yield_task		= yield_task_dl,

	.wakeup_preempt		= wakeup_preempt_dl,

	.pick_task		= pick_task_dl,
	.put_prev_task		= put_prev_task_dl,
	.set_next_task		= set_next_task_dl,

#ifdef CONFIG_SMP
	.balance		= balance_dl,
	.select_task_rq		= select_task_rq_dl,
	.migrate_task_rq	= migrate_task_rq_dl,
	.set_cpus_allowed       = set_cpus_allowed_dl,
	.rq_online              = rq_online_dl,
	.rq_offline             = rq_offline_dl,
	.task_woken		= task_woken_dl,
	.find_lock_rq		= find_lock_later_rq,
#endif

	.task_tick		= task_tick_dl,
	.task_fork              = task_fork_dl,

	.prio_changed           = prio_changed_dl,
	.switched_from		= switched_from_dl,
	.switched_to		= switched_to_dl,

	.update_curr		= update_curr_dl,
#ifdef CONFIG_SCHED_CORE
	.task_is_throttled	= task_is_throttled_dl,
#endif
};

enqueue_task_dl

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
static void enqueue_task_dl(struct rq *rq, struct task_struct *p, int flags)
{
	if (is_dl_boosted(&p->dl)) {
		/*
		 * Because of delays in the detection of the overrun of a
		 * thread's runtime, it might be the case that a thread
		 * goes to sleep in a rt mutex with negative runtime. As
		 * a consequence, the thread will be throttled.
		 *
		 * While waiting for the mutex, this thread can also be
		 * boosted via PI, resulting in a thread that is throttled
		 * and boosted at the same time.
		 *
		 * In this case, the boost overrides the throttle.
		 */
		if (p->dl.dl_throttled) {
			/*
			 * The replenish timer needs to be canceled. No
			 * problem if it fires concurrently: boosted threads
			 * are ignored in dl_task_timer().
			 */
			cancel_replenish_timer(&p->dl);
			p->dl.dl_throttled = 0;
		}
	} else if (!dl_prio(p->normal_prio)) {
		/*
		 * Special case in which we have a !SCHED_DEADLINE task that is going
		 * to be deboosted, but exceeds its runtime while doing so. No point in
		 * replenishing it, as it's going to return back to its original
		 * scheduling class after this. If it has been throttled, we need to
		 * clear the flag, otherwise the task may wake up as throttled after
		 * being boosted again with no means to replenish the runtime and clear
		 * the throttle.
		 */
		p->dl.dl_throttled = 0;
		if (!(flags & ENQUEUE_REPLENISH))
			printk_deferred_once("sched: DL de-boosted task PID %d: REPLENISH flag missing\n",
					     task_pid_nr(p));

		return;
	}

	check_schedstat_required();
	update_stats_wait_start_dl(dl_rq_of_se(&p->dl), &p->dl);

	if (p->on_rq == TASK_ON_RQ_MIGRATING)
		flags |= ENQUEUE_MIGRATING;

	enqueue_dl_entity(&p->dl, flags);

	if (dl_server(&p->dl))
		return;

	if (!task_current(rq, p) && !p->dl.dl_throttled && p->nr_cpus_allowed > 1)
		enqueue_pushable_dl_task(rq, p);
}