文章目錄

• • • 1 基本分頁存儲管理
    • • 1.1 什么是分頁存儲
      • 1.2 重要的數據結構——頁表
      • 1.3 基本地址變換機構
      • 1.4 具有快表的地址變換機構
      • • 1.4.1 什么是快表（TLB）
        • 1.4.2 引入快表后，地址的變換過程
        • 1.4.3 地址變換過程小結
      • 1.5 兩級頁表
      • • 1.5.1 單級頁表存在的問題，為啥引入兩極頁表
        • 1.5.2 兩級頁表的原理、地址結構
        • 1.5.3 二級頁表如何實現地址變換
        • 1.5.4 二級頁表小結
    • 2 基本分段存儲管理方式
    • • 2.1 分段
      • 2.2 段表
      • 2.3 地址變換
      • 2.4 分段、分頁管理的對比
      • 2.5 分段存儲管理小結
    • 3 段頁式存儲管理
    • • 3.1 分頁、分段優缺點分析
      • 3.2 分段+分頁=段頁式管理
      • 3.3 段頁式管理的邏輯地址結構
      • 3.4 段表、頁表
      • 3.5 段頁式管理地址變換過程
      • 3.6 段頁式管理小結

1 基本分頁存儲管理

連續分配：為用戶進程分配的必須是一個連續的內存空間。
非連續分配：為用戶進程分配的可以是一些分散的內存空間。

1.1 什么是分頁存儲

將內存空間分為一個個大小相等的分區（比如：每個分區4KB），每個分區就是一個“頁框”（頁框=頁幀=內存塊=物理塊=物理頁面）。每個頁框有一個編號，即“頁框號”（頁框號=頁幀號=內存塊號=物理塊號=物理頁號），頁框號從 0 開始 。

將進程的邏輯地址空間也分為與頁框大小相等的一個個部分， 每個部分稱為一個“頁”或“頁面” 。每個頁面也有一個編號， 即“頁號”，頁號也是從 0 開始 。

操作系統以頁框為單位為各個進程分配內存空間。進程的每個頁面分別放入一個頁框中。也就是說，進程的頁面與內存的頁框有一一對應的關系。 各個頁面不必連續存放，可以放到不相鄰的各個頁框中。
（注意：進程的最后一個頁面可能沒有一個頁框那么大。也就是說，分頁存儲有可能產生內部碎片，因此頁框不能太大，否則可能產生過大的內部碎片造成浪費）

1.2 重要的數據結構——頁表

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

注：頁表通常存在PCB（進程控制塊）中

一個進程對應一張頁表

進程的每個頁面對應一個頁表項

每個頁表項由“頁號”和“塊號”組成

頁表記錄進程頁面和實際存放的內存塊之間的映射關系

每個頁表項的長度是相同的

核心問題：

每個頁表項多大？占幾個字節？

如何通過頁表實現邏輯地址到物理地址的轉換？

已知計算機中內存塊的數量→頁表項中塊號至少占多少字節？

假設某系統物理內存大小為4GB，頁面大小為4KB，則每個頁表項至少應該為多少字節？

內存塊大小=頁面大小=4KB=2¹² B

4GB的內存總共會被分為 2³²/2¹² =2²⁰個內存塊

內存塊號的范圍應該是0~ 2²⁰-1

內存塊號至少要用20bit來表示 →至少要用3B來表示塊號（3*8=24bit）

頁表項連續存放，因此頁號可以是隱含的，不占存儲空間（類比數組）

引出問題：假設頁表中的各頁表項從內存地址為X的地方開始連續存放…
如何找到頁號為i的頁表項？
i號頁表項的存放地址=X+3*I因此，頁表中的頁號可以是隱含的，即頁號不占用存儲空間

假設某系統物理內存大小為4GB，頁面大小為4KB，則每個頁表項至少應該為多少字節？

內存塊大小=頁面大小=4KB=2¹² B

4GB的內存總共會被分為 2³²/2¹² =2²⁰個內存塊

內存塊號的范圍應該是0~ 2²⁰-1

內存塊號至少要用20bit來表示 →至少要用3B來表示塊號（3*8=24bit）

由于頁號是隱含的，因此每個頁表項占3B，存儲整個頁表至少需要3*(n+1)B

如何實現地址的轉換

進程在內存中連續存放時 ， 操作系統是如何實現邏輯地址到物理地址的轉換的？
過程如下：

思考：將進程地址空間分頁之后 ，操作系統該如何實現邏輯地址到物理地址的轉換 ？

特點：雖然進程的各個頁面是離散存放的，但是頁面內部是連續存放的

如果要訪問邏輯地址A，則 ：

