第10講物理內存管理：非連續(xù)內存分配

1、第第1010講講 物理內存管理：物理內存管理：非連續(xù)內存分配非連續(xù)內存分配授課教師：馬立平授課教師：馬立平聯(lián)系方式：聯(lián)系方式：Southwest University of Science and Technology概 述非連續(xù)內存分配的需求背景 段式存儲管理頁式存儲管理頁表段頁式存儲管理非連續(xù)分配的設計目標分配給程序的物理內存必須連續(xù)存在外碎片和內碎片內存分配的動態(tài)修改困難內存利用率較低允許一個程序的使用非連續(xù)的物理地址空間允許共享代碼與數(shù)據(jù)支持動態(tài)加載和動態(tài)鏈接連續(xù)分配的缺點非連續(xù)分配的設計目標：提高內存利用效率和管理靈活性非連續(xù)內存分配的實現(xiàn)如何實現(xiàn)虛擬地址和物理地址的轉換軟件實現(xiàn) （

2、靈活，開銷大）硬件實現(xiàn) （夠用，開銷?。┤绾芜x擇非連續(xù)分配中的內存分塊大小段式存儲管理 （segmentation）頁式存儲管理 （paging）非連續(xù)分配需要解決的問題非連續(xù)分配的硬件輔助機制概 述非連續(xù)內存分配的需求背景段式存儲管理段地址空間段訪問機制頁式存儲管理頁表段頁式存儲管理段地址空間進程的段地址空間由多個段組成主代碼段子模塊代碼段公用庫代碼段堆棧段(stack)段式存儲管理的目的更細粒度和靈活的分離與共享堆數(shù)據(jù)(heap)初始化數(shù)據(jù)段符號表等代碼子模塊堆棧符號表主代碼邏輯地址空間公用庫段式地址空間的不連續(xù)二維結構堆棧邏輯地址空間數(shù)據(jù)段代碼段堆函數(shù)庫代碼程序數(shù)據(jù)堆棧物理地址空間堆數(shù)據(jù)

3、用戶代碼段地址空間的邏輯視圖1324邏輯地址空間1423物理地址空間段式存儲管理段訪問機制單地址實現(xiàn)方案0n1+n2saddr段的概念段表示訪問方式和存儲數(shù)據(jù)等屬性相同的一段地址空間對應一個連續(xù)的內存“塊”若干個段組成進程邏輯地址空間段訪問：邏輯地址由二元組(s, addr)表示s 段號addr 段內偏移“段基址+段內偏移”實現(xiàn)方案saddrn100n2段訪問的硬件實現(xiàn)0程序段10001500物理地址段基址寄存器+1000是段表段號基址長度段描述符操作系統(tǒng)設置段表CPU019910段號偏移程序P邏輯地址段長度寄存器500內存異常否MMU概 述非連續(xù)內存分配的需求背景頁式存儲管理頁式存儲管理的概

4、念頁式存儲管理的地址轉換頁表段頁式存儲管理段式存儲管理頁式存儲管理頁幀（幀、物理頁面, Frame, Page Frame）把物理地址空間劃分為大小相同的基本分配單位2的n次方，如512, 4096, 8192頁面（頁、邏輯頁面, Page）把邏輯地址空間也劃分為相同大小的基本分配單位幀和頁的大小必須是相同的頁面到頁幀邏輯地址到物理地址的轉換頁表MMU/TLB幀 (Frame)物理內存被劃分成大小相等的幀內存物理地址的表示：二元組 (f, o) fo1SF+S物理地址fo(f,o)(0,0)(2F-1,2S-1)物理地址空間f 幀號 (F 位, 共有2F 個幀) o 幀內偏移 (S 位, 每幀

5、有2S 字節(jié)) 物理地址 = f * 2S + o基于頁幀的物理地址計算實例假定16-bit的地址空間9-bit (512 byte) 大小的頁幀物理地址表示 = (3, 6)36物理地址 = 2S*f + o019物理地址1611101000000000010F=7 S=9 f=3 o=6 實際物理地址 =29 *3+ 6=1536+6=154215420(0,0)物理地址空間物理地址計算fo(3,6)頁(Page)進程邏輯地址空間被劃分為大小相等的頁頁內偏移 = 幀內偏移通常：頁號大小 幀號大小po邏輯地址:1SP+S2n-1 =(2P-1, 2S-1)(0,0)邏輯地址空間進程邏輯地址的

6、表示：二元組 (p, o)p 頁號 (P 位, 2P 個頁)o 頁內偏移 (S 位, 每頁有2S 字節(jié)) 虛擬地址 = p * 2S + o po(p,o)頁式存儲中的地址映射頁到幀的映射 邏輯地址中的頁號是連續(xù)的物理地址中的幀號是不連續(xù)的不是所有的頁都有對應的幀(f1,o1)(f2,o2)物理地址空間邏輯地址空間(p2,o2)(p1,o1)頁表頁表保存了邏輯地址物理地址之間的映射關系(p,o)邏輯地址空間物理地址空間(f,o)116910fo物理地址頁表pfCPU120910po程序P邏輯地址 頁表基址 頁號 幀號 概 述非連續(xù)內存分配的需求背景頁式存儲管理頁表概述快表頁表段頁式存儲管理段式

