第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ǔ)管理頁(yè)式存儲(chǔ)管理頁(yè)表段頁(yè)式存儲(chǔ)管理非連續(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)：提高內(nèi)存利用效率和管理靈活性非連續(xù)內(nèi)存分配的實(shí)現(xiàn)如何實(shí)現(xiàn)虛擬地址和物理地址的轉(zhuǎn)換軟件實(shí)現(xiàn) （

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

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

4、念頁(yè)式存儲(chǔ)管理的地址轉(zhuǎn)換頁(yè)表段頁(yè)式存儲(chǔ)管理段式存儲(chǔ)管理頁(yè)式存儲(chǔ)管理頁(yè)幀（幀、物理頁(yè)面, Frame, Page Frame）把物理地址空間劃分為大小相同的基本分配單位2的n次方，如512, 4096, 8192頁(yè)面（頁(yè)、邏輯頁(yè)面, Page）把邏輯地址空間也劃分為相同大小的基本分配單位幀和頁(yè)的大小必須是相同的頁(yè)面到頁(yè)幀邏輯地址到物理地址的轉(zhuǎn)換頁(yè)表MMU/TLB幀 (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 位, 每幀

5、有2S 字節(jié)) 物理地址 = f * 2S + o基于頁(yè)幀的物理地址計(jì)算實(shí)例假定16-bit的地址空間9-bit (512 byte) 大小的頁(yè)幀物理地址表示 = (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)頁(yè)(Page)進(jìn)程邏輯地址空間被劃分為大小相等的頁(yè)頁(yè)內(nèi)偏移 = 幀內(nèi)偏移通常：頁(yè)號(hào)大小 幀號(hào)大小po邏輯地址:1SP+S2n-1 =(2P-1, 2S-1)(0,0)邏輯地址空間進(jìn)程邏輯地址的

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

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

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

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

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

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

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