這是 herongwei 的第 100 篇原創(chuàng)

閱讀本文大概需要 6.66 分鐘

前言

1、什么是 User space 與 Kernel space？

2、什么是棧區(qū)？

3、什么是堆區(qū)？

4、malloc 算法是如何實現(xiàn)的？

5、Linux 系統(tǒng)下，有幾種堆空間分配方式？

6、Linux 下一個進程地址空間布局是怎樣的？

上面幾個問題，你心里有答案嗎？如果沒有，跟我一起來探究一下吧。

1、User space 與 Kernel space

現(xiàn)代的應用程序都運行在一個內(nèi)存空間里，在 32 位系統(tǒng)中，這個內(nèi)存空間擁有 4GB （2 的 32 次方）的尋址能力。

盡管現(xiàn)在大部分計算機的內(nèi)存空間配置越來越高，但實際上內(nèi)存仍然在不同的地址區(qū)間有著不同的地位，例如，大多數(shù)操作系統(tǒng)都會將 4GB 的內(nèi)存空間一部分挪給內(nèi)核使用，應用程序無法直接訪問這一段內(nèi)存，這一部分內(nèi)存地址被稱為內(nèi)核空間。

Windows 在默認的情況下會將高地址的 2GB 空間分配給內(nèi)核（也可以配置 1GB）。

Linux 默認情況下將高地址的 1GB 空間分配給內(nèi)核。

用戶使用的剩下的 2GB 或 3GB 的內(nèi)存空間稱為用戶空間。

為什么要區(qū)分內(nèi)核空間和用戶空間？

大致有三點因素：

第一點：操作系統(tǒng)的數(shù)據(jù)都是存放于系統(tǒng)空間的，用戶進程的數(shù)據(jù)是存放于用戶空間的；

第二點：分開來存放，就讓系統(tǒng)的數(shù)據(jù)和用戶的數(shù)據(jù)互不干擾，保證系統(tǒng)的穩(wěn)定性，并且管理上很方便；

第三點：也是重要的一點，將用戶的數(shù)據(jù)和系統(tǒng)的數(shù)據(jù)隔離開，就可以對兩部分的數(shù)據(jù)的訪問進行控制。這樣就可以確保用戶程序不能隨便操作系統(tǒng)的數(shù)據(jù)，這樣防止用戶程序誤操作或者是惡意破壞系統(tǒng)。

下面這一張圖，比較形象的解釋了 User space 與 Kernel space 的區(qū)別。

第一點：操作系統(tǒng)的數(shù)據(jù)都是存放于系統(tǒng)空間的，用戶進程的數(shù)據(jù)是存放于用戶空間的；

簡單說，Kernel space 是 Linux 內(nèi)核的運行空間，User space 是用戶程序的運行空間。為了安全，它們是隔離的，即使用戶的程序崩潰了，內(nèi)核也不受影響。

Kernel space 可以執(zhí)行任意命令，調(diào)用系統(tǒng)的一切資源；

相對來說，User space 執(zhí)行的是較為簡單的運算，執(zhí)行的運算不影響其他程序的執(zhí)行，并且不能直接調(diào)用系統(tǒng)資源，必須通過系統(tǒng)接口（又稱 system call），才能向內(nèi)核發(fā)出指令。

這里補充下知乎網(wǎng)友@風云評論：

其實，在用戶空間，幾乎所有內(nèi)核資源在用戶空間都是可以訪問的（必須有相應的權限），即使是操作系統(tǒng)內(nèi)核的大腦（調(diào)度程序）。

2、Linux 進程地址空間布局

在用戶空間里，也有許多地址區(qū)間有特權的地位，一般來講，應用程序使用的內(nèi)存空間里有如下“默認”的區(qū)域。

棧區(qū)： 棧用于維護函數(shù)調(diào)用的上下文，離開了棧，函數(shù)調(diào)用就無法實現(xiàn)，棧通常在用戶空間的最高地址處分配，通常有數(shù)兆字節(jié)的大小。

