系統級程式設計筆記（unit4——堆棧、堆和動态記憶體配置設定）

這個專題的所有學習筆記來自于對武漢大學計算機學院軟體工程專業大三上學期的專業必修課《系統級程式設計》的學習（教材為深入了解計算機系統CSAPP），涉及的程式設計語言全部為C語言和C++語言。

該部落格為第4單元的學習筆記，這一單元的主要内容是堆棧的再認識、動态記憶體配置設定、堆的認識、隐式空閑連結清單、垃圾回收、C語言中與記憶體有關的常見錯誤等，部分内容來自《深入了解計算機系統》的第三章第七節的内容和第九章第九節的内容。對應ssd6課程的lecture5。

靜态聲明（Conclusions to C++ static Declarations）

（1）書上的内容：當我們同時編譯多個檔案時，所有未加static字首的全局變量和函數都具有全局可見性，其它的源檔案也能通路。如果加了static，就會對其它源檔案隐藏。利用這一特性可以在不同的檔案中定義同名函數和同名變量，而不必擔心命名沖突。static可以用作函數和變量的字首，對于函數來講，static的作用僅限于隐藏。

PPT上的内容：C程式員使用靜态屬性來隐藏變量和函數聲明的内部子產品，就像你會使用public和private在java和C++的聲明。C源檔案起子產品作用。

任何靜态屬性聲明的全局變量或函數都是私有的。類似地，沒有靜态屬性聲明的任何全局變量或函數都是公共的，并且可以由任何其他子產品通路。

盡可能地用靜态屬性保護變量和函數，這是好的程式設計風格。

有趣的是，使用C靜态屬性定義的本地過程變量沒有在堆棧上進行管理。

（2）靜态配置設定的注意事項：

靜态配置設定的資料使用記憶體作為程式的生命周期。

它一定是固定大小的。

不是靜态配置設定記憶體，而是等待運作時配置設定（如果知道大小）。

對靜态資料的限制取決于系統。

（3）

setjmp(jmp_buf j) //first load

longjmp(jmp_buf j, int i) //destroy buf, and back

①setjmp和logjmp是配合使用的，用它們可以實作跳轉的功能，和goto語句很類似，不同的是goto隻能實作在同一個函數之内的跳轉，而setjmp和longjmp可以實作在不同函數間的跳轉

用法：首先用setjmp設定跳轉的地點，setjmp的參數buf是用來儲存設定跳轉點時的函數使用的重要資料，當從其他函數跳轉回來，如果不用這個儲存的資料恢複目前函數的一些資料的話，跳轉回來是不能運作的。第一次設定的時候setjmp傳回值為0

使用longjmp就可以跳轉到setjmp的地方了，參數buf就是使用setjmp的時候儲存的，而第二個參數會在跳轉以後把這個值讓setjmp傳回的，也就是longjmp第二個參數，就是跳轉到setjmp之後setjmp函數要傳回的值

如何實作異常處理

首先設定一個跳轉點（setjmp()函數可以實作這一功能），然後在其後的代碼中任意地方調用longjmp()跳轉回這個跳轉點上，以此來實作當發生異常時，轉到處理異常的程式上，在其後的介紹中将介紹如何實作。setjmp()為跳轉傳回儲存現場并為異常提供處理程式，longjmp()則進行跳轉（抛出異常），setjmp()與longjmp()可以在函數間進行跳轉，這就像一個全局的goto語句，可以跨函數跳轉。

②例子

main()    
{
  volatile int b;
  b =;
  if(setjmp(buf)!=)  {
    printf("%d ", b);  
    exit();
  }
  b=;
  longjmp(buf , );
} 
//請問輸出是？
           

這個代碼裡運作步驟：

1.先執行setjmp，因為是第一次設定跳轉點，傳回值是0，不執行if語句塊裡的語句，

2.然後執行b=5，b的值就是5了

3.再執行longjmp跳轉之後， 最後再執行setjmp， 這時setjmp會傳回1（也就是longjmp的第二個參數指定的值），就會執行if語句塊裡的語句—-列印之後終止程式，這時b的值是5，就會列印出5來

③

#include<stdio.h>
#include<setjmp.h>
jmp_buf buf;
int times=;
void second(int *k){
    printf(“second times=%d\n”,++(*k));
    longjmp(buf,);
}
void first(int *k){
    prinf(“first times=%d\n”,++(*k));
    second(k);
}
int main(void){
    int ret=setjmp(buf);
    if(ret==){
        printf(“.ret is %d\n”,ret);
        first(&times);
    }else{
        printf(“.ret is %d\n”,ret);
    }
}
           

