故宮角樓是很多攝影愛好者常去的地方，夕陽餘輝下的故宮角樓平靜而安詳。

首先，瞭解一下進程的基本概念，進程在記憶體中佈局和內容。

此外，還需要知道運行時是如何為動態數據結構（如鏈表和二叉樹）分配額外記憶體的。

一 進程

1 進程和程式

進程：是一個可執行程式的實例。

程式：包含一系列信息的文件，這些信息描述瞭如何在運行時創建一個進程。包含如下信息：

1. 二進位格式標識：如最常見的ELF格式。
2. 機器語言指令：對程式演算法進行編碼。
3. 程式入口地址：標識程式開始執行時的起始指令位置。
4. 數據：程式文件包含的變數初始值和程式使用的字面常量值，如字元串。
5. 符號表和重定位表：描述程式中函數和變數的位置及名稱。
6. 共用庫和動態鏈接信息：程式文件中所包含的一些欄位，列出了程式運行時需要使用的共用庫，以及載入共用庫的動態鏈接器的路徑名。
7. 其他信息。

進程的再定義：進程是由內核定義的抽象的實體，併為該實體分配用以執行程式的各項系統資源。

從內核的角度看，進程由用戶記憶體空間和一系列內核數據結構組成，其中用戶記憶體空間包含了程式代碼及代碼所使用的變數，而內核數據結構則用於維護進程狀態信息。

2 典型的進程記憶體佈局

每個進程所分配的記憶體由很多部分組成，通常稱之為“段（segment）”。如上圖所示：

1. 文本段：包含進程運行的程式機器語言指令。文本段具有隻讀屬性，因此多個進程可同時運行同一程式，共用文本段。
2. 初始化數據段：包含顯式初始化的全局變數和靜態變數。當程式載入到記憶體時，從可執行文件中讀取這些變數的值。
3. 未初始化數據段（BSS段，block started by symbol）：包含了未進行顯式初始化的全局變數和靜態變數。程式啟動之前，系統將本段內所有記憶體初始化為0.所以又叫做零初始化數據段。
4. 棧（stack）：動態增長和收縮的段，由棧幀（stack frame）組成。系統會為每個當前調用的函數分配一個棧幀。棧幀中存儲了函數的局部變數、實參和返回值。
5. 堆（heap）：在運行時為變數動態進行記憶體分配的一塊區域。堆頂端成為程式中斷（program break）

需要註意一點時，該記憶體佈局的討論是在虛擬記憶體中的，並不是物理記憶體中的佈局。

在後面會專門討論虛擬記憶體的一些細節。

二 記憶體分配

1 在堆上分配記憶體

堆：一段長度可變的連續虛擬記憶體，始於進程的未初始化數據段末尾，隨著記憶體的分配和釋放而增減。將堆的當前記憶體頂部邊界稱為“程式中斷（program break）”

program break是一個非常重要的概念，因為分配和釋放記憶體的實際動作就是改變進程的program break位置。

program break的起始位置（堆的大小為0）位於未初始化數據段末尾之後。

細節：在分配新的記憶體後，program break位置升高，程式可以訪問新分配區域內的任何記憶體地址，而此時物理記憶體頁尚未分配。記憶體會在進程首次試圖訪問這些虛擬記憶體地址時自動分配新的物理記憶體頁。

函數malloc和free

malloc函數聲明

#include
void *malloc(size_t size); 

作用：在堆上分配參數size位元組大小的記憶體。

返回值：成功返回指向新分配記憶體起始地址的指針，失敗返回NULL

free函數聲明 

#include
void free(void *ptr);


作用：釋放ptr參數所指向的記憶體塊，該參數應該是之前由malloc或者其他記憶體分配函數之一所返回的地址。

需要註意的是：一般情況下，free並不降低program break的位置，而是將這塊記憶體增加到空閑記憶體列表中，供後續的malloc函數迴圈使用。因為：

• 被釋放的記憶體塊通常位於堆的中間，而非堆的頂部，因而降低program break是不可能的。
• 它最大限度地減少了內核調用調整program break系統調用的次數。
• 通常程式會持有分配的記憶體或者反覆釋放和重新分配，而不是釋放所有記憶體再運行一段時間。

僅當堆頂空閑記憶體“足夠”大的時候，free函數的glibc實現會調用sbrk()來降低program break的地址，至於“足夠”與否則取決於malloc函數包行為的控制參數（128KB為典型值）。這減少了必須對sbrk()發起的調用次數。

malloc和free的實現

malloc()的實現

1. 掃描之前由free()所釋放的空閑記憶體塊列表，以求找到尺寸大於或者等於要求的一塊記憶體
2. 如果這一記憶體塊的尺寸正好與要求相當，就把它直接返回給調用者。
3. 如果是一塊較大的記憶體，那麼將對其進行分割，在將一塊大小相當的記憶體返回給調用者的同時，把較小的那塊空閑記憶體塊保留在空閑列表。
4. 如果在空閑記憶體列表中找不到足夠大的空閑記憶體塊，那麼malloc會調用sbrk()以分配更多的記憶體，並且malloc會分配出比所需位元組數更多的記憶體，將超出的部分置於空閑記憶體列表中。

free()的實現

首先先瞭解兩點：malloc返回的記憶體塊和空閑列表中的記憶體塊的結構

為了知道每一個記憶體塊的大小，當malloc分配記憶體塊時，會額外分配幾個位元組來存放記錄這塊記憶體大小的整數值。該整數位於記憶體塊的起始處，而實際返回給調用者的記憶體地址恰好位於這一長度記錄位元組之後。如下圖所示:

為了管理空閑記憶體列表，free()會使用記憶體塊本身的空間來存放鏈表指針，將自身添加到列表中。如下圖所示：

所以，在頻繁地分配和釋放記憶體之後，堆中的鏈表可能會變成下圖的樣子，空閑鏈表中的空閑記憶體會和已分配的在用記憶體混雜在一起。

三 編程需要註意的事項

通過對記憶體相關知識更多的瞭解，在平時編程的時候，應更清楚為什麼我們需要遵守下麵的規則。

1. 分配一塊記憶體後，不要改變這塊記憶體範圍外的任何內容。
2. 釋放同一塊已分配記憶體超過一次是錯誤的。當兩次釋放同一塊記憶體時，常見的後果是導致不可預知的行為。
3. 若非經由malloc函數包中函數所返回的指針，絕不能在調用free()函數使用。
4. 如果需要反覆分配記憶體，那麼應當確保釋放所有已使用完畢的記憶體，不然將導致記憶體泄露。

雖然在我們平時的工作當中，可能涉及不到這麼底層的原理，但是通過對這些基本原理的瞭解，可以讓我們更加清除，我們寫代碼究竟在寫些什麼 :)

參考資料：

《Linux/Unix系統編程手冊（上冊）》 第6章，第7章