SZ神庙

从此开始,遁入幻想

2016年12月9日

Linux 秘术记闻>

Linux上的NUMA初步探索

一.NUMA是什么

随着对计算机计算能力要求的提升,现代计算机已经发展成为多处理器系统(multi-processor computers)。大多数的多处理器系统中的各个处理器是对称的(symmetric),即各个处理器的地位完全相同,称为对称多处理器系统(Symmetric Multi Processors, SMP)。SMP系统中,各个处理器都通过同一条系统总线和内存进行数据交换,这导致总线不堪重负,日益成为性能瓶颈。为了解决这个问题,提出了非一致内存访问技术(Non-Uniform Memory Access, NUMA)。

NUMA的基本思想是,将各个CPU划分为不同的NUMA node。每个node拥有自己的内存,各node访问自己的内存的速度较快。同时,硬件层为各个node之间的数据交互提供交换网络,各node之间交换数据的速度要比读取自己的内存局域数据的速度要慢很多。如下图所示。

%e5%9b%be%e7%89%871二.Linux对NUMA的支持

NUMA架构改善了系统总线的瓶颈问题,在服务器端得到了广泛的应用。作为服务器端最受欢迎的操作系统之一,Linux对NUMA提供了越来越完善的支持。

对于Linux来说,要支持NUMA,就要解决以下几个问题:

  • 建立描述系统拓扑的数据结构,即系统必须知道哪个cpu属于哪个node,node之间的连接关系等。
  • 让跨node数据交换的开销最小化。
  • 提出一个内存分配策略。
  • 针对NUMA架构设计调度器。

本文接下来将分别从这几个方面讨论Linux对NUMA支持的具体做法。

三.NUMA拓扑结构

3.1 node和cpu

NUMA拓扑结构中最基本的元素就是node。一个node通常包含有CPU、内存块和IO总线。一个cpu只能属于一个node。系统使用如下函数查找给定的cpu所属的node:

每个node包含一组cpu。Linux使用cpu位图来描述一个node包含的cpu。cpu位图定义如下:

Linux使用cpumask_of_node()这个API取得给定node的cpumask。在不同硬件架构下该函数的实现并不一样。在x86架构下,系统维护一个node_to_cpu_mask全局数组,实现如下:

此外,Linux还提供了以下这些和设置、查询CPU和node关系的API:

3.2 内存管理结构

Linux NUMA中采用node、zone、页三级结构来描述物理内存。在非NUMA架构的系统中,zone被用来描述那些无法进行DMA(Direct Memory Access)的内存区域。一个node可能有多个zone,每个zone有多个page。

Linux采用pg_data_t结构体描述node。该结构体的简化版定义如下:

可见,node里面主要包含了zone、page的信息,以及一些供调度使用的信息,如等待队列等。

zone包含的信息与此类似,主要包含了该zone所属的node信息、zone包含的page信息等。简化版定义如下:

3.3 拓扑信息的初始化

为了能够对CPU、内存分配等进行优化,Linux必须知道底层的NUMA硬件拓扑,也就是哪些CPU在哪些node上等等。这些物理拓扑信息是由高级配置与电源接口(Advanced Configuration and Power Interface,ACPI)描述的。ACPI是由Compaq、Intel、Microsoft、Phoenix和Toshiba联合制定的BIOS规范,它定义了一个非常广泛的配置和电源管理。

Linux从系统的firmware中的ACPI表来获取底层NUMA拓扑信息。其中最重要的是SRAT(System Resource Affinity Table)和SLIT(System Locality Information Table)表。SRAT表记录了哪些CPU、内存在哪些node上,而SLIT则记录了node之间的distance。

Distance是node之间通信的延时的度量。两个node间的distance越大,则它们之间传输数据的延时就越大。各node间的distance组成一个distance matrix,如下例所示。假设各结点到自身的distance是10。

%e5%9b%be%e7%89%871

其distance matrix如下:

四.NUMA 调度器

4.1  O(1)调度器及其改进

对于进程来说,如果能够保持其运行在在进程已经分配的内存的node上,那么访存效率就可以做到最大化。Linux的NUMA调度正是采用的这个策略。

对非NUMA的机器来说,调度器通常采用的是O(1)算法。该算法为每个处理器设置了一个等待队列,并实现了一个O(1)的在队列中搜索下一个执行的任务的算法。O(1)调度器解决了多个CPU争抢资源的问题,然而它不能感知NUMA拓扑结构,因而不能保证进程在调度之后仍然运行在同一个node上。

Erich Focht在O(1)调度器的基础上进行了改进,使之能够感知到NUMA的拓扑结构。他在task_struct上新增了一个int node字段, 用来指示进程的homenode。homenode是指进程最初分配的内存所在的node,由于内存不能在node间迁移,因此进程应当尽可能的在其homenode上执行。这样,选择进程的homenode,也就是选择进程的初始内存分配在哪个node上就是一个关键的问题。

选择homenode实际上就是扫描当前所有node的负载量,然后选择一个最合适的node,因此也叫initial node balancing。这个时机可以发生在fork()中,也可以发生在exec()中。在fork()中进行balancing的好处是保证多线程任务也能够做到各node负载量大体均衡,但劣势是开销大,因为即使是一个只执行很短代码的小线程也会触发balancing,更可能引起进程跨node迁移。而在exec()中进行balancing可以避免这种小线程带来开销,但长期运行的多线程程序可能会导致各node负载的不均衡。

