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

1、第第1010講講 物理內(nèi)存管理：物理內(nèi)存管理：非連續(xù)內(nèi)存分配非連續(xù)內(nèi)存分配授課教師：馬立平授課教師：馬立平聯(lián)系方式：聯(lián)系方式：Southwest University of Science and Technology概 述非連續(xù)內(nèi)存分配的需求背景 段式存儲(chǔ)管理頁式存儲(chǔ)管理頁表段頁式存儲(chǔ)管理Southwest University of Science and Technology 非連續(xù)分配的設(shè)計(jì)目標(biāo)分配給程序的物理內(nèi)存必須連續(xù)存在外碎片和內(nèi)碎片內(nèi)存分配的動(dòng)態(tài)修改困難內(nèi)存利用率較低允許一個(gè)程序的使用非連續(xù)的物理地址空間允許共享代碼與數(shù)據(jù)支持動(dòng)態(tài)加載和動(dòng)態(tài)鏈接連續(xù)分配的缺點(diǎn)非連續(xù)分配的設(shè)計(jì)目標(biāo)

2、：提高內(nèi)存利用效率和管理靈活性Southwest University of Science and Technology 非連續(xù)內(nèi)存分配的實(shí)現(xiàn)如何實(shí)現(xiàn)虛擬地址和物理地址的轉(zhuǎn)換軟件實(shí)現(xiàn) （靈活，開銷大）硬件實(shí)現(xiàn) （夠用，開銷?。┤绾芜x擇非連續(xù)分配中的內(nèi)存分塊大小段式存儲(chǔ)管理 （segmentation）頁式存儲(chǔ)管理 （paging）非連續(xù)分配需要解決的問題非連續(xù)分配的硬件輔助機(jī)制Southwest University of Science and Technology 概 述非連續(xù)內(nèi)存分配的需求背景段式存儲(chǔ)管理段地址空間段訪問機(jī)制頁式存儲(chǔ)管理頁表段頁式存儲(chǔ)管理Southwest Univer

3、sity of Science and Technology 段地址空間進(jìn)程的段地址空間由多個(gè)段組成主代碼段子模塊代碼段公用庫(kù)代碼段堆棧段(stack)段式存儲(chǔ)管理的目的更細(xì)粒度和靈活的分離與共享堆數(shù)據(jù)(heap)初始化數(shù)據(jù)段符號(hào)表等代碼子模塊堆棧符號(hào)表主代碼邏輯地址空間公用庫(kù)Southwest University of Science and Technology 段式地址空間的不連續(xù)二維結(jié)構(gòu)堆棧邏輯地址空間數(shù)據(jù)段代碼段堆函數(shù)庫(kù)代碼程序數(shù)據(jù)堆棧物理地址空間堆數(shù)據(jù)用戶代碼Southwest University of Science and Technology 段地址空間的邏輯視圖1324

4、邏輯地址空間1423物理地址空間段式存儲(chǔ)管理Southwest University of Science and Technology 段訪問機(jī)制單地址實(shí)現(xiàn)方案0n1+n2saddr段的概念段表示訪問方式和存儲(chǔ)數(shù)據(jù)等屬性相同的一段地址空間對(duì)應(yīng)一個(gè)連續(xù)的內(nèi)存“塊”若干個(gè)段組成進(jìn)程邏輯地址空間段訪問：邏輯地址由二元組(s, addr)表示s 段號(hào)addr 段內(nèi)偏移“段基址+段內(nèi)偏移”實(shí)現(xiàn)方案saddrn100n2Southwest University of Science and Technology 段訪問的硬件實(shí)現(xiàn)0程序段10001500物理地址段基址寄存器+1000是段表段號(hào)基址長(zhǎng)度段描

5、述符操作系統(tǒng)設(shè)置段表CPU019910段號(hào)偏移程序P邏輯地址段長(zhǎng)度寄存器500內(nèi)存異常否MMUSouthwest University of Science and Technology 概 述非連續(xù)內(nèi)存分配的需求背景頁式存儲(chǔ)管理頁式存儲(chǔ)管理的概念頁式存儲(chǔ)管理的地址轉(zhuǎn)換頁表段頁式存儲(chǔ)管理段式存儲(chǔ)管理Southwest University of Science and Technology 頁式存儲(chǔ)管理頁幀（幀、物理頁面, Frame, Page Frame）把物理地址空間劃分為大小相同的基本分配單位2的n次方，如512, 4096, 8192頁面（頁、邏輯頁面, Page）把邏輯地址空間也劃