運作結果：

1.ret is 0

first times=1

second times=2

2.ret is 65536

堆棧

（1）堆棧配置設定：

堆棧非常有效地支援遞歸和動态配置設定。

當函數被調用時：堆棧儲存參數值、本地變量和調用函數的位址。

當函數傳回時：堆棧空間被回收用于重用。

不同函數中的變量可以具有相同的名稱，但仍然表示不同的變量。

遞歸函數的每個執行個體都可以有自己的私有變量集。

遞歸函數可以建立任意多個函數執行個體。

（2）使用堆棧的函數調用：

主要概念：

①Activation Record or Stack Frame（活動記錄或者棧幀）

函數調用時，為該函數配置設定的，用于記錄函數資訊的存儲塊。（因為活動記錄使用棧存儲，一個活動記錄又稱棧幀（Stack Frame））

一次函數調用包括将資料和控制從代碼的一個部分傳遞到另外一個部分，棧幀與某個過程調用一一映射。每個函數的每次調用，都有它自己獨立的一個棧幀，這個棧幀中維持着所需要的各種資訊。

②TOS=Top of Stack

即棧指針（Stack Pointer），記錄了棧頂位置，也就是下一個活動記錄将被配置設定的位置。又稱TOS棧頂（Top of Stack）,在Pentium裡面又稱（ESP）

③Frame=Activation Record Base

幀指針（Frame Pointer），記錄了目前活動記錄的結束位址，也就是函數傳回時，棧指針将指向的位置。又稱活動基址（Activity Record Base）,在Pentium中又稱作（EBP）

④PC=Program Counter（程式計數器）

用于儲存下一條指令位址的寄存器。

（3）堆配置設定（顯式）：

不要在堆棧上傳回本地變量的位址。

堆記憶體：堆棧記憶體的另一種選擇

配置設定記憶體：malloc或new

傳回記憶體：free或delete

堆上的記憶體總是用指針表示和通路。

常見的記憶體錯誤：

忘記釋放記憶體

記憶體洩漏

懸挂指針問題

動态記憶體配置設定

（1）動态記憶體配置設定器維護一個程序的虛拟記憶體區域，稱為堆。對于每個程序，核心維護着一個變量brk，指向堆的頂部。

配置設定器将堆視為一組不同大小的塊的集合來維護，每個塊是一個連續的虛拟記憶體片，要麼是已配置設定的，要麼是空閑的。

配置設定器有兩種基本風格，兩種風格都要求應用顯式地配置設定塊，它們的不同之處在于由哪個實體來負責釋放已配置設定的塊。顯式配置設定器要求應用顯式地釋放任何已配置設定的塊，比如C中的malloc和free，C++中的new和delete。隐式配置設定器要求配置設定器檢測一個已配置設定塊何時不再被程式所使用，那麼就釋放這個塊，隐式配置設定器也叫做垃圾收集器。

（2）顯式配置設定器：C标準庫提供了一個稱為malloc程式包的顯示配置設定器，程式通過調用malloc函數來從堆中配置設定塊

①void *malloc(size_t size);

malloc函數傳回一個指針，指向大小至少size位元組的記憶體塊，這個塊會為可能包含在這個塊内的任何資料對象類型做對齊。

如果malloc遇到問題（例如程式要求的記憶體塊比可用的虛拟記憶體還要大），那麼它就傳回NULL，并設定errno。malloc不初始化它傳回的記憶體。

②sbrk函數：void *sbrk(intptr_t incr);

sbrk函數通過将核心的brk指針增加incr來擴充和收縮堆。

如果成功，它就傳回brk的舊值，否則它就傳回-1，并将errno設定為ENOMEM

如果incr為零，那麼sbrk就傳回brk的目前值(2017-2018學年期末考試考了這裡)

③free函數：void free(void *ptr);

ptr參數必須指向一個從malloc、calloc或者realloc獲得的已配置設定塊的起始位置。如果不是，那麼free的行為就是未定義的。更糟糕的是，既然它什麼都不傳回，free就不會告訴應用出現了錯誤。

（3）為什麼要使用動态記憶體配置設定：程式使用動态記憶體配置設定的最重要的原因是經常直到程式實際運作時，才知道某些資料結構的大小。而使用寫死的大小來配置設定數組不是一種好想法（不利于維護，還可能需要重新編譯）

