內(nèi)存管理分頁技術，（簡稱：分頁）(Paging)是一種內(nèi)存管理方案，是將進程以頁的形式從輔助內(nèi)存中檢索到主存中的過程，不需要連續(xù)分配物理內(nèi)存，將每個進程劃分為頁。分頁的主要思想是將主存的虛擬(邏輯)地址空間和真實(物理)地址空間劃分成容量和大小相等的頁，使所有地址都可以用頁號拼接頁內(nèi)地址的形式表示。

在計算機操作系統(tǒng)中，連續(xù)分配的算法阻礙了存儲管理方案的設計，造成了大量的內(nèi)存碎片，因此需要考慮非連續(xù)分配的算法，分頁管理就是其中最具代表性的一種。1959年，亞多拉斯系統(tǒng)被開發(fā)出來，使用分頁將虛擬地址映射到主存，并于1962年投入使用。1969年，IBM的研究人員證明了虛擬內(nèi)存覆蓋系統(tǒng)比早期的手動系統(tǒng)工作得更好。在20世紀70年代，大型機和小型計算機通常使用虛擬內(nèi)存。1982年Intel在80286處理器的保護模式下引入了虛擬內(nèi)存，1985年80386出來的時候引入了分頁支持。

分頁存儲管理將內(nèi)存空間分成若干大小相等、位置固定的小分區(qū)，每個小分區(qū)稱為一個存儲塊，依次編號。每個存儲塊的大小由不同的系統(tǒng)決定，一般是2的n次方。分頁提高了內(nèi)存管理的效率，進而提高了系統(tǒng)性能和響應能力。但是在頁面存儲下，程序的模塊化較差，需要占用大量的存儲空間。

早期操作系統(tǒng)采用的連續(xù)分配管理模式，要求分配給進程的物理空間必須是連續(xù)的，這是產(chǎn)生大量碎片的主要原因，所以一直考慮非連續(xù)分配算法。在分頁技術出現(xiàn)之前，內(nèi)存管理方案偶爾會使用覆蓋技術。它只需要將CPU當前需要的指令和數(shù)據(jù)保存在內(nèi)存中，以維持計算機系統(tǒng)的運行。當需要其他指令、數(shù)據(jù)或程序段時，只需將它們加載到不再需要的指令所占用的內(nèi)存空間中。

分頁管理是不連續(xù)分配管理中具有代表性的算法，它要求將物理內(nèi)存空間劃分成固定大小的塊，分頁技術不會產(chǎn)生外部碎片。分頁技術的具體應用可以追溯到一個早期的重要系統(tǒng)Atlas，它是在1959年開發(fā)的，使用分頁將虛擬地址映射到主存，并于1962年投入使用。1969年，IBM的研究人員證明了虛擬內(nèi)存覆蓋系統(tǒng)比早期的手動系統(tǒng)工作得更好。在20世紀70年代，大型機和小型計算機通常使用虛擬內(nèi)存。1982年Intel在80286處理器的保護模式下引入了虛擬內(nèi)存，1985年80386出來的時候引入了分頁支持。

隨著分頁技術的不斷成熟，它已經(jīng)成為一種關鍵的內(nèi)存管理技術，用于實現(xiàn)計算機操作系統(tǒng)中的虛擬內(nèi)存管理方法，提供進程間的內(nèi)存保護和隔離。后來隨著硬件技術的發(fā)展，Intel在1985年推出了Intel 80386微處理器，開啟了處理器內(nèi)置分頁機制的時代。

為了降低分頁機制的缺頁率，提高虛擬內(nèi)存的性能，相關技術人員開發(fā)了許多頁面替換算法，包括最優(yōu)替換算法、先進先出替換算法、最近未使用替換算法等頁面替換算法。20世紀10年代，云計算開始出現(xiàn)。是計算服務的分發(fā)，虛擬化是云計算的基礎，通過制作虛擬鏡像，有助于共享系統(tǒng)資源。分頁作為一種內(nèi)存管理技術，也應用于云計算，讀寫數(shù)據(jù)到硬盤。

