編譯原理及編譯程序構造(第2版)（簡體書）

《普通高校計算機專業精品教材系列:編譯原理及編譯程序構造(第2版)》可作為高等院校計算機專業的本科生或專科教材，也可作為碩士生入學考試及計算機軟件技術人員的參考書。

這種技術除了可以減少搜索時間外，還有一個優點是把兩小塊合并為較大塊比較容易實現。其缺點是會使內部碎片增加，因為分配的塊可能大于所申請的長度。另外，外部碎片也可能增加。因為，雖然兩塊是毗鄰的，但由于它們不是雙胞塊，所以不能合并。盡管這樣，這種技術還是比前兩種技術更為有效。
8.3.2堆空間的釋放與無用單元收集
1）堆空間的釋放
在程序設計語言中有堆空間的釋放語句，像Pascal中的dispose（P），PL/1中的free等語句都是釋放語句。這些語句是將指針變量P所指的存儲塊退回到可利用表中。最簡單的處理辦法是將釋放塊作為新塊插入到可利用表的鏈首位置。但這種回收策略有個缺點，就是在程序運行一段時間后，可利用表中將含有大量小塊，分配程序的搜索時間將變得過分冗長，而且有不能滿足用戶申請要求的危險。一種較好的解決辦法是將兩個連續的小塊合并成一大塊。對新釋放的塊，按存儲地址大小在可利用表中檢查是否有與它是相鄰關系的塊，若有就將它們合并成一大塊，否則僅按地址大小插入到適當位置。為實現此操作，可利用表必須按塊的地址順序組織，以便搜索和插入。
在Pascal中，堆空間是全局量。設P是某過程內的局部變量，執行new（P）以后，在堆中為P分配一塊空間，如果在退出該過程前沒有把P空問釋放掉（這不算語法錯或語義錯），那么在退出該過程后P所指的空間既沒有用但又不能再分配給其他用戶，造成資源浪費，并經常導致死機。
為了克服這個問題，有些語言的編譯程序提供堆管理程序，對無用單元進行收集。
2）無用單元收集（garbage collection）
無用單元收集程序一般是在堆的可利用空間幾乎耗盡，以至于不能滿足用戶申請存儲區要求，或者發現可利用空問已降至某個危險點時才執行。無用單元收集過程通常分為兩個階段：第一階段稱為作標記階段，即對已分配的塊查閱這一段時間內是否被訪問過，若被訪問過就作一標記；第二階段是收集階段，即把所有未加標記的存儲塊加入到可利用表中，然后消除加過標記的那些存儲塊的標記，包括訪問標記。這種方法可以防止死塊的產生，因為加上標記的塊不會被釋放（表示它還在用），而沒有加標記的塊都會被釋放到可利用表中。
這種無用單元收集技術存在一個缺點：它的開銷（主要指收集時間）隨可利用空問的下降而增加。解決這個問題的途徑是在可利用空間降至某個數值時就調用收集程序，使得可利用空問總保持在較佳的狀態。另外，在執行無用單元收集程序時必須中斷用戶程序的執行，要等到收集程序執行結束后再執行用戶程序。所以，若頻繁地執行收集程序，必然影響計算機的運算速度。因此，選擇執行收集程序的時刻必須要合理。
上述的無用單元的收集只能收集死塊單元（包括長期不用單元）和外部碎片，不能收集內部碎片。解決這個問題的方法是在收集的第一階段，標記的對象不是以存儲塊為單位而是以存儲單元為單位。第二階段是既實行收集又進行內存大搬家，對每一使用塊重新定位，將已用塊歸于一端，騰出另一端為可利用空間。這種操作可以收集所有無用單元。