基本介紹
- 中文名：哈希頁表
- 外文名：hashed page table
- 釋義：分頁記憶體管理方案的頁表結構
- 組成：虛擬頁碼，所映射的幀號
- 方式工作：虛擬頁號轉換到哈希表
組成,工作方式,詳細介紹,方法變種,
組成
哈希頁表的每一條目都包括一個鍊表的元素，這些元素哈希成同一位置（要處理碰撞）。每個元素有3個域：（1）虛擬頁碼（2）所映射的幀號（3）指向鍊表中下一個元素的指針
工作方式
虛擬地址中的虛擬頁號轉換到哈希表中，用虛擬頁號與鍊表中的每一個元素的第一個域相比較。如果匹配，那么相應的幀號（第二個域）就用來形成物理地址；如果不匹配，那么就對鍊表中的下一個節點進行比較，以尋找一個匹配的頁號。
詳細介紹
哈希頁表（Hash Page Table）為可變大小數據結構，頁表保存的是虛擬頁號和物理頁號之間的映射關係，其實也就是一個函式關係，將24位的VSID和16位的頁索引作為參數，通過某種函式關係映射，結果就是實際的物理記憶體中，由於這種映射關係一般通過哈希函式實現，因此頁表也稱作哈希表。頁索引為16位，而頁大小4k，由此也可見段的大小為256M（2^28）。
頁表的設計必須注意2個問題：
1． 頁表大小設計；
2． 頁表地址轉換速度。
頁表大小與邏輯地址位寬和實際的物理記憶體大小有關係。而頁錶轉換速度可以通過使用快表TLB等來提高速度。
如果TLB沒有命中，處理器必須在OS建立的頁表搜尋PTE，哈希函式就是根據虛擬地址位來訪問頁表。因此PTE必須均勻的分布在頁表中，來提高頁表的命中率。這兒有個比較費解的問題，地址轉換，需要使用頁表，而頁表地址本身就不能再次轉換，否則就是個雞與蛋的問題了，因此地址轉換，訪問頁表時，最好應在實地址模式下。
頁大小為2的N次方，起始地址也應能為頁大小的整數倍,哈希表存儲位置記憶體WIMG屬性必須為0b0010，也就是快取和記憶體一致。
頁表中由PTE組（Page Table Entry Group）組成。一個PTEG包含8個PTE，而每個PTE為8位元組，因此一個PTEG共64位元組。PTEG地址也就是表搜尋操作的入口點，哈希函式的最終功能就是根據虛擬頁號，生成PTEG地址，在主輔PTEG中找到對應的PTE。
給定一個PTE，可能存在於2個可能的PTEG中，一個是主PTEG，而另外一個是輔PTEG，而且可能存在於PTEG中的任何一個PTE內，因此一個PTE儲存在頁表中的16個可能的地址。表搜尋操作開始時，對虛擬地址執行主哈希函式，結構和SDR1暫存器中的位一起創建主PTEG的物理地址。然後對命中PTEG的每個PTE進行檢查，查看是否匹配，如果都不匹配，則執行第二個哈希函式，生成新的PTEG物理地址，重新匹配PTE。如果主PTEG和輔PTEG中都找不到該PTE，則產生缺頁故障（page fault）。
SDR1暫存器：SDR1包含了頁表結構的控制信息，包括頁表物理地址的高位，以及頁表大小。
HTABORG:頁表物理基地址
頁表大小為2^n位元組，16 <= n <= 25,也就是 64K < size < 32M，因此頁表索引必須為10 <= index <= 19，因此HTABMASK為9位，剛好對應於頁大小對應，末尾的幾個1bit加上10與哈希函式結果相與，HTABMASK低位1bit數目正好與HTABORG低位的0bit數相等。
比如1M頁表大小，2^14 * 64則:
HTABORG = 0bxxxx xxxx xxxx 0000
HTABMASK = 0b0 0000 1111
頁大小影響頁表命中率，也就影響系統性能。32位系統，頁表大小範圍見SDR1暫存器定義。推薦頁表大小，包含的PTEG數目至少應超過映射的物理頁數目一半大小，比如256M(2^28)記憶體，包含2^16個4K的頁，因此頁表包含的PTEG也至少需要一半即2^15，因此頁表大小至少為2^15 * 64 = 2M。
方法變種
為了解決在64位地址空間下的使用，人們提出了該方法的一個變種，即群集頁表(clustered page table)。群集頁表類似於哈希頁表，不過它的每一條目不僅僅包括一頁信息，而是包含了多頁。因此，一個頁表條目可以存儲多個物理頁幀的映射。群集頁表特別適合稀疏地址空間，稀疏地址空間中的地址引用不是連續的，並且分散於整個地址空間中。
