6

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

Linux 调度程序基本上使用 runques 来存储它接下来必须运行的任务，现在考虑多处理器系统的情况 load_balancer() 的实现方式如 Robert Loves 的书 Linux Kernel Development 2nd edition 中给出的解释如下

首先，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; 
}

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

4

1 回答 1

15

调度域和调度程序组/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 包含 sd0s，它们恰好是 sd1 的调度程序组。每个 cpu 都有一个与之关联的调度程序域层次结构。例如。
cpu0->sd=sd0；sd0->parent=sd1。这样通过链表我们可以遍历一个cpu所属的所有调度器域。

这有什么帮助？

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

如果它转到 sd1，那么它会探测 sd1 的“组”，都是 sd0s。这是下一个优势。它只需要有关 sched 组的信息，不会打扰其中的单个 cpu。它检查负载（sd0 [ cpu2,cpu3]) > load(sd0[cpu0,cpu1]) 只有当这是真的时，它才会继续查看 cpu2/3 是否负载更多。如果没有调度程序域或组，我们将不得不查看状态cpu2 和 cpu3 在两次迭代中，而不是像我们现在做的 1 次迭代。

现在将此问题和解决方案扩展到 128 cpu！想象一下，如果没有什么可以告诉您哪个 cpu 最能减轻负载，那将是多么混乱，在最坏的情况下，您将不得不遍历所有 128 个 cpu。

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

8+16 = 24 次迭代。而这种减少仅与一级 sched 域有关。想象一下，如果你有更多的关卡，你会让迭代次数更少。

因此，简而言之，调度程序域和组是“分而治之；但要尽可能多地征服更有用的”解决方案来调度相关的东西。

我张贴以防将来有人想阅读它。

于 2013-01-10T15:11:50.720 回答