確定邏輯地址A對應的“頁號”P

找到P號頁面在內存中的起始地址（需要查頁表）

確定邏輯地址A的“頁內偏移量”W
邏輯地址A對應的物理地址=P號頁面在內存中的起始地址+頁內偏移量W

子問題：如何確定一個邏輯地址對應的頁號、頁內偏移量？

Eg：在某計算機系統中，頁面大小是50B。某進程邏輯地址空間大小為200B，則邏輯地址110對應的頁號、頁內偏移量是多少？

如何計算：
頁號=邏輯地址/頁面長度 （取除法的整數部分）
頁內偏移量=邏輯地址%頁面長度（取除法的余數部分）

本例中頁號=110/50=2
頁內偏移量=110%50=10

邏輯地址可以拆分為（頁號，頁內偏移量）
通過頁號查詢頁表，可知頁面在內存中的起始地址
頁面在內存中的起始地址+頁內偏移量=實際的物理地址

邏輯地址→物理地址，二進制轉化

在計算機內部，地址是用二進制表示的， 如果頁面大小剛好是2的整數冪，則計算機硬件可以很快速的把邏輯地址拆分成（頁號，頁內偏移量）

假設某計算機用32個二進制位表示邏輯地址，頁面大小為4KB =2¹² B=4096B

0號頁的邏輯地址范圍應該是0-4595，用二進制表示應該是： 00000000000000000000000000000000~00000000000000000000111111111111

1號頁的邏輯地址范圍應該是4096~8191，用二進制表示應該是： 00000000000000000001000000000000~00000000000000000001111111111111

2號頁的邏輯地址范圍應該是8192~12287，用二進制表示應該是： 00000000000000000010000000000000~00000000000000000010111111111111

Eg：邏輯地址2，用二進制表示應該是00000000000000000000000000000010
頁號=2/4096=0=00000000000000000000
頁內偏移量=2%4096=2=000000000010

Eg：邏輯地址4097，用二進制表示應該是00000000000000000001000000000001
頁號=4097/4096=1=00000000000000000001
頁內偏移量=4097%4096=1=000000000001

如果每個頁面大小為2^KB，用二進制數表示邏輯地址， 則末尾K位即為頁內偏移量，其余部分就是頁號

假設物理地址也用32個二進制位表示，則由于內存塊的大小=頁面大小，因此：

0號內存塊的起始物理地址是00000000000000000000000000000000

1號內存塊的起始物理地址是00000000000000000001000000000000

2號內存塊的起始物理地址是00000000000000000010000000000000

3號內存塊的起始物理地址是00000000000000000011000000000000

根據頁號可以查詢頁表，而頁表中記錄的只是內存塊號，而不是內存塊的起始地址！
起始地址計算： J號內存塊的起始地址=J*內存塊大小

假設通過查詢頁表得知1號頁面存放的內存塊號是9（1001），
則9號內存塊的起始地址=9X4096=00000000000000001001000000000000
則邏輯地址4097對應的物理地址=頁面在內存中存放的起始地址+頁內偏移量 =（00000000000000000011000000000001）

結論：如果頁面大小剛好是2 的整數冪，則只需把頁表中記錄的物理塊號拼接上頁內偏移量就能得到對應的物理地址

1.3 基本地址變換機構

基本地址變換機構可以借助進程的頁表將邏輯地址轉換為物理地址。

通常會在系統中設置一個頁表寄存器（PTR），存放頁表在內存中的起始地址F和頁表長度M。

進程未執行時，頁表的始址和頁表長度放在進程控制塊（PCB）中，當進程被調度時，操作系統內核會把它們放到頁表寄存器中。

注意：頁面大小是2的整數冪

設頁面大小為L，邏輯地址A到物理地址E的變換過程如下：

變換過程說明：

計算頁號P和頁內偏移量W（十進制手算：P=A/L，W=A%L；但是在計算機實際運行時，邏輯地址結構固定不變，因此計算機硬件可以更快地得到二進制表示的頁號、頁內偏移量）

比較頁號P和頁表長度M，若P>=M，則產生越界中斷，否則繼續執行
（注意：頁號從0開始，而頁表長度至少是1，因此P=M時也會越界）

頁表中頁號P對應的頁表項地址=頁表起始地址F+頁號P*頁表項長度，取出改頁表項內容b，即為內存塊號。
注意區分頁表項長度、頁表長度、頁面大小的區別、頁表長度指的是這個頁表中總共有幾個頁表項，即總共有幾個頁；頁表項長度指的是每個頁表項占多大存儲空間；頁面大小指的是一個頁面占多大的存儲空間

