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架构下的处理（例如负载均衡）等，我们在这里不再一一探讨。