反向頁表

一般意義上，每個進程都有一個相關頁表。該進程所使用的每個頁都在頁表中有一項。這種頁的表示方式比較自然，這是因為進程是通過頁的虛擬地址來引用頁的。作業系統必須將這種引用轉換成物理記憶體地址。這種方法的缺點之一是每個頁表可能有很多項。這些表可能消耗大量物理記憶體，卻僅用來跟蹤物理記憶體是如何使用的。
為了解決這個問題，可以使用反向頁表（invertedpagetable）。反向頁表對於每個真正的記憶體頁或幀才有一個條目。每個條目包含保存在真正記憶體位置的頁的虛擬地址以及擁有該頁的進程的信息。因此，整個系統只有一個頁表，對每個物理記憶體的頁只有一條相應的條目。因為系統只有一個頁表，而有多個地址空間映射物理記憶體，所以反向頁表的條目中通常需要一個地址空間標識符，以確保一個特定進程的一個邏輯頁可以映射到相應的物理幀。採用反向頁表的系統包括64位的UltraSPARC和PowerPC。
雖然這種方案減少了存儲每個頁表所需要的記憶體空間，但是當引用頁時，它增加了查找頁表所需要的時間。由於反向頁表按物理地址排序，而查找是根據虛擬地址，因此可能需要查找整個表來尋求匹配。這種查找會花費很長時間。為了解決這一問題，可以使用哈希頁表來將查詢限制在一個或少數幾個頁表條目。當然，每次訪問哈希頁表也為整個過程增加了一次記憶體引用，因此一次虛擬地址引用至少需要兩個記憶體讀：一個查找哈希頁表條目，另一個查找頁表。為了改善性能，可以在訪問哈希頁表時先查找TLB。
反向頁表（ inverted page table ）一般被視為使用正常的系統記憶體的TLB的片外擴展。與真正的頁表不同，它不需要容納目前所有的映射。
反向頁表將一個頁表和一個幀表組合成一個數據結構。其核心是一個行數與存儲器中幀數相同的大小固定的表格。如果存儲器中有4000幀，那么反向頁表就有4000行。反向頁表中每一行都有一個條目，其中包含虛擬頁號（VPN），物理頁號（不是物理地址），其他的一些數據以及生成衝突鏈的一個方法。搜尋反向頁表結構核心的所有條目是效率低下的，因此我們使用哈希表（hash table）將虛擬地址（如果需要的話還可是地址空間/PID信息）映射到反向頁表的索引。
採用反向頁表的系統在實現共享記憶體時存在困難。共享記憶體通常作為被映射到一個物理地址的多虛擬地址來實現。這種標準的方法不能用到反向頁表，因為此時每個物理頁只有一個虛擬頁條目，一個物理頁不可能有兩個（或更多）的共享虛擬地址。解決該問題的一個簡單方法是允許頁表僅包含一個虛擬地址到共享物理地址的映射，這意味著對未被映射的虛擬地址的引用將導致頁錯誤。
反向頁表是作業系統中實現快速實虛轉換、支持頁遷移的關鍵部件，它的實現有利於提高頁遷移的效率。通常，一個遷移的候選物理頁可能被多個進程所共享。遷移過程中，需要找到所有映射到該物理頁的進程，這將多次涉及虛實地址的相互轉換。
面向頁遷移的反向頁表設計（基於CC—NUMA體系結構和Linux2．4．18核心）
1設計思想
反向頁表是作業系統中實現快速實虛轉換、支持頁遷移的關鍵部件，它的實現有利於提高頁遷移的效率．通常，一個遷移的候選物理頁可能被多個進程所共享。遷移過程中，需要找到所有映射到該物理頁的進程，這將多次涉及虛實地址的相互轉換。Linux的頁表技術完成了虛存中虛實地址的映射；我們所研究的反向頁表技術，彌補了僅僅依靠正向頁表實現實虛映射所帶來的開銷，能夠通過遷移頁的物理地址快速定位需要修改的進程頁表項。
2反向頁表在頁遷移中的作用
頁遷移的設計目標是通過動態地開發數據局部性，來減小遠程存儲開銷。實現頁遷移的關鍵技術之一是控制頁遷移本身的開銷，否則頁遷移所帶來的數據局部性好處可能被頁遷移本身的開銷抵消。
反向頁表在頁遷移中的作用是根據中斷給出的物理地址，迅速定位到進程PTE表項的虛地址。從而在頁遷移過程中能夠快速將遷移後新頁的物理地址填入該PTE表項．當多個進程共享遷移頁時，通過查找反向頁表能夠同時定位多個進程的頁表項，同傳統頁遷移技術相比，不需遍歷整個進程地址空間，有效地降低了遷移開銷。
3反向頁表數據結構設計
反向頁表技術的主要設計思想是，在傳統頁表基礎上，為每個物理頁增加一個反向指針集合，指向使用該物理頁的各個頁表項，形成物理地址到虛地址的反向映射。如圖所示，其中虛線部分表示反向頁表結構。
反向頁表及其映射關係
反向頁表結構


4性能分析
反向頁表提供了進程頁表的反向映射。它能夠指出哪個進程用到了該物理頁，及其對應的虛地址。通過運用反向頁表，與傳統方法相比，頁遷移的實現存在以下優勢：
·因頁遷移而引起對頁表項的修改時，不需要遍歷所有進程的虛存，僅僅搜尋頁面的反向頁表。這意味著頁遷移代碼僅僅做很少的記憶體搜尋工作．對於頻繁的遷移複製來說，減少了頁遷移/複製開銷。
·當多個進程共享同一物理頁時，可以迅速通過物理頁的地址找到所有的PTE項。
·當負載很大時，記憶體管理可以花費較少的CPU時間，提高頁遷移/複製的效率。
這種方法的不足之處是存在鍊表存儲空間的開銷。系統中的每一個物理頁結構都要維護一個額外的鍊表結構pte—chain．一個記憶體大小為256MB的系統中物理頁的數目為64k，則需要為反向頁表分配64×(sizeof(structpte—chain))kB大小的物理記憶體。與頁表所占據的空間相比，這個數目比較可觀。而且為反向頁表分配記憶體空間時，可能存在濫出或越界的問題。
儘管如此，經過測試，在高端系統和負載很大的情況下，反向頁表支持的頁遷移系統性能明顯優於傳統頁遷移系統。