[TOC]
## NUMA
### 为什么要有NUMA
在NUMA架构出现前，CPU欢快的朝着频率越来越高的方向发展。受到物理极限的挑战，又转为核数越来越多的方向发展。即SMP架构（对称多处理器结构）。如果每个core的工作性质都是share-nothing（类似于map-reduce的node节点的作业属性），那么也许就不会有NUMA。<font color=red>由于所有CPU Core都是通过共享一个北桥来读取内存</font>，随着核数如何的发展，北桥在响应时间上的性能瓶颈越来越明显。于是，聪明的硬件设计师们，想到了把内存控制器（原本北桥中读取内存的部分）也做个拆分，平分到了每个die上[什么是die](https://zhuanlan.zhihu.com/p/51354994)。于是NUMA就出现了。
### NUMA是什么
在NUMA架构中有多个CPU模块，每个CPU模块由多个CPU组成，并且具有独立的本地内存、I/O槽口等。由于其节点之间可以通过互联模块（如称为Crossbar Switch）进行连接和信息交互，因此每个CPU可以访问整个系统的内存。显然，访问本地内存的速度将远远高于访问远地内存（系统内其它节点的内存）的速度，这也是非一致内存访问的由来。NUMA（Non-Uniform Memory Access）就此得名。
## CPU
从操作系统的视角来看，CPU可以划分为几个不同的层级，从大到小依次为NUMA 节点，物理CPU，CPU core，逻辑cpu。 core，逻辑cpu(core上的超线程)。在/proc/cpuinfo中可以查看cpu的相关信息。或者通过lscpu命令。
> 判断依据：
1.具有相同core id的cpu是同一个core的超线程。
2.具有相同physical id的cpu是同一颗cpu封装的线程或者cores。
英文版：
1.Physical id and core id are not necessarily consecutive but they are unique. Any cpu with the same core id are hyperthreads in the same core.
2.Any cpu with the same physical id are threads or cores in the same physical socket.
echo "logical CPU number:"
#逻辑CPU个数
cat /proc/cpuinfo | grep "processor" | wc -l
echo "physical CPU number:"
#物理CPU个数：
cat /proc/cpuinfo | grep "physical id" | sort -u | wc -l
echo "core number in a physical CPU:"
#每个物理CPU中Core的个数：
cat /proc/cpuinfo | grep "cpu cores" | uniq | awk -F: '{print $2}'
#查看core id的数量,即为所有物理CPU上的core的个数
cat /proc/cpuinfo | grep "core id" | uniq | wc -l
#是否为超线程？
#如果有两个逻辑CPU具有相同的”core id”，那么超线程是打开的。或者siblings数目比cpu cores数目大。
#每个物理CPU中逻辑CPU(可能是core, threads或both)的个数：
cat /proc/cpuinfo | grep "siblings"
/proc/cpuinfo 文件包含系统上每个处理器的数据段落。/proc/cpuinfo 描述中有 6 个条目适用于多内核和超线程（HT）技术检查：processor, vendor id, physical id, siblings, core id 和 cpu cores。
processor 条目包括这一逻辑处理器的唯一标识符。
physical id 条目包括每个物理封装的唯一标识符。
core id 条目保存每个内核的唯一标识符。
siblings 条目列出了位于相同物理封装中的逻辑处理器的数量。
cpu cores 条目包含位于相同物理封装中的内核数量。
如果处理器为英特尔处理器，则 vendor id 条目中的字符串是 GenuineIntel。
### 与操作系统的关系
由于硬件工程师的不懈努力，设计了如此复杂的硬件结构，操作系统必须对如此复杂的硬件结构形成完成的拓扑关系图以及复杂的调度访问算法来充分利用硬件的性能。所以这个锅必须硬件工程师来背。。。
Linux对NUMA系统的物理内存分布信息是从系统firmware的ACPI表中获得的，最重要的是SRAT（System Resource Affinity Table）和SLIT（System Locality Information Table）表，其中SRAT包含两个结构：
-Processor Local APIC/SAPIC Affinity Structure：记录某个CPU的信息；
-Memory Affinity Structure：记录内存的信息；
SLIT表则记录了各个结点之间的距离，在系统中由数组node_distance[ ]记录。
Linux采用Node、Zone和页三级结构来描述物理内存的，如图所示：
## NUMA调度器
NUMA系统中，由于局部内存的访存延迟低于远地内存访存延迟，因此将进程分配到局部内存附近的处理器上可极大优化应用程序的性能。Linux 2.4内核中的调度器由于只设计了一个运行队列，可扩展性较差，在SMP平台表现一直不理想。当运行的任务数较多时，多个CPU增加了系统资源的竞争，限制了负载的吞吐率。在2.5内核开发时，Ingo Molnar写了一个多队列调度器，称为O(1)，从2.5.2开始O(1)调度器已集成到2.5内核版本中。O(1)是<font color=red>多队列调度器，每个处理器都有一条自己的运行队列，</font>但由于O(1)调度器不能较好地感知NUMA系统中结点这层结构，从而不能保证在调度后该进程仍运行在同一个结点上，为此，Eirch Focht开发了结点亲和的NUMA调度器，它是建立在Ingo Molnar的O(1)调度器基础上的，Eirch将该调度器向后移植到2.4.X内核中，该调度器最初是为基于IA64的NUMA机器的2.4内核开发的，后来Matt Dobson将它移植到基于X86的NUMA-Q硬件上。
### Linux下的CPU拓扑结构
如前所述，CPU的物理架构如此复杂，调度器要解决的一个首要问题就是如何发挥这么多 CPU 的性能，使得负载均衡。不存某些 CPU 一直很忙，进程在排队等待运行，而某些 CPU 却是处于空闲状态。但是在这些 CPU 之间进行 Load Balance 是有代价的，比如对处于两个不同物理 CPU 的进程之间进行负载平衡的话，将会使得 Cache 失效。造成效率的下降。而且过多的 Load Balance 会大量占用 CPU 资源。
由于进程的迁移是基于cpu的，而cpu最小级别的就是超线程处理器的一个smt核，次小的一级就是一个多核cpu的核，然后就是一个物理cpu封装，再往后就是cpu阵列，根据这些cpu级别的不同，<font color=red>Linux将所有同一级别的cpu归为一个“调度组”，然后将同一级别的所有的调度组组成一个“调度域”，</font> 负载均衡首先在调度域的各个调度组之间进行，然后再在最低一级的cpu上进行，注意负载均衡是基于最小一级的cpu的。整个架构如下图所示：
Linux下将物理cpu映射成如上的树形结构，load balance就是针对Scheduling domain的。从叶节点往上遍历。直到所有的 domain 中的负载都是平衡的。当然对不同的 domain 会有不同的策略识别是否负载不平衡，以及不同的调度策略。通过这样的方式，从而很好的发挥众多 cpu 的效率。
### 调度域
```
struct sched_domain {
/* These fields must be setup */
struct sched_domain *parent; /* top domain must be null terminated */
struct sched_domain *child; /* bottom domain must be null terminated */
struct sched_group *groups; /* the balancing groups of the 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 watermark */
unsigned int cache_nice_tries; /* Leave cache hot tasks for # tries */
unsigned int busy_idx;
unsigned int idle_idx;
unsigned int newidle_idx;
unsigned int wake_idx;
unsigned int forkexec_idx;
unsigned int smt_gain;
int nohz_idle; /* NOHZ IDLE status */
int flags; /* See SD_* */
int level;
/* 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 */
u64 last_update;
/* idle_balance() stats */
u64 max_newidle_lb_cost;
unsigned long next_decay_max_lb_cost;
#ifdef CONFIG_SCHED_DEBUG
char *name;
#endif
union {
void *private; /* used during construction */
struct rcu_head rcu; /* used during destruction */
};
unsigned int span_weight;
/*
* Span of all CPUs in this domain.
*
* NOTE: this field is variable length. (Allocated dynamically
* by attaching extra space to the end of the structure,
* depending on how many CPUs the kernel has booted up with)
*/
unsigned long span[0];
#ifndef __GENKSYMS__
/* CONFIG_SCHEDSTATS */
/* load_balance() stats */
unsigned int lb_count[CPU_MAX_IDLE_TYPES];
unsigned int lb_failed[CPU_MAX_IDLE_TYPES];
unsigned int lb_balanced[CPU_MAX_IDLE_TYPES];
unsigned int lb_imbalance[CPU_MAX_IDLE_TYPES];
unsigned int lb_gained[CPU_MAX_IDLE_TYPES];
unsigned int lb_hot_gained[CPU_MAX_IDLE_TYPES];
unsigned int lb_nobusyg[CPU_MAX_IDLE_TYPES];
unsigned int lb_nobusyq[CPU_MAX_IDLE_TYPES];
/* Active load balancing */
unsigned int alb_count;
unsigned int alb_failed;
unsigned int alb_pushed;
/* SD_BALANCE_EXEC stats */
unsigned int sbe_count;
unsigned int sbe_balanced;
unsigned int sbe_pushed;
/* SD_BALANCE_FORK stats */
unsigned int sbf_count;
unsigned int sbf_balanced;
unsigned int sbf_pushed;
/* try_to_wake_up() stats */
unsigned int ttwu_wake_remote;
unsigned int ttwu_move_affine;
unsigned int ttwu_move_balance;
#endif /* __GENKSYMS__ */
};
```
struct sched_domain: 代表一个 Scheduling Domain，也就是一个 CPU 集合，这个集合里所有的 CPU 都具有相同的属性和调度策略。 Load Balance 是针对每个 domain 里的 CPU 进行的。这里要注意 Scheduling Domains 是分级的。像上节所讲的复杂系统就分为 Allnuma_domain,Numa_domain, Phy_domain, Core_domain, Smt_domain(Cpu_domain) 五个等级。
### 调度组
```
struct sched_group {
struct sched_group *next; /* Must be a circular list */
atomic_t ref;
unsigned int group_weight;
struct sched_group_power *sgp;
/*
* The CPUs this group covers.
*
* NOTE: this field is variable length. (Allocated dynamically
* by attaching extra space to the end of the structure,
* depending on how many CPUs the kernel has booted up with)
*/
unsigned long cpumask[0];
};
```
struct sched_group: 每个 Scheduling domain 都有一个或多个 CPU group，每个 group 都被 domain 当做一个单独的单元来对待。 Load Balance 就是在这些 CPU group 之间的 CPU 进行的。
### 举个例子
假设每个CPU只有两个核，每个核只有两个逻辑CPU。
物理CPU示意图：
系统启动时，会分别把每个核的两个逻辑 CPU 放入一个 Scheduling Domain，
这个级别的 domain 叫做 cpu_domain 。其中每个 domain 包括两个 CPU groups，每个 CPU group 只有一个逻辑 CPU 。
逻辑CPU：
同时每个物理 CPU 的两个核被放入一个高一级的 Scheduling Domain 。这个 domain 命名为 core_domain 。其中每个 domain 包括两个 CPU groups，每个 CPU group 有两个逻辑 CPU 。如下图所示：
对于我们前述的复杂系统，再往上的话依次还有 phys_domain( 物理 CPU 放入的 domain)
### load balance原则
每个 Scheduling Domain 都包含一些重要的信息用来决定在这级 domain 的 CPU groups 之间如何进行 Load Balance 。
典型的一些原则如下：
- 在 cpu_domain 级： 因为是共享 cache，cpu_power 也基本是共用的。所以可以在这个 domain 级的 cpu groups - 之间可以不受限制的进行 load balance 。
- 在 core_domain 级：可能会共享 L2 级 cache, 具体跟实现相关了。因此这一级的 balance 相对没那么频繁。要 core 之间负载的不平衡达到一定程度才进行 balance 。
- 在 phys_domain 级：在这一个 domain 级，如果进行 balance 。则每个物理 CPU 上的 Cache 会失效一段时间，并且要考虑 cpu_power，因为物理 CPU 级的 power 一般是被数关系。比如两个物理 CPU 是 power*2，而不像 core, 或逻辑 CPU，只是 power*1.1 这样的关系。
- 在 numa_domain 级：这一级的开销最大，一般很少进行 balance 。
### 内核代码
CPU定时器调用scheduler_tick()的时候会调用trigger_load_balance()，如果cpu的当前runqueue收到下一个rebalancing event的时候它将会触发一个软中断。
>start_kernel->sched_init->init_sched_fair_class->run_rebalance_domains->rebalance_domains->load_balance
scheduler_tick->trigger_load_balancd->raise_softirq(SCHED_SOFTIRQ)
该中断的响应函数就是run_rebalance_domains->rebalance_domains
```
__init void init_sched_fair_class(void)
{
#ifdef CONFIG_SMP
open_softirq(SCHED_SOFTIRQ, run_rebalance_domains);
#ifdef CONFIG_NO_HZ_COMMON
nohz.next_balance = jiffies;
zalloc_cpumask_var(&nohz.idle_cpus_mask, GFP_NOWAIT);
cpu_notifier(sched_ilb_notifier, 0);
#endif
#endif /* SMP */
}
```
定时器中断处理函数会调用update_process_times来更新进程时间。update_process_times会调用scheduler_tick.
```
/*
* This function gets called by the timer code, with HZ frequency.
* We call it with interrupts disabled.
*/
void scheduler_tick(void)
{
int cpu = smp_processor_id();
struct rq *rq = cpu_rq(cpu);
struct task_struct *curr = rq->curr;
sched_clock_tick();
raw_spin_lock(&rq->lock);
update_rq_clock(rq);
update_cpu_load_active(rq);
curr->sched_class->task_tick(rq, curr, 0);
raw_spin_unlock(&rq->lock);
perf_event_task_tick();
#ifdef CONFIG_SMP
rq->idle_balance = idle_cpu(cpu);
trigger_load_balance(rq, cpu);
#endif
rq_last_tick_reset(rq);
}
```
```
/*
* Trigger the SCHED_SOFTIRQ if it is time to do periodic load balancing.
*/
void trigger_load_balance(struct rq *rq, int cpu)
{
/* Don't need to rebalance while attached to NULL domain */
if (time_after_eq(jiffies, rq->next_balance) &&
likely(!on_null_domain(cpu)))
raise_softirq(SCHED_SOFTIRQ);
#ifdef CONFIG_NO_HZ_COMMON
if (nohz_kick_needed(rq, cpu) && likely(!on_null_domain(cpu)))
nohz_balancer_kick(cpu);
#endif
}
```
## Ref
http://cenalulu.github.io/linux/numa/