（4）配置設定器的規則和目标：

• 規則：
• 處理任意請求序列（不能假設所有的配置設定請求都有相比對的釋放請求）
• 立即響應請求（不允許配置設定器為了提高性能重新排列或者緩沖請求）
• 隻使用堆（為了使配置設定器是可擴充的）
• 對齊塊
• 不修改已配置設定的塊（配置設定器隻能操作或者改變空閑塊，一旦塊被配置設定就不允許修改或者移動了）
• 目标：
• 目标1：最大化吞吐率
• 目标2：最大化記憶體使用率

（5）碎片

内部碎片：已配置設定塊比有效載荷大的時候發生的

外部碎片：空閑記憶體合計起來足夠滿足一個配置設定請求，但沒有一個單獨的空閑塊足夠大可以來處理這個請求

（6）實作問題

可以想象出的最簡單的配置設定器會把堆組織成一個大的位元組數組，還有一個指針p，初始指向這個數組的第一個位元組。為了配置設定size個位元組，malloc将p的目前值儲存在棧裡，将p增加size，并将p的舊值傳回到調用函數。free隻是簡單地傳回到調用函數而不做任何事情。

這個簡單的配置設定器是一種極端情況，因為每個malloc和free隻執行很少的指令，吞吐率會極好。然而，因為配置設定器從不重複使用任何塊，記憶體使用率将極差。一個實際的配置設定器要在吞吐率和使用率之間把握好平衡要考慮以下問題：（2017-2018學年期末考試考了這裡）

• 空閑塊組織：如何記錄空閑塊？
• 放置：如何選擇一個合适的空閑塊來放置一個新配置設定的塊？
• 分割：在将一個新配置設定的塊放置到某個空閑塊之後，如何處理這個空閑塊中的剩餘部分？
• 合并：如何處理一個剛剛被釋放的塊？

（7）隐式空閑連結清單

①介紹

任何實際的配置設定器都需要一些資料結構，允許它來差別塊邊界，以及差別已配置設定塊和空閑塊。大多數配置設定器将這些資訊嵌入塊本身。如下圖所示

在這種情況中，一個塊是由一個字的頭部、有效載荷、以及可能的一些額外的填充組成的。頭部編碼了這個塊的大小以及這個塊是配置設定的還是空閑的。如果有一個雙字的對齊限制條件，塊大小就總是8的倍數，塊大小的最低3位總是0.假設有一個已配置設定的塊（a=1），大小為24（0x18）位元組，頭部将是

0x00000018|0x1=0x00000019

類似地，一個空閑塊（a=0），大小為40（0x28）位元組，頭部将是

0x00000028|0x=0x00000028

記憶體對齊的原理（原因？）是？（Alignment）

平台原因：不是所有的硬體平台都能通路任意位址上的任意資料，某些硬體平台隻能在某些位址取某些特定類型的資料，否則抛出硬體異常

性能原因：資料結構應該盡可能在自然邊界上對齊，為了通路未對齊的記憶體，處理器需要作兩次記憶體通路，而對齊的記憶體僅需要一次。

可以将堆組織一個連續的已配置設定塊和空閑塊的序列，如下圖所示：

用隐式空閑連結清單來組織堆，其中陰影部分是已配置設定塊，沒陰影部分是空閑塊

頭部标記為（大小（位元組）/已配置設定位）

稱這種結構為隐式空閑連結清單是因為空閑塊是通過頭部中的大小字段隐含地連接配接着的。配置設定器可以通過周遊堆中所有的塊進而間接地周遊整個空閑塊的集合。我們需要某種特殊标記的結束塊，一個設定已配置設定位而大小為零的終止頭部。

隐式空閑連結清單優點：簡單

缺點：任何操作的開銷要求對空閑連結清單進行搜尋，所需時間與堆中已配置設定塊和空閑塊的總數呈線性關系。

P593練習題6

②放置已配置設定的塊

首次适配、下一次适配和最佳适配

首次适配從頭開始搜尋連結清單，選擇第一個合适的空閑塊。

下一次适配從上一次查詢結束的地方開始搜尋，選擇第一個合适的空閑塊。

最佳适配檢查每個空閑塊，選擇适合所需請求大小的最小空閑塊。

③分割空閑塊