計算E=b*L+W，用得到的物理地址E去訪存。（如果內存塊號、頁面偏移量是用二進制表示的，那么把二者拼接起來就是最終的物理地址了）

例：若頁面大小L為1K字節，頁號2對應的內存塊號b=8，將邏輯地址A=2500轉換為物理地址E。

題目等價描述：某系統按字節尋址，邏輯地址結構中，頁內偏移量占10位，頁號2對應的內存塊號b=8，將邏輯地址A=2500轉換為物理地址E。
頁內偏移量占10位，說明一個頁面的大小L為2¹⁰B=1KB

計算頁號、頁內偏移量
頁號P=A/L=2500/1024=2；頁內偏移量W=A%L=2500%1024=452

根據題中條件可知，頁號2沒有越界，其存放的內存塊號b=8

物理地址E=b*L+W=8X1024+452=8644

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

1.4 具有快表的地址變換機構

快表的地址變換機構：是基本地址變換機構的改進版本

1.4.1 什么是快表（TLB）

快表，又稱聯想寄存器（TLB，translation lookaside buffer ），是一種訪問速度比內存快很多的高速緩存（TLB不是內存！），用來存放近訪問的頁表項的副本，可以加速地址變換的速度。 與此對應，內存中的頁表常稱為慢表。

1.4.2 引入快表后，地址的變換過程

CPU給出邏輯地址，由某個硬件算得頁號、頁內偏移量，將頁號與快表中的所有頁號進行比較。

如果找到匹配的頁號，說明要訪問的頁表項在快表中有副本，則直接從中取出該頁對應的內存塊號，再將內存塊號與頁內偏移量拼接形成物理地址，然后訪問該物理地址對應的內存單元。因此， 若快表命中，則訪問某個邏輯地址僅需一次訪問內存即可。

如果沒有找到匹配的頁號，則需要訪問內存中的頁表，找到對應頁表項，得到頁面存放的內存塊號，再將內存塊號與頁內偏移量拼接形成物理地址，然后訪問該物理地址對應的內存單元。因此， 若快表未命中，則訪問某個邏輯地址需要兩次訪存
（注意：在找到頁表項后，應同時將其存入快表， 以便后面可能的再次訪問。但若快表已滿，則必須按照一定的算法對舊的頁表項進行替換）

由于查詢快表的速度比查詢頁表的速度快很多，因此只要快表命中，就可以節省很多時間。 因為局部性原理，一般來說快表的命中率可以達到90%以上。

• 例：某系統使用基本分頁存儲管理，并采用了具有快表的地址變換機構。訪問一次快表耗時1us，訪問一次內存耗時100us。若快表的命中率為90%，那么訪問一個邏輯地址的平均耗時是多少？

(1+100)* 0.9+(1+100+100)* 0.1=111us

說明：

(1+100)* 0.9 訪問邏輯地址，首先優先根據頁號查詢快表，耗時1us，若快表命中，就可以得到邏輯地址對應的最終的物理地址，再訪問一次內存，就是訪問我們最終要訪問的物理單元，所以命中耗時101us；

若快表未命中，需要訪問內存，查詢慢表，最后就可以得到邏輯地址對應的最終的物理地址，再訪問一次內存，就是訪問我們最終要訪問的物理單元，所以未命中耗時201us；

不管命中否，首先都得訪問一次快表；

本題是優先查詢快表。

• 有的系統支持快表和慢表同時查找，如果是這樣，平均耗時應該是(1+100)* 0.9+(100+100)* 0.1= 110.9us 若未采用快表機制，則訪問一個邏輯地址需要100+100=200us 顯然，引入快表機制后，訪問一個邏輯地址的速度快多了。

1.4.3 地址變換過程小結

TLB和普通Cache的區別：

TLB中只有頁表項的副本，而普通Cache中可能會有其他各種數據的副本

1.5 兩級頁表

1.5.1 單級頁表存在的問題，為啥引入兩極頁表

單級頁表：

某計算機系統按字節尋址，支持32位的邏輯地址，采用分頁存儲管理，頁面大小為4KB，頁表項長度為4B。
4KB=2¹²B，因此頁內地址要用12位表示，剩余20位表示頁號。
因此，該系統中用戶進程最多有2²⁰ 頁。相應的，一個進程的頁表中，最多會有2²⁰ =1M=1048576個頁表項，所以一個頁表最大需要 2²⁰ * 4B=2²² B，共需要2²² /2¹² =2¹⁰ 個頁框存儲該頁表。
根據頁號查詢頁表的方法：K號頁對應的頁表項存放位置=頁表始址+K* 4
要在所有的頁表項都連續存放的基礎上才能用這種方法找到頁表項