7、存儲管理多級頁表反置頁表頁表結構每個進程都有一個頁表每個頁面對應一個頁表項頁表基址寄存器(PTBR: Page Table Base Register)隨進程運行狀態(tài)而動態(tài)變化頁表p120910po116910fo物理地址邏輯地址f0PTBRCPU+1 0 頁表項組成幀號：f頁表項標志修改位(dirty bit)引用位(clock/reference bit)存在位(resident bit)頁表地址轉換實例假定：具有16位地址的計算機系統(tǒng)物理內存大?。?2 KB每頁大小：1024字節(jié)物理地址空間(4,1023)(0,0)15 910fo物理地址015CPU910po邏輯地址01 0 0 1

8、0 0頁表0 0 0 0 0 010標志位幀號1010存在位標志邏輯地址空間(3,1023)(4,0)(0,0)頁式存儲管理機制的性能問題內存訪問性能問題訪問一個內存單元需要2次內存訪問第二次訪問：訪問數(shù)據(jù)第一次訪問：獲取頁表項頁表大小問題：頁表可能非常大64位機器如果每頁1024字節(jié)，那么一個頁表的大小會是多少？如何處理?緩存（Caching）間接（Indirection）訪問概 述頁表頁表概述多級頁表快表非連續(xù)內存分配的需求背景段式存儲管理頁式存儲管理反置頁表段頁式存儲管理緩存近期訪問的頁表項TLB 使用關聯(lián)存儲(associative memory)實現(xiàn)，具備快速訪問性能如果TLB命中，

9、物理頁號可以很快被獲取如果TLB未命中，對應的表項被更新到TLB中120910po116910fo物理地址邏輯地址CPUCPU中的快表fKeyValuepp內存中的頁表f快表(Translation Look-aside Buffer, TLB)多級頁表p2o邏輯地址p3p1通過間接引用將頁號分成k級建立頁表“樹”減少每級頁表的長度第三級頁表第一級頁表第二級頁表p1p2p3二級頁表實例1201016116 10p1ofo物理地址邏輯地址CPUp2內存第二級頁表p2fPTBR+第一級頁表頁表項p1CR3+概述非連續(xù)內存分配的需求背景頁表概述段式存儲管理頁式存儲管理頁表快表多級頁表反置頁表段頁式存

10、儲管理大地址空間問題對于大地址空間(64-bits)系統(tǒng)，多級頁表變得繁瑣.比如：5 級頁表邏輯 (虛擬) 地址空間增長速度快于物理地址空間頁寄存器和反置頁面的思路不讓頁表與邏輯地址空間的大小相對應讓頁表與物理地址空間的大小相對應頁寄存器(Page Registers)頁寄存器示例每個幀與一個頁寄存器(Page Register)關聯(lián)，寄存器內容包括：占用頁號(Occupier): 對應的頁號p使用位(Residence bit): 此幀是否被進程占用保護位(Protection bits)頁面大小: 4096 bytes = 4KB物理內存大小: 4096*4096=4K*4KB=16 MB

11、 頁幀數(shù): 4096 = 4K頁寄存器使用的空間 (假設每個頁寄存器占8字節(jié)):虛擬內存的大?。?任意頁寄存器帶來的額外開銷: 8*4096=32 Kbytes32K/16M = 0.2% (大約)頁寄存器方案的特征優(yōu)點:頁表大小相對于物理內存而言很小頁表大小與邏輯地址空間大小無關缺點:頁表信息對調后，需要依據(jù)幀號可找頁號在頁寄存器中搜索邏輯地址中的頁號頁寄存器中的地址轉換 CPU生成的邏輯地址如何找對應的物理地址? 對邏輯地址進行Hash映射，以減少搜索范圍 需要解決可能的沖突 快表的限制快表的容量限制快表的功耗限制(StrongARM上快表功耗占27%)在快表中查找對應頁表項有沖突時遍歷沖

12、突項鏈表查找失敗時，產生異常 用快表緩存頁表項后的頁寄存器搜索步驟 對邏輯地址進行Hash變換反置頁表基于Hash映射值查找對應頁表項中的幀號fo內存PTBR+=?=?運行進程PIDHashPID頁號 進程標識與頁號的Hash值可能有沖突頁表項中包括保護位、修改位、訪問位和存在位等標識CPUpo0 x10 x1230pidvpnoffset反置頁表的Hash沖突018F1B0 x123ppnoffset索引表0 x18F1C0 xAF0130 x0pid1vpnnextIndex0 x00 x18F1B0 x18F1C030 xA630 x18F1B0 x1-0 x31AB 0 x0A921hash概述非連續(xù)內存分配的需求背景段式存儲管理頁式存儲管理頁表段頁式存儲管理段頁式存儲管理的需求段式存儲在內存保護方面有優(yōu)勢，頁式存儲在內存利用和優(yōu)化轉移到后備存儲方面有優(yōu)勢。段式存儲、頁式存儲能否