一、 前言
非一致性内存访问（Non-Uniform Memory Access）结构是分布式共享内存（Distributed Shared Memory）体系结构的主要分支，它通过结合分布式内存技术和单一系统映像（SSI）技术，实现了SMP 系统的易编程性和 MPP系统的易扩展性的折中，已成为当今高性能服务器的主流体系结构之一。目前国外著名的服务器厂商都先后推出了基于 NUMA 架构的高性能服务器，如HP的Superdome、SGI 的 Altix 3000、Origin 3000、IBM 的 x440、NEC 的 TX7、AMD 的Opteron 等。
随着NUMA架构的高性能服务器被逐渐推广，系统软件针对这种分布式共享内存架构的特点，在调度器、存储管理和用户级接口等方面进行了大量的优化工作。例如，SGI的Origin 3000 ccNUMA系统在许多领域得到了广泛应用，是个非常成功的系统，为了优化Origin 3000的性能，SGI的IRIX操作系统在其上实现了CpuMemSets，通过将应用与处理器和内存的绑定，充分发挥NUMA系统本地访存的优势。Linux社区在自己的NUMA项目中也实现了CpuMemSets，并且在SGI的Altix 3000的服务器中得到实际应用。
本文将以 SGI 的 ProPack v2.2 为研究对象，分析 CpuMemSets 在Linux-2.4.20 中的具体实现。CpuMemSets 是 SGI 进行的一个开放源码项目，由针对 Linux2.4 内核的补丁、用户库、python 模块和 runon 等命令共四部分组成，以实现处理器和内存块的分区为目标，控制系统资源（处理器、内存块）面向内核、任务以及虚拟存储区的分配，为 dplace、RunOn 等 NUMA 工具提供支持，最终优化 Linux 系统的 NUMA 性能。
二、 相关工作
分区技术（Partition）最初出现在大型机（MainFrame）上，如今被广泛应用到服务器领域，支持在单个服务器上运行一个操作系统的多个实例或者多个操作系统的多个实例，主要特点是"机器独立、屏障可靠、单点管理"。在分区技术支持下，当前多台服务器运行的多个操作系统就可以在同一地点的一台服务器上同时运行，优于在一个组织中四处分散用多个服务器来支持不同的操作系统，从而有效地实现了服务器整合。支持分区技术的服务器可以当作应用服务器，运行Windows平台供市场部门使用；同时还可以运行Linux系统供工程部门使用。还可以在大多数用户运行Windows 2000 Advanced Server系统的同时，在另一个分区中为发展组测试其它操作系统；或者所有节点都应用在一个操作系统环境下。各种分区实现技术的主要差别体现在分区故障隔离手段（硬件或软件）、分区资源粒度、分区资源灵活性以、虚拟分区资源以及对动态分区重构的支持等方面。典型的有IBM的LPAR和DLAPAR（AIX 5L 5.1）、HP的nPartitions和vPartitions（HP-UX 11i）、SUN的Dynamic Domains（Solaris 8）、以及Compaq的Alpha Servers（Tru64 Unix 5.1）。但是，针对NUMA系统采用的分区技术与NUMA系统本身具有的单系统映像优势是矛盾的。
从用户的角度来看，NUMA系统提供了对本地主存和远程主存访问的透明性；但是，从性能的角度来看，由于存储模块物理上分布在不同的节点引起的存储访问延迟不一致现象，对系统的性能也带来了较大的影响。在这类系统中，一个节点对远程节点存储访问的延迟通常比本地访问延迟高1到2个数量级。页迁移与页复制是对数据进行动态局部性优化的主要方法之一。其实质是一种预测技术，根据收集到的信息预测将来对页面的访问情况，然后作出迁移或复制页面的决策。采用适当的页复制与页迁移策略可以减小cache容量和冲突失效，平衡远程和本地访问延迟的不一致，达到优化NUMA系统性能的目的。但是现有的页迁移与页复制策略大都过分依赖于体系结构和特殊的硬件支持，开销比较大，通用性也不好。
在NUMA结构的多处理器系统中，一个任务可以在任何一个处理器上运行，然而任务在各种情况的执行会被中断；被中断的任务在恢复执行的时候，如果选择恢复在另外一个处理器上执行，就会导致它失去原有的处理器cache数据。我们知道，访问cache数据只需要几个纳秒，而访问主存需要大约50纳秒。这时处理器运行的速度处在访问主存的级别上，直到任务运行了足够的时间，任务运行所需要的数据重新充满该处理器的cache为止。为解决这个问题，系统可以采用处理器亲近调度策略调度每个节点上的任务：系统记录下最后执行这个任务的处理器并维持这种关系，在恢复执行被中断的任务时，尽量恢复在最后执行这个任务的处理器上执行。但是，由于应用程序的特点各有不同，而且工作集具有动态属性，处理器亲近调度的作用是有限的。
用户是系统的使用者，也是性能的评判者，他们最清楚应用对系统的需求和评价指标。在一个大的NUMA系统中，用户往往希望控制一部分处理器和内存给某些特殊的应用。CpuMemSets允许用户更加灵活的控制（它可以重叠、划分系统的处理器和内存），允许多个进程将系统看成一个单系统映像，并且不需要重启系统，保障某些处理器和内存资源在不同的时间分配给指定的应用；也是对分区技术、页迁移和亲近调度策略的有益补充。
三、 系统实现
在介绍CpuMemSets在Linux-2.4.20中的具体实现之前，我们首先说明CpuMemSets涉及的几个基本概念，包括：
处理器：指承载任务调度的物理处理器，但是不包括DMA设备、向量处理器等专用处理器；
内存块：在SMP、UP系统中，所有的内存块与所有处理器的距离相等，因此不存在差别；但是在NUMA系统中，可以按照与处理器的距离对内存块划分等价类。此外，CpuMemSets不考虑具有速度差异的特殊存储器，如输入输出设备缓存、帧缓存等。
任务：一个任务，在任一时刻，或者等待事件、资源，或者被中断，或者在处理器上运行。
虚拟存储区：内核为每个任务维护的多个虚拟地址区域，可为多个任务共享。位于虚拟存储区内的页，或者没有分配，或者已分配但被换出，或者已分配且在内存中。可以指定允许分配给某个虚拟存储区的内存块以及分配顺序。
CpuMemSets为Linux提供了将系统服务和应用绑定在指定的处理器上进行调度、在指定的结点上分配内存的机制。CpuMemSets在已有的Linux调度和内存分配代码基础上增加了cpumemmap（cmm）和cpumemset（cms）两层结构，底层的cpumemmap层提供一个简单的映射对，实现系统的处理器号与应用的处理器号、系统的内存块号与应用的内存块号的映射。这种映射不一定是单射，一个系统号可以对应多个应用号。上层的cpumemset层负责说明允许把任务调度到哪些应用处理器号所对应的处理器上运行、可以从哪些应用内存块号所对应的内存块中为相应的内核或虚拟存储区分配内存页，也就是说，指定可供内核、任务、虚拟存储区使用的资源集合。在这种两层结构中，资源的系统号供内核执行调度和内存分配时使用；而资源的应用号供用户进程指定本应用的资源集合时使用。系统号在启动期间全系统范围内有效，而应用号仅仅相对于共享同一个cmm的所有用户进程有效。而且，由于负载平衡和热插拔引发的资源物理编号的变化对应用号是不可见的。
Linux的进程调度和内存分配在保持现有代码正常运转的基础上，添加了对CpuMemSets的支持，使用"系统处理器号"和"系统内存块号"以及其他数据结构如cpus_allowed和mems_allowed等实现资源的分区。此外，CpuMemSets的API提供了对cpusets、dplace、runon、psets、MPI、OpenMP、nodesets的支持，并且提供/proc接口以显示cmm和 cms的结构、设置以及与任务、虚拟存储区、内核的连接关系、系统资源号和应用资源号等信息。下面我们分别对cpumemmap和cpumemset、进程调度和内存分配、以及API这三个部分进行详细分析：
3.1 cmm&cms
3.1.1 数据结构
cpumemmap和cpumemset的数据结构如下所示，具体定义在include/linux/cpumemset.h中。Cpumemmap中的scpus和smems域分别指向一组系统处理器号和一组系统内存块号，实现应用的资源号（数组下标）与系统的资源号（数组元素值）的映射。Cpumemset中的acpus域指向一组应用处理器号，而amems域指向一组cms_memory_list_t类型的内存块列表。每个内存块列表描述了一组应用内存块号（mems）以及享有该列表的一组应用处理器号（cpus）。内存块分配策略由cpumemset中的policy域决定，缺省使用本地优先方式。Cpumemset通过cmm域与相应的cpumemmap建立关联。两个数据结构中的counter域的作用将在后文介绍。
【include/linux/cpumemset.h】
84 typedef struct cpumemmap {
85 int nr_cpus; /* number of cpus in map */
86 int nr_mems; /* number of mems in map */
87 cms_scpu_t *cpus; /* array maps application to system cpu num */
88 cms_smem_t *mems; /* array maps application to system mem num */
89 atomic_t counter; /* reference counter */
90 } cpumemmap_t;
92 typedef struct cpumemset {
93 cms_setpol_t policy; /* CMS_* policy flag ：Memory allocation policy */
94 int nr_cpus; /* Number of cpus in this CpuMemSet */
95 int nr_mems; /* Number of Memory Lists in this CpuMemSet */
96 cms_acpu_t *cpus; /* The 'nr_cpus' app cpu nums in this set */
97 cms_memory_list_t *mems; /* Array 'nr_mems' Memory Lists */
98 unsigned long mems_allowed; /* memory_allowed vector used by vmas */
99 cpumemmap_t *cmm; /* associated cpumemmap */
100 atomic_t counter; /* reference counter */
101 } cpumemset_t;
76 typedef struct cms_memory_list {
77 int nr_cpus; /* Number of cpu's sharing this memory list */
78 int nr_mems; /* Number of memory nodes in this list */
79 cms_acpu_t *cpus; /* Array of cpu's sharing this memory list */
80 cms_amem_t *mems; /* Array of 'nr_mems' memory nodes */
81 } cms_memory_list_t;
以一个包含四个节点的NUMA系统为例简单说明上述数据结构的使用。假设每个节点由四个节点和一个内存块组成，16个处理器的系统号依次是：c0（0）、c1（1）、… …、c15（15），4个内存块的系统号依次是mb0（0）、mb1（1）、mb2（2）、mb3（3）。构造一个只包含第2和第3节点的处理器和内存块cpumemmap，并且把某个应用绑定在奇数号的处理器上，同时以本地优先的方式分配内存块。数据结构如图1所示：
图1 CpuMemSets的数据结构使用示例
javascript:if(this.width>screen.width-600)this.style.width=screen.width-600;">
3.1.2 基本操作
多个任务可以同时对指定的cms&cmm执行访问、挂接、释放或替换的操作。这些操作都是通过下列例程执行：
javascript:if(this.width>screen.width-600)this.style.width=screen.width-600;">
句柄结构定义如下：
【include/linux/cpumemset.h】
417 typedef struct cmshandle {
418 cpumemset_t *set;
419 cpumemmap_t *map;
420 int error;
421 } cmshandle_t;
上述例程通过锁机制以及对cmm&cms中的引用计数counter的管理，保证了对CpuMemSets进行并行操作的完整性。每个cms中的counter记录着：使用者的引用计数（指向这个cms的任务、虚拟存储区、内核总数）和句柄的引用计数（临时指向这个cms的句柄的总数）。每个cmm中的counter记录着：cms的引用计数（指向这个cmm的cms总数）和句柄的引用计数（临时指向这个cmm的句柄的总数）。
替换CpuMemSets的操作分为下列三个步骤：
1. 调用合适的cmsGetHandle*()安全的获得cms和cmm的句柄；
2. 构造新的cms和cmm；
3. 调用合适的cmsExchange*()安全的更换上述的新旧cms和cmm。
访问任务或虚拟存储区的cms和cmm的操作分为下列三个步骤：
1. 调用合适的cmsGetHandle*()安全的获得cms和cmm的句柄；
2. 调用cms和cmm，此期间无法保证原来的任务或虚拟存储区仍然使用这些cms和cmm；
3. 调用cmsRelease()释放句柄。
挂接、放弃句柄的操作步骤：
1. 调用合适的cmsGetHandle*()或cmsNewHandle*()安全的获得cms和cmm的句柄；
2. 调用合适的cmsAttachNew*()或cmsDiscard()。
3.1.3 基本设置
内核拥有自己的kernel_cms。内核在start_kernel()的开头（build_all_ zonelists()之后，trap_init()之前）首先调用cms_cmm_static_init()为kernel_cms构造静态的初始cmm&cms，其中只包含执行本内核的处理器和所在节点的内存块，并且将kernel_cms -> mems_allowed赋值-1UL，允许内核在cpu_init()过程中使用所有内存块。然后，内核在start_kernel()的结尾执行cms_cmm_init()，创建cmm和cms高速缓存，为kernel_cms构造包含所有处理器和内存块的cmm&cms，并传递给init_task。如果系统启动时设置了cpumemset_minimal参数，则使用的是cms_cmm_static_init()构造的最小集。
每个进程都拥有两个cms：current_cms影响自己的处理器分配和虚拟存储区创建， child_cms继承给由自己fork的子进程。每个新建进程的current_cms和child_cms都继承自父进程的child_cms。
【include/linux/sched.h】
296 struct task_struct {
:
325 cpumask_t cpus_allowed;
:
429 cpumemset_t * current_cms;
430 cpumemset_t * child_cms;
431 /* stash mems_allowed of most recent vma to page fault here */
432 unsigned long mems_allowed;
:
462 };
【kernel/fork.c】
620 int do_fork(unsigned long clone_flags, unsigned long stack_start,
621 struct pt_regs *regs, unsigned long stack_size)
622 {
:
751 SET_CHILD_CMS(p, current);
：
871 }
【include/linux/cpumemset.h】
173 /*
174 * Set child's current, child and alloc cpumemset
175 * from parent's child_cms (used in fork).
176 */
177
178 #define SET_CHILD_CMS(child, parent) do { 179 cpumemset_t *cms = (parent)->child_cms; 180 CMS_TRACE_HOOK("fork task", cms); 181 atomic_inc(&cms->counter); 182 (child)->current_cms = cms; 183 update_cpus_allowed(child); 184 atomic_inc(&cms->counter); 185 (child)->child_cms = cms; 186 } while (0)
每个虚拟存储区都拥有各自的vm_mems_allowed位向量。新建虚拟存储区的vm_mems_ allowed通过cms_current_mems_allowed()继承自创建者任务current_cms的mems_allowed。对于被挂接的已存在的虚拟存储区，如mmap的内存对象和共享内存区，则继承自挂接进程current_cms的mems_allowed。cms的mems_allowed位向量由mems_allowed_build(cms)根据cms中的所有内存块列表来构造。
【include/linux/mm.h】
45 struct vm_area_struct {
：
77 unsigned long vm_mems_allowed; /* cpumemset managed memory placement */
：
81 };
【kernel/cpumemset.c】
1538 static unsigned long
1539 mems_allowed_build(cpumemset_t *cms)
1540 {
1541 int i;
1542 unsigned long mems_allowed = 0;
1543
1544 for (i = 0; i < cms->nr_mems; i++)
1545 mems_allowed |= mems_allowed_value(cms, cms->mems + i);
1546 return mems_allowed;
1547 }
3.2 进程调度及内存分配
内核调用update_cpus_allowed(struct task_struct *p)根据任务的current_cms的处理器列表更改它的cpus_allowed位向量，从而影响该任务的处理器调度。
【kernel/cpumemset.c】
585 void
586 update_cpus_allowed(struct task_struct *p)
587 {
588 #ifdef CONFIG_SMP
589 int i;
590 cpumemset_t *cms = p->current_cms;
591 cpumask_t cpus_allowed = CPU_MASK_NONE;
592
593 for (i = 0; i < cms->nr_cpus; i++)
594 __set_bit(cms->cmm->cpus[cms->cpus[i]], &cpus_allowed);
595 if (any_online_cpu((cpumask_t*)&cpu_online_map) < NR_CPUS) {
：
609 set_cpus_allowed(p, &cpus_allowed);
610 }
611 #endif
612 }
内核根据虚拟存储区的vm_mems_allowed位向量为任务分配内存，如果是在中断上下文中，虚拟存储区的内存分配则依赖于kernel_cms的mems_allowed。宏CHECK_MEMS_ALLOWED(mems_allowed, zone)负责检查zone所在的节点是否落在mems_allowed设定的内存块集合内。
【mm/memory.c】
1383 int handle_mm_fault(struct mm_struct *mm, struct vm_area_struct * vma,
1384 unsigned long address, int write_access)
1385 {
：
1390 /*
1391 * We set the mems_allowed field of the current task as
1392 * the one pointed by the faulting vma. The current
1393 * process will then use the correct mems_allowed mask
1394 * if a new page has to be allocated.
1395 */
1396 if(!in_interrupt())
1397 current->mems_allowed = vma->vm_mems_allowed;
：
1417 }
【mm/page_alloc.c】
334 struct page * __alloc_pages(..)
：
343 if (in_interrupt())
344 mems_allowed = kernel_cms->mems_allowed;
345 else
346 mems_allowed = current->mems_allowed;
347 if (mems_allowed == 0) {
348 printk(KERN_DEBUG "workaround zero mems_allowed in alloc_pages\n");
349 mems_allowed = -1UL;
350 }
：
if(!CHECK_MEMS_ALLOWED(mems_allowed, z))
continue;
：
450 }
【include/linux/cpumemset.h】
194 /* Used in __alloc_pages() to see if we can allocate from a node */
195 #define CHECK_MEMS_ALLOWED(mems_allowed, zone) 196 ((1UL << (zone)->zone_pgdat->node_id) & (mems_allowed))
为虚拟存储区分配页时，如果当前执行该任务的处理器包含在该虚拟存储区的cms中，则从该处理器的内存块列表中分配，否则从该虚拟存储区的cms定义的CMS_DEFAULT_CPU的内存块列表中分配。
3.3 API设计
CpuMemSets提供了一系列的内核级和应用级的编程接口，分别定义在内核的include/linux/cpumemset.h文件和库代码CpuMemSets/cpumemsets.h文件中（如表2所示）。
javascript:if(this.width>screen.width-600)this.style.width=screen.width-600;">
通过调用用户级接口对cmm&cms进行设置将导致内核的调度器和内存分配器所使用的系统位向量如cpus_allowed和mems_allowed的变化，从而使内核调度代码使用新的系统处理器号、内存分配代码从新内存块中分配内存页；但是，原先从旧内存块中分配的内存页将不会发生迁移，除非强制采用其他手段。具体来说，系统在cmsAttachNewTask()、cmsExchangeTask()和cmsExchangePid()过程中，执行update_cpus_allowed()根据任务的current_cms的当前处理器列表更改它的cpus_allowed位向量；在cms_set()过程中，执行mems_allowed_build()根据任务的current_cms的当前内存块列表更改当前虚拟存储区或任务、内核的mems_allowed位向量。
【kernel/cpumemset.c】
1661 static int
1662 cms_set(unsigned long *preq, char *rec, int size, target_option cmm_or_cms)
：
1713 if (choice == CMS_VMAREA) {
：
1772 vma->vm_mems_allowed = mems_allowed_build(newhan.set);
：
1792 } else {
：
1822 newhan.set->mems_allowed = mems_allowed_build(newhan.set);
：
1840 }
:
1842 }
在权限保护方面，只有根权用户才可以修改内核所使用的cms&cmm和任何任务的cms&cmm；而一般用户只能修改自身的任务和虚拟存储区所拥有的cms&cmm；具有相同uid的任务之间可以互相修改对方的cms&cmm。只有根权用户才可以扩展自身的cmm，一般用户只可以缩小自己的cmm。
【kernel/cpumemset.c】
409 cmshandle_t
410 cmsGetHandlePid(int choice, pid_t pid, int do_check_perm)
411 {
：
425 if (pid &&
426 do_check_perm &&
427 (current->euid ^ p->suid) &&
428 (current->euid ^ p->uid) &&
429 (current->uid ^ p->suid) &&
430 (current->uid ^ p->uid) &&
431 !capable(CAP_SYS_ADMIN))
432 han.error = -EPERM;
：
442 }
【kernel/cpumemset.c】
1478 /*
1479 * Unless you have CAP_SYS_ADMIN capability, you can only shrink cmm.
1480 */
1481
1482 static int
1483 cmm_restrict_checking(cpumemmap_t *oldmap, cpumemmap_t *newmap)
1484 {
1485 int i;
1486
1487 if (capable(CAP_SYS_ADMIN))
1488 return 0;
1489
1490 /* newmap must be a subset of oldmap */
1491 for (i = 0; i < newmap->nr_cpus; i++)
1492 if (!foundin (newmap->cpus[i], oldmap->cpus, oldmap->nr_cpus))
1493 return -EINVAL;
1494 for (i = 0; i < newmap->nr_mems; i++)
1495 if (!foundin (newmap->mems[i], oldmap->mems, oldmap->nr_mems))
1496 return -EINVAL;
1497 return 0;
1498 }
四、 使用举例
示例1：显示当前任务current_cms中的处理器
/*
* sample1 - display current cpumemset cpus
*
* Compile with:
* cc sample1.c -o sample1 -lcpumemsets
* Displays on stdout the number and a list of the cpus
* on which the current process is allowed to execute.
*/
#include "cpumemsets.h"
main()
{
int i;
cpumemset_t *pset;
pset = cmsQueryCMS(CMS_CURRENT, (pid_t)0, (void *)0);
if (pset == (cpumemset_t *)0) {
perror("cmsQueryCMS");
exit (1);
}
printf("Current CpuMemSet has %d cpu(s):\n\t", pset->nr_cpus);
for (i = 0; i < pset->nr_cpus; i++)
printf("%s%d", (i > 0 ? ", " : ""), pset->cpus[i]);
printf("0);
exit(0);
}
示例2：设置当前任务的子任务仅运行在0号处理器上，并启动sh运行
/*
* sample2 - change child cpumemset cpus to just cpu 0
*
* Compile with:
* cc sample2.c -o sample2 -lcpumemsets
* Change the cpus which the child task is allowed
* execute on to just cpu 0. Start a subshell,
* instead of just exiting, so that the user has
* the opportunity to verify that the change occurred.
*/
#include
main()
{
int i;
cpumemset_t *pset;
pset = cmsQueryCMS(CMS_CHILD, (pid_t)0, (void *)0);
if (pset == (cpumemset_t *)0) {
perror("cmsQueryCMS");
exit (1);
}
pset->nr_cpus = 1;
free(pset->cpus);
pset->cpus = (cms_acpu_t *) malloc(sizeof(cms_acpu_t));
pset->cpus[0] = (cms_acpu_t)0;
if (cmsSetCMS(
CMS_CHILD, (pid_t)0, (void *)0, (size_t)0, pset) < 0) {
perror ("cmsSetCMS");
exit(1);
}
cmsFreeCMS (pset);
printf ("Invoking subshell running on cpu 0.0);
execl("/bin/sh", "sh", 0);
exit (2);
}
先运行示例2，再运行示例1：
# PS1='Sub> ' ./sample2
Invoking subshell running on cpu 0.
Sub> ./sample1
Current CpuMemSet has 1 cpu(s):
0
Sub> exit
五、 小结
CpuMemSets通过在已有的Linux调度和内存分配代码基础上增加cpumemmap（cmm）和cpumemset（cms）两层结构，为Linux提供了将系统服务和应用绑定在指定的处理器上进行调度、在指定的结点上分配内存的机制。从数据结构和控制机制上看，目前的实现比较简单实用，但是仍然有进一步优化的空间。但是，CpuMemSets仅仅是提供了一套挖掘本地访存优势、优化Linux系统的NUMA性能的机制，如何基于这种支持手段制定合适的NUMA系统优化策略需要进行更多更深入的研究。
