[toc]

kernel/sched/rt.c 实时调度(Real-Time Scheduling) 保证关键任务的优先执行

历史与背景

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

kernel/sched/rt.c 是Linux内核实时调度器的核心实现。它的诞生不是为了“公平”或“高吞吐量”，而是为了解决一个截然不同的、至关重要的问题：可预测的时间行为（Predictable Temporal Behavior）。

在通用计算中（由CFS调度器处理），一个任务晚几毫秒完成通常无伤大雅。但在很多领域，任务的正确性不仅取决于计算结果，更取决于结果产生的时间。如果一个任务错过了它的截止时间（deadline），即使结果正确，也可能造成灾难性后果。这些场景包括：

  1. 工业控制：机器人手臂的控制指令必须在几毫秒内发出，否则可能导致生产事故。
  2. 电信基础设施：处理5G网络数据包的设备，必须在严格的时间窗内完成，以保证通信质量。
  3. 专业音视频处理：音频处理线程必须周期性地、准时地向声卡提供数据，否则就会出现爆音（xrun）。
  4. 金融交易：高频交易算法的执行延迟直接关系到经济效益。

kernel/sched/rt.c 实现了SCHED_FIFO和SCHED_RR这两种基于静态优先级的实时调度策略，其唯一目标就是：确保在任何时刻，CPU总是被分配给系统中优先级最高的可运行实时任务。

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

实时调度器是Linux内核长期存在的核心功能，其演进主要体现在健壮性和功能的完善上。

  • POSIX标准兼容：其核心API（SCHED_FIFO - 先入先出, SCHED_RR - 轮转）源自POSIX标准，这使得Linux从早期就能很好地支持需要实时特性的应用程序。
  • 集成到调度类框架：在现代内核中，实时调度器被实现为一个调度类（rt_sched_class），其优先级高于CFS（fair_sched_class）。这使得调度决策逻辑非常清晰：内核总是先检查是否有实时任务需要运行，如果没有，才轮到普通任务。
  • 实时抢占（PREEMPT_RT）：这是一个与rt.c相辅相成的、极其重要的发展。rt.c本身只定义了“谁应该运行”的策略，但如果内核本身在关键路径上（如持有自旋锁时）不可抢占，那么高优先级任务仍然可能被延迟。PREEMPT_RT补丁集（现在大部分已合入主线）通过将自旋锁替换为可睡眠的互斥锁等技术，极大地降低了内核内部的调度延迟，是实现硬实时Linux的基石。
  • 实时节流（RT Throttling）：为了防止有bug或恶意的实时任务（例如一个无限循环的SCHED_FIFO进程）完全“霸占”CPU，导致系统死锁（连管理员shell都无法运行），内核引入了实时带宽控制机制。它允许管理员限制实时任务在某个时间周期内可以使用的CPU时间总量。

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

实时调度器是内核中一个高度成熟和稳定的部分，并且是所有需要确定性行为的Linux系统的核心。

  • 主流应用：
    • 嵌入式与工业自动化：这是SCHED_FIFO/RR应用最广泛的领域。
    • 电信与网络设备：路由器、交换机、基站等。
    • 高性能计算（HPC）：用于管理MPI等并行计算中的消息传递线程，以降低通信延迟。
    • 桌面专业应用：专业音频工作站（如JACK Audio Connection Kit）会将其关键音频线程设置为SCHED_FIFO，以实现超低延迟的音频录制和处理。

核心原理与设计

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

