行程中的記憶體配置方法

在行程執行的過程中,經常會需要取得某些記憶空間,以便儲存電腦運算過程中所產生的資料。程式中的資料通常被放在兩個記憶體區塊中,一個稱為堆疊區 (Stack),一個稱為堆積區 (Heap)。

在 9.4 節當中,我們曾經看過編譯器使用堆疊的方法。副程式參數、區域變數與返回點等資訊會被推入堆疊中,然後利用框架暫存器 (Frame Pointer) 進行變數的存取。在這個過程當中,記憶體的配置並不困難,當需要記憶體時,使用的一定是堆疊最上層的區域,編譯器只要根據變數的型態與數量,決定配置空間的大小即可。

堆積區的記憶體使用方法就較為複雜了。在 C 語言當中,malloc() 函數是主要的記憶體請求指令,這種指令通常被稱為動態記憶體 (Dynamic Allocation) 配置請求,因為 malloc() 函數會在執行的過程當中,動態的取得足夠的記憶體空間,以便分配給程式使用。

在程式剛開始執行的時候,載入器會將程式段 (.text) 與資料段 (.data) 載入,接著分配空間給位初始化資料 BSS段,然後將剩下的空間分配給堆疊段 (Stack) 與堆積段 (Heap) 共用。堆疊段與堆積段的成長方向是相反的,假如堆積由上往下成長,堆疊段的成長方向就會是由下往上。堆疊與堆積兩段共用同一塊記憶體空間。但是起始點與成長方向完全相反。如圖 10.6圖 10.6 (a) 所示。

MemoryAllocation.jpg

圖 10.6行程的記憶體分配圖

在記憶體不斷被分配與釋放的過程當中,記憶空間會逐漸變得凌亂,已配置的空間與未配置的空間交錯出現,形成一格一格的空洞。圖 10.6圖 10.6 (b) 顯示了此種凌亂的情況,此時記憶體中會有很多漏洞。

當程式利用像 malloc() 這樣的函數請求記憶體配置時,如果已經釋放的區塊中可以找到足夠大的區塊,就可以從該區塊中分配記憶體給程式使用,如果無法找到足夠大的『洞』,就必須讓堆積段繼續成長,以便分配記憶體給程式。

當堆積區塊不斷成長的過程中,可能會與堆疊區重疊,而導致相互破壞的情況。這對程式設計人員而言是一種很難處理的錯誤,最好能設計其錯誤處理機制以防止此種情況。

C 語言的程式設計師必須在使用完 malloc() 所分配的記憶體後,盡快的利用 free() 函數以歸還記憶體給堆積區,這樣才能避免堆疊溢出 (或堆積溢出) 的情況,讓程式能在堆積尚未滿出之前完成。但是如果所有堆積空間都滿了,而且沒有任何的『記憶體空洞』可以滿足記憶體分配的請求時,C語言程式仍然會被迫停止,或者進入不可預知的錯誤狀況。

當記憶體被歸還時 (例如使用 free() 函數),記憶體管理系統可以將該歸還記憶體與緊鄰的上下方空洞合併,以便變形成更大的可用區塊,這將有助於增加記憶體使用率,避免形成太多的小區塊,導致分配演算法的失敗情況。

記憶體分配策略

在再分配記憶體時,必須找出足夠大的可用區塊,以便分配給程式。通常記憶體管理系統會利用連結串列 (Linked List) 結構記載各個可用區塊的大小,然後遵循特定的配置策略,以尋找足夠大的可用區塊。一個好的記憶體分配策略,應該能有效的管理這些記憶體空洞,能夠快速的分配記憶體,並且延後錯誤的發生時間。在有新的記憶體需求出現時,記憶體分配系統必須決定要將哪一段記憶空間分配給程式,這就是記憶體管理當中頗具關鍵地位的記憶體分配問題。常見的記憶體分配策略有最先符合法 (First-Fit)、最佳符合法 (Best-Fit) 、最差符合法 (Worst-Fit) 與下一個符合法 (Next-Fit) 等等。

1. First Fit (最先符合法):從串列開頭開始尋找,然後將所找到的第一個足夠大的區塊分配給該程式。
2. Next-Fit (下一個符合法):使用環狀串列的結構,每次都從上一次搜尋停止的點開始搜尋,然後將所找到的第一個足夠大的區塊分配給該程式。
3. Best-Fit (最佳符合法):從頭到尾搜尋整個串列一遍,然後將大小最接近的可用區塊分配給該程式。
4. Worst-Fit (最差符合法):則是將大小最大的區塊分配給程式 (以便留下較大的洞)。

研究顯示 First-Fit 的記憶體使用率比 Next-Fit 、Best-Fit 好,而 Worst-Fit 是四種當中最差的。但是仍然有一些更複雜的配置策略,能得到更快且更好的記憶體使用率,以上所列只是記憶體分配策略中最簡單的四種而已。

堆積空間不足時的處理方式

假如無法從堆積區找到足夠大可用的區塊時,就會產生記憶空間不足的情況,此時系統可以已直接回報錯誤,或者試圖處理記憶體不足的狀況。

有兩種方法可以處理記憶體不足的狀況,一種稱為記憶體聚集法,另一種稱為垃圾蒐集法。

記憶體聚集法乃是將記憶體重新搬動,以便將分散的小型可用區塊聚集為大型可用區塊,然後再試圖分配給使用程式的方法。但是記憶體聚集巨集所附出的代價非常的高,需要大量的時間搬移記憶體,因此在現代的系統中很少被使用到。

垃圾蒐集法 (Garbge Collection Algorithm) 則是利用程式自動回收記憶體。在使用垃圾收集法的程式中,通常不需要由程式主動釋放記憶體,因為垃圾蒐集系統會在記憶體不足時被啟動,以蒐集記憶體中已經沒有被任何程式變數指到的記憶區塊,然後再將這些區塊標示為可用區塊,以便回收使用。

C語言當中通常沒有支援垃圾蒐集演算法,但是在Java, C# 等語言中則內建了垃圾蒐集機制,該機制會在發現記憶體不足的情況時,自動回收記憶體。因此 Java 與 C# 的程式設計人員通常不需要釋放記憶體,這對程式設計人員而言是很好用的一項功能,可以減輕不少負擔。

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License