Reg*_*ser 5 c kernel processor intel scheduler
我试图了解负载均衡器如何在Linux内核中的多处理器系统上运行,
Linux调度程序基本上使用runques来存储它必须在下一次运行的任务,现在以执行load_balancer()的方式处理多处理器系统的情况,如Robert Loves书中给出的解释Linux内核开发第2版正在关注
首先,load_balance()调用find_busiest_queue()来确定最繁忙的runqueue.换句话说,这是其中包含最多进程的runqueue.如果没有比当前进程多25%或更多进程的runqueue,则find_busiest_queue()返回NULL并返回load_balance().否则,返回最繁忙的runqueue.
其次,load_balance()决定它想从中拉出的最繁忙的runqueue上的哪个优先级数组.过期的阵列是首选,因为这些任务在相对较长的时间内没有运行,因此很可能不在处理器的缓存中(即,它们不是缓存热点).如果过期的优先级数组为空,则活动的数组是唯一的选择.
接下来,load_balance()查找具有任务的最高优先级(最小值)列表,因为公平分配高优先级任务比低优先级任务更重要.
分析给定优先级的每个任务,以查找未运行的任务,不阻止通过处理器关联迁移,而不是缓存热.如果任务满足此条件,则调用pull_task()将任务从最繁忙的runqueue拉到当前的runqueue.
只要运行队列保持不平衡,就会重复前两个步骤,并将更多任务从最繁忙的队列中拉到当前.最后,当解决不平衡时,当前的runqueue被解锁并且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需要调度域？这些域名代表什么？
Reg*_*ser 14
调度域和调度程序组/ cpu组有助于简化调度任务的过程,例如:
它有两个优点:
它将系统中的cpu很好地组织成组和层次结构.
它
以一种有用的方式组织cpus.共享l2缓存的所有cpus
属于一个域.共享l3缓存的所有cpus 属于更高级域,其包含
共享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
您在上面看到的是调度程序域hierarchy.sd1包含sd0s,它恰好是sd1的调度程序组.每个cpu都有一个与之关联的调度程序域层次结构.例如.
cpu0-> SD = SD0; sd0-> parent = sd1.通过链表我们可以迭代cpu所属的所有调度程序域.
这有什么用？
1.load balancing:假设cpu0处于空闲状态,并准备将任务拉到自身以减轻任何其他负载cpu.在上述方法中,它首先检查属于第一级sched域的其他cpus是否需要被释放load.Here,cpu1.如果它从cpu1接受任务,否则它转到更高级别的域sd1.如果它选择从cpu1迁移任务,那是最好的事情,因为可以利用缓存内容;共享缓存.无需再次从内存中获取.这是第一个优点:基于硬件必须提供的优势形成了sched域.
如果它转到sd1,那么它会探测sd1的'groups',两者都是sd0s.Here是下一个优势.它只需要有关sched组的信息而不会打扰它中的个别cpus.它会检查是否加载(sd0 [ cpu2,cpu3])> load(sd0 [cpu0,cpu1])只有当这是真的时才继续查看cpu2/3是否加载更多.如果没有调度程序域或组,我们必须看到状态cpu2和cpu3在两次迭代中代替1次迭代,就像我们现在正在做的那样.
现在将此问题和解决方案扩展到128 cpu!想象一下,如果没有什么可以告诉你哪个cpu最能减轻负载,那将是多么糟糕,在最坏的情况下你将不得不迭代所有的128 cpu.
但是对于调度程序域或组,假设你将128 cpus分成16个cpus的组,你将有8个group.see哪个是最繁忙的,所以这将是8次迭代,然后你会知道最繁忙的组,然后下降.另外16次迭代.最糟糕的情况
8 + 16 = 24次迭代.这种减少仅适用于一个级别的sched域.想象一下,如果你有更多级别,你会使迭代次数更低.
因此,简而言之,调度程序域和组是一个"分而治之;但尽可能地征服什么是更有用的"解决方案来安排相关的东西.
我张贴以防将来某些人可能想要阅读它.