Paging
Motivation
在 contiguous memory allocation 我們談到 external fragmentation 是記憶體無法最大化利用的元兇，原因是
- process 必須使用連續記憶體所以碎片化的記憶體無法被充分利用
- 每個 process 所需記憶體大小不同造成沒有最佳的記憶體分配方法，fragmentation 無法避免
Basic Concept
Page and Frame
我們將 physical address 切成固定的方塊，稱為 frame；也將 logical address 切成同樣大小的方塊，稱為 page。他們的大小永遠相等並且為 2 的次方
Page Table
Address Translation Scheme
當 compiler 或 loader 產生一個記憶體位址 CPU 將其分為兩個部分：
- page number ()：告訴我們這個地址在哪個 page
- page offset ()：告訴我們這個地址在那個 page 的哪裡
轉換過程便是：
- 用 page number 去查 page table 得到 frame number ()
- 把 frame number 和 page offset 做一點計算便可以得到 physical address
因此只要有足夠的 free frames 就算散落各地也沒關係，因為 page table 會負責把 page 對應到這些 free frames
Memory Protection
Protection Bit
Valid-Invalid Bit
Share Pages
Problem
Internal Fragmentation
這個方法顯然會有 internal fragmentation 的問題
Efficiency
要做到一次地址轉換我們需要存取 main memory 兩次：
- 查詢 page table（page table 存在 main memory）
- 根據算出的實際地址去存取 data
這樣效率很慢，所以引入了 TLB (Translation Look-Aside Buffer)