分頁的主要思想是將主存的虛擬(邏輯)地址空間和真實(物理)地址空間劃分成容量和大小相等的頁面，使所有地址都可以用頁號拼接頁內(nèi)地址的形式表示，按頁分配主存的存儲管理方式稱為頁管理。

系統(tǒng)中通常有一個地址翻譯機制，將程序在地址空間中的邏輯地址翻譯成在內(nèi)存空間中的物理地址，實現(xiàn)它們之間的重定位。當訪問和操作一個進程的邏輯地址時，地址翻譯機制自動將有效邏輯地址根據(jù)頁面大小分為兩部分:頁碼和頁內(nèi)位移。邏輯地址除以頁面長度得到的商和余數(shù)分別是邏輯頁碼和頁內(nèi)位移。

在分頁中，物理內(nèi)存被劃分為固定大小的塊，稱為頁幀，其大小與進程使用的頁面大小相同。進程的邏輯地址空間也分為固定大小的塊，稱為頁面，其大小與頁框相同。當進程請求內(nèi)存時，操作系統(tǒng)將為該進程分配一個或多個頁框，并將該進程的邏輯頁映射到物理頁框。邏輯頁面和物理頁面幀之間的映射由頁面表維護，內(nèi)存管理單元使用該頁面表將邏輯地址轉(zhuǎn)換為物理地址。頁表將每個邏輯頁號映射到物理頁框號。

分頁技術提高了主存的利用率，有利于多程序運行，可以增加ram(隨機存取存儲器)或期望分頁的數(shù)量，提高RAM讀取的命中率來提高系統(tǒng)性能，還可以通過減少CPU等待從磁盤加載頁面的時間來提高性能。

多級頁面表：多級頁表可以去除頁表中的無效區(qū)域，對頁表進行索引。采用分頁存儲管理模式時，頁表會占用相當大的內(nèi)存空間。因為很難找到足夠的內(nèi)存空間來存儲頁表，所以也可以將頁表分成若干頁并進行編號，這樣就可以將每一頁離散地存儲在不同的物理塊中。為了管理這些頁表，需要建立另一個頁表，稱為外頁表，也就是頁表的索引表。外部頁表的每個頁表條目記錄頁表頁的物理塊號。

對于32位機器，采用兩級頁表結(jié)構是合適的，但對于64位機器，則需要采用多級頁表，對外層頁表進行分頁，然后將每個頁離散地分布到不相連的物理塊中，再用二級頁表映射它們的關系。

散列頁表：哈希頁表是操作系統(tǒng)用來有效管理虛擬和物理內(nèi)存地址之間的內(nèi)存映射的數(shù)據(jù)結(jié)構。與傳統(tǒng)的頁表相比，搜索速度更快，只存儲當前使用的頁面的條目就可以減小頁表的大小。

使用以邏輯頁號作為哈希值的哈希頁表。在哈希頁表中，每個頁表項都包含一個鏈表，鏈表中元素的哈希值都指向同一個位置，哈希值相同的元素使用隊列處理沖突。哈希頁表的地址轉(zhuǎn)換過程是根據(jù)邏輯頁號找到哈希值，并將這個頁號與鏈表中第一個元素的字段進行比較。如果匹配，則將對應的物理塊號和位移拼接形成物理地址；如果不匹配，則沿著鏈表依次搜索匹配的頁表項。

倒頁表：傳統(tǒng)的頁表和哈希頁表包含數(shù)百萬個頁表項，會消耗大量的內(nèi)存空間。所以引入了倒排頁表，按物理地址排序。每個物理塊都有一個條目，每個條目包含物理塊中存儲的頁面的邏輯地址和擁有該頁面的進程的信息。當使用倒排頁表進行地址轉(zhuǎn)換時，將根據(jù)進程標識符和頁碼檢索倒排頁表。如果檢索到匹配的頁表項，則頁表項的序列號(中間的)是該頁的物理塊號，它可以與頁中的地址一起用于形成物理地址，并將其發(fā)送到存儲器地址寄存器。如果搜索了整個倒排頁表，但沒有找到匹配的頁表條目，則意味著該頁還沒有被加載到內(nèi)存中。