6、分為相同大小的基本分配單位幀和頁的大小必須是相同的頁面到頁幀邏輯地址到物理地址的轉(zhuǎn)換頁表MMU/TLBSouthwest University of Science and Technology 幀 (Frame)物理內(nèi)存被劃分成大小相等的幀內(nèi)存物理地址的表示：二元組 (f, o) fo1SF+S物理地址fo(f,o)(0,0)(2F-1,2S-1)物理地址空間f 幀號(hào) (F 位, 共有2F 個(gè)幀) o 幀內(nèi)偏移 (S 位, 每幀有2S 字節(jié)) 物理地址 = f * 2S + oSouthwest University of Science and Technology 基于頁幀的物理地址計(jì)算

7、實(shí)例假定16-bit的地址空間9-bit (512 byte) 大小的頁幀物理地址表示 = (3, 6)36物理地址 = 2S*f + o019物理地址1611101000000000010F=7 S=9 f=3 o=6 實(shí)際物理地址 =29 *3+ 6=1536+6=154215420(0,0)物理地址空間物理地址計(jì)算fo(3,6)Southwest University of Science and Technology 頁(Page)進(jìn)程邏輯地址空間被劃分為大小相等的頁頁內(nèi)偏移 = 幀內(nèi)偏移通常：頁號(hào)大小 幀號(hào)大小po邏輯地址:1SP+S2n-1 =(2P-1, 2S-1)(0,0)邏輯

8、地址空間進(jìn)程邏輯地址的表示：二元組 (p, o)p 頁號(hào) (P 位, 2P 個(gè)頁)o 頁內(nèi)偏移 (S 位, 每頁有2S 字節(jié)) 虛擬地址 = p * 2S + o po(p,o)Southwest University of Science and Technology 頁式存儲(chǔ)中的地址映射頁到幀的映射 邏輯地址中的頁號(hào)是連續(xù)的物理地址中的幀號(hào)是不連續(xù)的不是所有的頁都有對(duì)應(yīng)的幀(f1,o1)(f2,o2)物理地址空間邏輯地址空間(p2,o2)(p1,o1)Southwest University of Science and Technology 頁表頁表保存了邏輯地址物理地址之間的映射關(guān)系(

9、p,o)邏輯地址空間物理地址空間(f,o)116910fo物理地址頁表pfCPU120910po程序P邏輯地址 頁表基址 頁號(hào) 幀號(hào) Southwest University of Science and Technology 概 述非連續(xù)內(nèi)存分配的需求背景頁式存儲(chǔ)管理頁表概述快表頁表段頁式存儲(chǔ)管理段式存儲(chǔ)管理多級(jí)頁表反置頁表Southwest University of Science and Technology 頁表結(jié)構(gòu)每個(gè)進(jìn)程都有一個(gè)頁表每個(gè)頁面對(duì)應(yīng)一個(gè)頁表項(xiàng)頁表基址寄存器(PTBR: Page Table Base Register)隨進(jìn)程運(yùn)行狀態(tài)而動(dòng)態(tài)變化頁表p120910po11

10、6910fo物理地址邏輯地址f0PTBRCPU+1 0 頁表項(xiàng)組成幀號(hào)：f頁表項(xiàng)標(biāo)志修改位(dirty bit)引用位(clock/reference bit)存在位(resident bit)Southwest University of Science and Technology 頁表地址轉(zhuǎn)換實(shí)例假定：具有16位地址的計(jì)算機(jī)系統(tǒng)物理內(nèi)存大?。?2 KB每頁大?。?024字節(jié)物理地址空間(4,1023)(0,0)15 910fo物理地址015CPU910po邏輯地址01 0 0 1 0 0頁表0 0 0 0 0 010標(biāo)志位幀號(hào)1010存在位標(biāo)志邏輯地址空間(3,1023)(4,0)(0,

11、0)Southwest University of Science and Technology 頁式存儲(chǔ)管理機(jī)制的性能問題內(nèi)存訪問性能問題訪問一個(gè)內(nèi)存單元需要2次內(nèi)存訪問第二次訪問：訪問數(shù)據(jù)第一次訪問：獲取頁表項(xiàng)頁表大小問題：頁表可能非常大64位機(jī)器如果每頁1024字節(jié)，那么一個(gè)頁表的大小會(huì)是多少？如何處理?緩存（Caching）間接（Indirection）訪問Southwest University of Science and Technology 概 述頁表頁表概述多級(jí)頁表快表非連續(xù)內(nèi)存分配的需求背景段式存儲(chǔ)管理頁式存儲(chǔ)管理反置頁表段頁式存儲(chǔ)管理Southwest Universit

12、y of Science and Technology 緩存近期訪問的頁表項(xiàng)TLB 使用關(guān)聯(lián)存儲(chǔ)(associative memory)實(shí)現(xiàn)，具備快速訪問性能如果TLB命中，物理頁號(hào)可以很快被獲取如果TLB未命中，對(duì)應(yīng)的表項(xiàng)被更新到TLB中120910po116910fo物理地址邏輯地址CPUCPU中的快表fKeyValuepp內(nèi)存中的頁表f快表(Translation Look-aside Buffer, TLB)Southwest University of Science and Technology 多級(jí)頁表p2o邏輯地址p3p1通過間接引用將頁號(hào)分成k級(jí)建立頁表“樹”減少每級(jí)頁表的長(zhǎng)

