include/linux/sched.h中的struct sched_domain代表什么意思？（内核中的调度域）

Question

我正在学习Linux内核中多处理器系统上负载均衡器的工作原理。Linux调度器基本上使用运行队列来存储它要下一步运行的任务，现在考虑到多处理器系统，load_balancer()的实现方式如下解释：

首先，load_balance()调用find_busiest_queue()确定最繁忙的运行队列。换句话说，这是具有最多进程的运行队列。如果没有运行队列比当前队列的进程多25％或更多，则find_busiest_queue()返回NULL并且load_balance()返回。否则，将返回最繁忙的运行队列。

其次，load_balance()决定从最繁忙的运行队列中拉取哪个优先级数组。过期的数组优先，因为这些任务相对较长时间未运行，因此最可能不在处理器缓存中（也就是不是缓存热点）。如果过期的优先级数组为空，则只能选择活动数组。

接下来，load_balance()找到具有任务的最高优先级（最小值）列表，因为公平地分配高优先级任务比低优先级任务更重要。

分析给定优先级的每个任务，以查找不在运行、不通过处理器亲和力阻止迁移且不是缓存热点的任务。如果任务符合此标准，则调用pull_task()将任务从最繁忙的运行队列拉到当前运行队列中。

只要运行队列保持不平衡，就会重复前两个步骤，并从最繁忙的运行队列拉取更多任务到当前队列。最后，当不平衡得到解决时，当前运行队列被解锁并且load_balance()返回。

以下是相关代码：

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; 
}

我不太清楚的是上述代码中的结构体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需要调度域？这些域代表着什么？

- Registered User

Answer 1

调度域和调度器组/ CPU组有助于简化调度任务的过程，例如：

1. 在CPU之间平衡负载。
2. 选择要在其上运行新任务的CPU。
3. 为正在睡眠的任务选择CPU以在唤醒时运行。

它具有双重优势：

1. 它非常好地将系统中的CPU组织成组和层次结构。

2. 它以一种有用的方式组织CPU。所有共享L2缓存的CPU都属于一个域。所有共享L3缓存的CPU都属于更高级别的域，该域包括共享L2缓存的所有域。

这里树形数据结构的优点与调度域和组的优点类似。

请参见以下图表：

     _________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涵盖了它是sd0的调度程序组，每个CPU都有一个与其关联的调度程序域层次结构。例如，cpu0->sd = sd0; sd0->parent = sd1。通过连接列表，我们可以迭代地访问CPU所属的所有调度程序域。
那这有什么好处呢？

1.负载平衡：假设cpu0空闲并准备承担任务以减轻任何其他负担的CPU。在上述方法中，它首先检查是否需要解除第一级调度程序域的其他CPU的负载。这里是cpu1。如果需要，则从cpu1获取任务，否则转到更高级别域sd1。如果选择从cpu1迁移任务，则这是最好的事情，因为可以利用缓存内容；共享缓存。无需再次从内存获取。这是第一个优点：基于硬件的优势形成调度程序域。

2.通过sd1探测“groups”，包括两个sd0。以下是下一个优点。它只需要有关sched组的信息，不需要理会其中的每个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次迭代。这种减少仅针对一个级别的sched域。想象一下，如果您有更多的级别，迭代次数将更低。

总之，调度程序域和组是处理调度相关内容的“分而治之；但尽可能征服更有用”的解决方案。

我发布这篇文章是因为未来可能会有人想要阅读它。

- Registered User