存儲分配

編譯程序的整個編譯過程大體分成五部分：詞法分析、語法分析、代碼優化、存儲分配和代碼生成。在代碼生成之前還必須先確定程序、變量以及常數在內存中存放的地址，這些工作，統稱為存儲分配，也就是把程序或數據塊分配到指定的存儲單元的過程。 ^[1] 

數據區可以分為靜態數據區（全局數據區）和動態數據區，後者又可分為堆區和棧區。之所以這樣劃分，是因為它們存放的數據和對應的管理方法不同。靜態數據區、棧區和堆區的存儲空間分別遵循3種不同的規則：靜態存儲分配、棧式存儲分配和堆式存儲分配。後兩種分配方式皆稱為“動態存儲分配”，因為這兩種方式中存儲空間並不是在編譯的時候靜態分配好的，而是在運行時才進行的。 ^[2] 

某些編程語言，如早期的FORTRAN語言及COBOL語言等，其存儲分配是完全靜態的，程序的數據對象與其存儲的綁定是在編譯期間進行的，稱為靜態語言。而對於另一些語言，所有數據對象與其存儲的綁定只能發生在運行期間，此類語言稱為動態語言，如Lisp、ML、Perl等。多數語言（如C/C++、Java、Pascal等）採取的存儲分配策略是介於二者之間的。 ^[2] 

所謂的靜態存儲分配，即在編譯期間為數據對象分配存儲空間。這要求在編譯期間就可以確定數據對象的大小，同時還可以確定數據對象的數目。 ^[2] 

多數（現代）語言只實施部分靜態存儲分配。可靜態分配的數據對象包括大小固定且在程序執行期間可全稱訪問的全局變量、靜態變量、程序中的常量以及class的虛函數表等，如C語言中的static和extern變量，以及C++中的static變量，這些數據對象的存儲將被分配在靜態數據區。 ^[2] 

從道理上講，或許可以將靜態數據對象與某個絕對存儲地址綁定，然而，通常的做法是將靜態數據對象的存取地址對應到偶對（DataArerStart，Offset）。Offset是在編譯時刻確定的固定偏移量，而DataArerStart則可以推遲到鏈接或運行時刻才確定。有時，DataArerStart的地址也可以裝入某個基地址寄存器Register，此時數據對象的存取地址對應到偶對（DataArerStart，Offset），即所謂的寄存器偏址尋址方式。 ^[2] 

採用這種方式，存儲分配極其簡單。

（1）採用這種方式會帶來存儲空間的浪費。為解決存儲空間浪費問題，人們設計了變量的重疊佈局機制，如FORTRAN語言的equivalence語句。重疊佈局帶來的問題是使得程序難寫難讀。

（2）完全靜態分配的語言還有另外一個缺陷，就是無法支持遞歸過程或函數。

（3）對於一些動態的數據結構，例如動態數據（C++中使用new關鍵字來分配內存）以及遞歸函數的局部變量等最終空間大小必須在運行時才能確定的場合，靜態存儲分配就無能為力了。 ^[2] 

棧區是作為“棧”這樣的一種數據結構來使用的動態存儲區，稱為運行棧。運行棧數據空間的存儲和管理方式稱為棧式存儲分配，它將數據對象的運行時存儲按照棧的方式來管理，常用於實現可動態嵌套的程序結構，如過程、函數以及嵌套程序塊（分程序）等。 ^[2] 

與靜態存儲分配方式不同，棧式存儲分配是動態的，也就是説必須是在運行的時候才能確定數據對象的存儲分配結果。例如，對如下的C代碼片段：

int factorial (int n)

{

int tmp;

if (n<=1)

return 1;

else

{

temp=n-1;

tmp=n*factorial(tmp);

return tmp;

}

}

隨着n的不同，這段代碼運行時所需要的總內存空間大小是不同的，而且每次遞歸的時候tmp對應的內存單元都不同。 ^[2] 

在過程/函數的實現中，參與棧式存儲分配的存儲單位擬是活動記錄，運行時每當進入一個過程/函數，就在棧頂為該過程/函數分配存放活動記錄的數據空間。當一個過程/函數工作完畢返回時，它在棧頂的活動記錄數據空間也隨機釋放。

