paging是指把process的address space切成多個等分的塊，每塊稱為一個page，而physical memory也相應地切成等分的page，又稱為page frames，每個frame剛好可以容納一個address space的page。
paging有幾個好處，第一個是很彈性，我無須再去理會process是如何使用自己的address space的，例如它是heap還是stack，它的增長方向到底是往上還是往下等等。
第二個好處是簡化了free-space的管理，假設現在kernel要為一個process分配address space且一個process需要4個page的空間，那麼kernel可以maintain一個free list存放著目前free的所有physical page frame，然後拿其中四個出來裝這個process的page即可。
另外paging由於是大小等分的塊，不會有external fragmentation。
virtual address
從process的視角來看，有一塊連續的address space，假設總大小為64bytes，以16bytes為一個page，總共就會有4個page。
而假設整個physical memory為128bytes，總共就有8個page frame。
把一個process A的4個page分別放到不同的frame，例如page0->frame3，page1->frame7，page2->frame5，page3->frame2。
從程式的視角來看，地址都是連續的，且地址就是0~63，但這0~63是virtual address。
實際上，當CPU要讀取或寫入某個virtual address(VA)時，會將其轉換成對應的physical address(PA)，例如VA0~15會被轉成PA48~63，因為page0->frame3，而VA16~31會被轉成PA112~127，看似連續的VA其實是分散在physical memory中。
page table
kernel會給每個process一張自己獨立的page table，記載著自己的page被放在哪些frame中，依照table，virtual page(VP)會被轉成physical frame(PF)，完成VA->PA的轉換。
以上面的例子來說，會有一個table寫著VP和PF的對應，page0->frame3，page1->frame7，page2->frame5，page3->frame2。
這時候如果還有另一個process B，它也有4個page的address space，和一張自己的page table，VA也是0~63，但是它的4個page就會被放到跟A不同的frame中。
因此A跟B都有0~63的VA，但實際上對應的PA並不同，這樣他倆就不能互相讀取修改對方的資料，達到安全隔絕的效果。
不過也有個情況是兩個process的page對應到同個frame，用來做share code或data。
如果frame不夠了，例如上面的例子，其實放了A後剩下的空間是放不下B的，因為總共8個frame而已，扣除A用的4個frame剩下的空間其實不滿4個frame，因為OS本身也需要佔據memory(可能佔走兩個frame)，又或者再來一個process C的話該怎麼辦，之後再寫。
address translations
接下來看VA如何透過table轉成PA。
因為每個process的space是64bytes，所以只需要6個bit來表示VA，把VA拆成兩個部分來看，第一是virtual page number(VPN)，第二是offset。
用前兩個bit(msb)表示page number(因為總共4個page，用2個bit即可表示)，後四個bit表示offset。
延續前面的例子
假設有個指令要執行，會把VA 21存的值放到eax(這裡先不談執行這條指令前，要先去哪fetch這條指令的問題)。
1 | movl 21, %eax |
VA是21，轉成6bits就是010101，前兩個bit代表著VA21在哪一個page，後4個bit代表VA21在該page的offset，也就是VA21在page1內(前兩個bit是01，第二個page)，且offset為0101(從page1開始offset 5)。
可以算一下，page1的起始位址是16，offset 5，因此16+5就是21。
接下來拿01去查表，對應的是PFN(physical frame number)是7，再加上offset 0101，前三個bit對應PFN(因為共有8個frame，需要三個bits表示)，後四個bit對應offset，因此VA21對應到的PA就是1110101，十進位的117。
page table entry
page table基本上就是用來把virtual pager number(VPN)轉成physical frame number(PFN)的，因此這裡先假設page table是一個linear的array，index就是VPN，因此table[0]的內容就是page0對應的PFN，還有其他相關的flag。
PTE的內容除了PFN外還有以下
valid bit
valid bit表示該page的轉換是否有效，如果process嘗試存取被標記invalid的page，可能會被OS終止執行。又例如一個4G的address space，以4K為一個page，總共就有2^20個page，但不可能每個page都有使用，而且如果每個page明明沒在用卻又要分配一個frame給它，那很浪費physical frame，因此可以把沒使用的page標記成invalid，這樣也無須分配frame給invalid的page，可以大幅節省physical memory。
protection bit
page的RWX權限，如果寫入不可寫的page會trap到OS。
present bit
用來標示page是在physical memory還是在disk上，也就是判斷page是不是被swap out了。
swap可以支援address space大於physical memory的問題，它可以把比較少用的page放到硬碟中，因此釋放出physical frame。
dirty bit
判斷page是否有被修改過。
reference/accessed bit
用來track page是否有被存取，可以用來決定哪些page比較常使用，在page replacement的時候會需要這個資訊。
一些問題
page table 很大
前面的例子都是比較簡單的情況，如果address space是4G而page大小是4K的話，總共會有2^20個page，那麼page table就會有2^20個entry，每一個entry佔4bytes的話，一個table就要大概4MB，process數量假設有100個，就要占掉400MB的memory來裝這些table。
由於page table很大，因此存在memory中，而不會在MMU等硬體內。
這裡先認為所有page table都存在OS管理的physical memory中，後面會看到OS自己的memory也能被virtualize，而page table會存在OS的virtual memory中，甚至swap到硬碟中，但這後面再說。
paging 很慢
還是用上面的例子
1 | movl 21, %eax |
為了要存取到VA21對應的PA，要先知道該process的page table在哪裡，目前先假設有個page-table base register(PTBR)，存著page table的PA。
第一步先靠PTBR找到PTE[21]的PA
1 | VPN = (VirtualAddress & VPN_MASK) >> SHIFT |
這裡的VPN_MASK是0x30(110000)，SHIFT是4，21(010101) & VPN_MASK的結果就是010000，再右移4bits，就會得到VPN=01的結果，然後拿01 * sizeof(PTE)再加上PTBR的PA，就能算出PTE[21]的PA了。
第二步就是去存取PTE[21]的內容，取得PFN後，左移SHIFT再和從VA取得的offset結合，就能得到正確對應的PA了。
1 | offset = VirtualAddress & OFFSET_MASK |
這裡的OFFSET_MASK是001111。
總之，硬體會先根據PTBR，查表存取一次PTE的PA，再依查表的結果去存取正確的PA，這會有兩次存取PA的過程，每一次讀寫memory都要有一個額外查表的動作，拖慢了速度。
下圖可以看到有兩次的AccessMemory。
1 | // Extract the VPN from the virtual address |
後面會再寫到這兩個問題的解法。