Erich算法中一共提供了三种balance方案,它们由task_struct中的int node_policy字段决定:

node_policy = 0 : 在exec()中进行balance。

node_policy = 1 : 当子线程有自己的新mm结构时,在fork()中进行balance。

node_policy = 2 : 总是在fork()中进行balance。

在具体实现上,使用static atomic_t node_nr_running[MAX_NUMNODES]数组来记录每个node上运行的task数目。使用如下三个函数来进行调度:

sched_best_cpu() : 返回负载最小的node上负载最小的cpu。

sched_migrate_task() : 将task迁移至指定的cpu上。

sched_balance_exec() : 该函数由do_execve()调用,将当前task迁移至负载最小的cpu上。

4.2 动态负载均衡

前一小节介绍的关于homenode的设置属于初始负载均衡。事实上,即使初始负载均衡做的比较好,但经过一段时间的运行,系统中仍然可能出现负载不均衡的情况。对于SMP系统来说,这时就有必要进行动态负载均衡,将负载较大的CPU上的一些task迁移到空闲CPU上。

对于NUMA架构的系统来说,动态均衡意味着进程可能跨node迁移,但由于内存并不会跟着一起迁移,所以就会带来较大的访存开销。这是负载均衡策略中需要考虑到的。

目前最新版本内核(4.8)中,负载均衡的方法和Erich算法并不完全一致。在当前版本的内核中,调度是通过调度域调度组来进行的。调度组是一组cpu的集合,而调度域则包含一组调度组。调度域定义如下:

调度域的简化版定义如下:

在4.8版本的内核中,系统通过在时钟中断中调用scheduler_tick()函数来进行负载均衡,后者调用trigger_load_balance()函数。代码如下:

而trigger_load_balance()函数调用load_balance()函数,后者进行实际的负载均衡。load_balance()首先找出当前调度域中负载最大的调度组,然后找出其所有CPU中负载最大的执行队列。然后,从负载最大的调度队列上迁移一些任务到当前CPU的执行队列中。detach_task()函数会遍历负载最大的执行队列上的task,然后按一定规则选取一些任务,这些任务写入env变量的tasks队列中,再由attach_task()函数迁移到当前执行队列上:

可见,调度组在动态负载均衡中扮演重要角色。事实上,在NUMA系统中,每个node上的cpu组成一个调度组,而整个机器作为一整个调度域,它是所有调度组的父调度域。调度组和调度域的设计还使得多级NUMA调度成为可能,系统可以在一个node内部设计多个子调度组。

五. NUMA内存分配策略

内存分配策略,指的是NUMA从哪个node上给当前的task分配内存。在NUMA中,每个task都可以拥有自己的内存分配策略。

一个很自然的想法是,既然跨node访存的延时较大,那么我们应该尽量让所有task都在自己所在node上分配内存。事实上,NUMA中最常见的两种分配策略是这样的:

  • Node Local. 只在task所在node上分配内存。
  • Interleave. 在两个node间交替式的分配内存。例如,第一页分配在node 0上,第二页分配在node 1上,第三页又分配在node 0上,以此类推。这主要是用于一些多处理器共享的数据结构分配。

NUMA内存分配策略由一个mode、一组标志位和一组node组成。其中,mode定义了内存分配策略的主要行为。mode一共有以下几种:

  • Default Mode这意味着使用系统全局内存分配策略。
  • MPOL_BIND. 这表示将只从策略指定的一组node上分配内存。系统将从这组node中选择一个内存充足而又最靠近当前task所在node的node。
  • MPOL_PREFERRED. 这表示将只从策略指定的某一个prefered node上分配内存。仅当该node上分配失败时,系统才会搜索其他的node。搜索顺序是从离prefered node最近到最远。如果prefered node为task所在node,这事实上就是Node Local策略。
  • MPOL_INTERLEAVED. 即前面所说的Interleave策略。

在内核中,内存分配策略的数据结构如下:

可以使用set_mempolicy()和get_mempolicy两个API来获取和设置task的内存分配策略。

六. 小结

本文主要从拓扑结构、调度策略、内存分配策略三个方面对Linux上的NUMA技术进行了讨论分析。随着SMP架构的机器在服务端的大量普及,NUMA成为大势所趋。Linux对NUMA的支持也是经过了一个时期的发展进步。相信未来这些技术还会有更多的提升。

参考资料

[1] Matthew Dobson, Patricia Gaughen, Michael Hohnbaum, Erich Focht, “Linux Support for NUMA Hardware”, Linux Symposium 2003

[2] Christoph Lameter, “NUMA (Non-Uniform Memory Access): An Overview”, http://queue.acm.org/detail.cfm?id=2513149

[3] Erich Focht, “Node affine NUMA scheduler”, http://home.arcor.de/efocht/sched/

[4] The Linux Kernel Archives, “numa ” , https://www.kernel.org/doc/Documentation/vm/numa

[5] The Linux Kernel Archives, “Kernel NUMA memory policy” , https://www.kernel.org/doc/Documentation/vm/numa_memory_policy.txt