連續分配方式的缺點：
固定分區分配：缺乏靈活性，產生大量的內部碎片，內存的利用率較低
動態分區分配：會產生許多外部碎片，雖然可以用緊湊技術處理，但是緊湊技術的時間代價較高

基本分頁存儲管理

思想：把內存分為一個個相等的小分區，再按照分區大小將進程拆分成一個個小部分。

分區：頁框/頁幀/內存塊/物理塊
每一個頁框有一個編號，叫做頁框號/頁幀號/內存塊號/物理塊號，從0開始

我們將用戶進程的地址空間也分為與頁框大小相等的一個個區域，成為“頁”/“頁面”，每個頁面也有一個編號，叫做頁號。也是從0開始。

操作系統以頁框為單位為各個進程分配內存空間，進程的每個頁面分別放入一個頁框中。各個頁面不必連續存放，也不必按先后順序來，可以放到不相鄰的各個頁框中。

適用分頁存儲管理如何實現從邏輯地址到物理地址的轉換呢？

1. 算出邏輯地址對應的頁號 頁號=邏輯地址/頁面長度（整除）
2. 知道頁號對應頁面在內存中的起始地址 操作系統用某種數據結構記錄各個頁面的起始地址
3. 算出邏輯地址在頁面中的偏移量 頁內偏移量=邏輯地址%頁面長度
4. 物理地址=頁面地址+頁面偏移量

在計算機中為了方便計算頁號、頁內偏移量，頁面的大小一般為2的整數冪。

以32位邏輯地址為例，我們假設頁面的大小位4KB(4096B=2¹²B)，那么頁號就是前20位，頁內偏移量就是后12位。即如果頁面的大小為2^kB,地址總共為n位，那么后k位是頁內偏移量，前面的n-k位就是頁號，這樣就解決了1、3問題。

頁內偏移量最大等于頁面大小等于頁框大小。一個進程最多有2^n-k個頁（因為內存就這么大）

那如何知道頁號對應頁面在內存中的起始地址呢？

為了能夠知道進程的每個頁面在內存中存放的位置，操作系統要為每個進程創建一張頁表。

1. 一個進程對應一張頁表
2. 進程的每一頁對應一個頁表項
3. 每個頁表項由頁號(一般不用儲存)和塊號組成，這一頁表項對應的起始地址=塊號*內存塊的大小+頁表首地址
4. 頁表記錄進程頁面和實際存放內存塊之間的對應關系

內存/頁面大小=內存塊號的最大值
每個頁表項占字節數$N=┌(lo{g}_2內存塊號最大值)/8┐$（因為每個字節是8B）

頁表的首地址為$X$
頁號$Y$對應的頁表項的地址為$X+N?Y$

基本地址變換機構

頁表寄存器（PTR：存放頁表的起始地址F和頁表長度M）
進程未執行時，頁表的起始地址和頁表長度放在進程控制塊(PCB)中，當進程被調度時，操作系統內核會將他們放入頁表寄存器中。

頁面大小為$L$，邏輯地址$A$到物理地址$E$的變換：

1. 計算頁號$P=A/L$ 頁內偏移量$W=A\mathrm{m}\mathrm{o}\mathrm{d}L$
2. 比較頁號$P$和頁表寄存器$PTR$中頁表長度M（存儲了該進程有多少個頁）,如果$P>=M$，則發生越界中斷，否則繼續執行
3. 頁號P對應的頁表項地址=頁表起始地址F(存儲在PTR中)+P*頁表項長度（每個頁表項占多大的空間），取出頁表項內容b，即為該頁表所對應的頁框號/頁幀號/內存塊好。
4. $E=b?L+W$（如果是二進制則直接拼接）

頁內偏移量 = 頁面大小

在分頁儲存管理（頁式管理）的系統中，只要確定了每個頁面的大小，邏輯地址結構就確定了。因此，頁式管理中地址是一維的。即， 只要給出一個邏輯地址，系統就可以自動算出頁號、頁內偏移量兩個部分，并不需要顯式告訴系統這個邏輯地址中，頁內偏移量占多少位。

上面計算出頁表項長度就可以表示內存塊號的范圍，但是為了方便頁表的查詢，常常讓一個頁表項占2^kB，使得每個頁面恰好可以裝得下整數個頁表項也不至于當頁表長度超過一個頁框可以裝下的范圍的時候出現計算困難的問題。

