一.背景

所謂物理內存，就是安裝在機器上的，實打實的內存設備（不包括硬件cache），被CPU通過總線訪問。在多核系統中，如果物理內存對所有CPU來說沒有區別，每個CPU訪問內存的方式也一樣，則這種體系結構被稱為Uniform Memory Access(UMA)。

如果物理內存是分布式的，由多個cell組成（比如每個核有自己的本地內存），那么CPU在訪問靠近它的本地內存的時候就比較快，訪問其他CPU的內存或者全局內存的時候就比較慢，這種體系結構被稱為Non-Uniform Memory Access(NUMA)。

以上是硬件層面上的NUMA，而作為軟件層面的Linux，則對NUMA的概念進行了抽象。即便硬件上是一整塊連續內存的UMA，Linux也可將其劃分為若干的node。同樣，即便硬件上是物理內存不連續的NUMA，Linux也可將其視作UMA。

所以，在Linux系統中，你可以基于一個UMA的平臺測試NUMA上的應用特性。從另一個角度，UMA就是只有一個node的特殊NUMA，所以兩者可以統一用NUMA模型表示。

傳統的SMP（對稱多處理器）中，所有處理器都共享系統總線，因此當處理器的數目增大時，系統總線的競爭沖突加大，系統總線將成為瓶頸，所以目前SMP系統的CPU數目一般只有數十個，可擴展能力受到極大限制。NUMA技術有效結合了SMP系統易編程性和MPP（大規模并行）系統易擴展性的特點，較好解決了SMP系統的可擴展性問題，已成為當今高性能服務器的主流體系結構之一。

在NUMA系統中，當Linux內核收到內存分配的請求時，它會優先從發出請求的CPU本地或鄰近的內存node中尋找空閑內存，這種方式被稱作local allocation，local allocation能讓接下來的內存訪問相對底層的物理資源是local的。

每個node由一個或多個zone組成（我們可能經常在各種對虛擬內存和物理內存的描述中迷失，但以后你見到zone，就知道指的是物理內存），每個zone又由若干page frames組成（一般page frame都是指物理頁面）。

基于NUMA架構的高性能服務器有HP的Superdome、SGI的Altix 3000、IBM的 x440、NEC的TX7、AMD的Opteron等。

概念

NUMA具有多個節點(Node)，每個節點可以擁有多個CPU(每個CPU可以具有多個核或線程)，節點內使用共有的內存控制器，因此節點的所有內存對于本節點的所有CPU都是等同的，而對于其它節點中的所有CPU都是不同的。節點可分為本地節點(Local Node)、鄰居節點(Neighbour Node)和遠端節點(Remote Node)三種類型。

本地節點：對于某個節點中的所有CPU，此節點稱為本地節點；

鄰居節點：與本地節點相鄰的節點稱為鄰居節點；

遠端節點：非本地節點或鄰居節點的節點，稱為遠端節點。

鄰居節點和遠端節點，稱作非本地節點(Off Node)。

CPU訪問不同類型節點內存的速度是不相同的：本地節點>鄰居節點>遠端節點。訪問本地節點的速度最快，訪問遠端節點的速度最慢，即訪問速度與節點的距離有關，距離越遠訪問速度越慢，此距離稱作Node Distance。

常用的NUMA系統中：硬件設計已保證系統中所有的Cache是一致的(Cache Coherent, ccNUMA)；不同類型節點間的Cache同步時間不一樣，會導致資源競爭不公平，對于某些特殊的應用，可以考慮使用FIFO Spinlock保證公平性。

二.NUMA存儲管理

NUMA系統是由多個結點通過高速互連網絡連接而成的，如圖1是SGI Altix 3000 ccNUMA系統中的兩個結點。