堆區(qū)： 堆是用來容納應用程序動態(tài)分配的內(nèi)存區(qū)域，當程序使用 malloc 或者 new 分配內(nèi)存的時候，得到的內(nèi)存會來自堆里。

堆通常存在棧的下方（低地址方向），在某些時候，堆也可能沒有固定統(tǒng)一的存儲區(qū)域。堆一般比棧大很多，可以有幾十至數(shù)百兆字節(jié)的容量。

可執(zhí)行文件映像： 存儲著可執(zhí)行文件在內(nèi)存里的映像，由裝載器在裝載時將可執(zhí)行文件的內(nèi)存讀取或映射到這里。

保留區(qū)： 保留區(qū)并不是一個單一的內(nèi)存區(qū)域，而是對內(nèi)存中受到保護而禁止訪問的內(nèi)存區(qū)域的總稱：例如大多數(shù)操作系統(tǒng)中，極小的地址通常都是不允許訪問的，如 NULL，C 語言將無效指針賦值為 0 也是這個考慮。

動態(tài)鏈接庫映射區(qū)： 這個區(qū)域用于映射裝載的動態(tài)鏈接庫。在 Linux 下，如果可執(zhí)行文件依賴其它共享庫，那么系統(tǒng)就會為它在從 0x40000000 開始的地址分配相應的空間，并將共享庫載入該空間。

剩下的還有以下幾部份組成：

（1）代碼段

（2）初始化數(shù)據(jù)段（數(shù)據(jù)段）

（3）未初始化數(shù)據(jù)段（BSS 段）

下圖是 Linux 下一個進程里典型的內(nèi)存布局

圖中的箭頭，標明了幾個大小可變的尺寸增長的方向，在這里，可以清晰地看出：

棧是由高地址向低地址增長。

堆是由低地址向高地址增長。

當棧或堆現(xiàn)有的大小不夠用的時候，它將按照圖中的增長方向擴大自身的尺寸，直到預留的空間被用完為止。

在講堆和棧之前，我們先來看一下代碼段，初始化數(shù)據(jù)段和未初始化數(shù)據(jù)段。

3、代碼段

代碼段中存放可執(zhí)行的指令，在內(nèi)存中，為了保證不會因為堆棧溢出被覆蓋，將其放在了堆棧段下面（從上圖可以看出）。

通常來講代碼段是共享的，這樣多次反復執(zhí)行的指令只需要在內(nèi)存中駐留一個副本即可，比如 C 編譯器，文本編輯器等。

代碼段一般是只讀的，這樣程序執(zhí)行時不能隨意更改指令，也是為了進行隔離保護。

4、初始化數(shù)據(jù)段

初始化數(shù)據(jù)段有時就稱之為數(shù)據(jù)段。數(shù)據(jù)段是一個程序虛擬地址空間的一部分，包括一全局變量和靜態(tài)變量，這些變量在編程時就已經(jīng)被初始化。數(shù)據(jù)段是可以修改的，不然程序運行時變量就無法改變了，這一點和代碼段不同。

數(shù)據(jù)段可以細分為初始化只讀區(qū)和初始化讀寫區(qū)。這一點和編程中的一些特殊變量吻合。比如全局變量 int global n = 1就被放在了初始化讀寫區(qū)，因為 global 是可以修改的。而 const int m = 2 就會被放在只讀區(qū)，很明顯，m 是不能修改的。

5、棧

棧 (stack) 是現(xiàn)代計算機程序里最為重要的概念之一，幾乎每一個程序都使用了棧，沒有棧就沒有函數(shù)，沒有局部變量，也就沒有我們?nèi)缃衲軌蚩匆姷乃械挠嬎銠C語言。

在解釋為什么棧會如此重要之前，讓我們來先了解一下傳統(tǒng)的棧的定義：

在經(jīng)典的計算機科學中，棧被定義為一個特殊的容器，用戶可以將數(shù)據(jù)壓入棧中（入棧,push），也可以將已經(jīng)壓入棧中的數(shù)據(jù)彈出(出棧, pop)。

