地址空間與內(nèi)存分配詳解！

時間：2023-05-07 06:21:01 | 來源：網(wǎng)站運營

時間：2023-05-07 06:21:01 來源：網(wǎng)站運營

地址空間與內(nèi)存分配詳解！：

【文章推薦】：極致Linux內(nèi)核：代碼大佬的【Linux內(nèi)核開發(fā)筆記】分享，前人栽樹后人乘涼！

極致Linux內(nèi)核：Linux文件系統(tǒng)詳解

極致Linux內(nèi)核：linux進程管理---實時調(diào)度

極致Linux內(nèi)核：linux內(nèi)核內(nèi)存管理-brk系統(tǒng)調(diào)用

極致Linux內(nèi)核：linux內(nèi)核內(nèi)存管理-缺頁異常

地址空間

1.地址空間分為物理地址空間和邏輯地址空間。

物理地址空間和硬件直接對應(yīng)，如內(nèi)存條代表的主存，硬盤代表的磁盤 ，都是物理內(nèi)存，其管理由硬件完成

邏輯地址空間是運行的程序看到的地址空間，是一維的線性的地址空間。

邏輯地址空間依賴物理地址空間而存在。

2.邏輯地址生成

程序中函數(shù)的位置（入口），變量的名字就是邏輯地址。C程序通過編譯，匯編，鏈接link，載入（程序重定位）生成EXE，存放在硬盤中。匯編后（.o文件）起始地址為0，把變量名和函數(shù)名轉(zhuǎn)為相應(yīng)的從0開始的連續(xù)邏輯地址，link把多個.o合成一個，放在硬盤中，通過loader應(yīng)用程序再把exe放在內(nèi)存中執(zhí)行，這里有分配地址空間和映射（偏移）的過程。上述過程與OS無關(guān)，編譯器和loader來完成。此時得到的仍然是邏輯地址。

3、地址映射

物理地址生成的四個步驟

• CPU要在內(nèi)存中執(zhí)行指令，ALU需要知道這條指令的內(nèi)容，發(fā)送請求，傳參數(shù)，參數(shù)就是邏輯地址
• 查表。CPU中的MMU查找邏輯地址的映射表（有塊區(qū)域表示映射關(guān)系，如果在MMU沒查到會去內(nèi)存中的MAP找）
• 找到后CPU給主存（就是內(nèi)存）發(fā)請求，請求一個物理地址的內(nèi)容（就是指令的內(nèi)容）
• 主存會通過總線把內(nèi)容傳給CPU，CPU執(zhí)行指令。

• 操作系統(tǒng)的作用是在這些步驟之前建立好映射表，以及地址安全檢查 ，OS要檢查邏輯地址起始地址和長度 ，設(shè)置邏輯地址的界限和基址，如果邏輯地址滿足區(qū)域限制，則正常訪問，如果不滿足，就拋出內(nèi)存訪問異常。

• 內(nèi)存分配

連續(xù)內(nèi)存分配和內(nèi)存碎片

連續(xù)內(nèi)存分配：給應(yīng)用程序分配一塊不小于指定大小的連續(xù)的物理內(nèi)存區(qū)域。

碎片：連續(xù)分配會造成內(nèi)存碎片問題，空閑內(nèi)存不能被利用，外部碎片，在分配單元間的未使用內(nèi)存，內(nèi)部碎片，在分配單元中的未使用內(nèi)存。