請求頁面調(diào)度：在按需分頁中，操作系統(tǒng)僅在程序運行時將程序的必要頁面加載到內(nèi)存中。當程序啟動時，它首先不會將任何頁面加載到內(nèi)存中。當程序訪問當前不在內(nèi)存中的頁面時，會發(fā)生頁面錯誤，然后操作系統(tǒng)將所需的頁面從磁盤加載到內(nèi)存中，并相應地更新頁面表。

高級分頁：預分頁將所有頁面加載到內(nèi)存中，當進程實際引用這些頁面時，它們將被一起調(diào)用，因此加載到主存中的頁面可能會被使用，也可能不會被使用。預分頁是用來在進程開始的時候盡量減少大量的頁面錯誤，但是會有資源的浪費。

分段分頁：段-頁管理模式是將進程的邏輯地址空間分段，建立段表，實現(xiàn)分段模式下的地址翻譯，然后對每個段進行分頁建立頁表，實現(xiàn)分頁模式下的地址翻譯。大多數(shù)CPU都采用這種思路，比如Intel CPU的Intel 80386架構。

命中缺頁：當CPU試圖從主內(nèi)存中獲取所需的頁面，并且該頁面存在于主內(nèi)存(RAM)中時，這被稱為“頁面命中”，當頁面丟失時，就會發(fā)生“未命中”。當進程試圖訪問物理內(nèi)存中不存在的頁面時，就會發(fā)生頁面錯誤。頁面出錯的原因有三:一是頁面從未被加載到內(nèi)存中；第二，頁面已經(jīng)從內(nèi)存中刪除；第三，頁面在內(nèi)存中被修改，需要寫回磁盤。

操作系統(tǒng)使用分頁方法或終止進程來處理頁面錯誤。如果該頁不重要或者程序不在臨界區(qū)，則終止程序，或者將未使用的頁移到輔助存儲器，并將導致頁面錯誤的頁引入主存儲器。此外，通過使用適合當前需求并最大化頁面命中率的適當頁面替換算法，可以減輕頁面錯誤對性能的影響。

缺頁率：缺頁率是指一定時間內(nèi)缺頁中斷次數(shù)與頁面趨勢次數(shù)的比值。缺頁中斷是影響程序性能的一個重要指標。系統(tǒng)在處理缺頁中斷時會產(chǎn)生大量的開銷。通常，缺頁率越低，系統(tǒng)的性能就越高。缺頁率計算過程舉例:采用最優(yōu)替換算法，假設系統(tǒng)給一個進程分配三個物理塊，進程運行時的頁面走向為:4，3，2，1，4，3，5，4，3，2，3，5，三個物理塊一開始都是空閑的。

頁面替換：頁面替換是當一個頁面由于缺頁而中斷時所采用的策略。頁面替換算法可以選擇換出頁面，并將內(nèi)存中的頁面換出到外部存儲器。常用的頁面替換算法包括OPT、FIFO、LRU等頁面替換算法。

最佳置換算法：最好的替換算法是從存儲器中選擇不再被訪問的頁面或者在最長時間之后需要被訪問的頁面來消除。這種算法很難實現(xiàn)，因為很難準確預測頁面訪問的未來順序，但可以用來評估其他算法的優(yōu)劣。

先進先出排列算法：先進先出替換算法總是選擇在內(nèi)存中停留時間最長的頁面進行淘汰，即先進入內(nèi)存的頁面先退出內(nèi)存。這個算法很容易實現(xiàn)，但是沒有考慮到緩存頁面被使用的情況，會有一個頻繁訪問的頁面會被清除出緩存。最近一段時間內(nèi)最長時間未被訪問的頁面由最長時間替換算法選擇以被消除。這種算法的性能接近最佳算法，但實現(xiàn)起來比較困難。它需要花費巨大的系統(tǒng)開銷來找出最長時間沒有使用的頁面，為每個頁面設置相關記錄，記錄頁面訪問情況。

