系統級程序設計筆記（中）

系統級程序設計筆記（中）

來自專欄 文卿的學習筆記

該學習筆記來自於對武漢大學計算機學院軟體工程專業大三上學期的專業必修課《系統級程序設計》的學習，這門必修課對應卡內基梅隆大學的ssd6課程，教材主要為深入理解計算機系統CSAPP，涉及的編程語言全部為C語言和C++語言。

本篇文章包括第2單元和第4單元的學習筆記，其中第2單元的主要內容是堆棧原理的介紹、指針和數組、變數和地址等，部分內容來自《深入理解計算機系統》的第三章的部分內容，部分內容來自《C專家編程》。對應ssd6課程的lecture3；第4單元的主要內容是對堆棧的再認識、動態內存分配、堆的介紹、隱式空閑鏈表、垃圾回收、C語言中與內存有關的常見錯誤等，部分內容來自《深入理解計算機系統》的第三章第七節的內容和第九章第九節的內容。對應ssd6課程的lecture5。

unit2——程序的機器級表示

1.The Wonder of Program Execution

（1）觀察下面的代碼

#define ARRAY_SIZE 10void natural_numbers (void) { int i; int array[ARRAY_SIZE]; i = 1; while (i <= ARRAY_SIZE) { array[i] = i - 1; i = i + 1; }}

該代碼會陷入一種死循環的狀態，這是因為在內存中，局部變數的位置。數組a[9]結束後，是變數i，因此，對a[10]進行操作時，實際上是對變數i進行操作，所以變數i的值被修改為9，再次滿足進入循環的條件。i的值一直在9和10之間擺動，while條件總成立，造成了死循環。

（2）C語言中的抽象層次

C編程模型本身就是抽象的，體現在以下的方面：

使用變數名，而不是直接通過地址值進行訪問變數。

使用array[i]的形式訪問數組元素，而不需要自己計算元素的地址。

使用c=a+b，這樣的代碼實現加法，而不需要直接向CPU下達命令編譯器負責將C程序翻譯成機器代碼。

我們考慮變數和數據類型，而不是內存晶元。

我們考慮實現的演算法，而不是在這些晶元之間移動數據。

我們考慮程序語句，而不是存儲這些語句的位置和方式。

我們不太考慮執行過程，因為沒有必要 。

計算機系統使用了多種不同形式的抽象，利用更簡單的抽象模型來隱藏實現的細節。對於機器級編程來說，兩種抽象很重要，第一種是由指令集體系結構（Instruction Set Architecture，ISA）來定義機器級程序的格式和行為，第二種抽象是機器級程序使用的內存地址是虛擬地址，提供的內存模型看上去是一個非常大的位元組數組。

（3）對以下代碼的解釋：

