c - include/linux/sched.h 中的 struct sched_domain 代表什么(内核中的调度域)

Question

我想了解负载均衡器如何在 Linux 内核的多处理器系统上工作，

Linux 调度器基本上使用 runques 来存储它接下来要运行的任务， 现在考虑多处理器系统的情况 load_balancer() 的实现方式 Robert Loves 书 Linux 内核开发第 2 版中给出的解释如下

First, load_balance() calls find_busiest_queue() to determine the busiest runqueue. In other words, this is the runqueue with the greatest number of processes in it. If there is no runqueue that has 25% or more processes than the current, find_busiest_queue() returns NULL and load_balance() returns. Otherwise, the busiest runqueue is returned.

Second, load_balance() decides which priority array on the busiest runqueue it wants to pull from. The expired array is preferred because those tasks have not run in a relatively long time, thus are most likely not in the processor's cache (that is, they are not cache hot). If the expired priority array is empty, the active one is the only choice.

Next, load_balance() finds the highest priority (smallest value) list that has tasks, because it is more important to fairly distribute high priority tasks than lower priority ones.

Each task of the given priority is analyzed, to find a task that is not running, not prevented to migrate via processor affinity, and not cache hot. If the task meets this criteria, pull_task() is called to pull the task from the busiest runqueue to the current runqueue.

As long as the runqueues remain imbalanced, the previous two steps are repeated and more tasks are pulled from the busiest runqueue to the current. Finally, when the imbalance is resolved, the current runqueue is unlocked and load_balance()returns.

代码如下

static int load_balance(int this_cpu, runqueue_t *this_rq,
                        struct sched_domain *sd, enum idle_type idle)
{
        struct sched_group *group;
        runqueue_t *busiest;
        unsigned long imbalance;
        int nr_moved;

        spin_lock(&this_rq->lock);

        group = find_busiest_group(sd, this_cpu, &imbalance, idle);
        if (!group)
                goto out_balanced;

        busiest = find_busiest_queue(group);
        if (!busiest)
                goto out_balanced;

        nr_moved = 0;
        if (busiest->nr_running > 1) {
                double_lock_balance(this_rq, busiest);
                nr_moved = move_tasks(this_rq, this_cpu, busiest,
                                      imbalance, sd, idle);
                spin_unlock(&busiest->lock);
        }
        spin_unlock(&this_rq->lock);

        if (!nr_moved) {
                sd->nr_balance_failed++;

                if (unlikely(sd->nr_balance_failed > sd->cache_nice_tries+2)) {
                        int wake = 0;

                        spin_lock(&busiest->lock);
                        if (!busiest->active_balance) {
                                busiest->active_balance = 1;
                                busiest->push_cpu = this_cpu;
                                wake = 1;
                        }
                        spin_unlock(&busiest->lock);
                        if (wake)
                                wake_up_process(busiest->migration_thread);
                        sd->nr_balance_failed = sd->cache_nice_tries;
                }
        } else
                sd->nr_balance_failed = 0;

        sd->balance_interval = sd->min_interval;

        return nr_moved;

out_balanced:
        spin_unlock(&this_rq->lock);

        if (sd->balance_interval < sd->max_interval)
                sd->balance_interval *= 2;

        return 0; 
}

我不清楚的是上面代码中的结构 struct sched_domain *sd 我检查的这个结构定义在 include/linux/sched.h 如下 http://lxr.linux.no/linux+v3.7.1/include/linux/sched.h#L895 这是一个很大的结构，所以为了简单起见，我只是给出了一个链接。 我想知道上面代码中的struct sched_domain有什么用？

为什么在调用 load_balancer() 时使用它这个结构代表什么？

这里可能给出了一些东西 http://www.kernel.org/doc/Documentation/scheduler/sched-domains.txt 为什么 CPU 需要调度域？这些域名代表什么？

Answer 1

调度域和调度器组/cpu 组有助于缓解 调度任务的过程，例如:

1. 跨 CPU 的负载平衡任务。
2. 为要运行的新任务选择一个 CPU。
3. 为 sleep 任务选择一个 cpu，以便在它醒来时运行。

它有两个优势:

1. 它将系统中的 cpu 很好地组织成组和层次结构。

2. 它以有用的方式组织 cpus。所有 cpus
   共享一个属于一个域的二级缓存。共享一个三级缓存的所有cpu
   属于更高级别的域，包含所有域
   共享二级缓存。

你看到的树状数据结构的优点是相似的 这是调度程序域和组的优势。

引用下图

     _________sd1________
    /                    \
    ----------------------
         l3 cache
    ----------------------
    ---------   ----------
    l2 cache    l2 cache
    ---------   ----------
    cpu0 cpu1   cpu2 cpu3
    \_______/   \________/
      sd0          sd0

 ________sd1_________
/                    \
----------------------
      l3 cache
----------------------
---------   ----------
l2 cache    l2 cache
---------   ----------
cpu4 cpu5   cpu6 cpu7
\_______/   \________/
  sd0          sd0

您在上面看到的是调度程序域层次结构。sd1 包含 sd0s 恰好是 sd1 的调度程序组。每个 cpu 都有一个调度程序 与之关联的域层次结构。例如。
cpu0->sd=sd0; sd0->parent=sd1.这样通过一个链表我们可以 遍历一个 cpu 所属的所有调度程序域。

这有什么帮助？

1.load balancing: 假设 cpu0 是空闲的并且准备好拉取任务 本身减轻任何其他负担的 cpu。在上述方法中，它首先 检查是否属于第一级 sched 域的其他 cpus ，需要减轻负载。这里是 cpu1。如果是这样，它会从 cpu1，否则它会转到更高级别的域 sd1。如果它选择 从 cpu1 迁移任务是最好的事情，因为缓存内容 可以利用；共享缓存。无需再次从内存中获取。这是 第一个优势:sched域是基于优势形成的 该硬件必须提供。

如果它转到 sd1，那么它会探测 sd1 的“组”，包括 sd0s。这是 下一个优势。它只需要有关计划组的信息，并且 不会理会其中的单个 CPU。它会检查是否 加载(sd0[cpu2,cpu3]) > 加载(sd0[cpu0,cpu1]) 只有当这是真的时，它才会继续查看 cpu2/3 是否加载更多。如果 没有调度程序域或组，我们必须查看状态 cpu2 和 cpu3 在两次迭代中而不是像我们这样的 1 次迭代 现在做。

现在将这个问题和解决方案扩展到 128 个 CPU!想象一下它有多乱 如果没有什么可以告诉你哪个 cpu 会是 最好减轻负载，在最坏的情况下你将不得不迭代 通过所有 128 个 CPU。

但是对于调度程序域或组，假设您将 128 个 cpu 划分为 16 个 CPU 组，你将有 8 个组。看看哪个最忙，所以 那将是 8 次迭代，然后你会知道最忙的组，然后 下降。另外 16 次迭代。所以最坏的情况

8+16 = 24 次迭代 领域。想象一下，如果你有更多的层次，你会 迭代次数甚至更低。

所以简而言之，调度程序域和组是一个“分而治之” ;但尽可能征服更有用的解决方案 安排相关的东西。

我发帖是为了防止将来有人想阅读它。