例如：假設一個頁面4KB,32位的操作系統。則共有2²⁰個內存塊，即我們至少需要3個字節來保存內存塊的地址，每個頁表項長度為3B。頁表也是儲存在頁框中的。那么一個頁框可以存儲4096/3=1365個頁表項，最后會剩下一個字節。但是一個進程最多可以有2²⁰個頁表項，因此我們有可能需要跨頁框進行儲存。可是上一個頁框剩下的那一個字節我們不能夠再適用了，那么第1365個頁表的初始地址就不能簡單的計算為頁表起始地址+3頁號，在這里應該是頁表起始地址+3頁號+1。為了解決這個問題我們不妨讓每個頁表項占4KB，這樣就可以整除，雖然浪費了一些空間，但是計算上更加方便。

實際查詢兩次內存：第一次查詢頁表（相當于查找指針），第二次訪問內存（指針對應的值）

具有塊表的地址變換機構

局部性原理

時間局部性：如果在程序中執行了某條指令（訪問了某個數據），那么不久后這條指令（這個數據）很可能再次被訪問。（因為程序中存在大量的循環）

空間局部性：一旦程序訪問了某個儲存單元，不久之后，其附近的存儲單元也有可能被訪問。（因為很多數據在內存中都是連續存放的）

由于局部性原理，可能連續很多次查到的都是同一個頁表項。

快表

快表，又稱作聯想寄存器（TLB)，是一種訪問速度比內存快很多的高速緩沖存儲器，用來存放當前訪問的若干頁表項，以加速地址變換的過程。與此對應，內存中的頁表常稱為慢表。

1. CPU給出邏輯地址，由某個硬件算得頁號、頁內偏移量，將頁號與快表中的所有頁號進行比較。
2. 如果找到匹配的頁號，說明要訪問的頁表項在快表中有副本，則直接從中取出該頁對應的內存塊號，再將內存塊號與頁內偏移量拼接形成物理地址，最后訪問該物理地址對應的內存單元。因此，若快表命中，則訪問某個邏輯地址僅需要一次訪存即可。
3. 如果在快表中沒有找到匹配的頁號，則需要訪問內存中的頁表，找到對應頁表項，得到頁面存放的內存塊號，，再將內存塊號與頁內偏移量拼接形成物理地址，最后訪問該物理地址對應的內存單元。（需要兩次訪存）在找到頁表項以后，應同時將其存入快表，以便后面可能的再次訪問。但若快表已滿，則必須按照一定的算法對舊的頁表項進行替換。

如果快表命中就可以節省很多時間。
快表和慢表同時查找：對于查詢快表和慢表的操作是同時進行的，如果在快表中查詢到，則會停止在慢表中的查詢。

兩級頁表

單級頁表存在的問題

問題1：如果計算機按字節尋址，支持32位邏輯地址，采用分頁存儲管理，頁面大小為4KB（2¹²），頁表項長度為4B。那么一個進程最多有1M(2²⁰)個頁面，那么頁表的大小為2²²B，每一個頁框大小同樣為4KB，那么總共需要1K的頁框存儲這個頁表。這就要求所有的頁表都是連續的。這是比較困難的。

問題2：沒有必要讓整個頁表常駐內存，因為進程在一段時間內可能只需要訪問幾個特定的頁面

為了解決上面的問題，我們為頁表建立一個頁表，成為頁目錄表（外層頁表、頂層頁表），讓每一個內存塊存放一些頁表項。

在上面的例子中，一個內存塊（頁面）可以存放1K個頁表項。最多需要1K個這樣的內存塊，每個內存塊的地址為4B，剛好可以放在一個頁面中，而這個頁面就是頁目錄表。

將邏輯地址轉換為物理地址：

1. 按照地址結構將邏輯地址拆分為三部分
2. 從PCB中讀出頁目錄表地址，再根據一級頁號查頁目錄表，找到下一級頁表在內存中的存放位置
3. 再根據二級頁號以及該頁號所在的內存塊得到邏輯地址對應的內存塊
4. 結合頁內偏移量得到物理地址：內存塊*內存塊大小+頁內偏移量

注意事項

1. 若采用多級頁表機制，則各級頁表的大小不能超過一個頁面
   
2. 兩級頁表的訪存次數分析（假設沒有快表機構）
   第一級訪存：訪問內存中的頁目錄表
   第二次訪存：訪問內存中的二級頁表
   第三次訪存：訪問目標中內存單元
   n級頁表的訪存次數是n+1次