NUMA系統的結點通常是由一組CPU（如，SGI Altix 3000是2個Itanium2 CPU）和本地內存組成，有的結點可能還有I/O子系統。由于每個結點都有自己的本地內存，因此全系統的內存在物理上是分布的，每個結點訪問本地內存和訪問其它結點的遠地內存的延遲是不同的，為了減少非一致性訪存對系統的影響，在硬件設計時應盡量降低遠地內存訪存延遲（如通過Cache一致性設計等），而操作系統也必須能感知硬件的拓撲結構，優化系統的訪存。

目前IA64 Linux所支持的NUMA架構服務器的物理拓撲描述是通過ACPI（Advanced Configuration and Power Interface）實現的。ACPI是由Compaq、Intel、Microsoft、Phoenix和Toshiba聯合制定的BIOS規范，它定義了一個非常廣泛的配置和電源管理，目前該規范的版本已發展到2.0，3.0o版本正在制定中，具體信息可以從 http://www.acpi.info網站上獲得。ACPI規范也已廣泛應用于IA-32架構的至強服務器系統中。

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和頁三級結構來描述物理內存的，如圖2所示，

圖2 Linux中Node、Zone和頁的關系

2.1 結點

Linux用一個struct pg_data_t結構來描述系統的內存，系統中每個結點都掛接在一個pgdat_list列表中，對UMA體系結構，則只有一個靜態的pg_data_t結構contig_page_data。對NUMA系統來說則非常容易擴充，NUMA系統中一個結點可以對應Linux存儲描述中的一個結點，具體描述見linux/mmzone.h。

typedef struct pglist_data {
    zone_t node_zones[MAX_NR_ZONES];
    zonelist_t node_zonelists[GFP_ZONEMASK+1];
    int nr_zones;
    struct page *node_mem_map;
    unsigned long *valid_addr_bitmap;
    struct bootmem_data *bdata;
    unsigned long node_start_paddr;
    unsigned long node_start_mapnr;
    unsigned long node_size;
    int node_id;
    struct pglist_data *node_next;
} pg_data_t;

下面就該結構中的主要域進行說明，

系統中所有結點都維護在 pgdat_list 列表中，在 init_bootmem_core 函數中完成該列表初始化工作。

影響zonelist方式

采用Node方式組織的zonelist為：

即各節點按照與本節點的Node Distance距離大小來排序，以達到更優的內存分配。

zonelist[2]

配置NUMA后，每個節點將關聯2個zonelist：

1. zonelist[0]中存放以Node方式或Zone方式組織的zonelist，包括所有節點的zone；
2. zonelist[1]中只存放本節點的zone即Legacy方式；

zonelist[1]用來實現僅從節點自身zone中的內存分配(參考__GFP_THISNODE標志)。

Page Frame

雖然內存訪問的最小單位是byte或者word，但MMU是以page為單位來查找頁表的，page也就成了Linux中內存管理的重要單位。包括換出（swap out）、回收（relcaim）、映射等操作，都是以page為粒度的。

因此，描述page frame的struct page自然成為了內核中一個使用頻率極高，非常重要的結構體，來看下它是怎樣構成的（為了講解需要并非最新內核代碼）：

struct page {
    unsigned long flags;
    atomic_t count;  
    atomic_t _mapcount; 
    struct list_head lru;
    struct address_space *mapping;
    unsigned long index;         
    ...  
}

• flags表示page frame的狀態或者屬性，包括和內存回收相關的PG_active, PG_dirty, PG_writeback, PG_reserved, PG_locked, PG_highmem等。其實flags是身兼多職的，它還有其他用途，這將在下文中介紹到。
• count表示引用計數。當count值為0時，該page frame可被free掉；如果不為0，說明該page正在被某個進程或者內核使用，調用page_count()可獲得count值。
• _mapcount表示該page frame被映射的個數，也就是多少個page table entry中含有這個page frame的PFN。
• lru是"least recently used"的縮寫，根據page frame的活躍程度（使用頻率），一個可回收的page frame要么掛在active_list雙向鏈表上，要么掛在inactive_list雙向鏈表上，以作為頁面回收的選擇依據，lru中包含的就是指向所在鏈表中前后節點的指針（參考這篇文章）。
• 如果一個page是屬于某個文件的（也就是在page cache中），則mapping指向文件inode對應的address_space（這個結構體雖然叫address_space，但并不是進程地址空間里的那個address space），index表示該page在文件內的offset（以page size為單位）。