其他頁面替換算法

第二次機會算法：第二次機會算法是先進先出算法的改進，以避免消除頻繁使用的頁面。它與頁表中的“參考位”相結(jié)合。算法的實現(xiàn)思想是:在選擇一個頁面替換時，先檢查先入先出頁面隊列中隊列的第一頁。如果其“參考位”為0，則消除該頁面。如果為1，則將它的“參考位”清除為0。

簡單時鐘算法：簡單時鐘算法是二次機會算法的改進，也是LRU算法的近似。該算法要求為每個頁面設置一個訪問位，并將內(nèi)存中的所有頁面鏈接到一個循環(huán)隊列中。當訪問頁面時，系統(tǒng)將其訪問位設置為1。替換時，使用指針從當前指針位置開始按順序檢查頁面。如果訪問位為0，則選擇要替換的頁面。如果訪問位為1，則其被設置為0，并且重復該過程，直到找到具有0的參考頁面的頁面。最后，指針停留在被替換頁面的下一頁。

在計算機操作系統(tǒng)中，內(nèi)存分配策略包括固定分配和可變分配，在替換頁面時也可以采用兩種策略，即全局替換和局部替換。全局替換允許一個進程從所有內(nèi)存物理塊的集合中選擇過時對象，而局部替換規(guī)定每個進程只能從分配給它的物理塊中選擇過時對象。

固定分配：固定分配是一種持續(xù)的內(nèi)存管理技術，在這種技術中，主內(nèi)存被劃分為固定大小的分區(qū)(分區(qū)大小可以相等，也可以不相等)。當需要分配進程內(nèi)存時，會找到一個足夠大的空閑分區(qū)來容納該進程。然后將內(nèi)存分配給該進程。如果沒有空閑空間，進程就在隊列中等待分配內(nèi)存。

可變分配：變量分配也是一種連續(xù)內(nèi)存管理技術，在這種技術中，不會將主內(nèi)存劃分為分區(qū)，而是將足夠大的可用內(nèi)存塊分配給進程。剩余的空間被視為可用空間，可以被其他進程進一步使用。它還提供了壓縮的概念。在壓縮中，空閑空間和未分配給進程的空間組合在一起，形成一個大的內(nèi)存空間。

保護：分頁技術為進程間的內(nèi)存提供保護和隔離。通過為每個進程分配一個獨立的虛擬地址空間和頁表，保證了進程只能訪問自己的存儲空間。每個邏輯地址訪問都通過硬件地址轉(zhuǎn)換機制映射到進程的物理地址空間。這樣，所有的進程活動都被限制在它們自己的內(nèi)存空間中。確保一個進程不能訪問或修改另一個進程的內(nèi)存。

分享：操作系統(tǒng)中有許多程序和數(shù)據(jù)由多個作業(yè)共享。內(nèi)存中的每個進程在調(diào)用它們之前，必須將這些共享的程序和數(shù)據(jù)放入自己的地址空間。在共享內(nèi)存中，內(nèi)存的一部分被映射到一個或多個進程的地址空間，操作系統(tǒng)在這個內(nèi)存段中讀寫。要實現(xiàn)信息共享，需要解決共享信息的保護問題，可以通過在頁表中增加一個標志位來表示該頁的信息只讀/讀寫/可執(zhí)行狀態(tài)，并在進程訪問該頁時檢查訪問方式來實現(xiàn)。重入技術也是一種實現(xiàn)共享的技術，支持內(nèi)存的高效使用。共享程序的副本只留在內(nèi)存中，其他共享者用指針連接，幫助系統(tǒng)解決多任務共享同一個程序的問題。