一旦配置設定器找到一個比對的空閑塊，就必須做出一個政策決定，那就是配置設定這個空閑塊中多少空間。一個選擇是用整個空閑塊，雖然簡單快捷，但會造成内部碎片。如果防止政策趨向于産生好的比對，那麼額外的内部碎片也是可以接受的。

然而如果比對不太好，那麼配置設定器通常會把這個空閑塊分割為兩部分，第一部分變成配置設定塊，剩下的變成一個新的空閑塊。如下圖展示了配置設定器如何分割圖中8個字的空閑塊來滿足一個應用的對堆記憶體3個字的請求。

④擷取額外的堆記憶體

如果配置設定器不能為請求塊找到合适的空閑塊将發生什麼呢？

一個選擇是通過合并那些在記憶體中實體上相鄰的空閑塊來建立一些更大的空閑塊。然而如果這樣還是不能生成一個足夠大的塊，或者空閑塊已經最大程度地合并了，那麼配置設定器就會通過調用sbrk函數向核心請求額外的堆記憶體。配置設定器将額外的記憶體轉化成一個大的空閑塊，将這個塊插入到空閑連結清單中，然後将被請求的塊放置在這個新的空閑塊中。

⑤合并空閑塊

當配置設定器釋放一個已配置設定塊時，可能有其他空閑塊與這個新釋放的空閑塊相鄰。這些鄰接的空閑塊引起一種現象叫做假碎片，就是有許多可用的空閑塊被切割成為小的、無法使用的空閑塊。

立即合并和推遲合并：立即合并簡單明了，但對于某些請求模式會産生一種形式的抖動，塊會反複合并然後馬上分割，産生大量不必要的分割和合并。

⑥帶邊界标記的合并（書P596）+練習題7

（8）垃圾回收機制的算法有哪些？

①标記-清除算法

首先标記處所有需要回收的對象，在标記完成後統一收掉所有被标記的對象。缺點有兩個：一個事效率問題。标記和清除過程的效率都不高；另一個是空間問題，标記清除之後會産生大量的不連續的記憶體碎片。

②複制算法

它将可用記憶體按容量劃分成大小相等的兩塊，每次隻使用其中的一塊。當這塊的記憶體用完了，就将還存活的對象複制到另一塊上面，然後再把已使用的記憶體空間一次清理掉。記憶體配置設定時也就不用考慮碎片的問題了，隻要移動堆頂指針，按順序配置設定記憶體即可實作簡單，運作高效。但代價是記憶體縮小為原來的一半。

③标記-整理算法

前半部分與标記-清除算法相似，但不是直接回收，而是讓所有存貨的對象都向一端移動，然後直接清理掉邊界以外的記憶體。

④引用計數法

給對象添加一個引用計數器，每當有一個地方引用它時，計數器值加1，當引用失效時，減1，任何時候計數器為0的對象都是不可能再被使用的，可以被清除掉。它不能解決對象之間的互相循環引用問題。

⑤分代收集算法

根據對象的存活周期不同将記憶體劃分為幾塊。一般是把java堆分為新生代和老年代，這樣就可以根據各個年代的特點采用最适當的收集算法。

C語言中的一些常見的錯誤

（1）未初始化的本地指針

int sum(int a[], int n)
{
    int *p;
    int sum = ;
    for (int i = ; i < n; i++)
        sum += *p++;
}
           

假設您聲明了一個本地指針但是忘記初始化它。由于變量的記憶體在堆棧上，并且堆棧可能充滿了之前的活動記錄所丢棄的資料，是以指針可以有任何值：

（2）未初始化的局部變量

int i;
double d;
scanf("%d %g", i, d); // wrong!!!
// here is the correct call:
scanf("%d %g", &i, &d);
           

scanf()不指定所有參數的類型，而形參在預編譯的時候需要告訴系統要預留出多少的記憶體空間，是以這裡的參數不可以是未初始化的局部變量。

（3）記憶體溢出問題

#define array_size 100
int *a = (int *) malloc(sizeof(int *) * array_size);
for (int i = ; i <= array_size; i++)
    a[i] = NULL;
           

這是一個顯然而低級的錯誤，但卻是我們經常會不小心犯，應該把for循環中的小于等于改成小于。

（4）超出所配置設定的記憶體

#define array_size 100
int *a = (int *) malloc(array_size);
a[] = ; // this overwrites memory beyond the block
           

配置設定太少的記憶體會導緻之後的指派覆寫掉之前的記憶體。

應該為a=(int*)malloc(array_size*sizeof(int))

（5）忘記給\0配置設定空間

