記憶體管理： 分頁機制
記憶體管理機制： 分頁
怎樣虛擬化記憶體來避免分段（segmentation）問題？
怎樣虛擬記憶體來避免分段問題（內部分段問題Interal segmentation fault 和外部分段問題 external segmentation fault）？
需要哪些基礎技術呢 ？
這些技術又是如何工作的呢 ？
分頁 （Paging）
透過分頁技術， 我們不在將地址空間分割為三個大小可變的邏輯分段； 而是
將地址空間分割為固定大小的單元
， 每個單元我們稱之為
頁
作業系統透過
分頁表
來儲存虛擬頁與物理地址之間的對應關係，分頁表負責地址轉換： 它將每個地址空間的虛擬頁轉化為對應的物理記憶體地址。
作業系統會為每個程序單獨建立其分頁表。不同程序的頁面表會對映到物理記憶體的不同部分（共享模組除外）
分頁的工作方式
假設我們有一塊64 bytes 的地址空間。當我們執對地址空間中某個地址執行以下命令時時：
movl
該命令會將
裡的內容載入到暫存器
eax
中。
為了實現該命令， 我們需要將
翻譯為物理地址。
我們將
分為兩部分：
VPN（virtial page number 虛擬頁碼）
offset（偏移量）
在這個例子中， 由於虛擬地址空間大小為64 bytes且每個分頁大小為16 bytes， 所以我們需要6 bits 來代表我們的虛擬地址（2^6 = 64）。
由於每個分頁大小為16bytes， 我們共計需要4個分頁，所以我們需要2 bits （2^2 = 4）來代表VPN， 其餘4 bits （2^4 = 16） 則用來確定我們需要的地址在分頁內的位置。
最後我們透過分頁表來查詢VPN 對應的物理分頁地址（physical page number， PPN a。k。a physical frame number of PFN）， 然後將offset部分新增到PPN尾端。 最終獲得了我們需要的物理地址。一個簡單的例子
movl 21， %eax
將21轉化為二進位制形式為
010101
。
分解為VPN和offset：
頁面表將VPN轉化為PFN
獲得物理地址
1110101
分頁表記憶體儲的內容
分頁表僅僅是一種用來
虛擬記憶體地址對映到物理記憶體地址
的資料結構， 或者更直白地講， 分頁表是一種
將VPN對映到PFN
的資料結構。
分頁表的每個資料單元為PTE（page-table entry 分頁表單元）
最簡單的分頁表結構為線性分頁表（linear page table）：
採用陣列來儲存資料形式。
陣列的索引為VPN。
PFN及相關資訊即為索引VPN對應的資訊。
分頁表單元（PTE）不僅儲存PF還儲存一些與該物理地址相關的資訊：
Valid bit： 表示該物理記憶體地址目前是否可用。
當一個程式執行起來後，分配在物理記憶體中堆和棧之間的物理記憶體是不可用的。其 valid bit 為
false
， 如果強行讀取， 則會生成一個系統排程。系統排程會終結該程序。
Protection bit： 表示該物理分頁的內容是否可以讀取，寫入，和執行。
如果強行讀取（寫入或執行） 一個禁止讀取（寫入或執行）的分頁， 則會生成一個系統呼叫，
Present bit： 表示該分頁是對映到物理記憶體上， 還是對映到磁碟上。
Dirty bit： 表示該分頁自載入進記憶體時起， 是否被修改過。
分頁機制的兩個問題
太慢
每次記憶體讀取都需要執行兩次記憶體讀取：
第一次讀取分頁表獲得PFN， 合成實際物理記憶體地址。
第二次讀取實際記憶體地址獲得其內容。
透過上個例項具體分析
執行命令：
movl 21， %eax
為了讀取虛擬記憶體地址
21
的內容，我們需要將虛擬記憶體地址轉化為物理記憶體地址。
首先我們需要知道當前程序的分頁表的地址。（假設該地址儲存在
Page-table base
暫存器中）
訪問 VPN 對應的 PTE（分頁表單元地址）。
然後獲得PTN。
PTN與offset 結合獲得最終物理記憶體地址。
訪問 物理記憶體地址內容// 從VPN中獲得VPN VPN = （VIrtualAddress & VPN_MASK） >> SHIFT； // 生成PTE對應的地址 PTEAddr = PageTableBaseRegister + （VPN * sizeof（PTE））； // 讀取PTE內容 PTE = AccessMemory（PTEAddr）； // 檢測該物理分頁是否可用 if （PTE。Valid == False）{ RaiseExpection（SEGMENTATION_FAULT）； } else if （CanAccess（PTE。ProtectBits） == False） { RaiseException（PROTECTION_FAULT）； } else { // 可以讀取，則生成物理記憶體地址，讀取之。 offset = VirtualAddress & OFFSET_MASK； PhysAddr = （PTE。PFN << PFN_SHIFT） | offset； Register = AccessMemory（PhysAddr）； } // VPN_MASK 設定為 0x30 （二進位制110000），與 VirtualAddress進行按位與（&）運算。SHIFT設定為4。 // PageTableRegister 表示分頁表的其實虛擬記憶體地址。 // OFFSET_MASK 二進位制值為001111。 // PFN_SHIFT值也為4。 // PTE。PFN << PFN_SHIFT：將PFN左shift了4位。 // PTE。PRN << PFE_SHIFT 之後的結果與offset進行按位或運算獲得物理記憶體地址
分頁表太大
對於一個32-bits 的地址空間，如果一個分頁大小為4Kb， 那麼虛擬記憶體地址需要12 bit（2^12約等於4000）作為offset， 其餘20 bits 作為VPN。
20 bits 作為VPN則意味著一個Page Table 要儲存2^20（大約一百萬條）條分頁表單元。
假如一條分頁表單元大小為4 bytes， 那麼整個分頁表大小約為4MB ！
如果共計有100個程序在執行， 那麼所有分頁表佔據的記憶體為400MB！！！
例項
透過一個簡單的程式來了解採用分頁機制下程式進行記憶體讀取的過程。
int array［1000］；
void main（）{
array［i］ = 0；
}
該程式對應彙編程式碼如下：
0x1024 movl $0x0， （%edi， %eax， 4） 0x1028 incl %eax 0x102c cmpl $0x03e8， %eax 0x1030 jne 0x1024
我們假設：
虛擬記憶體空間大小為64KB， 分頁大小為1KB。
分頁表為線性分頁表， 類似陣列。 分頁表的物理記憶體地址為1KB（1024）。
虛擬記憶體地址
0x1024
到
0x1034
對應的物理記憶體空間儲存程式碼， 由於分頁大小為1KB， 所以
0x1024
屬於虛擬記憶體空間的第二個分頁VPN1（第一個分頁為VPN0）， 我們假設VPN1對映到PFN4。
陣列則儲存在虛擬記憶體地址
40000
到
44000
（由於陣列大小為40000），即有VPN39到VPN42。我們假設如下對應關係：
VPN39 -> PFN 7
VPN40 -> PFN 8
VPN41 -> PFN 9
VPN42 -> PFN 10
第一行：
%edi
中儲存了這個陣列的base address，
%eax
中則儲存了陣列的索引（i）
（%edi， %eax， 4）
計算出陣列中當前單元的虛擬地址。
movl $0x0， （%edi， %eax， 4）
將數值0移動到陣列相應單元對應的虛擬記憶體地址中。
第二行：將陣列索引加1。
第三行：將陣列索引值與
0x03e8
（十進位制10000）比較。如果不相等，則執行第四行。
第四行：跳回虛擬記憶體地址
0x1024
即第一行。
執行過程：
每條命令會產生兩個記憶體訪問：
根據VPN訪問分頁表對應的分頁表單元（PTE），獲得PTN。
根據PTN和offset生成對應的物理記憶體地址。訪問對應的物理記憶體地址，獲得命令，交給CPU處理
在
movl
命令中， 每次陣列單元的訪問也會產生產生兩個記憶體訪問：
根據VPN訪問分頁表對應的分頁表單元（PTE），獲得PTN。
根據PTN和offset生成對應的物理記憶體地址， 獲得陣列單元內容。
前五個迴圈中記憶體訪問情況：