kernel/sched/rt.c 的核心是一个简单、高效、基于静态优先级的调度模型。

  1. 优先级驱动：它管理着0-99范围内的实时优先级（数值越大，优先级越高）。这个优先级是静态赋予的，在任务运行时不会像CFS的vruntime那样动态变化。
  2. 数据结构：优先级数组：每个CPU的实时运行队列（struct rt_rq）内部有一个核心数据结构 struct rt_prio_array。它包含：
    • 一个拥有100个链表头的数组（queue），每个链表对应一个实时优先级。
    • 一个位图（bitmap），用于快速查找哪个优先级的链表上挂有可运行的任务。
  3. O(1) 任务选择：当调度器需要从实时队列中选择下一个任务时：
    • 它首先使用 sched_find_first_bit() 在位图上查找，这个操作的时间复杂度是常数O(1)。
    • 一旦找到最高优先级的非空链表，它就从该链表的头部取出第一个任务作为下一个要运行的任务。
  4. 两种策略的区别：
    • SCHED_FIFO (First-In, First-Out)：一个SCHED_FIFO任务会一直运行，直到它自愿阻塞（如等待I/O）、调用sched_yield()、或者被一个更高优先级的实时任务抢占。同优先级的SCHED_FIFO任务之间不会相互抢占。
    • SCHED_RR (Round-Robin)：SCHED_RR是带有时间片的SCHED_FIFO。它同样会一直运行直到阻塞、屈服或被更高优先级任务抢占。但如果它的时间片用完了，而此时同一优先级还有其他可运行的任务，它就会被放到该优先级链表的末尾，然后链表头部的下一个任务开始运行。这实现了在同优先级任务之间的“公平”轮转。
  5. 抢占（Preemption）：只要一个高优先级的实时任务被唤醒，它会立即抢占当前正在运行的任何低优先级实时任务或任何CFS任务。

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

  • 可预测性（Predictability）：行为简单、确定。只要你知道系统中所有实时任务的优先级，你就能准确预测出在任何时刻哪个任务会获得CPU。
  • 低延迟：高优先级任务的抢占是即时的，能保证其尽快得到响应。
  • O(1) 调度：选择下一个要运行的实时任务的开销极小，且与实时任务的总数无关。

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

  • 不公平：这是其设计的必然结果。一个高优先级的、CPU密集型的实时任务可以**永久地饿死（starve）**所有比它优先级低的任务（包括所有普通的用户进程和大部分内核线程），从而导致系统对用户完全失去响应。
  • 优先级反转（Priority Inversion）：这是一个经典的实时系统问题。如果一个高优先级任务需要等待一个被低优先级任务持有的锁，那么这个高优先级任务实际上就被降级到了那个低优先级任务的水平。Linux通过优先级继承互斥锁（Priority Inheritance Mutexes）来解决这个问题。
  • 配置复杂性：正确地为系统中的所有实时任务分配优先级是一个复杂的系统设计问题，分配不当很容易导致问题。

使用场景

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

当任务的时间约束比资源公平性更重要时，实时调度器是首选解决方案。

  • 硬实时控制循环：一个控制机器人马达的线程，必须每5毫秒运行一次，它会被设置为SCHED_FIFO并赋予高优先级。
  • 数据采集：一个从高速ADC（模数转换器）读取数据的线程，必须在硬件缓冲区溢出前取走数据，它也会被设置为SCHED_FIFO。
  • 低延迟网络包处理：在电信或金融领域，处理特定网络流的线程可能会被提升为实时优先级，以最小化处理延迟。

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

  • 通用桌面和服务器负载：绝对不应该将Web浏览器、数据库、编译器等普通应用设置为实时优先级。这会破坏CFS的公平性，导致整个系统响应迟钝甚至卡死。实时调度器是一个需要被小心使用的“专家级”工具。

对比分析

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

特性 SCHED_FIFO/RR (rt.c) SCHED_NORMAL (CFS) SCHED_DEADLINE
核心调度目标 可预测性，基于静态优先级。 公平性，基于虚拟运行时间。 保证截止时间，基于任务的(runtime, period, deadline)。
决策依据 静态优先级。数字越大越优先。 虚拟运行时间(vruntime)。vruntime越小越优先。 任务的截止时间。截止时间最早的任务最优先。
任务选择复杂度 O(1) O(log N) (N为可运行任务数) O(1) (基于红黑树的最左节点)
公平性 不保证。高优先级会饿死低优先级。 极好。是其核心设计目标。 不以公平为目标，但通过带宽限制实现了任务间的隔离。
配置复杂度 简单。只需要为任务选择一个0-99的优先级。 简单。通过nice值(-20到+19)进行微调。 复杂。需要精确定义任务的运行时间、周期和截止时间。
适用场景 传统实时应用 (工业控制, 音频)。 通用桌面、服务器应用。 需要可验证的硬实时保证的复杂系统 (如虚拟化实时)。

include/linux/sched/rt.h

rt_prio 检查实时任务优先级

1
2
3
4
static inline bool rt_prio(int prio)
{
	return unlikely(prio < MAX_RT_PRIO && prio >= MAX_DL_PRIO);
}

rt_mutex_get_top_task 获取实时互斥锁的顶层任务

1
2
3
4
5
6
7
/*
 * Must hold either p->pi_lock or task_rq(p)->lock.
 */
static inline struct task_struct *rt_mutex_get_top_task(struct task_struct *p)
{
	return p->pi_top_task;
}

kernel/sched/rt.c