但棧這個容器必須遵守一條規(guī)則：先入棧的數(shù)據(jù)后出棧(First In Last Out, FIFO)，多多少少像疊成一疊的書：先疊上去的書在最下面：因此要最后才能取出。

在計算機系統(tǒng)中，棧則是一個具有以上屬性的動態(tài)內(nèi)存區(qū)域，程序可以將數(shù)據(jù)壓入棧中，也可以將數(shù)據(jù)從棧頂彈出，壓棧操作使得棧增大,而彈出操作使棧減小。

在經(jīng)典的操作系統(tǒng)里，?？偸窍蛳略鲩L的。

在 i386 下，棧頂由稱為 esp 的寄存器進行定位。壓棧的操作使棧頂?shù)牡刂窚p小，彈出的操作使棧頂?shù)刂吩龃蟆?/span>

這里棧底的地址是 0xbffff，而 esp 寄存器標明了棧頂，地址為 0xbifff4。

在棧上壓入數(shù)據(jù)會導致 esp 減小，彈出數(shù)據(jù)使得 esp 增大。

棧在程序運行中具有舉足輕重的地位。最重要的，棧保存了一個函數(shù)調(diào)用所需要的維護信息，這常常被稱為堆棧幀(Stack Frame)或活動記錄(Activate Record)，堆棧幀一般包括如下幾方面內(nèi)容：

1、函數(shù)的返回地址和參數(shù)。

2、臨時變量:包括函數(shù)的非靜態(tài)局部變量以及編譯器自動生成的其他臨時變量。

3、保存的上下文:包括在函數(shù)調(diào)用前后需要保持不變的寄存器。

6、堆

相對于棧，堆這片內(nèi)存面臨著一個稍微復雜的行為模式：在任意時刻，程序可能發(fā)出請求，要么申請一段內(nèi)存，要么釋放一段已經(jīng)申請過的內(nèi)存，而且申請的大小從幾個字節(jié)到數(shù) GB 都是有可能的。

我們不能假設程序會一次申請多少堆空間，因此，這時候堆的作用就凸顯出來了，同樣，相比較與棧，堆的管理顯得較為復雜。

光有棧，對于面向過程的程序設計還遠遠不夠，因為棧上的數(shù)據(jù)在函數(shù)返回的時候就會被釋放掉，所以無法將數(shù)據(jù)傳遞至函數(shù)外部。而全局變量沒有辦法動態(tài)地產(chǎn)生，只能在編譯的時候定義，有很多情況下缺乏表現(xiàn)力，在這種情況下，堆（Heap）是一種唯一的選擇。

堆是一塊巨大的內(nèi)存空間，常常占據(jù)整個虛擬空間的絕大部分，在這片空間里，程序可以請求一塊連續(xù)的內(nèi)存，并自由地使用，這塊內(nèi)存在程序主動放棄之前都活一直保持有效，下面是一個申請堆空間最簡單的例子：

int main(){ char* p = (char*) malloc(233); free(p); return 0;}

在代碼中，第 3 行用 malloc 申請了 233 個字節(jié)的空間之后，程序可以自由地使用這 233個字節(jié)，直到程序用 free 函數(shù)釋放它。

那么 malloc 到底是怎么實現(xiàn)的呢？

有一種做法是，把進程的內(nèi)存管理交給操作系統(tǒng)內(nèi)核去做，既然內(nèi)核管理著進程的地址空間，那么如果它提供一個系統(tǒng)調(diào)用，可以讓程序使用這個系統(tǒng)調(diào)用申請內(nèi)存，不就可以了嗎？

當然這是一種理論上可行的做法，但實際上這樣做的性能比較差，原因在于每次程序申請或者釋放堆空間都需要進行系統(tǒng)調(diào)用。

我們知道系統(tǒng)調(diào)用的性能開銷是很大的，當程序對堆的操作比較頻繁時，這樣做的結果是會嚴重影響程序的性能的。

比較好的做法就是：程序向操作系統(tǒng)申請一塊適當大小的堆空間，然后由程序自己管理這塊空間，而具體來講，管理著堆空間分配的往往是程序的運行庫。

