虛擬記憶體之頁表
為何需要邏輯地址
由於系統中的物理記憶體是隨分配不斷在變化的，有時候這個程式使用，有時候那個程式在使用。如果不使用邏輯地址直接使用物理地址，那當前程序操作的地址被佔用，則不能使用記憶體。透過將連續的邏輯地址對映成不連續的物理地址，程式將只用關係的連續的邏輯地址，而物理地址再透過一些方法找到並對映過去就行了。
考慮一種簡單的對映方法：
如果簡單的使用
<物理地址起始地址，大小>
實現：程式A申請前0-199的記憶體，程式B申請200-299的記憶體。但程式A的200記憶體並沒有完成使用，大部份是空閒的，將會造成記憶體浪費。這種其實地址加大小的定址方式就是所謂的
可變分割槽管理
。容易產生外碎片。
如果此時程式A釋放，程式C想要申請300的記憶體，但是程式A釋放的0-199不足以滿足C的要求，C需要尋找更大塊的記憶體，而程式A釋放導致的空閒記憶體一直沒被用上，導致浪費。
記憶體碎片
內碎片：申請一段空間，但是沒有完全使用，一部分記憶體的空閒的，造成浪費
用不上
外碎片：申請一段空間，但是前邊剩餘的一段不滿足，需要找後邊的大塊記憶體。前邊剩餘的記憶體一直用不上操作從浪費
塞不下
因此引入分頁機制來最佳化記憶體碎片問題
分頁
將程式的邏輯地址空間分為若干等大的頁，稱為
頁/頁面/虛頁
。同樣將物理記憶體分成若干項大小同虛頁大小的頁，稱為
塊/頁幀/實頁
。虛頁是連續的，實頁是不連續的，
頁表
就維護了虛頁到實頁的對映關係，頁表中每一項稱為
頁表項(PTE)
，表示一個虛頁到實頁是對映關係。每個程序都有自己的頁表，稱為
程序頁表
。
程式中使用的虛地址大致如下：
|頁號|頁內偏移|
頁表中的內容大致如下（當然還可以有一些標誌資訊，如是否有讀寫許可權、是否可用等）：
頁號1： |標記|物理頁號|
頁號2： |標記|物理頁號|
頁號3： |標記|物理頁號|
頁號4： |標記|物理頁號|
標註頁號僅表示頁表項之間的位置關係（連續），不佔用實際記憶體
每個程序為了找到自己的程序頁表還需要
頁表基地址暫存器(PTBR)
的幫忙，其指向程序頁表的實頁號/頁表起始地址（
PPN
）。程序切換時會切換PTBR的值。
注意
，頁號表示頁表項之間的位置關係（連續），實際不佔物理記憶體，透過
PTBR+頁號x頁表項大小算出目標地址
由虛地址到實際物理地址的變化叫做記憶體對映，過程如下：
┌────┐ ┌────────┬─────────┐
│PTBR│ │虛擬頁號│ 頁內偏移│ 主存
└─┬──┘ └──┬─────┴────┬────┘ ┌─────────────┐
│ │ │ │ │
│ │ │ │ │
│ │ │ │ │
│ │ │ ├─────────────┤
└──────────+──────────┼────────────►│ │
│ 物理頁號 │page table │
x─◄───────────┤ │
│ ├─────────────┤
│ │ │
│ │ │
│ │ │
│ 物理地址 │ │
└───────────► │ │
│ │
│ │
└─────────────┘
如果對應地址缺頁，則會觸發缺頁中斷。進入核心態（異常/中斷型），從磁碟換入或載入記憶體並填寫到記憶體中，並填寫幀號，然後重新進行定址過程。
如
0x000011a3
的地址對映過程
邏輯地址32位=20位頁號+12位頁內偏移
頁表項32位=20位塊號（與20位頁號對應）+12位標記位
物理地址=20位塊號+12為頁內偏移
頁表如下：
起址：PTBR
+頁號 |標記| 幀號 |
|——|————————|
+0x00001 -> | | 0x000f3 |
第一次訪問記憶體，透過PTBR+0x00001找到對應的頁表項的地址，讀取物理頁號/頁幀/實頁號。再透過幀號0x000f3
拼接
頁內偏移0x1a3得到物理地址（不需要加法，一部分高位，一部分低位，直接拼接更快），第二次訪問記憶體讀取資料。
至少需要兩次記憶體訪問
分頁機制的最佳化
要真正獲取一個記憶體中的內容實際需要載入兩次記憶體，第一次是查頁表找到物理頁號，第一次是根據物理頁號加頁內偏移到對應記憶體，因此可以進行時間上的最佳化。而每個程序都需要維護一個頁表，頁表本身也是佔記憶體空間的，因此還可以進行空間最佳化。
空間最佳化與多級頁表
引入多級頁表有兩個原因
如果頁表大小超過了一個頁面的大小/容量，則可能將資料存放到兩個不同的頁面
，將無法透過PTBR+頁號的方式找到
如通常一個頁4KB，32位系統中一PTE有32位4B，故PTE數不應超過1k
程序頁表本身也是在記憶體中的，需要佔用記憶體空間
如果不考慮頁面容量問題，
假設一個頁能容納所有頁表項
。一個32位的系統和程式，如果頁內偏移12位，要訪問全部4G記憶體則需要2^20個物理塊/物理頁面/物理頁號，對應就有2^20個頁號/虛頁號，即2^20個頁表項：
|12位標記位|20位表示物理頁號|
這麼一個頁表項32bit=4B，則維護一個程序的頁表需要佔用2^20x4B=4MB的記憶體空間。4MB看起來很小，但是作業系統是要執行很多程式的。
如果使用多級頁表，應當
頁表大小==頁面容量
，如將32位分為10位，10位，12位的分級方式。為何10位？10位能索引2^10個PTE，而每個PTE佔4B，一個頁表剛好就4KB，與頁容量相同。如果小於頁容量會產生內碎片，浪費；如果大於頁容量則無法透過頁表起址+offset定址。
64位系統中則常用9位索引頁表，64bit=8B，8Bx2^9=4KB，也剛好是一個頁的大小。
虛地址：
| VPN［1］ | VPN［0］ | 頁內偏移 |
PTE：
| PPN［1］ | PPN［0］ | 頁內偏移 |
PTBR指向一級頁表起始地址，加上VPN［1］可以索引到對應頁表項，一級頁表中的PPN［1］PPN［0］就是二級頁表的起始地址，再透過VPN［0］索引二級也被即可得到物理頁號，加上頁內偏移得到物理地址。
┌────┐ ┌──────┬─────┬───────┐
│PTBR│ │ VPN1 │VPN0 │offset │
└─┬──┘ └──┬───┴──┬──┴───┬───┘ ┌─────────────┐
│ │ │ │ │ │
│ │ │ │ ├─────────────┤
└─────────x──────┼──────┼──────────────────►│xxxxxxxxxxxxx│
│ │ │x L0 xx│
│ │ PPN1，PPN0 │x xx│
x──────┼─────◄─────────────┤xxxxxxxxxxxxx│
│ │ ├─────────────┤
│ │ │ │
│ │ │ │
│ │ │ │
│ │ ├─────────────┤
└──────┼──────────────────►│xxxxxxxxxxxxx│
│ │x L1 xxx│
│ PPN1，PPN0 │x xxx│
x─────◄─────────────┤xxxxxxxxxxxxx│
│ ├─────────────┤
│ │ │
│ │ │
│ │ │
│ │ │
│ │ │
└──────────────────►│ │
│ │
│ │
│ │
│ │
│ │
└─────────────┘
如果發現第一級只有3項指向第二級，而第二級頁表有2^10項，所以一共3個頁表需要（2^10+3x2^10）x4B = 16KB的記憶體空間。
當然上限還是2^10x2^10個表項x4B佔4M空間。
問題就是記憶體的訪問次數增加了
時間最佳化
前面使用多級頁表的方式雖然，減少了空間佔用，但是記憶體的訪問次數增加了。
TLB
將最常訪問的幾個（一般8-128個左右）頁表項儲存到訪問速度更快的硬體中，如關聯儲存器（相當於雜湊表），這個小表的名稱為
TLB (Translation Lookaside Buffer)
或
快表
。定址會同時尋找TLB和頁表，如果TLB命中則查頁表定址的操作作廢。
使用大頁
依舊上述多級頁表的例子，但是使用某種機制讓大頁表地址連續，那麼就可以使用起址+offset的方式定址，而不需要多級頁表多次訪問記憶體。
虛地址：
| VPN［1］ | VPN［0］ | 頁內偏移 |
PTE：
| PPN［1］ | PPN［0］ | 頁內偏移 |
只是訪問一級頁表（L0）時其返回PPN［1］作為大頁的索引（高10位），然後使用虛擬地址的
所謂大頁的頁內偏移。如此一來訪問次數就降低了。
┌────┐ ┌──────┬─────┬───────┐
│PTBR│ │ VPN1 │VPN0 │offset │
└─┬──┘ └──┬───┴──┬──┴──┬────┘
│ │ │ │
│ │ └──┬──┘ ┌─────────────┐
│ │ │ │ │
│ │ │ ├─────────────┤
└───────x─────────┼───────────►│xxxxxxxxxxxxx│
│ │x L0 xx│
│ PPN1， │x xx│
x───────◄────┤xxxxxxxxxxxxx│
│ ├─────────────┤
│ │ │
│ │ │
│ │ │
│ ├─────────────┤
└───────────►│ │
│ huge page │
│ │
│ │
│ │
│ │
│ │
│ │
├─────────────┤
└─────────────┘
