理解RT调度类linux的dequeue_rt_stack()

Question

./kernel/sched/rt.c中的enqueue_task_rt函数负责将任务排入运行队列。enqueue_task_rt包含对enqueue_rt_entity的调用，后者调用dequeue_rt_stack。大部分代码看起来很合乎逻辑，但我有点迷惑了，因为函数dequeue_rt_stack无法理解它的作用。谁能告诉我我遗漏的逻辑是什么，或者建议一些好的阅读。

编辑:以下是dequeue_rt_stack函数的代码

     struct sched_rt_entity *back = NULL;
     /* macro for_each_sched_rt_entity defined as
     for(; rt_se; rt_se = rt_se->parent)*/
     for_each_sched_rt_entity(rt_se) {
             rt_se->back = back;
             back = rt_se;
     }

     for (rt_se = back; rt_se; rt_se = rt_se->back) {
             if (on_rt_rq(rt_se))
                     __dequeue_rt_entity(rt_se);
     }

更具体地说，我不明白为什么需要这样的代码：

     for_each_sched_rt_entity(rt_se) {
             rt_se->back = back;
             back = rt_se;
     }

它的相关性是什么。

Answer 1

使用group scheduler，任务始终位于树的最低层，并且可能有多个祖先：

       NULL
         ^
         |
+-----parent------+
|                 |
| top-level group |
|                 |
+-----------------+
         ^      ^_____________
         |                    \
+-----parent------+   +-----parent------+
|                 |   |                 |
| mid-level group |   |   other group   |  ...
|                 |   |                 |
+-----------------+   +-----------------+
         ^      ^_____________
         |                    \
+-----parent------+   +-----------------+
|                 |   |                 |
|      task       |   |   other task    |  ...
|                 |   |                 |
+-----------------+   +-----------------+

要从树中删除任务，必须将其从所有组的队列中删除，并且必须首先在顶级组中执行此操作(否则，调度程序可能会尝试运行已部分删除的任务)。因此，dequeue_rt_stack使用back指针以相反的方向构造一个列表：

   NULL    back
     ^      |
     |      V
+-parent----------+
|                 |
| top-level group |
|                 |
+----------back---+
     ^      |   ^_____________
     |      V                 \
+-parent----------+   +-----parent------+
|                 |   |                 |
| mid-level group |   |   other group   |  ...
|                 |   |                 |
+----------back---+   +-----------------+
     ^      |   ^_____________
     |      V                 \
+-parent----------+   +-----------------+
|                 |   |                 |
|      task       |   |   other task    |  ...
|                 |   |                 |
+----------back---+   +-----------------+
            |
            V
           NULL

然后，可以使用该back列表向下遍历树，以按正确的顺序删除实体。

Answer 2

我是一个内核黑客的新手。这是我第一次回答linux内核的问题。也许这对你有帮助。

我读了源代码。我认为这可能与团队日程安排有关。

当内核有这些代码时：

#ifdef CONFIG_RT_GROUP_SCHED

它表示我们可以将一些调度实体收集到一个调度组中。

static void enqueue_rt_entity(struct sched_rt_entity *rt_se, bool head)

{

    dequeue_rt_stack(rt_se);
    for_each_sched_rt_entity(rt_se)
          __enqueue_rt_entity(rt_se, head);

}

Function dequeue_rt_stack(rt_se)提取出组内的所有调度实体，添加到运行队列中。

Hierarchical group I/O scheduling

CFS group scheduling