有時，程式員忘記字元串是由\0結束的。考慮下面的函數，該函數将字元串傳輸到堆：

char *heapify_string(char *s){
    int len = strlen(s);

    char *new_s = (char *) malloc(len);
    strcpy(new_s, s);
    return new_s;
}
           

在這個例子中，程式沒有為字元串配置設定足夠的空間。malloc中的參數應該為len+1，為終止的零位元組留下空間。如果malloc配置設定的是8位元組的倍數，當len是8位元組的倍數的時候heapify_string這個函數将會失敗（除非記憶體大小不是舍入到更大的記憶體大小）

另外，當兩個字元串連接配接時，結果字元串也有可能占用太多空間：

char q[] = “do not overflow”;

char r[] = ” memory”;

char s[16];

strcpy(s, q);

strcat(s, r);

需要22+1（終止0字元）個字元，但隻配置設定了16，是以寫操作會超出所配置設定的記憶體（要知道strcat函數并不會為結果配置設定額外的記憶體）

（6）在運作時堆棧上建構指針并将指針傳回給調用方

int *ptr_to_zero(){
    int i = ;
    return &i;
}
           

盡管這個函數傳回一個指向0值整數的指針，但是這個整數是在一個活動記錄中。而這個函數傳回時這個活動記錄就會被立刻删除，那麼指針引用的記憶體的值可以變成任意值，這還要取決于其他函數的調用情況。

（7）運算順序和優先級導緻的問題

// decrement a if a is greater than zero:
void dec_positive(int *a){
    *a--; // decrement the integer
    if (*a < ) *a = ; // make sure a is positive
}
           

函數裡的第一行代碼本來想減少a的值，但是事實上減少的是指向a的指針，錯誤原因是–的優先級雖然和*一樣高，但是執行順序是從右向左執行的。當不确定運算優先級時需要使用括号，之前的代碼改為(*a)–即可。

（8）意外地釋放相同的指針兩次

void my_write(x){
    ... use x ...
    free(x);
}
int *x = (int *) malloc(sizeof(int*) * N);
...
my_read(x);
...
my_write(x);
free(x); //oops, x is freed in my_write()!
           

（9）引用釋放的記憶體塊

一旦一個塊被釋放，如果塊占用的記憶體被另一個塊重用，它的資料随時可能被堆配置設定程式和應用程式改變。是以，使用一個被釋放指針會導緻不好的事情發生。您可能在塊被修改的地方讀取到垃圾，如果寫入塊，則可能破壞程式已經配置設定好的堆或資料。下面是一個引用已釋放指針的程式的示例：

void my_write(x){
    ... use x ...
    free(x);
}
int *x = (int *) malloc(sizeof(int*) * N);
...
my_read(x);
...
my_write(x);
...
my_read(x); // oops, x was freed by my write!
...
my_write(x);
           

避免這種錯誤的一種方法是在釋放指針時替換帶有null的指針。然而，如果指針有多個副本，這并不能解決問題。事實上這是一個常見的錯誤發生方式：程式員完成了一個引用并釋放了塊，忘記了還有其他引用可能被使用。

（10）記憶體洩漏

記憶體洩漏形象的比喻是”作業系統可提供給所有程序的存儲空間正在被某個程序榨幹”，最終結果是程式運作時間越長，占用存儲空間越來越多，最終用盡全部存儲空間，整個系統崩潰。

void my_function(char *msg){
    // allocate space for a string
    char *full_msg = (char *) malloc(strlen(msg) + );
    strcpy(full_msg, "The following error was encountered: ");
    strcat(full_msg, msg);
    if (!display(full_msg)) return;
    ...
    free(full_msg);   
}
           

在這個例子中，被配置設定的記憶體在函數最後一行被釋放，但如果在display那裡發生了錯誤，這個函數就會提前傳回而沒有釋放記憶體。異常、錯誤、各種形式的抛出和捕獲通常都會與記憶體洩漏有關。

（11）忘記釋放資料結構的各個部分導緻記憶體洩漏

typedef struct  {
    char *name;
    int age;
    char *address;
    int phone;
} Person;
void my_function(){
    Person *p = (Person *) malloc(sizeof(Person));
    p->name = (char *) malloc(M);
    ...
    p->address = (char *) malloc(N);
    ...
    free(p); // what about name and address?
}
           

在這個例子中，一個person結構體被配置設定和釋放，但是這個結構體的一部分，name和address被配置設定了但是沒有被釋放。