init_rt_rq 初始化实时运行队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void init_rt_rq(struct rt_rq *rt_rq)
{
	struct rt_prio_array *array;
	int i;

	array = &rt_rq->active;
	for (i = 0; i < MAX_RT_PRIO; i++) {
		INIT_LIST_HEAD(array->queue + i);
		__clear_bit(i, array->bitmap);
	}
	/* bitsearch 的分隔符： */
	__set_bit(MAX_RT_PRIO, array->bitmap);

	/* 我们启动 dequeued 状态，因为没有 RT 任务排队 */
	rt_rq->rt_queued = 0;
}

DEFINE_SCHED_CLASS(rt) 定义实时调度类

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

	.enqueue_task		= enqueue_task_rt,
	.dequeue_task		= dequeue_task_rt,
	.yield_task		= yield_task_rt,

	.wakeup_preempt		= wakeup_preempt_rt,

	.pick_task		= pick_task_rt,
	.put_prev_task		= put_prev_task_rt,
	.set_next_task          = set_next_task_rt,

#ifdef CONFIG_SMP
	.balance		= balance_rt,
	.select_task_rq		= select_task_rq_rt,
	.set_cpus_allowed       = set_cpus_allowed_common,
	.rq_online              = rq_online_rt,
	.rq_offline             = rq_offline_rt,
	.task_woken		= task_woken_rt,
	.switched_from		= switched_from_rt,
	.find_lock_rq		= find_lock_lowest_rq,
#endif

	.task_tick		= task_tick_rt,

	.get_rr_interval	= get_rr_interval_rt,

	.prio_changed		= prio_changed_rt,
	.switched_to		= switched_to_rt,

	.update_curr		= update_curr_rt,

#ifdef CONFIG_SCHED_CORE
	.task_is_throttled	= task_is_throttled_rt,
#endif

#ifdef CONFIG_UCLAMP_TASK
	.uclamp_enabled		= 1,
#endif
};