運行庫相當于是向操作系統(tǒng) “批發(fā)” 了一塊較大的堆空間，然后 “零售” 給程序用。

當全部“售完”或程序有大量的內(nèi)存需求時，再根據(jù)實際需求向操作系統(tǒng)“進貨”。

當然運行庫在向程序零售堆空間時，必須管理它批發(fā)來的堆空間，不能把同一塊地址出售兩次，導致地址的沖突。

7、Linux 進程堆管理

由第一節(jié)可知，進程的地址空間中，除了可執(zhí)行文件，共享庫和棧之外，剩余的未分配的空間都可以用來作為堆空間。

Linux 系統(tǒng)下，提供兩種堆空間分配方式：

brk() 統(tǒng)調(diào)用和 mmap() 系統(tǒng)調(diào)用。

這兩種方式分配的都是虛擬內(nèi)存，沒有分配物理內(nèi)存。在第一次訪問已分配的虛擬地址空間的時候，發(fā)生缺頁中斷，操作系統(tǒng)負責分配物理內(nèi)存，然后建立虛擬內(nèi)存和物理內(nèi)存之間的映射關系。

在標準 C 庫中，提供了malloc/free 函數(shù)分配釋放內(nèi)存，這兩個函數(shù)底層是由 brk，mmap，munmap 這些系統(tǒng)調(diào)用實現(xiàn)的。

brk() 系統(tǒng)調(diào)用

C 語言形式聲明：int brk() {void* end_data_segment;}

brk() 的作用實際上就是設置進程數(shù)據(jù)段的結束地址，即它可以擴大或者縮小數(shù)據(jù)段（Linux 下數(shù)據(jù)段和 BBS 合并在一起統(tǒng)稱數(shù)據(jù)段）。

如果我們將數(shù)據(jù)段的結束地址向高地址移動，那么擴大的那部分空間就可以被我們使用，把這塊空間拿過來使用作為堆空間是最常見的做法。

mmap() 系統(tǒng)調(diào)用

和 Windows 系統(tǒng)下的 VirtualAlloc 很相似，它的作用就是向操作系統(tǒng)申請一段虛擬地址空間，（堆和棧中間，稱為文件映射區(qū)域的地方）這塊虛擬地址空間可以映射到某個文件。

glibc 的 malloc 函數(shù)是這樣處理用戶的空間請求的：對于小于 128KB 的請求來說，它會在現(xiàn)有的堆空間里面，按照堆分配算法為它分配一塊空間并返回；對于大于128KB 的請求來說，它會使用 mmap() 函數(shù)為它分配一塊匿名空間，然后在這個匿名空間中為用戶分配空間。

聲明如下：

void* mmap{ void* start; size_t length; int prot; int flags; int fd; off_t offset;}

mmap 前兩個參數(shù)分別用于指定需要申請的空間的起始地址和長度，如果起始地址設置 0，那么 Linux 系統(tǒng)會自動挑選合適的起始地址。

prot/flags 參數(shù)：用于設置申請的空間的權限（可讀，可寫，可執(zhí)行）以及映射類型（文件映射，匿名空間等）。

最后兩個參數(shù)用于文件映射時指定的文件描述符和文件偏移的。

了解了 Linux 系統(tǒng)對于堆的管理之后，我們可以思考這么一個問題：

malloc 到底一次能夠申請的最大空間是多少？

為了回答這個問題，就不得不再回頭仔細研究一下之前的圖一。我們可以看到在有共享庫的情況下，留給堆可以用的空間還有兩處。

第一處就是從 BSS 段結束到 0x40 000 000 即大約 1GB 不到的空間；

第二處是從共享庫到棧的這塊空間，大約是 2GB 不到。這兩塊空間大小都取決于棧、共享庫的大小和數(shù)量。

于是可以估算到 malloc 最大的申請空間大約是 2GB 不到。（Linux 內(nèi)核 2.4 版本）。

當然還有其它諸多因素會影響 malloc 的最大空間大小，比如系統(tǒng)的資源限制（ulimit），物理內(nèi)存和交換空間的總和等。

