Links

2.5 RT调度器

本节我们简要介绍一下实时任务的调度思想,RT调度器的所有实现都在文件 kernel/sched/rt.c 中,想要详细研究的同学可以自行学习。
RT任务的调度与优先级直接相关,在前文介绍优先级时,我们提到调度器使用的是动态优先级,在动态优先级中,RT任务的优先级区间是[1, 99], 数字越大优先级越小。为了提升效率,调度器为每个优先级都单独维护了一个任务列表,对应的数据结构是:
/* file: kernel/sched/sched.h */
struct rt_prio_array {
DECLARE_BITMAP(bitmap,
MAX_RT_PRIO + 1); /* include 1 bit for delimiter */
struct list_head queue[MAX_RT_PRIO]; /* MAX_RT_PRIO的值为100 */
};
该结构体与 O(1) 调度器中的实现思路是一样的,都是为了降低调度器在查找下一个任务的时间复杂度。
rt_prio_array 包含在RT任务的运行队列 rt_rq 中:
/* file: kernel/sched/sched.h */
struct rt_rq {
struct rt_prio_array active;
unsigned int rt_nr_running;
unsigned int rr_nr_running;
int rt_queued;
int rt_throttled;
u64 rt_time;
u64 rt_runtime;
#ifdef CONFIG_RT_GROUP_SCHED
unsigned long rt_nr_boosted;
struct rq *rq;
struct task_group *tg;
#endif
};
此处仅保留了队列的部分字段,active 就是各优先级的任务列表,初始化函数 init_rt_rq 会对各个字段做初始化。这样调度器的调度算法就很简单了:先根据 bitmap 选出第一个为空的队列,然后从该队列中取出第一个任务。逻辑如下:
/* file: kernel/sched/rt.c */
static struct sched_rt_entity *pick_next_rt_entity(struct rq *rq,
struct rt_rq *rt_rq)
{
struct rt_prio_array *array = &rt_rq->active;
struct sched_rt_entity *next = NULL;
struct list_head *queue;
int idx;
/* 从位图中找出第一个为空列表的索引位置 */
idx = sched_find_first_bit(array->bitmap);
BUG_ON(idx >= MAX_RT_PRIO);
/* 通过索引位置拿到任务队列,并从中取出下一个元素,即下一个RT任务的调度实体 */
queue = array->queue + idx;
next = list_entry(queue->next, struct sched_rt_entity, run_list);
return next;
}
static struct task_struct *_pick_next_task_rt(struct rq *rq)
{
struct sched_rt_entity *rt_se;
struct rt_rq *rt_rq = &rq->rt;
/* 处理组调度,组调度的逻辑后续会有专门的章节进行分析 */
do {
rt_se = pick_next_rt_entity(rq, rt_rq);
BUG_ON(!rt_se);
rt_rq = group_rt_rq(rt_se);
} while (rt_rq);
return rt_task_of(rt_se);
}
static struct task_struct *pick_next_task_rt(struct rq *rq)
{
struct task_struct *p;
if (!sched_rt_runnable(rq))
return NULL;
p = _pick_next_task_rt(rq);
set_next_task_rt(rq, p, true);
return p;
}
函数 pick_next_task_rt 就是挑选下一个RT任务的逻辑。
这里只提供了对RT调度逻辑最简略的描述,完整的实现中还包含对CPU带宽的控制、对SMP架构下的处理(例如负载均衡)等,我们在这里不再一一探讨。