基本介紹
- 中文名：存儲分配
- 外文名：Storage allocation
- 策略：靜態存儲分配、棧和堆式存儲分配
- 靜態存儲分配：編譯期間為數據對象分配存儲空間
- 算法：最佳、最先、循環最先適應算法
- 套用學科：編譯原理、程式設計
定義,靜態存儲分配,現狀,常見做法,優點,缺點,棧式存儲分配,特點,活動記錄,必要條件,堆式存儲管理,兩種方式,3種方案的利弊,常見存儲分配算法,最佳適應算法,最先適應算法,循環最先適應算法,
定義
編譯程式的整個編譯過程大體分成五部分：詞法分析、語法分析、代碼最佳化、存儲分配和代碼生成。在代碼生成之前還必須先確定程式、變數以及常數在記憶體中存放的地址，這些工作，統稱為存儲分配，也就是把程式或數據塊分配到指定的存儲單元的過程。
數據區可以分為靜態數據區（全局數據區）和動態數據區，後者又可分為堆區和棧區。之所以這樣劃分，是因為它們存放的數據和對應的管理方法不同。靜態數據區、棧區和堆區的存儲空間分別遵循3種不同的規則：靜態存儲分配、棧式存儲分配和堆式存儲分配。後兩種分配方式皆稱為“動態存儲分配”，因為這兩種方式中存儲空間並不是在編譯的時候靜態分配好的，而是在運行時才進行的。
某些程式語言，如早期的FORTRAN語言及COBOL語言等，其存儲分配是完全靜態的，程式的數據對象與其存儲的綁定是在編譯期間進行的，稱為靜態語言。而對於另一些語言，所有數據對象與其存儲的綁定只能發生在運行期間，此類語言稱為動態語言，如Lisp、ML、Perl等。多數語言（如C/C++、Java、Pascal等）採取的存儲分配策略是介於二者之間的。
靜態存儲分配
所謂的靜態存儲分配，即在編譯期間為數據對象分配存儲空間。這要求在編譯期間就可以確定數據對象的大小，同時還可以確定數據對象的數目。
現狀
多數（現代）語言只實施部分靜態存儲分配。可靜態分配的數據對象包括大小固定且在程式執行期間可全稱訪問的全局變數、靜態變數、程式中的常量以及class的虛函式表等，如C語言中的static和extern變數，以及C++中的static變數，這些數據對象的存儲將被分配在靜態數據區。
常見做法
從道理上講，或許可以將靜態數據對象與某個絕對存儲地址綁定，然而，通常的做法是將靜態數據對象的存取地址對應到偶對（DataArerStart，Offset）。Offset是在編譯時刻確定的固定偏移量，而DataArerStart則可以推遲到連結或運行時刻才確定。有時，DataArerStart的地址也可以裝入某個基地址暫存器Register，此時數據對象的存取地址對應到偶對（DataArerStart，Offset），即所謂的暫存器偏址定址方式。
優點
採用這種方式，存儲分配極其簡單。
缺點
（1）採用這種方式會帶來存儲空間的浪費。為解決存儲空間浪費問題，人們設計了變數的重疊布局機制，如FORTRAN語言的equivalence語句。重疊布局帶來的問題是使得程式難寫難讀。
（2）完全靜態分配的語言還有另外一個缺陷，就是無法支持遞歸過程或函式。
（3）對於一些動態的數據結構，例如動態數據（C++中使用new關鍵字來分配記憶體）以及遞歸函式的局部變數等最終空間大小必須在運行時才能確定的場合，靜態存儲分配就無能為力了。
棧式存儲分配
棧區是作為“棧”這樣的一種數據結構來使用的動態存儲區，稱為運行棧。運行棧數據空間的存儲和管理方式稱為棧式存儲分配，它將數據對象的運行時存儲按照棧的方式來管理，常用於實現可動態嵌套的程式結構，如過程、函式以及嵌套程式塊（分程式）等。
特點
與靜態存儲分配方式不同，棧式存儲分配是動態的，也就是說必須是在運行的時候才能確定數據對象的存儲分配結果。例如，對如下的C代碼片段：
int factorial (int n)
{
int tmp;
if (n<=1)
return 1;
else
{
temp=n-1;
tmp=n*factorial(tmp);
return tmp;
}
}
隨著n的不同，這段代碼運行時所需要的總記憶體空間大小是不同的，而且每次遞歸的時候tmp對應的記憶體單元都不同。
活動記錄
在過程/函式的實現中，參與棧式存儲分配的存儲單位擬是活動記錄，運行時每當進入一個過程/函式，就在棧頂為該過程/函式分配存放活動記錄的數據空間。當一個過程/函式工作完畢返回時，它在棧頂的活動記錄數據空間也隨機釋放。
在過程/函式的某一次執行中，其活動記錄中會存放生存期在該過程/函式本次執行中的數據對象以及必要的控制信息單元。一般來說，運行棧中的數據通常都是屬於某個過程/函式的活動記錄。
必要條件
在編譯期間，過程、函式以及嵌套程式塊的活動記錄大小（最大值）應該是可以確定的（以便進入的時候動態地分配活動記錄的空間），這是進行棧式存儲分配的必要條件，如果不滿足則應該使用堆式存儲管理。
堆式存儲管理
當數據對象的生存期與創建它的過程/函式的執行期無關時，例如，某些數據對象可能在該過程/函式結束之後仍然長期存在，就不適合進行棧式存儲分配。一種靈活但是較昂貴的存儲分配方式是堆式存儲分配。在堆式存儲分配中，可以在任意時刻以任意次序從數據段的堆區分配和釋放數據對象的運行時存儲空間。通常，分配和釋放數據對象的操作是應用程式通過向作業系統提出申請來實現的，因此要占用相當的時間。
兩種方式
堆式存儲空間的分配和釋放可以是顯式的，也可以是隱式的。
（1）顯式的是指由程式設計師來負責應用程式的（堆）存儲空間管理，可藉助編譯器和運行時系統所提供的默認存儲管理機制。
（2）隱式的是指（堆）存儲空間的分配或釋放不需要程式設計師負責，而是由編譯器和運行時系統自動完成。
某些語言有顯式的存儲空間分配和釋放命令，如Pascal中的new/deposit，C++中的new/delete。在C語言中沒有顯式的存儲空間分配和釋放語句，但程式設計師可以使用標準庫中的函式malloc()和free()來實現顯式的分配和釋放。
某些語言支持隱士的堆區存儲空間釋放，這需要藉助垃圾資源回收筒機制。例如，Java程式設計師不需要考慮對象的析構，堆區存儲空間的釋放是由垃圾回收程式自動完成的。
3種方案的利弊
對於堆區存儲空間的釋放，下面簡單討論一下不釋放、顯式釋放以及隱式釋放3種方案的利弊。
（1）不釋放堆區存儲空間的方法。這種方法只分配空間，不釋放空間，待空間耗盡時停止。如果多數堆數據對象為一旦分配後永久使用，或者在虛存很大而無用數據對象不致帶來大零亂的情形下，那么這種方案有可能是合適的。這種方案的存儲管理機制很簡單，開銷很小，但套用面很窄，不是一種通用的解決方案。
（2）顯式釋放堆區存儲空間的方法。這種方法是由用戶通過執行釋放命令來清空無用的數據空間，存儲管理機制比較簡單，開銷較小，堆管理程式只維護可提供分配命令使用的空閒空間。然而，這種方案的問題是對程式設計師要求過高，程式的邏輯錯誤有可能導致災難性的後果，例如指針懸掛問題。
（3）隱式釋放堆區存儲空間的方法。該方法的優點是程式設計師不必考慮存儲空間的釋放，不會發生指針懸掛之類的問題，但缺點是對存儲管理機制要去較高，需要堆區存儲空間管理程式具備垃圾回收的能力。
常見存儲分配算法
由於在堆式存儲分配中可以在任意時刻以任意次序分配和釋放數據對象的存儲空間，因此程式運行一段時間之後，堆區存儲空間可能被劃分成許多塊，有些被占用，有些空閒。對於堆區存儲空間的管理，通常需要好的存儲分配算法，使得在面對多個可用的空閒存儲塊時，根據某些最佳化原則選擇最合適的一個分配給當前數據對象。以下是幾類常見的存儲分配算法：
最佳適應算法
最佳適應算法，即選擇空間浪費最少的存儲塊。
最先適應算法
最先適應算法，即選擇最先找到的足夠大的存儲塊。
循環最先適應算法
循環最先適應算法，，即起始點不同的最先適應算法。
另外，由於每次分配後一般不會用盡空閒存儲塊的全部空間，而這些剩餘的空間又不適於分配給其他數據對象，因而在程式運行一段時間之後，堆區存儲空間可能出現許多“碎片”。這樣，堆區存儲空間的管理中通常需要用到碎片整理算法，用於壓縮合併小的存儲塊，使其更可用。
