《多处理器运行队列的平衡》由会员分享，可在线阅读，更多相关《多处理器运行队列的平衡（15页珍藏版）》请在金锄头文库上搜索。
1、正如我们在上一节所看到的，schedule( )函数从本地 CPU 的运行队列挑选新进程运行。因此，一个指定的 CPU 只能执行它相应的运行队列中的可运行进程。另外，一个可运行进程总是存放在某一个运行队列中：任何一个可运行进程都不可能同时出现在两个或多个运行队列中。因此，一个保持可运行状态的进程通常被限制在一个固定的 CPU 上。这种设计通常对系统性能是有益的，因为，运行队列中的可运行进程所拥有的数据可能填满每个 CPU 的硬件高速缓存。但是，在有些情况下，把可运行进程限制在一个指定的CPU 上可能引起严重的性能损失。例如，考虑频繁使用 CPU 的大量批处理进程：如果他们绝大多数都在同一个运行
2、队列中，那么系统中一个 CPU 将会超负荷，而其他一些 CPU几乎处于空闲状态。因此，内核周期性地检查运行队列的工作量是否平衡，并在需要的时候，把一些进程从一个运行队列迁移到另一个运行队列。但是，为了从多处理器系统获得最佳性能，负载平衡算法应该考虑系统中 CPU 的拓扑结构。从内核 2.6.7 版本开始，Linux 提出一种基于“调度域”概念的复杂的运行队列平衡算法。正是有了调度域这一概念，使得这种算法能够很容易适应各种已有的多处理器体系结构（甚至诸如那些基于“多核”微处理器的新近出现的体系结构）。1 调度域调度域调度域实际上是一个 CPU 集合，他们的工作量应当由内核保持平衡。一般来说，调度
3、域采取分层的组织形式：最上层的调度域（通常包括系统中的所有 CPU）包括多个子调度域，每个子调度域包括一个 CPU 子集。正是调度域的这种分层结构，使工作量的平衡能以如下有效方式来实现：每个调度域被依次划分成一个或多个组，每个组代表调度域的一个 CPU 子集。工作量的平衡总是在调度域的组之间来完成。换而言之，只有在一些调度域的某些组的总工作量远远低于同一个调度域的另一个组的工作量时，才把进程从一个 CPU 迁移到另一个 CPU。下图说明三个调度域分层实例，对应三种主要的多处理器机器体系结构：图中（a）表示具有两 CPU 的标准多处理器体系结构中由单个调度域组成的一个层次结构，该调度域包括两个组
4、，每个组有一个 CPU。图中（b）表示一个两层的层次结构，用在使用超线程技术、有两 CPU 的多处理器结构中。最上层的调度域包括了系统中所有四个逻辑 CPU，它由两个组构成。上层域的每个组对应一个子调度域并包括一个物理 CPU。底层的调度域(也被称为基本调度域)包括两个组，每个组一个逻辑 CPU。最后，图中（c）表示有两个结点，每个结点有四个 CPU 的 8-CPUNUMA 体系结构上的两层层次结构。最上层的域由两个组构成，每个组对应一个不同的结点。每个基本调度域包括一个结点内的 CPU，包括四个组，每个组包括一个 CPU。每个调度域由一个 sched_domain 描述符表示，而调度域中的每
5、个组由 sched_group 描述符表示。每个 sched_domain 描述符包括一个 groups 字段，它指向组描述符链表中的第一个元素。此外，sched_domain 结构的 parent 字段指向父调度域的描述符（如果有的话）。struct sched_domain /* These fields must be setup */struct sched_domain *parent; /* top domain must be null terminated */struct sched_group *groups; /* the balancing groups of the
6、domain */cpumask_t span; /* span of all CPUs in this domain */unsigned long min_interval; /* Minimum balance interval ms */unsigned long max_interval; /* Maximum balance interval ms */unsigned int busy_factor; /* less balancing by factor if busy */unsigned int imbalance_pct; /* No balance until over
7、 watermark */unsigned long long cache_hot_time; /* Task considered cache hot (ns) */unsigned int cache_nice_tries; /* Leave cache hot tasks for # tries */unsigned int per_cpu_gain; /* CPU % gained by adding domain cpus */unsigned int busy_idx;unsigned int idle_idx;unsigned int newidle_idx;unsigned i
8、nt wake_idx;unsigned int forkexec_idx;int flags; /* See SD_* */* Runtime fields. */unsigned long last_balance; /* init to jiffies. units in jiffies */unsigned int balance_interval; /* initialise to 1. units in ms. */unsigned int nr_balance_failed; /* initialise to 0 */#ifdef CONFIG_SCHEDSTATS/* load
9、_balance() stats */unsigned long lb_cntMAX_IDLE_TYPES;unsigned long lb_failedMAX_IDLE_TYPES;unsigned long lb_balancedMAX_IDLE_TYPES;unsigned long lb_imbalanceMAX_IDLE_TYPES;unsigned long lb_gainedMAX_IDLE_TYPES;unsigned long lb_hot_gainedMAX_IDLE_TYPES;unsigned long lb_nobusygMAX_IDLE_TYPES;unsigned
10、 long lb_nobusyqMAX_IDLE_TYPES;/* Active load balancing */unsigned long alb_cnt;unsigned long alb_failed;unsigned long alb_pushed;/* SD_BALANCE_EXEC stats */unsigned long sbe_cnt;unsigned long sbe_balanced;unsigned long sbe_pushed;/* SD_BALANCE_FORK stats */unsigned long sbf_cnt;unsigned long sbf_ba
11、lanced;unsigned long sbf_pushed;/* try_to_wake_up() stats */unsigned long ttwu_wake_remote;unsigned long ttwu_move_affine;unsigned long ttwu_move_balance;#endif;系统中所有物理 CPU 的 sched_domain 描述符都存放在每 CPU 变量 phys_domains 中。如果内核不支持超线程技术，这些域就在域层次结构的最底层，运行队列描述符 rq 的 sd字段指向它们，即它们是基本的调度域。相反，如果内核支持超线程技术，底层调度域
12、存放在每 CPU 变量 cpu_domains 中。2 rebalance_tick( )函数函数为了保持系统中运行队列的平衡，每次经过一次时钟节拍 scheduler_tick( )，就调用rebalance_tick( )函数：static void rebalance_tick(int this_cpu, struct rq *this_rq, enum idle_type idle)unsigned long this_load, interval, j = cpu_offset(this_cpu);struct sched_domain *sd;int i, scale;this_l
13、oad = this_rq-raw_weighted_load;/* Update our load: */for (i = 0, scale = 1; i cpu_loadi;new_load = this_load;/* Round up the averaging division if load is increasing. This* prevents us from getting stuck on 9 if the load is 10, for* example.*/if (new_load old_load)new_load += scale-1;this_rq-cpu_lo
14、adi = (old_load*(scale-1) + new_load) / scale;for_each_domain(this_cpu, sd) if (!(sd-flags interval = sd-balance_interval;if (idle != SCHED_IDLE)interval *= sd-busy_factor;/* scale ms to jiffies */interval = msecs_to_jiffies(interval);if (unlikely(!interval)interval = 1;if (j - sd-last_balance = int
15、erval) if (load_balance(this_cpu, this_rq, sd, idle) /* Weve pulled tasks over so either were no* longer idle, or one of our SMT siblings is* not idle.*/idle = NOT_IDLE;sd-last_balance += interval;它接受的参数有：本地 CPU 的索引 this_cpu 、本地运行队列的地址 this_rq 以及一个标志 idle，该标志可以取下面的值：SCHED_IDLE：CPU 当前空闲，即 current 是 s
16、wapper 进程。NOT_IDLE：CPU 当前不空闲，即 current 不是 swapper 进程。rebalance_tick( )函数首先确定运行队列中的进程数，并更新进程队列的平均工作量，为了完成这个工作，函数要访问运行队列描述符的 nr_running and cpu_load 字段。随后，rebalance_tick( )开始在所有调度域上的循环，其路径是从基本域（本地运行队列描述符的 sd 字段所引用的域）到最上层的域。在每次循环中，函数确定是否已到调用函数load_balance( )的时间，从而在调度域上执行重新平衡的操作。由存放在 sched_domain域中的参数和 idle 值决定调用 load_balance( )的频率。如果 idle 等于 SCHED_IDLE，那么运行队列为空，rebalance_tick( )就以很高的频率调用 load_balance
