內存，第 1 部分：堆內存簡介 · UIUC CS241 系統編程中文講義

# 內存，第 1 部分：堆內存簡介 > 原文：<https://github.com/angrave/SystemProgramming/wiki/Memory%2C-Part-1%3A-Heap-Memory-Introduction> ## C 動態內存分配 ## 當我打電話給 malloc 時會發生什么？函數`malloc`是 C 庫調用，用于保留連續的內存塊。與棧內存不同，內存保持分配狀態，直到使用相同的指針調用`free`。還有`calloc`和`realloc`，將在下面討論。 ## malloc 可以失敗嗎？如果`malloc`無法再保留更多內存，則返回`NULL`。強大的程序應該檢查返回值。如果您的代碼假定`malloc`成功但它沒有，那么當您嘗試寫入地址 0 時，您的程序可能會崩潰（segfault）。 ## 堆在哪里，它有多大？堆是進程內存的一部分，它沒有固定的大小。當您調用`malloc`（`calloc`，`realloc`）和`free`時，堆存儲器分配由 C 庫執行。首先快速回顧一下進程內存：進程是程序的運行實例。每個進程都有自己的地址空間。例如，在 32 位機器上，您的進程可以獲得大約 40 億個地址，但并非所有這些地址都有效，甚至映射到實際物理內存（RAM）。在進程內存中，您將找到可執行代碼，棧空間，環境變量，全局（靜態）變量和堆。通過調用`sbrk`，C 庫可以增加堆的大小，因為程序需要更多的堆內存。由于堆和棧（每個線程一個）需要增長，我們將它們放在地址空間的兩端。因此，對于典型的體系結構，堆將向上生長并且棧向下增長。真實性：現代操作系統內存分配器不再需要`sbrk` - 相反，它們可以請求虛擬內存的獨立區域并維護多個內存區域。例如，可以將千兆字節請求放置在與小分配請求不同的存儲器區域中。然而，這個細節是一個不必要的復雜性：碎片化和有效分配內存的問題仍然適用，因此我們將在這里忽略這種實現，并將寫入就像堆是單個區域一樣。如果我們編寫一個多線程程序（稍后會詳細介紹），我們將需要多個棧（每個線程一個），但只有一個堆。在典型的體系結構中，堆是`Data segment`的一部分，并從代碼和全局變量的上方開始。 ## 程序需要調用 brk 或 sbrk 嗎？通常不會（雖然調用`sbrk(0)`會很有趣，因為它會告訴您堆當前的結束位置）。而程序使用`malloc,calloc,realloc`和`free`，它們是 C 庫的一部分。當需要額外的堆內存時，這些函數的內部實現將調用`sbrk`。 ```c void *top_of_heap = sbrk(0); malloc(16384); void *top_of_heap2 = sbrk(0); printf("The top of heap went from %p to %p \n", top_of_heap, top_of_heap2); ``` 輸出示例：`The top of heap went from 0x4000 to 0xa000` ## 什么是 calloc？與`malloc`不同，`calloc`將內存內容初始化為零，并且還采用兩個參數（項目數和每個項目的字節大小）。 `calloc`的簡單但可讀的實現如下所示： ```c void *calloc(size_t n, size_t size) { size_t total = n * size; // Does not check for overflow! void *result = malloc(total); if (!result) return NULL; // If we're using new memory pages // just allocated from the system by calling sbrk // then they will be zero so zero-ing out is unnecessary, memset(result, 0, total); return result; } ``` 這些局限性的高級討論是 [](http://locklessinc.com/articles/calloc/) 。程序員經常使用`calloc`而不是在`malloc`之后顯式調用`memset`，將存儲器內容設置為零。注意`calloc(x,y)`與`calloc(y,x)`相同，但您應遵循本手冊的慣例。 ```c // Ensure our memory is initialized to zero link_t *link = malloc(256); memset(link, 0, 256); // Assumes malloc returned a valid address! link_t *link = calloc(1, 256); // safer: calloc(1, sizeof(link_t)); ``` ## 為什么 sbrk 首先返回的內存初始化為零？如果操作系統沒有將物理 RAM 的內容清零，則一個進程可能會了解先前使用過該內存的另一個進程的內存。這將是一個安全漏洞。不幸的是，這意味著對于在釋放任何內存之前的`malloc`請求和簡單程序（最終使用系統中新保留的內存），內存 _ 通常為 _ 為零。然后程序員錯誤地寫 C 程序，假設 malloc 的內存 _ 總是 _ 為零。 ```c char* ptr = malloc(300); // contents is probably zero because we get brand new memory // so beginner programs appear to work! // strcpy(ptr, "Some data"); // work with the data free(ptr); // later char *ptr2 = malloc(308); // Contents might now contain existing data and is probably not zero ``` ## 為什么 malloc 總是將內存初始化為零？性能！我們希望 malloc 盡可能快。將內存清零可能是不必要的。 ## 什么是 realloc 以及何時使用它？ `realloc`允許您調整先前在堆上分配的現有內存分配（通過 malloc，calloc 或 realloc）。 realloc 最常見的用途是調整用于保存值數組的內存。下面提出了一個簡單但可讀的 realloc 版本 ```c void * realloc(void * ptr, size_t newsize) { // Simple implementation always reserves more memory // and has no error checking void *result = malloc(newsize); size_t oldsize = ... //(depends on allocator's internal data structure) if (ptr) memcpy(result, ptr, newsize < oldsize ? newsize : oldsize); free(ptr); return result; } ``` INCORRECT 使用 realloc 如下所示： ```c int *array = malloc(sizeof(int) * 2); array[0] = 10; array[1] = 20; // Ooops need a bigger array - so use realloc.. realloc (array, 3); // ERRORS! array[2] = 30; ``` 上面的代碼包含兩個錯誤。首先，我們需要 3 * sizeof（int）字節而不是 3 字節。其次，realloc 可能需要將存儲器的現有內容移動到新位置。例如，可能沒有足夠的空間，因為已經分配了相鄰的字節。正確使用 realloc 如下所示。 ```c array = realloc(array, 3 * sizeof(int)); // If array is copied to a new location then old allocation will be freed. ``` 強大的版本也會檢查`NULL`返回值。注意`realloc`可用于增長和縮小分配。 ## 我在哪里可以閱讀更多？請參見[手冊頁](http://man7.org/linux/man-pages/man3/malloc.3.html)！ ## 內存分配快速有多重要？非常！在大多數應用程序中，分配和取消分配堆內存是一種常見操作。 ## 分配簡介 ## 什么是最愚蠢的 malloc 和免費實現以及它有什么問題？ ```c void* malloc(size_t size) // Ask the system for more bytes by extending the heap space. // sbrk Returns -1 on failure void *p = sbrk(size); if(p == (void *) -1) return NULL; // No space left return p; } void free() {/* Do nothing */} ``` 上述實現存在兩個主要缺點： * 系統調用很慢（與庫調用相比）。我們應該保留大量的內存，只是偶爾要求系統提供更多內存。 * 沒有重用已釋放的內存。我們的程序永遠不會重用堆內存 - 它只是不斷要求更大的堆。如果在典型程序中使用此分配器，則該過程將很快耗盡所有可用內存。相反，我們需要一個可以有效使用堆空間的分配器，并且只在必要時請求更多內存。 ## 什么是貼裝策略？在程序執行期間，內存被分配和解除分配（釋放），因此堆內存中的間隙（空洞）可以重新用于將來的內存請求。內存分配器需要跟蹤當前分配的堆的哪些部分以及哪些部分可用。假設我們當前的堆大小是 64K，但并非所有的大小都在使用中，因為一些早期的 malloc 內存已被程序釋放： | 16KB 免費 | 分配 10KB | 1KB 免費 | 分配 1KB | 30KB 免費 | 分配 4KB | 2KB 免費 | | --- | --- | --- | --- | --- | --- | --- | 如果執行了 2KB 的新 malloc 請求（`malloc(2048)`），`malloc`應該在哪里保留內存？它可以使用最后 2KB 的孔（恰好是完美的尺寸！）或者它可以分開另外兩個自由孔中的一個。這些選擇代表不同的放置策略。無論選擇哪個孔，分配器都需要將孔分成兩個：新分配的空間（將返回到程序中）和一個較小的孔（如果有剩余空間）。完美貼合策略找到足夠大小（至少 2KB）的最小孔： | 16KB free | 10KB allocated | 1KB free | 1KB allocated | 30KB free | 4KB allocated | `2KB HERE!` | | --- | --- | --- | --- | --- | --- | --- | 最差的策略是找到足夠大的最大孔（所以將 30KB 的孔分成兩個）： | 16KB free | 10KB allocated | 1KB free | 1KB allocated | `2KB HERE!` | `28KB free` | 4KB allocated | 2KB free | | --- | --- | --- | --- | --- | --- | --- | --- | 第一個擬合策略找到第一個足夠大小的可用孔（將 16KB 孔分成兩個）： | `2KB HERE!` | `14KB free` | 10KB allocated | 1KB free | 1KB allocated | 30KB free | 4KB allocated | 2KB free | | --- | --- | --- | --- | --- | --- | --- | --- | ## 什么是外部碎片？在下面的例子中，64KB 的堆內存中，分配了 17KB，47KB 是免費的。但是，最大的可用塊只有 30KB，因為我們可用的未分配堆內存被分段為更小的塊。 | `16KB free` | 10KB allocated | 1KB free | 1KB allocated | 30KB free | 4KB allocated | 2KB free | | --- | --- | --- | --- | --- | --- | --- | ## 放置策略對外部碎片和性能有何影響？不同的策略以非顯而易見的方式影響堆內存的碎片，這只能通過數學分析或在真實條件下仔細模擬（例如模擬數據庫或 Web 服務器的內存分配請求）來發現。例如，乍一看最合適似乎是一個很好的策略，但是，如果我們找不到一個尺寸合適的孔，那么這個位置會產生許多微小的不可用孔，導致高度碎裂。它還需要掃描所有可能的孔。首次合身的優勢在于它不會評估所有可能的展示位置，因此速度更快。由于 Worst-fit 以最大的未分配空間為目標，因此如果需要大量分配，則選擇較差。在實踐中，首次適合和下一次適合（這里未討論）通常是常見的放置策略。存在混合方法和許多其他替代方案（請參閱實現內存分配器頁面）。 ## 編寫堆分配器有哪些挑戰？主要挑戰是， * 需要最小化碎片（即最大化內存利用率） * 需要高性能 * 繁瑣的實現（使用鏈表和指針算法的大量指針操作）一些額外的評論：碎片和性能都取決于應用程序分配配置文件，可以對其進行評估但不能預測，并且在實踐中，特定用途條件不足，專用分配器通常可以超出通用實現。分配器事先不知道程序的內存分配請求。即使我們這樣做，這就是[背包問題](http://en.wikipedia.org/wiki/Knapsack_problem)，它已知是 NP 難！ ## 你如何實現內存分配器？好問題。 [實現內存分配器](https://github.com/angrave/SystemProgramming/wiki/Memory%2C-Part-2%3A-Implementing-a-Memory-Allocator)