Збірка сміття

Явне звільнення динамічно виділеної пам'яті застосовується в багатьох системах програмування і тому звично для більшості програмістів, але воно має серйозний недолік: якщо програміст з якоїсь причини не звільняє виділені блоки, пам'ять втрачатиметься. Ця помилка, звана витоком пам'яті (memory leak) особливо неприємна в програмах, які тривалий час працюють без перезапуску, — підсистемах ядра ОС, постійно запущених сервісах або серверних застосуваннях. Додаткова неприємність полягає в тому, що повільні витоки можуть привести до помітних втрат пам'яті лише при багатоденній або навіть багатомісячній безперервній експлуатації системи, тому їх складно виявити при тестуванні.
Деякі системи програмування використовують спеціальний метод звільнення динамічної пам'яті, званий збіркою сміття (garbage collection). Цей метод полягає в тому, що непотрібні блоки пам'яті не звільняються явним чином. Замість цього використовується деякий більш менш витончений алгоритм, що стежить за тим, які блоки ще потрібні, а які — вже немає.
Найпростіший метод відрізняти використовувані блоки від непотрібних — вважати, що блок, на який є заслання, потрібний, а блок, на який жодного заслання не залишилося, — не потрібний. Для цього до кожного блоку приєднують дескриптор, в якому підраховують кількість заслань на нього. Кожна передача покажчика на цей блок наводить до збільшення лічильника заслань на 1, а кожне знищення об'єкту, що містив покажчик, — до зменшення.
Втім, при наївній реалізації такого підходу виникає специфічна проблема. Якщо у нас є циклічний список, на який немає жодного заслання ззовні, то всі об'єкти в нім вважатимуться використовуваними, хоча вони і є сміттям. Якщо ми по тих або інших причинах упевнені, що кільця не виникають, метод підрахунку заслань сповна прийнятний; якщо ж ми використовуємо графи довільного вигляду, необхідний розумніший алгоритм.
Найбільш поширеною альтернативою підрахунку заслань є періодичний перегляд всіх заслань, які ми рахуємо "существующими' (аби під цим не малося на увазі) (мал. 4.12). Якщо деякі з указуемых об'єктів самі по собі можуть містити заслання, ми вимушені здійснювати перегляд рекурсивно. Провівши цю рекурсію до кінця, ми можемо бути упевнені, що, то і лише то, що ми проглянули, є потрібними даними, і з чистою совістю можемо оголосити все інше сміттям. Ця стратегія вирішує проблему кільцевих списків, але вимагає зупинки всієї останньої діяльності, яка може супроводитися створенням або знищенням заслань.

Мал. 4.12. Збірка сміття переглядом заслань

Всі методи збірки сміття, так або інакше, зводяться до підтримки бази даних про те, які об'єкти на кого посилаються. Використання такої техніки можливе практично лише в мовах, що інтерпретуються, таких, як Java, Smalltalk або Lisp, де з кожною операцією можна асоціювати необмежено велику кількість дій.