操作系統(tǒng)需要維護的數(shù)據(jù)結(jié)構(gòu)包括所有進程的已分配分區(qū)和空閑分區(qū)(Empty-blocks）。

下面是三種簡單動態(tài)分區(qū)分配策略

1. First Fit 首次適配，

從0地址往后查找和使用第一個可用空閑快（要比需要的空間大）?；緦崿F(xiàn)機制要求把空閑的內(nèi)存塊按地址排序。回收要考慮能否合并內(nèi)存塊，能夠形成更大的內(nèi)存塊

優(yōu)點：簡單，易于產(chǎn)生更大的空閑快，向著地址空間的結(jié)尾

劣勢：易產(chǎn)生外部碎片（隨著動態(tài)分配加?。淮_定性

1. Best Fit 最優(yōu)適配：

找比需求大但最接近需求的空閑內(nèi)存塊，產(chǎn)生盡可能小的內(nèi)存碎片。原理是為了避免分割大空閑塊，最小化外部碎片產(chǎn)生的尺寸，需要對空閑地址快按尺寸size排序，分配需要尋找一個合適的分區(qū)，重分配需要搜索及合并與相鄰的空閑分區(qū)，若有。

優(yōu)點：當(dāng)大部分分配需要小空間時非常有效，比較簡單。
缺點：外部碎片太小太細，不利于后續(xù)重分配。

1. Worst Fit最差匹配
   使用最大的空閑快，大塊拆分變小塊，可以避免產(chǎn)生太多微小的碎片，也要排序，分配很快，重分配需要搜索及合并與相鄰的空閑分區(qū)，若有，然后調(diào)整空閑塊列表
   優(yōu)勢：分配中等尺寸最好
   缺點：重分配慢，外部碎片，易于破碎大的空閑塊以致大分區(qū)無法被分配。

碎片整理：通過調(diào)整進程占用的分區(qū)位置來減少或避免分區(qū)碎片

1、壓縮式碎片整理 ：調(diào)整內(nèi)存中程序運行的位置，通過拷貝盡量把程序緊湊放到一起，空出較多的空閑位置?？截愐紤]何時去挪，不能在程序運行的時候挪，要在waiting時，還有考慮開銷。

2、交換式碎片整理 ：硬盤當(dāng)做內(nèi)存的備份，把waiting的程序包括數(shù)據(jù)放在磁盤上，騰出空間給其余運行的程序。（搶占waiting程序回收其內(nèi)存），也要考慮開銷和換哪個程序

非連續(xù)內(nèi)存分配
連續(xù)內(nèi)存分配的缺點：分配給一個程序的物理內(nèi)存是連續(xù)的，內(nèi)存利用率較低，有外碎片和內(nèi)碎片的問題。

非連續(xù)內(nèi)存分配的優(yōu)點：一個程序的物理地址空間是非連續(xù)的，更好的內(nèi)存利用和管理，允許共享代碼和數(shù)據(jù)（共享庫等），支持動態(tài)加載和動態(tài)鏈接。

非連續(xù)內(nèi)存分配最大的問題在于管理的開銷。在虛擬地址和物理地址之間的轉(zhuǎn)換，如果用軟件來實現(xiàn)，開銷巨大。因此要考慮用硬件來協(xié)同解決。

非連續(xù)分配的硬件輔助機制：分段和分頁

分段考慮程序的分段地址空間和分段尋址方案。

將應(yīng)用程序地址空間看作多個段組成

段訪問機制：將一維的邏輯地址分成兩塊 。程序訪問內(nèi)存地址分為兩部分，段的尋址（段號segment number）+ 段內(nèi)偏移的尋址（addr）

段訪問的硬件實現(xiàn)

將邏輯地址看成兩部分段號+偏移。段表里面存放了邏輯地址段號與物理地址段號的對應(yīng)關(guān)系，段表里面還包含段的起始地址和段的長度限制，段表在尋址之前由OS建立。CPU會檢測訪問的段的長度限制。段的起始地址+偏移量形成了物理地址。

分頁：

現(xiàn)在絕大多數(shù)CPU采取分頁機制

分頁：分頁地址空間和頁尋址方案。

分頁機制需要頁號和頁內(nèi)偏移。

頁幀（幀、物理頁面,Frame, Page Frame）

• 把物理地址空間劃分為大小相同的基本分配單位
• 2的n次方，如512,4096, 8192

頁面（頁、邏輯頁面,Page）

• 把邏輯地址空間也劃分為相同大小的基本分配單位
• 幀和頁的大小必須是相同的

頁面到頁幀是邏輯地址到物理地址的轉(zhuǎn)換，需要用到頁表,MMU/TLB（快表）。

幀（Frame）:物理內(nèi)存被劃分成大小相等的幀，由幀號和幀內(nèi)偏移構(gòu)成。

例子：

頁（page）:進程邏輯地址空間被劃分為大小相等的頁,由頁號和頁內(nèi)偏移構(gòu)成

映射：頁表將頁號映射為幀號。

頁表由OS建立在初始化時建立。在分段里面段的尺寸可變，分頁里面頁和頁幀大小不變，內(nèi)偏移大小固定。邏輯地址空間會大于物理地址空間（后續(xù)會將到虛擬內(nèi)存），不是所有的頁都有對應(yīng)的幀，邏輯地址中的頁號是連續(xù)的，物理地址中的幀號是不連續(xù)的。

