程式語言導論/堆

堆

在本節中，我們將描述堆分配，但首先，讓我們瞭解什麼是堆。當編譯器讀取函式的原始碼時，它確切地知道該函式將在堆疊中使用多少空間。編譯器知道函式有多少個區域性變數，其返回值的大小等等。

但是，當談到在堆上分配的物件時，情況就有點不同了。程式設計師傾向於使用堆來分配依賴於使用者輸入的物件，因此它們的大小在編譯時是未知的。如果你曾經用 C 程式設計，每當你使用關鍵字 `malloc`（或 C++ 中的 `new`）或它的變體時，你都在堆上分配一個物件。

堆分配非常具有挑戰性。在接下來的部分中，我們將描述其主要問題。

堆管理問題

放置

堆管理的第一個挑戰在於將分配的物件放在哪裡。基本上有三個選項：首次適應、最佳適應和最差適應。我們將使用一個類比來描述它們。

假設你週末帶著家人去商場。因為停車場不像工作日那樣擁擠，所以你有許多選擇。如果天氣晴朗，你想盡快進入商場和孩子們一起吃冰淇淋，你可能會停在第一個空著的停車位。另一方面，如果你不著急吃冰淇淋，想知道你決定回家時停車場會不會滿了，你可能會嘗試停在一個對你來說有更多可用空間的停車位。最後，如果你是一名經驗豐富的司機並且喜歡挑戰，你會尋找最適合你汽車尺寸的停車位。

如果作業系統使用首次適應策略，它將像渴望吃冰淇淋的司機一樣，在它找到的第一個可用位置分配物件。另一方面，如果作業系統使用最差適應策略，它將與意識停車場滿意的司機幾乎一樣，在有儘可能多可用空間的位置分配物件。最後，如果作業系統使用最佳適應策略，它將像經驗豐富的司機一樣，在最適合物件大小的可用位置分配物件。通常，作業系統使用首次適應策略。

記憶體管理常見錯誤

現在我們將降低一點難度，暫時放下汽車、停車場等等，專注於 C 程式。

記憶體洩漏

當程式設計師想要使用記憶體時，他/她可以通過幾種方式來實現：一種是宣告靜態或全域性變數，在這種情況下，變數將被放在靜態儲存區；另一種是宣告函式內的區域性變數，在這種情況下，變數將被放在堆疊中；最後，他/她可以動態地分配變數，在這種情況下，變數將被放在堆中。在這種情況下，作業系統會在正在執行的程式請求變數空間時在堆中分配空間。

每當程式設計師分配記憶體但沒有釋放該記憶體時，就會發生記憶體洩漏。我們將在下面展示一個這種記憶體錯誤的示例。在這個示例中，我們請求了變數 i 的空間，但我們沒有 `free` 它的空間。

#include <stdio.h>
#include <stdlib.h>

void problem() {
  int* i = (int*) malloc (sizeof(int));
  *i = 3;
  printf("%d\n", *i);
}

int main() {
  problem();
}

要編譯上面的程式，我們可以這樣做

   $> gcc -g Leak.c

透過使用 valgrind，我們可以找到錯誤。有關 valgrind 的更詳細教程，請參閱此處。要找到像上面那樣簡單的錯誤，你可以只使用

   $> valgrind -v ./a.out

懸掛指標

另一個常見但更隱蔽的記憶體錯誤稱為 懸掛指標。在計算機程式設計中，懸掛指標和野指標是指向無效物件的指標，這些物件並非相應的型別。這些是記憶體安全違反的特殊情況。

當物件被刪除或釋放時，而指標的值沒有改變，因此指標仍然指向已釋放記憶體的記憶體位置，就會出現懸掛指標。由於系統可能會將以前釋放的記憶體重新分配給另一個程序，因此如果原始程式隨後取消引用（現在）懸掛指標，則可能會導致不可預測的行為，因為記憶體現在可能包含完全不同的資料。

下面的程式包含一個懸掛指標。嘗試檢查它以找到問題。

#include <stdio.h>
#include <stdlib.h>

void dangling() {
  int* i = (int*) malloc (sizeof(int));
  int* j;
  *i = 3;
  free(i);
  j = (int*) malloc (sizeof(int));
  *j = 8;
  printf("%d\n", *i);
} 

int main() {
  dangling();
}