#include <stdio.h>#include <string.h>#define MAXLINE_LENGTH 80char Buffer[MAXLINE_LENGTH];char * readString(void){ int nextInChar; int nextLocation; printf("Input> "); nextLocation = 0; while ((nextInChar = getchar()) !=
&& nextInChar != EOF) { Buffer[nextLocation++] = nextInChar; } return Buffer;}int main(int argc, char * argv[]){ char * newString; do { newString = readString(); printf("%s
", newString); } while (strncmp(newString, "exit", 4)); return 0;}

這段代碼並不能達到預期的效果，這是因為Buffer變數在這裡是全局的。在接連讀取的情況下。第二次讀取並不會清空第一次讀取中的數據。如果第二次讀取的數據比第一次短，那麼第一次比第二次多的那部分仍然會留在Buffer之中。例如

Input>Hello

Hello

Input>Hello world

Hello world

Input>Hello

Hello world

可以看到第三次輸入的是hello，但是依然保留了第二次輸出的world

2.變數和地址

（1）程序計數器(Program Counter)指示要執行的下一個指令的內存中的地址。

整數寄存器文件包含16個命名的位置，分別存儲64位的值。這些寄存器可以存儲地址（對應於C語言的指針）或整數數據。有些寄存器被用來記錄某些重要的程序狀態，而其他的寄存器用來保存臨時數據，例如過程的參數和局部變數，以及函數的返回值。

條件碼寄存器保存著最近執行的算術或邏輯指令的狀態信息。它們用來實現控制或數據流中的條件變化，比如if和while語句。

一組向量寄存器可以存放一個或多個整數或浮點數值。

（2）在硬體中，所有的數據都存儲在內存中。內存是一個從0開始的位元組序列。CPU執行的機器代碼在內存位置上運行，僅由它們的地址標識。編譯器負責將我們的程序在變數上執行的操作轉換為在地址上執行的操作，但無論是變數名稱還是變數的類型都不存在於此轉化中。

在大多數情況下，程序員不關心處理變數的地址。

&運算符返回存儲變數或表達式的地址。而*操作符做相反的操作，它返回存儲在它的地址中的值。這就引出了一個棘手的問題：C程序員可以使兩個變數名指向內存中相同的位置，而硬體無法區分。上述問題在源代碼中表現並不明顯。

（3）

這幅圖我們在unit1中已經見過了，現在詳細解釋一下：

從低地址向上：

程序代碼和數據：對所有的進程來說，代碼是從一個固定的地址開始的，緊接著是和C全局變數對應的數據位置。代碼和數據區是直接按照可執行目標文件的內容初始化的。

堆。代碼和數據區後緊隨著的是運行時堆。代碼和數據區在進程一開始運行時就被指定了大小，與此不同，調用像malloc和free這樣的C標準庫函數時，堆可以在運行時動態地擴展和收縮。

共享庫。大約在地址空間的中間部分是一塊用來存放像C標準庫和數學庫這樣的共享庫的代碼和數據的區域。

棧。位於用戶虛擬地址空間頂部的是用戶棧，編譯器用它來實現函數調用。和堆一樣，用戶棧在程序執行期間可以動態地擴展和收縮。調用函數時棧增長，從一個函數返回時棧收縮。

內核虛擬內存。地址空間頂部是為內核保留的。不允許應用程序讀寫這個區域的內容或者直接調用內核代碼定義的函數。

地址分為三組：所有局部變數都聚集在一起。在全局變數中，聲明時初始化的變數在一個集群中，而未初始化的則在另一個集群中。

我們看到所有的數據都有一個地址，而地址只是一個整數。由於內存能夠存儲整數，我們不僅可以將數據存儲在內存中，還可以將數據地址存儲在內存中。在後一種情況下，我們存儲地址的位置本身就有一個地址。C允許我們給出這些存儲地址名稱的位置，也就是說，C允許我們聲明保存數據地址的變數，而不是直接保存數據。您可能已經熟悉這種變數類型：它們通常稱為指針或引用。

可執行程序包括BSS段、數據段、代碼段（也稱文本段）。

BSS（Block Started by Symbol）通常是指用來存放程序中未初始化的全局變數和靜態變數的一塊內存區域。特點是:可讀寫的，在程序執行之前BSS段會自動清0。所以，未初始的全局變數在程序執行之前已經成0了。

注意和數據段的區別，BSS段存放的是未初始化的全局變數和靜態變數，數據段存放的是初始化後的全局變數和靜態變數。

3.數組和指針

（1）帶下標的數組和指針引用之間的等效性：

下面表格中每一行的兩者都是等效的。

（2）需要注意的是，雖然一個數組可以用指針引用來進行操作，但是我們也不能認為任何一個指針也可以被想像成為數組，觀察下面這個例子。

#include <stdio.h>void Initialize (char * a, char * b){ a[0] = T; a[1] = h; a[2] = i; a[3] = s; a[4] = ; a[5] = i; a[6] = s; a[7] = ; a[8] = A; a[9] = ; b = a; b[8] = B;}#define ARRAY_SIZE 10char a[ARRAY_SIZE];char b[ARRAY_SIZE];int main(int argc, char * argv[]){ Initialize(a, b); printf("%s
%s
", a, b); return 0;}

輸出結果

This is B

我們在前一行中指定了b=a。然而，與數組中的內容不一樣的是，兩個數組在賦值b=a之後具有相同的地址。修改一個也會修改另一個。賦值B（8）=「B」將修改包含「8」的內存位，並且原始B的內容將保持不變。這兩個原始數組仍然被列印，但第一個數組現在包含「This is b」，而第二個數組將是空的，因為它從未被觸摸過（根據英文直譯，意思到即可）。

這個例子說明了我們說「C語言沒有真正的數組」這句話的含義。具有真正數組支持的語言會把b = a這行代碼解釋為把a的內容複製給b，就像a和b是整數一樣（而不是把a的地址分配給b）。

真正的數組支持將使編譯器生成目標代碼，將數組A的內容複製到數組B中。生成的目標代碼將執行下面C代碼中所示的操作。它需要創建一個循環，一個接一個地將每個字元的內容從數組A複製到數組B：

void Initialize (char * a, char * b){ int i; a[0] = T; a[1] = h; a[2] = i; a[3] = s; a[4] = ; a[5] = i; a[6] = s; a[7] = ; a[8] = A; a[9] = ; for (i = 0; i < ARRAY_SIZE; i++) { b[i] = a[i]; } b[8] = B;}

（3）值傳遞和引用傳遞

值傳遞的例子：

#include <stdio.h>int first;int second;void callee (int first){ int second; second = 1; first = 2; printf("callee: first = %d second = %d
", first, second);}int main (int argc, char *argv[]){ first = 1; second = 2; callee(first); printf("caller: first = %d second = %d
", first, second); return 0;}

輸出結果：

callee:first=2 second=1

caller:first=1 second=2

在callee中的first是形參，在值傳遞的情況下也被當做局部變數進行處理（可以看到它和局部變數second的地址非常接近）

函數的參數也可以通過引用傳遞。在這種情況下，編譯器不會為正式參數分配一個新地址，而是使用調用者指定的參數的地址。這樣，一個分配的形式參數在函數（調用者）中最終會改變調用方傳遞的變數的值。

引用傳遞的例子：

#include <stdio.h>int first;int second;void callee (int * first){ int second; second = 1; *first = 2; printf("callee: first = %d second = %d
", *first, second);}int main (int argc, char *argv[]){ first = 1; second = 2; callee(&first); printf("caller: first = %d second = %d
", first, second); return 0;}

在這裡傳遞了地址，first不再被當做是局部變數來處理，此處的first不是形參，而是用指針的操作傳遞地址。

輸出結果：

callee:first=2 second=1

caller:first=2 second=2

（4）遞歸：

編譯器如何決定在何處分配變數？

為什麼局部變數和全局變數分配在不同的地方？

當我們檢查函數的遞歸調用時，運行如下代碼：

#include <stdio.h>#include <stdlib.h>void callee (int n){ if (n == 0) return; printf("%d (0x%08x)
", n, &n); callee (n - 1); printf("%d (0x%08x)
", n, &n);}int main (int argc, char * argv[]){ int n; if (argc < 2){ printf("USAGE: %s <integer>
", argv[0]); return 1; } n = atoi(argv[1]); callee(n); return 0;}

輸出結果：

10 (0x0065fda4)

9 (0x0065fd4c)

8 (0x0065fcf4)

7 (0x0065fc9c)

6 (0x0065fc44)

5 (0x0065fbec)

4 (0x0065fb94)

3 (0x0065fb3c)

2 (0x0065fae4)

1 (0x0065fa8c)

1 (0x0065fa8c)

2 (0x0065fae4)

3 (0x0065fb3c)

4 (0x0065fb94)

5 (0x0065fbec)

6 (0x0065fc44)

7 (0x0065fc9c)

8 (0x0065fcf4)

9 (0x0065fd4c)

10 (0x0065fda4)

這表明編譯器為每一個對callee的調用分配一個地址，但是編譯器是如何知道它必須分配10個n的實例呢？編譯器將為每一個函數調用和每個函數返回添加額外的代碼。這段代碼分配任何調用者所需要調用的局部變數。

全局變數可以靜態分配。這意味著編譯器可以在程序執行之前修復全局變數的特定地址。但是，由於函數可以遞歸調用，並且每個遞歸調用都需要自己實例化局部變數，編譯器必須動態地分配局部變數。這樣的動態行為會使程序運行得更慢，因此不可取。但對於局部變數是必要的。因為編譯器不知道需要動態分配多少變數，所以它保留了大量的擴展空間。這就是為什麼本地變數被分配到遠離全局變數的地址的地址。

（5）

extern char a[]與extern char a[100]都提示a是一個數組，也就是一個內存地址，數組內的字元可以從這個地址找到。編譯器並不需要知道數組總共有多長，因為它只需要產生偏離起始地址的偏移地址。從數組中提取一個字元只要簡單地從符號表顯示的a的地址加上下標，需要的字元就位於這個地址中。

相反，如果聲明extern char *p，它將告訴編譯器p是一個指針（四位元組的對象），它指向的對象是一個字元。為了取得這個字元，必須得到地址p的內容，把它作為字元的地址並從地址中取得這個字元。指針的訪問要靈活得多，但需要一次額外的提取。

在上面的mango中，如果把mango聲明為指針，那麼不管p原先是定義為指針還是數組，編譯器都會按照以下三步進行操作：1.取得符號表中mango的地址，提取存儲於此處的指針。2.把下標所表示的偏移量與指針的值相加，產生一個地址。3.訪問地址，取得字元。

但只有當p原來定義為指針時這個方法才是正確的。所以extern int*mango;在這裡用mango[i]這種形式提取聲明的內容時實際上得到的是一個字元，但是按照上面的三步編譯器把它當成指針，把ASCII字元解釋為地址顯然是錯的。

所以我們需要換一種方式去表達，如下的兩種方式都是可取的。

方式一：

File1:int mango[100];

File2:extern int mango[];

方式二：

File1:int *mango;

File2:extern int*mango;

（6）可修改的左值：

在

X=Y;

這行代碼的上下文環境里，X的含義是X所代表的地址，這被稱為左值。左值在編譯時可知，左值表示存儲結果的地方。Y的含義是Y所代表的地址的內容，這被稱為右值。右值直到運行時才知。

C語言引入了「可修改的左值」這個術語。它表示左值允許出現在賦值語句的左邊。這個奇怪的術語是為與數組名區分，數組名也用於確定對象在內存中的位置，也是左值，但它不能作為賦值的對象。因此，數組名是個左值但不是可修改的左值。標準規定賦值符必須用可修改的左值作為它左邊一側的操作數。用通俗的話說，只能給可以修改的東西賦值。

4.活動記錄和堆棧

（1）活動記錄Activation Records：過程的一次執行所需要的信息用一塊連續的存儲區來管理，這塊存儲區叫做活動記錄，是內存中的一個區域，在這個區域中包含了一個函數中所有參數，局部變數，臨時變數，返回地址等信息。

函數調用的活動記錄是在調用函數時創建的，當函數返回時就會被銷毀。活動記錄被組織在一個堆棧中。由於這個原因，它們通常也稱為棧幀(stack frame)。main函數的活動記錄在棧的底部，作為一個函數去調用另一個。被調用的活動記錄被推向調用者的上面。只有堆棧頂部（TOS,top of stack）的活動記錄可以被訪問。這是因為： 函數在其所有活動子程序返回之前都不會返回，也就是說，我們永遠不需要刪除一個不在堆棧頂部的活動記錄。

作用域的規則意味著一個函數無法訪問它的母變數的局部變數——也就是說，我們從來都不需要訪問一個來自不在棧頂的活動記錄的數據。

實際上，大多數計算機從更高的地址到更低的地址來分配活動記錄堆棧（通常直接稱為堆棧），即堆棧向下增長。

（2）在執行過程中的任何時刻，編譯器和硬體內部都維護兩個重要的值，這些值用於以簡單而優雅的方式分隔和操縱活動記錄：

棧指針(stack pointer)保存堆棧結束的地址，這裡將會分配一個新的活動記錄。

幀指針(frame pointer)保存之前的活動記錄結束的地址，這個值是噹噹前的函數返回時棧指針將會返回的地址。

當函數被調用時，編譯器和硬體會做的事情：

將幀指針壓入堆棧。

將幀指針設置為指向棧指針所指向的地方。

按照被調用函數所需要存儲局部狀態的內存大小來遞減棧指針指向的地址。

如下圖：

當函數返回時，編譯器和硬體會做的事情：

將棧指針設置為指向幀指針所指向的地方。

從堆棧中彈出舊的的幀指針的值。

接下來，我們將根據（3）中的問題完善這些步驟，完整版的步驟在（4）中。

（3）問題：在程序執行的每一步中，是什麼決定了是哪個數據項或者哪個CPU指令將要被取出？

回答：CPU保存著一個特殊的值，被叫做程序計數器(PC，program counter)，其中包含了將要執行的指令的地址（比如堆棧指針和幀指針）。

一個讀取-解碼-執行的周期包括： 從程序計數器中包含的地址中獲取內存，解讀操作碼代表的信息，獲取操作數，執行指令，並存儲結果。

問題：為了能在被調用者返回的時候老的程序計數器恢復，老的程序計數器應該被存儲在哪裡？

回答：堆棧中的每一個活動記錄都包含著一個幀指針的副本。幀指針被存儲在堆棧中，以便為每個函數返回還原不同的值，每個函數調用需要返回到調用它的地址。

（4）完整版本（加入了（3）中的PC和幀指針的副本之後，對（2）的一個補充）：

當進行一個函數調用的時候，編譯器：

①將返回地址（當前程序計數器）壓入堆棧中。

②將幀指針壓入堆棧中。

③將幀指針設置為指向棧指針所指向的地方。

④按照被調用函數所需要存儲局部狀態的內存大小來遞減棧指針指向的地址

函數返回時，編譯器：

①將棧指針設置為指向幀指針所指向的地方。

②從堆棧中彈出舊的的幀指針的值

③從堆棧中彈出返回地址的值

④跳回返回地址

注意：幀指針裡面存的是上一個棧幀（調用者）的幀指針的值。

我們將會在unit4中對堆棧、棧幀和函數調用過程有更深入的學習和認識。

unit4——堆棧、堆和動態內存分配

1.靜態聲明（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() { volatileint b; b=3; if(setjmp(buf)!=0) { printf("%d ", b); exit(0); } b=5; longjmp(buf , 1);} //請問輸出是？

這個代碼里的運行步驟：

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=0;void second(int*k){ printf(「second times=%dn」,++(*k)); longjmp(buf,65536);}void first(int*k){ prinf(「first times=%dn」,++(*k)); second(k);}int main(void){ int ret=setjmp(buf); if(ret==0){ printf(「1.ret is %dn」,ret); first(&times); }else{ printf(「2.ret is %dn」,ret); }}

運行結果：

1.ret is 0

first times=1

second times=2

2.ret is 65536

2.堆棧

（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

堆上的內存總是用指針表示和訪問。

常見的內存錯誤：

忘記釋放內存

內存泄漏

懸掛指針問題

3.動態內存分配

（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堆分為新生代和老年代，這樣就可以根據各個年代的特點採用最適當的收集演算法。

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

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

int sum(int a[], int n){ int *p; int sum = 0; for (int i = 0; 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 100int *a = (int *) malloc(sizeof(int *) * array_size);for (int i = 0; i <= array_size; i++) a[i] = NULL;

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

（4）超出所分配的內存

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

分配太少的內存會導致之後的賦值覆蓋掉之前的內存。

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

（5）忘記給分配空間

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

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個字元，但只分配了16，所以寫操作會超出所分配的內存（要知道strcat函數並不會為結果分配額外的內存）

（6）在運行時堆棧上構建指針並將指針返回給調用方

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

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

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

// decrement a if a is greater than zero:void dec_positive(int *a){ *a--; // decrement the integer if (*a < 0) *a = 0; // 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) + 100); 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被分配了卻沒有被釋放。

推薦閱讀：