内存是計算機五大組分裡的存儲器，指令和數據，都要先加載到内存，才能被CPU讀取執行。

Linux下，程序并不能直接訪問物理内存。

内存需被分成固定大小頁（Page），再通過虛拟内存地址（Virtual Address）到物理内存地址（Physical Address）的地址轉換（Address Translation），才能到達實際存放數據的物理内存位置。我們的程序看到的内存地址，都是虛拟内存地址。

那這些虛拟内存地址究竟是怎麼轉換成物理内存地址的呢？

簡單頁表

很直觀啊，建張映射表，完成虛拟内存裡面的頁 =》物理内存頁的一一映射，這就是頁表（Page Table）。

頁表把一個内存地址分成：

• 頁号（Directory）
• 偏移量（Offset）

如32位内存地址：

• 前面高位，内存地址的頁号
• 後面低位，内存地址裡的偏移量

做地址轉換的頁表，隻需保留虛拟内存地址的頁号 => 物理内存地址的頁号之間的映射關系

同一頁裡的内存，物理層面連續。比如頁大小4K比特（4KiB），需20位高位，12位低位。

一個内存地址轉換，就是如下步驟：

• 把虛拟内存地址，分為頁号、偏移量
• 從頁表裡，查詢出虛拟頁号，對應的物理頁号
• 直接拿物理頁号，加上前面的偏移量，即得物理内存地址

那這樣一個頁表需多大空間呢？

如32位内存地址空間，頁表共需記錄 2^20 個到物理頁号的映射關系。該存儲關系就像一個2^20大小數組。一個頁号是完整的32位4字節，這一個頁表就要4MB

但這空間可不是隻占用一份。每個進程都有獨立的虛拟内存地址空間。這意味着，每個進程都要這樣一個頁表。不管這進程需幾KB or 幾GB内存空間，都要這樣一個頁表。這還隻是32位内存地址空間，更多的64位os，用這數組的數據結構保存頁面，内存占用更大。

有啥更好的解決辦法呢？

多級頁表

沒必要存2^20個物理頁表，大部分進程所占内存有限，需要的頁自然很有限。隻需存那些用到的頁之間的映射關系即可。是不是應該用哈希表？No！實際采用的多級頁表（Multi-Level Page Table），為什麼不用哈希表呢？

一個進程的内存地址空間是怎麼分配的

整個進程的内存地址空間，通常“兩頭實、中間空”。程序運行時，内存地址從頂部往下，不斷分配占用的棧的空間。而堆的空間，内存地址則是從底部往上，不斷分配占用。

所以，實際程序進程裡，虛拟内存占用的地址空間，通常是兩段連續空間。而非完全随機的内存地址。而多級頁表，就特别适合這樣的内存地址分布。

示例

4級的多級頁表，同樣一個虛拟内存地址，偏移量的部分和上面簡單頁表一樣，但頁号部分拆成四段，從高到低，分成4級到1級，4個頁表索引。

• 對應一個進程會有個4級頁表。先通過4級頁表索引，找到4級頁表裡對應的條目（Entry）。該條目裡存放一張3級頁表所在位置。4級頁面裡的每個條目，都對應一張3級頁表，所以可能有多張3級頁表。
• 找到對應這張3級頁表後，用3級索引去找到對應的3級索引的條目。3級索引的條目再會指向一個2級頁表。
• 同理，2級頁表裡可用2級索引指向一個1級頁表。
• 最後一層的1級頁表裡面的條目，對應數據内容就是物理頁号。拿到物理頁号，同樣可用“頁号 偏移量”獲取物理内存地址。

可能有多張1級頁表、2級頁表乃至3級頁表。但因實際虛拟内存空間通常連續，很可能隻需很少的2級頁表，甚至隻需1張3級頁表即可。

多級頁表就像一個多叉樹，所以常稱為頁表樹（Page Table Tree）。因為虛拟内存地址分布的連續性，樹第一層節點的指針，很多空的，也就無需有對應子樹，不需要子樹就是不需要對應2級、3級頁表。找到最終物理頁号，就好像通過一個特定訪問路徑，走到樹最底層的葉節點。

以分成4級的多級頁表為例，每級若都用5比特表示。則每張某1級的頁表，隻需2^5=3225=32個條目。若每個條目還4字節，則共需128字節。一個1級索引表對應32個4KiB，即16KB。一個填滿的2級索引表，對應32個1級索引表，即512KB。

若某進程占用1MB内存空間，分成了2個512KB連續空間。則它共需2個獨立、填滿的2級索引表，即64個1級索引表，2個獨立3級索引表，1個4級索引表。共69個索引表，每個128字節，約9KB空間。比起4MB，差不多1/500了。

雖多級頁表節約存儲空間，卻帶來時間開銷，是個“時間換空間”策略。 原進行一次地址轉換，隻需訪問一次内存就能找到物理頁号，算出物理内存地址。但用了4級頁表，就得訪問4次内存才能找到物理頁号。内存訪問比Cache慢很多，本隻是做個簡單的地址轉換，反而要多訪問了好多次内存。對這時間性能損失，如何更好解決呢？

總結

從最簡單的進行虛拟頁号一一映射的簡單頁表說起，仔細講解了現在實際應用的多級頁表。多級頁表就像是一顆樹。因為一個進程的内存地址相對集中和連續，所以采用這種頁表樹的方式，可以大大節省頁表所需要的空間。而因為每個進程都需要一個獨立的頁表，這個空間的節省是非常可觀的。

在優化頁表的過程中，我們可以觀察到，數組這樣的緊湊的數據結構，以及樹這樣稀疏的數據結構，在時間複雜度和空間複雜度的差異。另外，純粹理論軟件的數據結構和硬件的設計也是高度相關的。

參考

《計算機組成與設計：硬件/軟件接口》的第5.7章節

《What Every Programmer Should Know About Memory》的第4部分，Virtual Memory

,

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!

查看全部