組成
哈希頁表的每一條目都包括一個鍊表的元素,這些元素哈希成同一位置(要處理碰撞)。每個元素有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。