根據局部性原理可知，很多時候，進程在一段時間內只需要訪問某幾個頁面就可以正常運行了。因此沒有必要讓整個頁表都常駐內存。

思考：我們是如何解決進程在內存中必須連續存儲的問題的？
將進程地址空間分頁，并為其建立一張頁表，記錄各頁面的存放位置同樣的思路也可用于解決“頁表必須連續存放”的問題，把必須連續存放的頁表再分頁，從而將頁表拆開

把頁表再分頁并離散存儲，然后再建立一張頁表記錄頁表各個部分的存放位置，稱為頁目錄表，或稱外層頁表，或稱頂層頁表

1.5.2 兩級頁表的原理、地址結構

32位邏輯地址空間，頁表項大小為4B，頁面大小為4KB，則頁內地址占12位 ，采用單級頁表：

因此，該系統中用戶進程最多有2²⁰ 頁。相應的，一個進程的頁表中，最多會有2²⁰ =1M=1048576個頁表項，所以一個頁表最大需要 2²⁰ * 4B=2²² B，共需要2²² /2¹² =2¹⁰ 個頁框存儲該頁表。

現在把頁表再分頁并離散存儲，然后再建立一張頁表記錄頁表各個部分的存放位置，稱為頁目錄表，或稱外層頁表，或稱頂層頁表

10位一級頁號剛好可表示0~1023

1.5.3 二級頁表如何實現地址變換

例：將邏輯地址(0000000000,0000000001,111111111111)轉換為物理地址（用十進制表示）。

按照地址結構將邏輯地址拆分成三部分

從PCB中讀出頁目錄表始址，再根據一級頁號查頁目錄表，找到下一級頁表在內存中的存放位置

根據二級頁號查二級頁表，找到最終想訪問的內存塊號

結合頁內偏移量得到物理地址

最終要訪問的內存塊號為4
該內存塊的起始地址為4*4096=16384
頁內偏移量為4095
最終的物理地址為 16384+4095=20479

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

可以在需要訪問頁面時才把頁面調入內存（虛擬存儲技術）。可以 在頁表項中增加一個標志位，用于表示該頁面是否已經調入內存

若分為兩級頁表后，頁表依然很長，則可以采用更多級頁表，一般來說各級頁表的大小不能超過一個頁面
例：某系統按字節編址，采用40位邏輯地址，頁面大小為4KB，頁表項大小為4B，假設采用純頁式 存儲，則要采用（）級頁表，頁內偏移量為（）位？

頁面大小= 4KB =2¹²B，按字節編址，因此頁內偏移量為12位
頁號= 40-12 = 28位
頁面大小= 2¹²B，頁表項大小= 4B ，則每個頁面可存放2¹² / 4 = 2¹⁰個頁表項
因此各級頁表最多包含2¹⁰個頁表項，需要10 位二進制位才能映射到2¹⁰個頁表項，因此每一級的頁表對應頁號應為10位。總共28位的頁號至少要分為三級

如果只分為兩級頁表，則一級頁號占18位， 也就是說頁目錄表中最多可能有2¹⁸個頁表項，超過了一個頁面， 顯然，一個頁面是放不下這么多頁表項的

兩級頁表的訪存次數分析（假設沒有快表機構）

第一次訪存：訪問內存中的頁目錄表
第二次訪存：訪問內存中的二級頁表
第三次訪存：訪問目標內存單元

N級頁表訪問一個邏輯地址，需要N+1次訪存

1.5.4 二級頁表小結

2 基本分段存儲管理方式

“分段”與“分頁”最大的區別就是——離散分配時所分配地址空間的基本單位不同

2.1 分段

進程的地址空間：按照程序自身的邏輯關系劃分為若干個段，每個段都有一個段名（在低級語言中，程序員使用段名來編程），每段從0開始編址

內存分配規則：以段為單位進行分配，每個段在內存中占據連續空間，但各段之間可以不相鄰。

編譯程序會 將段名轉換為段號
由于是按邏輯功能模塊劃分，用戶編程更方便，程序的可讀性更高

LOAD1,[D]|<A>; //將分段D中A單元內的值讀入寄存器1 STORE1,[X]|<B>; //將寄存器1的內容存入X分段的B單元中

上述匯編指令，寫程序時使用的段名[D]、[X]會被編譯程序翻譯成對應段號
<A>單元、<B>單元會被編譯程序 翻譯成段內地址

分段系統的邏輯地址結構由段號（段名）和段內地址（段內偏移量）所組成。如：

