背景

連續內存分配給內存分配帶來了很多不便，可能所有空閑片區大小都無法滿足需求大小，這個分配就會失敗。基于這種現狀，就有了非連續內存分配的需求。非連續分配成功的幾率更高，但也面對更多的問題，比如分配時是不是1個字節的空間也可以進行分配？顯然1個字節為單位分配太短了。因此我們需要選擇不同尺度的基本塊進行分配管理。實際操作系統中出現了兩種基本塊，一種是段式，一種是頁式。段式分的塊比較大，頁式分配的塊比較小。分配的塊越小，邏輯地址與物理地址之間的映射關系就越復雜。根據這種映射關系形成了頁表。還有一種結合的方式段頁式管理。

連續分配的缺點

分配給程序的物理內存必須連續
存在外碎片和內碎片
內存分配的動態修改困難
內存利用率較低

非連續分配的設計目標

針對連續內存分配的這些缺點，非連續分配的設計目標就顯而易見了：提高內存利用效率和管理靈活性。具體來說有以下幾條：

允許一個程序使用非連續的物理地址空間；
允許共享代碼與數據，因為各個進程可能有很多代碼是相同的或者使用的數據是相同的，比如使用了同一個函數庫；
支持動態加載和動態鏈接。

非連續分配需要解決的問題：

虛擬地址到物理地址的轉換。當進程的內存地址連續時，只要知道進程內存起頭的位置，就知道整個內存區域的位置了。而非連續分配則不然，邏輯地址中不同位置可能存儲于物理內存中不同的區域，因此轉換會比較復雜。具體的轉換方式有兩種：

軟件實現，靈活但開銷大，就比如數據的外排序時，需要分幾部分將數據排序存到外存，最后再整體排序；
硬件實現，夠用并且開銷小。

非連續分配的硬件輔助機制：

非連續分配中如何選擇非連續分配的內存分塊大小是個很重要的問題。實際操作中主要有兩種方式：

段式存儲管理，內存基本塊較大；
頁式存儲管理，內存基本塊較小。

段式存儲管理

段式存儲管理中，將程序的邏輯地址空間內容分為不同的段進行管理，邏輯地址空間與物理地址空間之間的映射關系圖可以如下所示：每個段內部是連續的，但是不同的段在物理內存上是不連續的。

段的概念：

段表示訪問方式和存儲數據等屬性相同的一段地址空間；
一個段對應一個連續的內存塊；
若干個段共同組成進程的邏輯地址空間。

段訪問：

邏輯地址由二元組（s,addr）表示。其中 s 表示段號，addr 表示段內偏移量。如下圖：

硬件實現：

如下圖所示：在程序P運行過程中，CPU要訪問邏輯地址中的某個位置，已經知道段號與偏移。操作系統中維護段表，段表記錄段號對應的基址與長度，首先MMU比對偏移量與段號對應的長度，如果偏移量大于長度說明操作不合法內存異常，否則是合法的，此時將段基址與偏移相加得到真實物理地址，然后進行訪問。

頁式存儲管理

頁式存儲管理中，物理內存被劃分為大小相同的基本分配單位，我們稱為頁幀，頁幀的大小必須是2的冪次方，這樣進行地址轉換的時候比較快，可以通過二進制移位實現。比如32位系統中，4Kbyte是常見的頁幀大小。而邏輯內存也被劃分為大小相同的基本分配單位，我們稱為頁面，頁面與頁幀大小必須相等。頁幀與頁面一個是對物理內存地址一個是對邏輯內存地址而言的。因此頁式存儲管理中要處理邏輯地址與物理地址的轉換，也就變為對頁面到頁幀的轉換。而儲存映射關系的表我們稱為頁表，由操作系統維護。具體硬件實現則是由MMU和TLB共同實現。

幀

物理內存被分為大小相等的幀，物理內存的地址用一個（f,o）二元組表示，其中 f 是幀號，比如一個幀號由 f?bit表示，那也就是說一共有?2**f 個幀，o 是幀內偏移，比如偏移由 S bit 表示，那么一個幀內 2**S 有字節。那么?物理地址 = $f*2^S+o$ ?。

頁

邏輯內存被劃分為大小相等的頁，表示方式與幀類似。由于幀與頁的大小是相等的。因此在映射關系中，頁內偏移與幀內偏移是相等的，但是頁號與幀號通常是不相等的。因為邏輯內存是連續的，物理地址不是連續的。

頁表

那么如何實現頁與幀之間的地址轉換呢？也就是如何實現邏輯地址與物理地址之間的轉換。如下圖：操作系統維護頁表，頁表內存儲頁號與幀號之間的映射關系。頁表基址表明了頁表存儲在什么地方。比如當程序P執行過程中，CPU要訪問(p, o)，操作系統通過頁表得到幀號f，通過(f, o)找到物理內存地址。而由于幀和頁的大小是2的冪次方，因此實際上地址就是將 f 左移 S 位之后加上 o 即得到物理地址。

上面簡單介紹了頁表的作用，而實際上頁表中還有一些其他輔助的內容。下面我們對頁表進行詳細討論。每個進程都有一個頁表，且有以下特點：

每個頁面對應一個頁表項
頁表隨進程運行狀態而動態變化
頁表的起始地址即基址存儲在頁表基址寄存器（PTBR: Page Table Base Register）中

頁表內除了存儲前面提過的幀號，還存儲了一些頁表項標志位：

存在位，記錄該頁號是否有對應的幀；
修改位，記錄頁面的內容是否修改了；
引用位，記錄是否有對該頁面的引用。