在過程/函數的某一次執行中，其活動記錄中會存放生存期在該過程/函數本次執行中的數據對象以及必要的控制信息單元。一般來説，運行棧中的數據通常都是屬於某個過程/函數的活動記錄。 ^[2] 

在編譯期間，過程、函數以及嵌套程序塊的活動記錄大小（最大值）應該是可以確定的（以便進入的時候動態地分配活動記錄的空間），這是進行棧式存儲分配的必要條件，如果不滿足則應該使用堆式存儲管理。 ^[2] 

當數據對象的生存期與創建它的過程/函數的執行期無關時，例如，某些數據對象可能在該過程/函數結束之後仍然長期存在，就不適合進行棧式存儲分配。一種靈活但是較昂貴的存儲分配方式是堆式存儲分配。在堆式存儲分配中，可以在任意時刻以任意次序從數據段的堆區分配和釋放數據對象的運行時存儲空間。通常，分配和釋放數據對象的操作是應用程序通過向操作系統提出申請來實現的，因此要佔用相當的時間。 ^[2] 

堆式存儲空間的分配和釋放可以是顯式的，也可以是隱式的。

（1）顯式的是指由程序員來負責應用程序的（堆）存儲空間管理，可藉助編譯器和運行時系統所提供的默認存儲管理機制。

（2）隱式的是指（堆）存儲空間的分配或釋放不需要程序員負責，而是由編譯器和運行時系統自動完成。

某些語言有顯式的存儲空間分配和釋放命令，如Pascal中的new/deposit，C++中的new/delete。在C語言中沒有顯式的存儲空間分配和釋放語句，但程序員可以使用標準庫中的函數malloc()和free()來實現顯式的分配和釋放。

某些語言支持隱式的堆區士的堆區存儲空間釋放，這需要藉助垃圾回收站機制。例如，Java程序員不需要考慮對象的析構，堆區存儲空間的釋放是由垃圾回收程序自動完成的。 ^[2] 

對於堆區存儲空間的釋放，下面簡單討論一下不釋放、顯式釋放以及隱式釋放3種方案的利弊。

（1）不釋放堆區存儲空間的方法。這種方法只分配空間，不釋放空間，待空間耗盡時停止。如果多數堆數據對象為一旦分配後永久使用，或者在虛存很大而無用數據對象不致帶來大零亂的情形下，那麼這種方案有可能是合適的。這種方案的存儲管理機制很簡單，開銷很小，但應用面很窄，不是一種通用的解決方案。

（2）顯式釋放堆區存儲空間的方法。這種方法是由用户通過執行釋放命令來清空無用的數據空間，存儲管理機制比較簡單，開銷較小，堆管理程序只維護可提供分配命令使用的空閒空間。然而，這種方案的問題是對程序員要求過高，程序的邏輯錯誤有可能導致災難性的後果，例如指針懸掛問題。

（3）隱式釋放堆區存儲空間的方法。該方法的優點是程序員不必考慮存儲空間的釋放，不會發生指針懸掛之類的問題，但缺點是對存儲管理機制要去較高，需要堆區存儲空間管理程序具備垃圾回收的能力。 ^[2] 

由於在堆式存儲分配中可以在任意時刻以任意次序分配和釋放數據對象的存儲空間，因此程序運行一段時間之後，堆區存儲空間可能被劃分成許多塊，有些被佔用，有些空閒。對於堆區存儲空間的管理，通常需要好的存儲分配算法，使得在面對多個可用的空閒存儲塊時，根據某些優化原則選擇最合適的一個分配給當前數據對象。以下是幾類常見的存儲分配算法：

最佳適應算法，即選擇空間浪費最少的存儲塊。 ^[2] 

最先適應算法，即選擇最先找到的足夠大的存儲塊。 ^[2] 

循環最先適應算法，，即起始點不同的最先適應算法。 ^[2] 

另外，由於每次分配後一般不會用盡空閒存儲塊的全部空間，而這些剩餘的空間又不適於分配給其他數據對象，因而在程序運行一段時間之後，堆區存儲空間可能出現許多“碎片”。這樣，堆區存儲空間的管理中通常需要用到碎片整理算法，用於壓縮合並小的存儲塊，使其更可用。 ^[2]