每個進程都有一個頁表，每個頁面對應(yīng)一個頁表項，隨進程運行狀態(tài)而動態(tài)變化，頁表基址在頁表基址寄存器(PTBR: Page Table Base Register)中。

頁表結(jié)構(gòu)：由頁表項標(biāo)志（Flags)和幀號構(gòu)成，F(xiàn)lags由修改位(dirty bit)、存在位(resident bit)、引用位(clock/reference bit）構(gòu)成，存在為0表示邏輯地址不存在對應(yīng)的物理地址，內(nèi)存訪問異常，為1表示存在。

由于邏輯地址很大，為滿足映射關(guān)系，再者應(yīng)用程序很多，可能有多個頁表，這都可能導(dǎo)致頁表很大，不可能都存在CPU中，那么就需要放在內(nèi)存中，這會導(dǎo)致一次內(nèi)存尋址要訪問兩次內(nèi)存，開銷很大。

從時間上解決：快表(TranslationLook-aside Buffer, TLB)，緩存近期訪問的頁表項。TLB 使用關(guān)聯(lián)存儲(associative memory)實現(xiàn)，具備快速訪問性能，容量有限。如果TLB命中，物理頁號可以很快被獲取。如果TLB未命中，對應(yīng)的表項被更新到TLB中。

TLB的缺失不會很大，32位一個頁4K，訪問4K次miss一次，可以接受。寫程序時注意具有局部性，把頻繁的訪問集中在一個區(qū)域。以避免對內(nèi)存的訪問。另外，還需要注意，miss后，更新是硬件完成（x86），還是OS完成（MIPS）。

從空間上解決：多級頁表，以時間開銷換取空間開銷

二級頁表為例，一級頁表存放的是二級頁表的起始地址

若P1對應(yīng)得映射關(guān)系不存在，則二級頁表沒有必要存在，節(jié)省空間。

反向頁表：由于2個問題：大地址空間（64-bits）使前向映射頁表繁瑣（5級），空間任然很大；虛擬地址空間增長速度快魚物理地址空間 。因此，前向頁表與邏輯空間地址的大小相關(guān)→反向頁表則是與物理地址空間的大小相對應(yīng)。優(yōu)點：空間開銷少。映射表的大小相對于物理內(nèi)存很小，且與邏輯地址空間的大小無關(guān)。

方案1：基于頁寄存器

優(yōu)點:頁表大小相對于物理內(nèi)存而言很小，頁表大小與邏輯地址空間大小無關(guān)

缺點:頁表信息對調(diào)后，需要依據(jù)幀號可找頁號，在頁寄存器中搜索邏輯地址中的頁號

方案2：關(guān)聯(lián)存儲器：類似TLB，并行查找，KEY是頁號，value是幀號 。但關(guān)聯(lián)存儲器用到的硬件邏輯很復(fù)雜，開銷很大，本身size做不了多大，還需要放到CPU否則要二次訪問內(nèi)存。大的關(guān)聯(lián)存儲器也會造成時間開銷大。

方案3：哈希表：建立哈希表來實現(xiàn)反向頁表。 對頁號i做哈希計算，頁i放在表中f(i)的位置，求得f(i)作為頁寄存器表的索引獲取對應(yīng)的頁寄存器,再檢查標(biāo)簽是否有i。

問題：

• 會有碰撞，多個邏輯地址對應(yīng)一個值，加入?yún)?shù)PID==ID of running program來緩解沖突；
• 哈希表在內(nèi)存中，要訪問內(nèi)存，內(nèi)存的時間開銷還是很大

優(yōu)點：本身物理存址小省空間，不再是每個應(yīng)用程序都要page table了，整個系統(tǒng)只用一個。

缺點：需求高，有高效哈希函數(shù)和解決沖突的機制，要硬件軟件配合，任然需要TLB機制。

沖突解決：

若pid和vpn不一樣，則尋找到next項。

原文作者：- - 內(nèi)核技術(shù)中文網(wǎng) - 構(gòu)建全國最權(quán)威的內(nèi)核技術(shù)交流分享論壇

原文地址：地址空間與內(nèi)存分配詳解！ - 圈點 - 內(nèi)核技術(shù)中文網(wǎng) - 構(gòu)建全國最權(quán)威的內(nèi)核技術(shù)交流分享論壇（版權(quán)歸原文作者所有，侵權(quán)聯(lián)系刪除）