有了文件的inode和index，當這個page的內容需要和外部disk/flash上對應的部分同步時，才可以找到具體的文件位置。如果一個page是anonymous的，則mapping指向表示swap cache的swapper_space，此時index就是swapper_space內的offset。

事實上，現在最新Linux版本的struct page實現中大量用到了union，也就是同一個元素在不同的場景下有不同的意義。這是因為每個page frame都需要一個struct page來描述，一個page frame占4KB，一個struct page占32字節，那所有的struct page需要消耗的內存占了整個系統內存的32/4096，不到1%的樣子，說小也小，但一個擁有4GB物理內存的系統，光這一項的開銷最大就可達30多MB。

如果能在struct page里省下4個字節，那就能省下4多MB的內存空間，所以這個結構體的設計必須非常考究，不能因為多一種場景的需要就在struct page中增加一個元素，而是應該盡量采取復用的方式。

需要注意的是，struct page描述和管理的是這4KB的物理內存，它并不關注這段內存中的數據變化。

2.2 Zone

每個結點的內存被分為多個塊，稱為zones，它表示內存中一段區域。一個zone用struct_zone_t結構描述，zone的類型主要有ZONE_DMA、ZONE_NORMAL和ZONE_HIGHMEM。ZONE_DMA位于低端的內存空間，用于某些舊的ISA設備。

ZONE_NORMAL的內存直接映射到Linux內核線性地址空間的高端部分，許多內核操作只能在ZONE_NORMAL中進行。

因為硬件的限制，內核不能對所有的page frames采用同樣的處理方法，因此它將屬性相同的page frames歸到一個zone中。對zone的劃分與硬件相關，對不同的處理器架構是可能不一樣的。

比如在i386中，一些使用DMA的設備只能訪問016MB的物理空間，因此將016MB劃分為了ZONE_DMA。ZONE_HIGHMEM則是適用于要訪問的物理地址空間大于虛擬地址空間，不能建立直接映射的場景。除開這兩個特殊的zone，物理內存中剩余的部分就是ZONE_NORMAL了。

例如，在X86中，zone的物理地址如下：

Zone是用struct zone_t描述的，它跟蹤頁框使用、空閑區域和鎖等信息，具體描述如下：

typedef struct zone_struct {
    spinlock_t lock;
    unsigned long free_pages;
    unsigned long pages_min, pages_low, pages_high;
    int need_balance;
    free_area_t free_area[MAX_ORDER];
    wait_queue_head_t * wait_table;
    unsigned long wait_table_size;
    unsigned long wait_table_shift;
    struct pglist_data *zone_pgdat;
    struct page *zone_mem_map;
    unsigned long zone_start_paddr;
    unsigned long zone_start_mapnr;char *name;unsigned long size;
} zone_t;

在其他一些處理器架構中，ZONE_DMA可能是不需要的，ZONE_HIGHMEM也可能沒有。比如在64位的x64中，因為內核虛擬地址空間足夠大，不再需要ZONE_HIGH映射，但為了區分使用32位地址的DMA應用和使用64位地址的DMA應用，64位系統中設置了ZONE_DMA32和ZONE_DMA。

所以，同樣的ZONE_DMA，對于32位系統和64位系統表達的意義是不同的，ZONE_DMA32則只對64位系統有意義，對32位系統就等同于ZONE_DMA，沒有單獨存在的意義。

此外，還有防止內存碎片化的ZONE_MOVABLE和支持設備熱插拔的ZONE_DEVICE。可通過“cat /proc/zoneinfo |grep Node”命令查看系統中包含的zones的種類。