那么實際操作中，如下圖，標志位為0意味著沒有給頁分配幀，就可以動態的進行變化。

頁式訪問的性能問題

內存訪問的性能問題：訪問一個物理內存單元需要兩次訪問內存。第一次先訪問頁表進行查詢，第二次才是訪問物理內存獲取數據。
頁表的大小問題：頁表可能非常大。比如一個64位機器（2**64 字節內存），假如一頁大小為1024字節（2**10），那么一共可以產生頁（2**54 幀），64位的系統想要表示一個幀的地址就需要64位，也就是8字節，也就是說想表示一個幀，即使不考慮標志位也需要8字節，那使用很多頁面，比如全部使用 2**54 頁，就需要 2**57 字節，僅僅存儲頁表就要這么多字節占用了很多空間。

針對這些問題，也有一些對應的解決方案：

緩存：程序執行時具有連續性即相鄰性，訪問了一個數組第一個元素，下一個極有可能訪問第二個元素，因此當我緩存下來頁表項，利用緩存可以極大可能地訪問到想要的數據。
間接訪問：將長頁表切斷，實際就是多級頁表，一層層去查詢。

為了緩解上述性能問題，出現了一些解決方案，比如快表、多級頁表和反置頁表，下面對這幾種解決方案進行詳細討論。

快表（TLB: Translation Look-aside Buffer）：

快表是指緩存近期訪問過的頁表項。它有以下特點：

TLB使用關聯存儲（associative memory）實現，具備快速訪問性能，因為關聯存儲在CPU內；
如果TLB命中，可以直接訪問物理內存；
如果TLB未命中，仍需查詢頁表，并將對應表項更新到TLB中。

如果能夠很大比例地命中，就可以大幅度提高訪問效率。

多級頁表

多級頁表顧名思義，類似于樹的概念，一級一級往下查詢，圖示如下：比如圖中是三級頁表，邏輯地址的表示由四元組?表示。p1、p2、p3 分別表示在各級頁表中的偏移，o 則表示物理內存中的偏移。通過多級頁表可以有效減少每級頁表的長度。

具體操作中，比二級頁表的操作如下：一級頁表的起始地址存儲在CPU寄存器CR3中，然后一級一級根據偏移獲取實際內存地址。

反置頁表頁寄存器

反置頁表也是為了減少頁表占用存儲空間的一種做法。對于大地址空間系統，比如64位系統，多級頁表變的非常繁瑣，比如5級頁表，正常情況下總共需要6次查詢。并且邏輯地址空間的增長速度快于物理地址空間。每個進程有一個頁表，隨進程數量增加頁表占用的存儲空間也會增加。

針對上述情況，出現了頁寄存器，頁寄存器與反置頁表思路相同：

不讓頁表與邏輯地址空間的大小相對應；
讓頁表與物理地址空間的大小相對應。

通過這個思路就可以使頁表占用空間與進程數目沒有關系，而至于物理內存的大小有關。接下來我們首先對頁寄存器進行介紹，理解了頁寄存器就可以輕松理解反置頁表。頁寄存器將每個物理幀與與一個頁寄存器關聯，寄存器內存儲以下內容：

使用位：此幀是否被進程占用；
占用頁號：對應的邏輯頁號 p ；
保護位：比如可讀、可寫等性質。

由上面的內容我們可以看到頁寄存器的優點是與邏輯地址空間大小無關，并且大小相對物理內存而言很小。缺點是需要在頁寄存器中存儲頁號，也就是幀號是鍵，頁號是幀，而進程運行時CPU產生的是邏輯地址頁號，因此需要在頁寄存器中搜索邏輯地址的頁號。那么這種搜索是比較困難的。實際操作中，采用hash將頁號映射到幀號，提高檢索效率。這樣又產生一個問題就是hash沖突，出現沖突時遍歷沖突鏈表，找到需要的幀號。同時還可以將快表的思想融入進來，緩存使用過的頁號幀號映射。引入快表又引入了新的問題，快表存儲在CPU緩存中容量被限制到很小，同時快表的功耗是很大的。

反置頁表

接下來我們看下反置頁表。反置頁表也是基于hash映射查找頁對應的幀，但是反置頁表將進程號也考慮進來，對進程號和頁號同時進行hash。這里我自己的理解是最初給進程分配幀的時候就是根據哈希值進行分配的，因此查找時自然可以根據哈希值進行查詢。沖突解決方式依然是鏈表的方式解決，查詢發現第一個地址內的進程號與頁號與需要的進程號與頁號不一致時則繼續查詢鏈表中的下一個節點。過程如下圖：哈希值加反置頁表基址得到反置頁表中的位置，驗證進程號和頁號，命中則根據hash結果查詢物理內存。

具體實現看下圖。pid和vpn（virtual page number）共同參與哈希，得到一個物理地址，根據這個地址去查詢反置頁表，驗證pid和vpn是否匹配，不匹配則查詢next中存儲的地址，此時匹配，則訪問此時對應的物理地址。

段頁式存儲管理

段頁式存儲管理是將前面講過的段式存儲管理與頁式存儲管理結合起來。這一節對段頁式存儲管理進行討論。

段頁式存儲管理的需求

段式存儲管理在內存保護方面有優勢。如何理解呢？因為分段時是將具有相同訪問方式和數據屬性的內容分配到一段連續內存中，也就是每個段內的數據屬性是相似的，便于統一管理和保護。
頁式存儲管理在內存利用和優化轉移到后備存儲方面有優勢。因為頁式存儲管理中內存劃分的基本塊更小，對提高內存的利用率有很大幫助。同時對于內外存之間轉移也是比較快和利用率高的。