Non-Uniform Memory Access (NUMA)
Problem
在前面討論 frame allocation 時，我們其實一直有一個隱含假設：所有 physical memory 的存取成本都一樣
也就是說，OS 只要決定「要給 process 幾個 frame」以及「要從哪些 free frames 裡挑 frame」就好，不太需要在意這些 frame 實際上位於機器中的哪個位置。
但在現代 multiprocessor system 中，這個假設不一定成立。系統可能有多顆 CPU，而每顆 CPU 旁邊都有自己比較靠近的 local memory。此時 CPU 存取不同區域的 memory，延遲可能不同。
Concept
NUMA 指的是 Non-Uniform Memory Access，也就是「不同 memory location 對同一顆 CPU 來說，存取時間不一定相同」。
一個 NUMA system 通常由多個 CPU 與多個 memory region 組成，每顆 CPU 都有一塊離自己比較近的 local memory，CPU 之間則透過 shared system interconnect 彼此連接。
例如：
- CPU₀ 旁邊有 memory₀
- CPU₁ 旁邊有 memory₁
- CPU₂ 旁邊有 memory₂
- CPU₃ 旁邊有 memory₃
對 CPU₀ 來說，存取 memory₀ 會比存取 memory₁、memory₂、memory₃ 更快，因為後者需要跨過 interconnect，latency 比較高。
NUMA 的重點不是「不能存取遠端 memory」
CPU 還是可以存取其他 CPU local 的 memory，只是這個存取成本比較高。
因此 NUMA 的核心問題不是 correctness，而是 performance：如果 OS 把一個正在 CPU₀ 上跑的 thread 所需要的 frame 分配到 memory₃，程式仍然可以執行，但每次 memory access 都可能付出額外延遲。
Trade-off
- 壞處：memory access latency 變得不均勻，OS 必須考慮 memory placement
- 好處：系統可以容納更多 CPU，整體 parallelism 與 throughput 可以更高
Impact on Frame Allocation
在 NUMA system 中，管理「page frame 被放在哪裡」會直接影響效能。
如果 OS 仍然把 memory 當作 uniform memory 來看，可能會發生以下狀況：
- 一個 process / thread 被 scheduler 排到 CPU₀ 上執行
- 它發生 page fault，需要 OS 分配一個新的 frame
- OS 隨便從 free-frame list 拿了一個 frame，而這個 frame 剛好位於 memory₃
- 之後這個 thread 在 CPU₀ 上執行時，就必須一直跨 interconnect 存取遠端 memory
所以 NUMA-aware virtual memory system 的目標是：盡量把 frame 分配在離目前執行該 process / thread 的 CPU 最近的位置。
Scheduler 也必須配合
只讓 virtual memory system 做 NUMA-aware allocation 還不夠，因為 process / thread 之後可能被 scheduler 搬到另一顆 CPU 上執行。
例如：
- Thread 一開始在 CPU₀ 上跑
- OS 因為 NUMA-aware allocation，把它的 frames 分配在 memory₀
- 之後 scheduler 把這個 thread 搬到 CPU₃ 上跑
- 原本很近的 memory₀ 對 CPU₃ 來說就變成遠端 memory
因此 scheduler 也需要記錄每個 process / thread 上一次在哪顆 CPU 上執行，並且盡量把它排回原本的 CPU 或至少排在同一個 NUMA domain 中。
這樣做有兩個效果：
- memory access latency 下降，因為 thread 比較常存取 local memory
- cache hit rate 提升，因為 thread 留在同一顆 CPU 或鄰近 CPU 時，較可能重用原本的 cache state