[rongtao@toa ~]$ cat /proc/zoneinfo |grep Node
Node 0, zone      DMA
Node 0, zone    DMA32
[rongtao@toa ~]$

下面就該結構中的主要域進行說明，

當系統中可用的內存比較少時，kswapd將被喚醒，并進行頁交換。如果需要內存的壓力非常大，進程將同步釋放內存。如前面所述，每個zone有三個閾值，稱為pages_low，pages_min和pages_high，用于跟蹤該zone的內存壓力。pages_min的頁框數是由內存初始化free_area_init_core函數，根據該zone內頁框的比例計算的，最小值為20頁，最大值一般為255頁。當到達pages_min時，分配器將采用同步方式進行kswapd的工作；當空閑頁的數目達到pages_low時，kswapd被buddy分配器喚醒，開始釋放頁；當達到pages_high時，kswapd將被喚醒，此時kswapd不會考慮如何平衡該zone，直到有pages_high空閑頁為止。一般情況下，pages_high缺省值是pages_min的3倍。

Linux存儲管理的這種層次式結構可以將ACPI的SRAT和SLIT信息與Node、Zone實現有效的映射，從而克服了傳統Linux中平坦式結構無法反映NUMA架構的缺點。當一個任務請求分配內存時，Linux采用局部結點分配策略，首先在自己的結點內尋找空閑頁；如果沒有，則到相鄰的結點中尋找空閑頁；如果還沒有，則到遠程結點中尋找空閑頁，從而在操作系統級優化了訪存性能。

Zone雖然是用于管理物理內存的，但zone與zone之間并沒有任何的物理分割，它只是Linux為了便于管理進行的一種邏輯意義上的劃分。Zone在Linux中用struct zone表示（以下為了講解需要，調整了結構體中元素的順序）：

struct zone {
     spinlock_t         lock;

     unsigned long      spanned_pages;
     unsigned long      present_pages; 
     unsigned long      nr_reserved_highatomic;    
     atomic_long_t      managed_pages;

     struct free_area   free_area[MAX_ORDER];
     unsigned long      _watermark[NR_WMARK];
     long               lowmem_reserve[MAX_NR_ZONES];
     atomic_long_t      vm_stat[NR_VM_ZONE_STAT_ITEMS];

     unsigned long      zone_start_pfn;
     struct pglist_data *zone_pgdat;
     struct page        *zone_mem_map;
     ...    
}

• lock是用來防止并行訪問struct zone的spin lock，它只能保護struct zone這個結構體哈，可不能保護整個zone里的所有pages。
• spanned_pages是這個zone含有的總的page frames數目。在某些體系結構（比如Sparc）中，zone中可能存在沒有物理頁面的"holes"，spanned_pages減去這些holes里的absent pages就是present_pages。

nr_reserved_highatomic是為某些場景預留的內存，managed_pages是由buddy內存分配系統管理的page frames數目，其實也就是present_pages減去reserved pages。

• free_area由free list空閑鏈表構成，表示zone中還有多少空余可供分配的page frames。_watermark有min(mininum), low, high三種，可作為啟動內存回收的判斷標準

lowmem_reserve是給更高位的zones預留的內存。vm_stat作為zone的內存使用情況的統計信息，是“/proc/zoneinfo”的數據來源。

• zone_start_pfn是zone的起始物理頁面號，zone_start_pfn+spanned_pages就是該zone的結束物理頁面號。zone_pgdat是指向這個zone所屬的node的。zone_mem_map指向由struct page構成的mem_map數組。

因為內核對zone的訪問是很頻繁的，為了更好的利用硬件cache來提高訪問速度，struct zone中還有一些填充位，用于幫助結構體元素的cache line對齊。這和struct page對內存精打細算的使用形成了鮮明的對比，因為zone的種類很有限，一個系統中一共也不會有多少個zones，struct zone這個結構體的體積大點也沒有什么關系。

Node Distance