13、度第三級(jí)頁表第一級(jí)頁表第二級(jí)頁表p1p2p3Southwest University of Science and Technology 二級(jí)頁表實(shí)例1201016116 10p1ofo物理地址邏輯地址CPUp2內(nèi)存第二級(jí)頁表p2fPTBR+第一級(jí)頁表頁表項(xiàng)p1CR3+Southwest University of Science and Technology 概述非連續(xù)內(nèi)存分配的需求背景頁表概述段式存儲(chǔ)管理頁式存儲(chǔ)管理頁表快表多級(jí)頁表反置頁表段頁式存儲(chǔ)管理Southwest University of Science and Technology 大地址空間問題對(duì)于大地址空間(64-bits

14、)系統(tǒng)，多級(jí)頁表變得繁瑣.比如：5 級(jí)頁表邏輯 (虛擬) 地址空間增長(zhǎng)速度快于物理地址空間頁寄存器和反置頁面的思路不讓頁表與邏輯地址空間的大小相對(duì)應(yīng)讓頁表與物理地址空間的大小相對(duì)應(yīng)Southwest University of Science and Technology 頁寄存器(Page Registers)頁寄存器示例每個(gè)幀與一個(gè)頁寄存器(Page Register)關(guān)聯(lián)，寄存器內(nèi)容包括：占用頁號(hào)(Occupier): 對(duì)應(yīng)的頁號(hào)p使用位(Residence bit): 此幀是否被進(jìn)程占用保護(hù)位(Protection bits)頁面大小: 4096 bytes = 4KB物理內(nèi)存大小:

15、4096*4096=4K*4KB=16 MB 頁幀數(shù): 4096 = 4K頁寄存器使用的空間 (假設(shè)每個(gè)頁寄存器占8字節(jié)):虛擬內(nèi)存的大小： 任意頁寄存器帶來的額外開銷: 8*4096=32 Kbytes32K/16M = 0.2% (大約)Southwest University of Science and Technology 頁寄存器方案的特征優(yōu)點(diǎn):頁表大小相對(duì)于物理內(nèi)存而言很小頁表大小與邏輯地址空間大小無關(guān)缺點(diǎn):頁表信息對(duì)調(diào)后，需要依據(jù)幀號(hào)可找頁號(hào)在頁寄存器中搜索邏輯地址中的頁號(hào)Southwest University of Science and Technology 頁寄存器中的

16、地址轉(zhuǎn)換 CPU生成的邏輯地址如何找對(duì)應(yīng)的物理地址? 對(duì)邏輯地址進(jìn)行Hash映射，以減少搜索范圍 需要解決可能的沖突 快表的限制快表的容量限制快表的功耗限制(StrongARM上快表功耗占27%)在快表中查找對(duì)應(yīng)頁表項(xiàng)有沖突時(shí)遍歷沖突項(xiàng)鏈表查找失敗時(shí)，產(chǎn)生異常 用快表緩存頁表項(xiàng)后的頁寄存器搜索步驟 對(duì)邏輯地址進(jìn)行Hash變換Southwest University of Science and Technology 反置頁表基于Hash映射值查找對(duì)應(yīng)頁表項(xiàng)中的幀號(hào)fo內(nèi)存PTBR+=?=?運(yùn)行進(jìn)程PIDHashPID頁號(hào) 進(jìn)程標(biāo)識(shí)與頁號(hào)的Hash值可能有沖突頁表項(xiàng)中包括保護(hù)位、修改位、訪問位和

17、存在位等標(biāo)識(shí)CPUpoSouthwest University of Science and Technology 0 x10 x1230pidvpnoffset反置頁表的Hash沖突018F1B0 x123ppnoffset索引表0 x18F1C0 xAF0130 x0pid1vpnnextIndex0 x00 x18F1B0 x18F1C030 xA630 x18F1B0 x1-0 x31AB 0 x0A921hashSouthwest University of Science and Technology 概述非連續(xù)內(nèi)存分配的需求背景段式存儲(chǔ)管理頁式存儲(chǔ)管理頁表段頁式存儲(chǔ)管理Southwest University of Science and Technology 段頁式存儲(chǔ)管理的需求段式存儲(chǔ)在內(nèi)存保護(hù)方面有優(yōu)勢(shì)，頁式存儲(chǔ)在內(nèi)存利用和優(yōu)化轉(zhuǎn)移到后備存儲(chǔ)方面有優(yōu)勢(shì)。段式存儲(chǔ)、頁式存儲(chǔ)能否結(jié)合？Southwest University of Science and Technology 段頁式存儲(chǔ)管理在