段號的位數決定了每個進程最多可以分幾個段
段內地址位數決定了每個段的最大長度是多少

在上述例子中，若系統是按字節尋址的，則段號占16位，因此在該系統中，每個進程最多有2¹⁶ =64K個段； 段內地址占16位，因此每個段的最大長度是2¹⁶ =64KB。

2.2 段表

問題：程序分多個段，各段離散地裝入內存，為了保證程序能正常運行，就必須能從物理內存中找到各個邏輯段的存放位置。為此，需為每個進程建立一張段映射表，簡稱“段表”。

1. 每個段對應一個段表項，其中記錄了該段在內存中的起始位置（又稱 “基址”）和段的長度。
2. 各個段表項的長度是相同的。

例如：某系統按字節尋址，采用分段存儲管理，邏輯地址結構為（段號16位,段內地址16位），因此用16位即可表示最大段長。物理內存大小為4GB（可用32位表示整個物理內存地址空間）。
因此，可以讓每個段表項占16+32=48位，即6B。由于段表項長度相同，因此段號可以是隱含的，不占存儲空間。
若段表存放的起始地址為M，則K號段對應的段表項存放的地址為M+K*6

2.3 地址變換

2.4 分段、分頁管理的對比

頁是信息的物理單位。分頁的主要目的是為了實現離散分配，提高內存利用率。分頁僅僅是系統管理上的需要，完全是系統行為，對用戶是不可見的。
段是信息的邏輯單位。分段的主要目的是更好地滿足用戶需求。一個段通常包含著一組屬于一個邏輯模塊的信息。分段對用戶是可見的，用戶編程時需要顯式地給出段名。

頁的大小固定且由系統決定。
段的長度卻不固定，決定于用戶編寫的程序。

分頁的用戶進程地址空間是一維的，程序員只需給出一個記憶符即可表示一個地址。
分段的用戶進程地址空間是二維的，程序員在標識一個地址時，既要給出段名，也要給出段內地址。

分段比分頁更容易實現信息的共享和保護。
不能被修改的代碼稱為純代碼或可重入代碼（不屬于臨界資源），這樣的代碼是可以共享的。可修改的代碼是不能共享的（比如，有一個代碼段中有很多變量，各進程并發地同時訪問可能造成數據不一致）

只需讓各進程的段表項指向同一個段即可實現共享

訪問一個邏輯地址需要幾次訪存？
（1）分頁（單級頁表）：第一次訪存——查內存中的頁表，第二次訪存——訪問目標內存單元。總共兩次訪存
（2）分段：第一次訪存——查內存中的段表，第二次訪存——訪問目標內存單元。總共兩次訪存
（3）與分頁系統類似，分段系統中也可以引入快表機構，將近期訪問過的段表項放到快表中，這樣可以少一次訪問，加快地址變換速度。

2.5 分段存儲管理小結

3 段頁式存儲管理

3.1 分頁、分段優缺點分析

分段管理中產生的外部碎片也可以用“緊湊”來解決，只是需要付出較大的時間代價

3.2 分段+分頁=段頁式管理

3.3 段頁式管理的邏輯地址結構

即把段內地址再拆分為頁號+頁面偏移量
段號的位數決定了每個進程最多可以分幾個段
頁號位數決定了每個段最大有多少頁
頁內偏移量決定了頁面大小、內存塊大小是多少

在上述例子中，若系統是按字節尋址，則

• 段號占16位，因此在該系統中，每個進程最多有2¹⁶=64K個字段
• 頁號占4位，因此每個段最多有2⁴=16頁
• 頁內偏移量占12位，因此每個頁面\每個內存塊大小為2¹²=4096=4KB

“分段”對用戶是可見的，程序員編程時需要顯式地給出段號、段內地址。
而將各段“分頁”對用戶是不可見的。系統會根據段內地址自動劃分頁號和頁內偏移量。
因此段頁式管理的地址結構是二維的。

簡記：頁式一維、段式二維、段頁式二維

3.4 段表、頁表

每個段對應一個段表項，每個段表項由段號、頁表長度、頁表存放塊號（頁表起始地址）組成。每個段表項長度相等，段號是隱含的。

每個頁面對應一個頁表項，每個頁表項由頁號、頁面存放的內存塊號組成。每個頁表項長度相等，頁號是隱含的。

3.5 段頁式管理地址變換過程

也可引入快表機構，用段號和頁號作為查詢快表的關鍵字。若快表命中則僅需一次訪存

3.6 段頁式管理小結

總結

以上是生活随笔為你收集整理的12 操作系统第三章 内存管理 非连续分配管理方式 基本分页存储管理 基本分段存储管理 段页式存储管理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。