上節中的例子是以2個節點為例，如果有>2個節點存在，就需要考慮不同節點間的距離來安排節點，例如以4個節點2個ZONE為例，各節點的布局(如4個XLP832物理CPU級聯)值如下：

上圖中，Node0和Node2的Node Distance為25，Node1和Node3的Node Distance為25，其它的Node Distance為15。

三、NUMA調度器

NUMA系統中，由于局部內存的訪存延遲低于遠地內存訪存延遲，因此將進程分配到局部內存附近的處理器上可極大優化應用程序的性能。Linux 2.4內核中的調度器由于只設計了一個運行隊列，可擴展性較差，在SMP平臺表現一直不理想。當運行的任務數較多時，多個CPU增加了系統資源的競爭，限制了負載的吞吐率。在2.5內核開發時，Ingo Molnar寫了一個多隊列調度器，稱為O(1)，從2.5.2開始O(1)調度器已集成到2.5內核版本中。O(1)是多隊列調度器，每個處理器都有一條自己的運行隊列，但由于O(1)調度器不能較好地感知NUMA系統中結點這層結構，從而不能保證在調度后該進程仍運行在同一個結點上，為此，Eirch Focht開發了結點親和的NUMA調度器，它是建立在Ingo Molnar的O(1)調度器基礎上的，Eirch將該調度器向后移植到2.4.X內核中，該調度器最初是為基于IA64的NUMA機器的2.4內核開發的，后來Matt Dobson將它移植到基于X86的NUMA-Q硬件上。

3.1 初始負載平衡

在每個任務創建時都會賦予一個HOME結點（所謂HOME結點，就是該任務獲得最初內存分配的結點），它是當時創建該任務時全系統負載最輕的結點，由于目前Linux中不支持任務的內存從一個結點遷移到另一個結點，因此在該任務的生命期內HOME結點保持不變。一個任務最初的負載平衡工作（也就是選該任務的HOME結點）缺省情況下是由exec()系統調用完成的，也可以由fork()系統調用完成。在任務結構中的node_policy域決定了最初的負載平衡選擇方式。

3.2 動態負載平衡

在結點內，該NUMA調度器如同O(1)調度器一樣。在一個空閑處理器上的動態負載平衡是由每隔1ms的時鐘中斷觸發的，它試圖尋找一個高負載的處理器，并將該處理器上的任務遷移到空閑處理器上。在一個負載較重的結點，則每隔200ms觸發一次。調度器只搜索本結點內的處理器，只有還沒有運行的任務可以從Cache池中移動到其它空閑的處理器。

如果本結點的負載均衡已經非常好，則計算其它結點的負載情況。如果某個結點的負載超過本結點的25％，則選擇該結點進行負載均衡。如果本地結點具有平均的負載，則延遲該結點的任務遷移；如果負載非常差，則延遲的時間非常短，延遲時間長短依賴于系統的拓撲結構。

四、CpuMemSets

SGI的Origin 3000 ccNUMA系統在許多領域得到了廣泛應用，是個非常成功的系統，為了優化Origin 3000的性能，SGI的IRIX操作系統在其上實現了CpuMemSets，通過將應用與CPU和內存的綁定，充分發揮NUMA系統本地訪存的優勢。Linux在NUMA項目中也實現了CpuMemSets，并且在SGI的Altix 3000的服務器中得到實際應用。

CpuMemSets為Linux提供了系統服務和應用在指定CPU上調度和在指定結點上分配內存的機制。CpuMemSets是在已有的Linux調度和資源分配代碼基礎上增加了cpumemmap和cpumemset兩層結構，底層的cpumemmap層提供一個簡單的映射對，主要功能是：將系統的CPU號映射到應用的CPU號、將系統的內存塊號映射到應用的內存塊號；上層的cpumemset層主要功能是：指定一個進程在哪些應用CPU上調度任務、指定內核或虛擬存儲區可分配哪些應用內存塊。

4.1 cpumemmap