優(yōu)勢：空間利用率高:進程不需要占用內(nèi)存中連續(xù)的空間，減少了內(nèi)存碎片，提高了主存的空間利用率。每個程序最多浪費不到一頁的內(nèi)存空間。

頁表結(jié)構簡單:與段表相比，頁表結(jié)構更簡單，字段更少，可以有效節(jié)省頁表所需的存儲空間。

快速地址轉(zhuǎn)換:地址轉(zhuǎn)換只需要建立虛擬頁號和實際頁號的映射關系，簡化了用戶程序加載到主存的過程，加快了地址轉(zhuǎn)換的速度。

輔助存儲管理的簡化:頁的大小通常是512字節(jié)的整數(shù)倍，現(xiàn)代存儲系統(tǒng)中常見的頁的大小范圍是1KB到16KB，簡化了輔助存儲的管理。

劣勢：程序的模塊化較差:在頁面存儲管理下，用戶程序被劃分為固定大小的頁面，程序段的實際長度不固定，因此一個頁面可能只是一個程序段的一部分，也可能在一個頁面中包含兩個或兩個以上的程序段，不能代表一個完整的程序段功能。內(nèi)存空間占用大:頁表的長度也比較長，需要占用很大的存儲空間。通常，虛擬內(nèi)存的每一頁都在頁表中占據(jù)一個存儲字。如果分頁虛擬內(nèi)存的虛擬空間為4GB，每頁的大小為1KB，則頁數(shù)為4M，頁表的容量為4M存儲字。

影響因素：分頁系統(tǒng)的性能取決于各種因素，包括頁大小、頁表大小、頁替換算法和頁表組織。

內(nèi)存管理分頁技術

頁面大小:頁面大小越大，需要的頁表就越少，這可能會導致更快的內(nèi)存訪問時間。但是，較大的頁面大小也會導致內(nèi)部碎片，并且會由于進程的實際大小與頁面大小之間的差異而浪費內(nèi)存。

頁面替換算法:分頁的性能取決于所使用的頁面替換算法，算法的選擇會影響頁面出錯的次數(shù)和訪問頁面所需的時間；用于將虛擬地址映射到物理地址的頁表大小將影響存儲器訪問速度。頁表越大，內(nèi)存訪問時間越慢。

頁表大小:頁表的組織也會影響分頁的性能。例如，分層頁表可以減小頁表的大小，提高內(nèi)存訪問速度。

系統(tǒng)顛簸:系統(tǒng)顛簸也會影響計算機系統(tǒng)的性能，是由于頻繁的頁面調(diào)度活動導致系統(tǒng)效率大大降低的現(xiàn)象。Bump在大多數(shù)情況下會使系統(tǒng)處于等待狀態(tài)，進程被頻繁訪問、調(diào)入和淘汰，會耗費大量的系統(tǒng)開銷，降低系統(tǒng)的性能。

這種現(xiàn)象可以通過添加性能分析和調(diào)整軟件，持續(xù)監(jiān)控執(zhí)行任務的缺頁情況，并動態(tài)調(diào)整它們的頁面分配，增加分配給那些產(chǎn)生大量缺頁的任務的可用頁面來解決。

翻譯后備緩沖區(qū)(TLB)：為了解決由于進程存儲器太大而導致寄存器可能無法容納所有頁表條目的問題，為頁表條目設置了一個稱為翻譯后備緩沖器(TLB)的高速緩存，以跟蹤最近使用的事務。當進行進程調(diào)用時，TLB首先檢查該頁是否已經(jīng)在主存中，如果不在主存中，它發(fā)出一個頁錯誤，然后更新TLB以包含一個新的頁條目。

軟件干預：通過添加性能分析和調(diào)整軟件，我們可以持續(xù)監(jiān)控執(zhí)行任務的缺頁情況，并動態(tài)調(diào)整它們的頁面分配。對于那些產(chǎn)生大量缺頁的任務，我們可以增加分配給它們的可用頁面來解決系統(tǒng)顛簸現(xiàn)象。