__dequeue_rt_entity 从实时调度队列中移除任务实体

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
static inline
void dec_rt_tasks(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
{
	WARN_ON(!rt_prio(rt_se_prio(rt_se)));
	WARN_ON(!rt_rq->rt_nr_running);
	rt_rq->rt_nr_running -= rt_se_nr_running(rt_se);
	rt_rq->rr_nr_running -= rt_se_rr_nr_running(rt_se);

	dec_rt_prio(rt_rq, rt_se_prio(rt_se));
	dec_rt_group(rt_se, rt_rq);
}

static void __delist_rt_entity(struct sched_rt_entity *rt_se, struct rt_prio_array *array)
{
	list_del_init(&rt_se->run_list);

	if (list_empty(array->queue + rt_se_prio(rt_se)))
		__clear_bit(rt_se_prio(rt_se), array->bitmap);

	rt_se->on_list = 0;
}

static void __dequeue_rt_entity(struct sched_rt_entity *rt_se, unsigned int flags)
{
	struct rt_rq *rt_rq = rt_rq_of_se(rt_se);
	struct rt_prio_array *array = &rt_rq->active;

	if (move_entity(flags)) {
		WARN_ON_ONCE(!rt_se->on_list);
		__delist_rt_entity(rt_se, array);
	}
	rt_se->on_rq = 0;

	dec_rt_tasks(rt_se, rt_rq);
}

dequeue_top_rt_rq 从顶层实时调度队列中移除任务

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static void
dequeue_top_rt_rq(struct rt_rq *rt_rq, unsigned int count)
{
	struct rq *rq = rq_of_rt_rq(rt_rq);

	BUG_ON(&rq->rt != rt_rq);

	if (!rt_rq->rt_queued)
		return;

	BUG_ON(!rq->nr_running);

	sub_nr_running(rq, count);
	rt_rq->rt_queued = 0;

}

for_each_sched_rt_entity 遍历实时调度实体

1
2
#define for_each_sched_rt_entity(rt_se) \
	for (; rt_se; rt_se = NULL)

dequeue_rt_stack 从实时调度栈中移除任务

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

static inline int on_rt_rq(struct sched_rt_entity *rt_se)
{
	return rt_se->on_rq;
}

/*
 * 由于上层实体的优先级依赖于下层实体，必须按照从上到下的顺序移除任务实体。
 * 这种设计确保任务的优先级关系在移除过程中保持一致
 */
static void dequeue_rt_stack(struct sched_rt_entity *rt_se, unsigned int flags)
{
	struct sched_rt_entity *back = NULL;
	unsigned int rt_nr_running;

	for_each_sched_rt_entity(rt_se) {
		/* 将每个实体的 back 字段设置为上一个实体，构建栈结构 */
		rt_se->back = back;
		back = rt_se;
	}

	/* 获取栈顶实体所属的实时运行队列中的运行任务数量 */
	rt_nr_running = rt_rq_of_se(back)->rt_nr_running;

	/* 从栈顶开始，遍历栈结构，检查每个实体是否在实时调度队列中 */
	for (rt_se = back; rt_se; rt_se = rt_se->back) {
		/* 如果实体在队列中 */
		if (on_rt_rq(rt_se))
			__dequeue_rt_entity(rt_se, flags);
	}

	/* 更新顶层实时调度队列 */
	dequeue_top_rt_rq(rt_rq_of_se(back), rt_nr_running);
}

enqueue_rt_entity 将实时任务实体加入实时调度队列

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
static void __enqueue_rt_entity(struct sched_rt_entity *rt_se, unsigned int flags)
{
	struct rt_rq *rt_rq = rt_rq_of_se(rt_se);
	struct rt_prio_array *array = &rt_rq->active;
	/* return NULL; */
	struct rt_rq *group_rq = group_rt_rq(rt_se);
	struct list_head *queue = array->queue + rt_se_prio(rt_se);

	// /*
	//  * Don't enqueue the group if its throttled, or when empty.
	//  * The latter is a consequence of the former when a child group
	//  * get throttled and the current group doesn't have any other
	//  * active members.
	//  */
	// if (group_rq && (rt_rq_throttled(group_rq) || !group_rq->rt_nr_running)) {
	// 	if (rt_se->on_list)
	// 		__delist_rt_entity(rt_se, array);
	// 	return;
	// }

	if (move_entity(flags)) {
		WARN_ON_ONCE(rt_se->on_list);
		if (flags & ENQUEUE_HEAD)
			list_add(&rt_se->run_list, queue);
		else
			list_add_tail(&rt_se->run_list, queue);

		__set_bit(rt_se_prio(rt_se), array->bitmap);
		rt_se->on_list = 1;
	}
	rt_se->on_rq = 1;

	inc_rt_tasks(rt_se, rt_rq);
}

static void
enqueue_top_rt_rq(struct rt_rq *rt_rq)
{
	struct rq *rq = rq_of_rt_rq(rt_rq);

	BUG_ON(&rq->rt != rt_rq);

	if (rt_rq->rt_queued)
		return;

	if (rt_rq_throttled(rt_rq))
		return;

	if (rt_rq->rt_nr_running) {
		add_nr_running(rq, rt_rq->rt_nr_running);
		rt_rq->rt_queued = 1;
	}

	/* Kick cpufreq (see the comment in kernel/sched/sched.h). */
	cpufreq_update_util(rq, 0);
}

static void enqueue_rt_entity(struct sched_rt_entity *rt_se, unsigned int flags)
{
	struct rq *rq = rq_of_rt_se(rt_se);

	update_stats_enqueue_rt(rt_rq_of_se(rt_se), rt_se, flags);
	/*  从实时调度栈中移除任务 */
	dequeue_rt_stack(rt_se, flags);
	/* 遍历实时调度实体的层级结构 */
	for_each_sched_rt_entity(rt_se)
		/* 将每个实时调度实体加入实时调度队列 */
		__enqueue_rt_entity(rt_se, flags);
	/* 更新运行队列的顶层实时调度队列
	顶层实时调度队列存储最高优先级的任务，确保调度器能够快速选择需要运行的任务。 */
	enqueue_top_rt_rq(&rq->rt);
}

enqueue_task_rt 将实时任务添加到运行队列

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
/*
 * Adding/removing a task to/from a priority array:
 */
static void
enqueue_task_rt(struct rq *rq, struct task_struct *p, int flags)
{
	struct sched_rt_entity *rt_se = &p->rt;

	if (flags & ENQUEUE_WAKEUP)
		rt_se->timeout = 0;

	// check_schedstat_required();
	/* 更新任务的等待时间统计 */
	/* 通过 rt_rq_of_se(rt_se) 获取任务所属的实时运行队列（rt_rq） */
	update_stats_wait_start_rt(rt_rq_of_se(rt_se), rt_se);

	/* 将任务的实时调度实体加入实时调度队列 */
	enqueue_rt_entity(rt_se, flags);

	/* 如果任务不是当前运行的任务（!task_current(rq, p)），
	并且任务允许在多个 CPU 上运行（p->nr_cpus_allowed > 1） */
	if (!task_current(rq, p) && p->nr_cpus_allowed > 1)
		/*  将任务加入可迁移任务队列，支持任务在多个 CPU 之间迁移 */
		enqueue_pushable_task(rq, p);
}