[TOC]
## NUMA
### 為什么要有NUMA
在NUMA架構(gòu)出現(xiàn)前，CPU歡快的朝著頻率越來越高的方向發(fā)展。受到物理極限的挑戰(zhàn)，又轉(zhuǎn)為核數(shù)越來越多的方向發(fā)展。即SMP架構(gòu)（對稱多處理器結(jié)構(gòu)）。如果每個(gè)core的工作性質(zhì)都是share-nothing（類似于map-reduce的node節(jié)點(diǎn)的作業(yè)屬性），那么也許就不會有NUMA。<font color=red>由于所有CPU Core都是通過共享一個(gè)北橋來讀取內(nèi)存</font>，隨著核數(shù)如何的發(fā)展，北橋在響應(yīng)時(shí)間上的性能瓶頸越來越明顯。于是，聰明的硬件設(shè)計(jì)師們，想到了把內(nèi)存控制器（原本北橋中讀取內(nèi)存的部分）也做個(gè)拆分，平分到了每個(gè)die上[什么是die](https://zhuanlan.zhihu.com/p/51354994)。于是NUMA就出現(xiàn)了。
### NUMA是什么
在NUMA架構(gòu)中有多個(gè)CPU模塊，每個(gè)CPU模塊由多個(gè)CPU組成，并且具有獨(dú)立的本地內(nèi)存、I/O槽口等。由于其節(jié)點(diǎn)之間可以通過互聯(lián)模塊（如稱為Crossbar Switch）進(jìn)行連接和信息交互，因此每個(gè)CPU可以訪問整個(gè)系統(tǒng)的內(nèi)存。顯然，訪問本地內(nèi)存的速度將遠(yuǎn)遠(yuǎn)高于訪問遠(yuǎn)地內(nèi)存（系統(tǒng)內(nèi)其它節(jié)點(diǎn)的內(nèi)存）的速度，這也是非一致內(nèi)存訪問的由來。NUMA（Non-Uniform Memory Access）就此得名。
## CPU
從操作系統(tǒng)的視角來看，CPU可以劃分為幾個(gè)不同的層級，從大到小依次為NUMA 節(jié)點(diǎn)，物理CPU，CPU core，邏輯cpu。 core，邏輯cpu(core上的超線程)。在/proc/cpuinfo中可以查看cpu的相關(guān)信息。或者通過lscpu命令。
> 判斷依據(jù)：
1.具有相同core id的cpu是同一個(gè)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個(gè)數(shù)
cat /proc/cpuinfo | grep "processor" | wc -l
echo "physical CPU number:"
#物理CPU個(gè)數(shù)：
cat /proc/cpuinfo | grep "physical id" | sort -u | wc -l
echo "core number in a physical CPU:"
#每個(gè)物理CPU中Core的個(gè)數(shù)：
cat /proc/cpuinfo | grep "cpu cores" | uniq | awk -F: '{print $2}'
#查看core id的數(shù)量,即為所有物理CPU上的core的個(gè)數(shù)
cat /proc/cpuinfo | grep "core id" | uniq |? wc -l
#是否為超線程？
#如果有兩個(gè)邏輯CPU具有相同的”core id”，那么超線程是打開的?；蛘遱iblings數(shù)目比cpu cores數(shù)目大。
#每個(gè)物理CPU中邏輯CPU(可能是core, threads或both)的個(gè)數(shù)：
cat /proc/cpuinfo | grep "siblings"
/proc/cpuinfo 文件包含系統(tǒng)上每個(gè)處理器的數(shù)據(jù)段落。/proc/cpuinfo 描述中有 6 個(gè)條目適用于多內(nèi)核和超線程（HT）技術(shù)檢查：processor, vendor id, physical id, siblings, core id 和 cpu cores。
processor 條目包括這一邏輯處理器的唯一標(biāo)識符。
physical id 條目包括每個(gè)物理封裝的唯一標(biāo)識符。
core id 條目保存每個(gè)內(nèi)核的唯一標(biāo)識符。
siblings 條目列出了位于相同物理封裝中的邏輯處理器的數(shù)量。
cpu cores 條目包含位于相同物理封裝中的內(nèi)核數(shù)量。
如果處理器為英特爾處理器，則 vendor id 條目中的字符串是 GenuineIntel。
### 與操作系統(tǒng)的關(guān)系
由于硬件工程師的不懈努力，設(shè)計(jì)了如此復(fù)雜的硬件結(jié)構(gòu)，操作系統(tǒng)必須對如此復(fù)雜的硬件結(jié)構(gòu)形成完成的拓?fù)潢P(guān)系圖以及復(fù)雜的調(diào)度訪問算法來充分利用硬件的性能。所以這個(gè)鍋必須硬件工程師來背。。。
Linux對NUMA系統(tǒng)的物理內(nèi)存分布信息是從系統(tǒng)firmware的ACPI表中獲得的，最重要的是SRAT（System Resource Affinity Table）和SLIT（System Locality Information Table）表，其中SRAT包含兩個(gè)結(jié)構(gòu)：
-Processor Local APIC/SAPIC Affinity Structure：記錄某個(gè)CPU的信息；
-Memory Affinity Structure：記錄內(nèi)存的信息；
SLIT表則記錄了各個(gè)結(jié)點(diǎn)之間的距離，在系統(tǒng)中由數(shù)組node_distance[ ]記錄。
Linux采用Node、Zone和頁三級結(jié)構(gòu)來描述物理內(nèi)存的，如圖所示：
## NUMA調(diào)度器
NUMA系統(tǒng)中，由于局部內(nèi)存的訪存延遲低于遠(yuǎn)地內(nèi)存訪存延遲，因此將進(jìn)程分配到局部內(nèi)存附近的處理器上可極大優(yōu)化應(yīng)用程序的性能。Linux 2.4內(nèi)核中的調(diào)度器由于只設(shè)計(jì)了一個(gè)運(yùn)行隊(duì)列，可擴(kuò)展性較差，在SMP平臺表現(xiàn)一直不理想。當(dāng)運(yùn)行的任務(wù)數(shù)較多時(shí)，多個(gè)CPU增加了系統(tǒng)資源的競爭，限制了負(fù)載的吞吐率。在2.5內(nèi)核開發(fā)時(shí)，Ingo Molnar寫了一個(gè)多隊(duì)列調(diào)度器，稱為O(1)，從2.5.2開始O(1)調(diào)度器已集成到2.5內(nèi)核版本中。O(1)是<font color=red>多隊(duì)列調(diào)度器，每個(gè)處理器都有一條自己的運(yùn)行隊(duì)列，</font>但由于O(1)調(diào)度器不能較好地感知NUMA系統(tǒng)中結(jié)點(diǎn)這層結(jié)構(gòu)，從而不能保證在調(diào)度后該進(jìn)程仍運(yùn)行在同一個(gè)結(jié)點(diǎn)上，為此，Eirch Focht開發(fā)了結(jié)點(diǎn)親和的NUMA調(diào)度器，它是建立在Ingo Molnar的O(1)調(diào)度器基礎(chǔ)上的，Eirch將該調(diào)度器向后移植到2.4.X內(nèi)核中，該調(diào)度器最初是為基于IA64的NUMA機(jī)器的2.4內(nèi)核開發(fā)的，后來Matt Dobson將它移植到基于X86的NUMA-Q硬件上。
### Linux下的CPU拓?fù)浣Y(jié)構(gòu)
如前所述，CPU的物理架構(gòu)如此復(fù)雜，調(diào)度器要解決的一個(gè)首要問題就是如何發(fā)揮這么多 CPU 的性能，使得負(fù)載均衡。不存某些 CPU 一直很忙，進(jìn)程在排隊(duì)等待運(yùn)行，而某些 CPU 卻是處于空閑狀態(tài)。但是在這些 CPU 之間進(jìn)行 Load Balance 是有代價(jià)的，比如對處于兩個(gè)不同物理 CPU 的進(jìn)程之間進(jìn)行負(fù)載平衡的話，將會使得 Cache 失效。造成效率的下降。而且過多的 Load Balance 會大量占用 CPU 資源。
由于進(jìn)程的遷移是基于cpu的，而cpu最小級別的就是超線程處理器的一個(gè)smt核，次小的一級就是一個(gè)多核cpu的核，然后就是一個(gè)物理cpu封裝，再往后就是cpu陣列，根據(jù)這些cpu級別的不同，<font color=red>Linux將所有同一級別的cpu歸為一個(gè)“調(diào)度組”，然后將同一級別的所有的調(diào)度組組成一個(gè)“調(diào)度域”，</font> 負(fù)載均衡首先在調(diào)度域的各個(gè)調(diào)度組之間進(jìn)行，然后再在最低一級的cpu上進(jìn)行，注意負(fù)載均衡是基于最小一級的cpu的。整個(gè)架構(gòu)如下圖所示：
Linux下將物理cpu映射成如上的樹形結(jié)構(gòu)，load balance就是針對Scheduling domain的。從葉節(jié)點(diǎn)往上遍歷。直到所有的 domain 中的負(fù)載都是平衡的。當(dāng)然對不同的 domain 會有不同的策略識別是否負(fù)載不平衡，以及不同的調(diào)度策略。通過這樣的方式，從而很好的發(fā)揮眾多 cpu 的效率。
### 調(diào)度域
```
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: 代表一個(gè) Scheduling Domain，也就是一個(gè) CPU 集合，這個(gè)集合里所有的 CPU 都具有相同的屬性和調(diào)度策略。 Load Balance 是針對每個(gè) domain 里的 CPU 進(jìn)行的。這里要注意 Scheduling Domains 是分級的。像上節(jié)所講的復(fù)雜系統(tǒng)就分為 Allnuma_domain,Numa_domain, Phy_domain, Core_domain, Smt_domain(Cpu_domain) 五個(gè)等級。
### 調(diào)度組
```
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: 每個(gè) Scheduling domain 都有一個(gè)或多個(gè) CPU group，每個(gè) group 都被 domain 當(dāng)做一個(gè)單獨(dú)的單元來對待。 Load Balance 就是在這些 CPU group 之間的 CPU 進(jìn)行的。
### 舉個(gè)例子
假設(shè)每個(gè)CPU只有兩個(gè)核，每個(gè)核只有兩個(gè)邏輯CPU。
物理CPU示意圖：
系統(tǒng)啟動時(shí)，會分別把每個(gè)核的兩個(gè)邏輯 CPU 放入一個(gè) Scheduling Domain，
這個(gè)級別的 domain 叫做 cpu_domain 。其中每個(gè) domain 包括兩個(gè) CPU groups，每個(gè) CPU group 只有一個(gè)邏輯 CPU 。
邏輯CPU：
同時(shí)每個(gè)物理 CPU 的兩個(gè)核被放入一個(gè)高一級的 Scheduling Domain 。這個(gè) domain 命名為 core_domain 。其中每個(gè) domain 包括兩個(gè) CPU groups，每個(gè) CPU group 有兩個(gè)邏輯 CPU 。如下圖所示：
對于我們前述的復(fù)雜系統(tǒng)，再往上的話依次還有 phys_domain( 物理 CPU 放入的 domain)
### load balance原則
每個(gè) Scheduling Domain 都包含一些重要的信息用來決定在這級 domain 的 CPU groups 之間如何進(jìn)行 Load Balance 。
典型的一些原則如下：
- 在 cpu_domain 級： 因?yàn)槭枪蚕?cache，cpu_power 也基本是共用的。所以可以在這個(gè) domain 級的 cpu groups - 之間可以不受限制的進(jìn)行 load balance 。
- 在 core_domain 級：可能會共享 L2 級 cache, 具體跟實(shí)現(xiàn)相關(guān)了。因此這一級的 balance 相對沒那么頻繁。要 core 之間負(fù)載的不平衡達(dá)到一定程度才進(jìn)行 balance 。
- 在 phys_domain 級：在這一個(gè) domain 級，如果進(jìn)行 balance 。則每個(gè)物理 CPU 上的 Cache 會失效一段時(shí)間，并且要考慮 cpu_power，因?yàn)槲锢?CPU 級的 power 一般是被數(shù)關(guān)系。比如兩個(gè)物理 CPU 是 power*2，而不像 core, 或邏輯 CPU，只是 power*1.1 這樣的關(guān)系。
- 在 numa_domain 級：這一級的開銷最大，一般很少進(jìn)行 balance 。
### 內(nèi)核代碼
CPU定時(shí)器調(diào)用scheduler_tick()的時(shí)候會調(diào)用trigger_load_balance()，如果cpu的當(dāng)前runqueue收到下一個(gè)rebalancing event的時(shí)候它將會觸發(fā)一個(gè)軟中斷。
>start_kernel->sched_init->init_sched_fair_class->run_rebalance_domains->rebalance_domains->load_balance
scheduler_tick->trigger_load_balancd->raise_softirq(SCHED_SOFTIRQ)
該中斷的響應(yīng)函數(shù)就是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 */
}
```
定時(shí)器中斷處理函數(shù)會調(diào)用update_process_times來更新進(jìn)程時(shí)間。update_process_times會調(diào)用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/
