Deadline实时调度算法详解 深入解析Deadline实时调度算法(3)

Deadline实时调度算法详解

Deadline 调度器通过调用enqueue_dl_entity()函数来将一个实时任务添加到运行队列中，而enqueue_dl_entity()函数最终会调用__enqueue_dl_entity()函数来实现将任务添加到队列中。

我们来看看__enqueue_dl_entity()函数的实现：

static void __enqueue_dl_entity(struct sched_dl_entity *dl_se)
{
    struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
    struct rb_node **link = &dl_rq->rb_root.rb_node;
    struct rb_node *parent = NULL;
    struct sched_dl_entity *entry;
    int leftmost = 1;
    // 1. 通过任务的deadline，找到其在运行队列红黑树中的位置
    while (*link) {
        parent = *link;
        entry = rb_entry(parent, struct sched_dl_entity, rb_node);
        if (dl_time_before(dl_se->deadline, entry->deadline))
            link = &parent->rb_left;
        else {
            link = &parent->rb_right;
            leftmost = 0;
        }
    }
    // 2. 如果当前任务是队列中deadline最早到期的，那么缓存到运行队列的rb_leftmost字段中
    if (leftmost)
        dl_rq->rb_leftmost = &dl_se->rb_node;
    // 3. 将任务添加到运行队列的红黑树中
    rb_link_node(&dl_se->rb_node, parent, link);
    rb_insert_color(&dl_se->rb_node, &dl_rq->rb_root);
    // 4. 增加运行队列的任务数
    inc_dl_tasks(dl_se, dl_rq);
}

从上面代码可以看到，当把一个实时任务添加到运行队列的红黑树中时，是根据该任务的 deadline 来找到其在红黑树中的相应位置，然后添加到运行队列的红黑树中。任务添加成功后，会增加运行队列的任务计数器。

当进行任务切换时，Deadline 调度器选择红黑树最左面的节点进行调度，其通过pick_next_task_dl()函数来实现，代码如下：

struct task_struct *
pick_next_task_dl(struct rq *rq, struct task_struct *prev)
{
    struct sched_dl_entity *dl_se;
    struct task_struct *p;
    struct dl_rq *dl_rq;
    dl_rq = &rq->dl;
    ...
    // 1. 找到 deadline 最早到期的调度实体
    dl_se = pick_next_dl_entity(rq, dl_rq);
    // 2. 获取改调度实体对应的任务
    p = dl_task_of(dl_se);
    ...
    // 3. 返回 deadline 最早到期的任务
    return p;
}

pick_next_task_dl()函数通过取得运行队列红黑树的最左边的节点，并返回该节点上对应的任务。

那么 Deadline 调度器是怎么保证每个任务都能在其调度周期内执行呢？

每个任务都有一个高精度定时器（sched_dl_entity结构的dl_timer字段），其超时时间为任务的调度周期。当定时器触发时，便会调用dl_task_timer()函数来处理定时器事件。我们来看看dl_task_timer()函数的实现：

static enum hrtimer_restart dl_task_timer(struct hrtimer *timer)
{
    struct sched_dl_entity *dl_se = container_of(timer, struct sched_dl_entity, dl_timer);
    struct task_struct *p = dl_task_of(dl_se);
    ...
    // 1. 将任务添加到运行队列中
    enqueue_task_dl(rq, p, ENQUEUE_REPLENISH);
    if (dl_task(rq->curr)) {
        check_preempt_curr_dl(rq, p, 0);
    } else {
        // 2. 进行进程调度
        resched_curr(rq);
    }
    ...
}