mmap 申請匿名空間時，系統(tǒng)會為它在內(nèi)存或交換空間中預留地址，但是申請的空間大小不能超過空閑內(nèi)存+空閑交換空間的總和。

堆分配算法

1、空閑鏈表法（即調(diào)用 malloc 分配）

就是把堆中各個空閑的塊按照鏈表的方式連接起來，當用戶請求一塊空間的時候，可以遍歷整個列表，直到找到合適大小的塊并且將它拆分；當用戶釋放空間的時候將它合并到空閑鏈表中。

空閑鏈表是這樣一種結構，在堆里的每一個空閑空間的開頭(或結尾)有一個頭 (header)，頭結構里記錄了上一個 (prev) 和下一個 (next) 空閑塊的地址，也就是說，所有的空閑塊形成了一個鏈表。如圖所示。

具體實現(xiàn)方案：

1、malloc 函數(shù)的實質是它有一個將可用的內(nèi)存塊連接為一個長長的列表的所謂空閑鏈表。

2、調(diào)用 malloc函數(shù)時，它沿著連接表尋找一個大到足以滿足用戶請求所需要的內(nèi)存塊。然后，將該內(nèi)存塊一分為二（一塊的大小與用戶申請的大小相等，另一塊的大小就是剩下來的字節(jié)）。接下來，將分配給用戶的那塊內(nèi)存存儲區(qū)域傳給用戶，并將剩下的那塊（如果有的話）返回到連接表上。

3、調(diào)用 free 函數(shù)時，它將用戶釋放的內(nèi)存塊連接到空閑鏈表上。

4、到最后，空閑鏈會被切成很多的小內(nèi)存片段，如果這時用戶申請一個大的內(nèi)存片段， 那么空閑鏈表上可能沒有可以滿足用戶要求的片段了。于是，malloc() 函數(shù)請求延時，并開始在空閑鏈表上檢查各內(nèi)存片段，對它們進行內(nèi)存整理，將相鄰的小空閑塊合并成較大的內(nèi)存塊。

2、位圖法

針對空閑鏈表的弊端，另一種分配方式顯得更加穩(wěn)健。這種方式稱為位圍(Bitmap)，其核心思想是將整個堆劃分為大量的塊(block)，每個塊的大小相同。

當用戶請求內(nèi)存的時候，總是分配整數(shù)個塊的空間給用戶，第一個塊我們稱為已分配區(qū)域的頭(Head)，其余的稱為己分配區(qū)域的主體(Body)，而我們可以使用一個整數(shù)數(shù)組來記錄塊的使用情況，由于每個塊只有頭/主體/空閑三種狀態(tài)，因此僅僅需要兩位即可表示一個塊，因此稱為位圖。

3、對象池

還有一種方法是對象池，也是把堆空間分成了大小相等的一些塊，它是認為某些場合每次分配的空間都相等，所以每次就直接返回一個塊的大小，它的管理方法可以是鏈表也可以是位圖。因為不用每次查找合適的大小的內(nèi)存返回，所以效率很高。

實際上很多現(xiàn)實應用中，堆的分配算法往往是采取多種算法復合而成的。

比如對于glibc來說，它對于小于64字節(jié)的空間申請是采用類似于對象池的方法。

而對于大于512字節(jié)的空間申請采用的是最佳適配算法；

對于大于64字節(jié)而小于512字節(jié)的，它會根據(jù)情況采取上述方法中的最佳折中策略；

對于大于128KB的申請，它會使用mmap機制直接向操作系統(tǒng)申請空間。

參考資料：

1、

《程序員的自我修養(yǎng)》

2、http://www.ruanyifeng.com/blog/2016/12/user_space_vs_kernel_space.html

（完）。

今天的技術分享就到這里了，有問題，歡迎和我一起交流~

推薦閱讀

找工作那些事-做簡歷注意事項

找工作那些事-和表弟的一次聊天

《STL源碼剖析》之關聯(lián)式容器

《STL 源碼剖析》內(nèi)存管理，迭代器

認真的人，自帶光芒！

原創(chuàng)不易

點個在看唄