內核任務調度和內存分配代碼使用系統號，系統中的CPU和內存塊都有對應的系統號。應用程序使用的CPU號和內存塊號是應用號，它用于指定在cpumemmap中CPU和內存的親和關系。每個進程、每個虛擬內存區和Linux內核都有cpumemmap，這些映射是在fork()、exec()調用或創建虛擬內存區時繼承下來的，具有root權限的進程可以擴展cpumemmap，包括增加系統CPU和內存塊。映射的修改將導致內核調度代碼開始運用新的系統CPU，存儲分配代碼使用新的內存塊分配內存頁，而已在舊塊上分配的內存則不能遷移。Cpumemmap中不允許有空洞，例如，假設cpumemmap的大小為n，則映射的應用號必須從0到n-1。

Cpumemmap中系統號和應用號并不是一對一的映射，多個應用號可以映射到同一個系統號。

4.2 cpumemset

系統啟動時，Linux內核創建一個缺省的cpumemmap和cpumemset，在初始的cpumemmap映射和cpumemset中包含系統目前所有的CPU和內存塊信息。

Linux內核只在該任務cpumemset的CPU上調度該任務，并只從該區域的內存列表中選擇內存區分配給用戶虛擬內存區，內核則只從附加到正在執行分配請求CPU的cpumemset內存列表中分配內存。

一個新創建的虛擬內存區是從任務創建的當前cpumemset獲得的，如果附加到一個已存在的虛擬內存區時，情況會復雜些，如內存映射對象和Unix System V的共享內存區可附加到多個進程，也可以多次附加到同一個進程的不同地方。如果被附加到一個已存在的內存區，缺省情況下新的虛擬內存區繼承當前附加進程的cpumemset，如果此時標志位為CMS_SHARE，則新的虛擬內存區鏈接到同一個cpumemset。

當分配頁時，如果該任務運行的CPU在cpumemset中有對應的存儲區，則內核從該CPU的內存列表中選擇，否則從缺省的CPU對應的cpumemset選擇內存列表。

4.3硬分區和CpuMemSets

在一個大的NUMA系統中，用戶往往希望控制一部分CPU和內存給某些特殊的應用。目前主要有兩種技術途徑：硬分區和軟分區技術，CpuMemSets是屬于軟分區技術。將一個大NUMA系統的硬分區技術與大NUMA系統具有的單系統映像優勢是矛盾的，而CpuMemSets允許用戶更加靈活的控制，它可以重疊、劃分系統的CPU和內存，允許多個進程將系統看成一個單系統映像，并且不需要重啟系統，保障某些CPU和內存資源在不同的時間分配給指定的應用。

SGI的CpuMemSets軟分區技術有效解決硬分區中的不足，一個單系統的SGI ProPack Linux服務器可以分成多個不同的系統，每個系統可以有自己的控制臺、根文件系統和IP網絡地址。每個軟件定義的CPU組可以看成一個分區，每個分區可以重啟、安裝軟件、關機和更新軟件。分區間通過SGI NUMAlink連接進行通訊，分區間的全局共享內存由XPC和XPMEM內核模塊支持，它允許一個分區的進程訪問另一個分區的物理內存。

五、測試

為了有效驗證Linux NUMA系統的性能和效率，我們在SGI公司上海辦事處測試了NUMA架構對SGI Altix 350性能。

該系統的配置如下：CPU：8個1.5 GHz Itanium2 內存：8GB 互連結構：如圖3所示

圖3 SGI Altix350 4個計算模塊的Ring拓撲

測試用例：

1、Presta MPI測試包（來自ASCI Purple的Benchmark）

從互連拓撲結構可以看出，計算模塊內部的訪存延遲不需要通過互連，延遲最逗，剩下的需要通過1步或2步互連到達計算模塊，我們通過Presta MPI測試包，重點測試每步互連對系統的影響，具體結果如下：

2、NASA的NPB測試

上述測試表明，SGI Altix 350系統具有較高的訪存和計算性能，Linux NUMA技術已進入實用階段。