Збирання сміття

Збирання сміття (англ. garbage collection) — одна з форм автоматичного керування оперативною пам'яттю комп'ютера під час виконання програм. Підпрограма — «прибиральник сміття» — вивільняє пам'ять від об'єктів, які не використовуватимуться програмою надалі. Збирання сміття було винайдено Джоном Маккарті приблизно 1959 року для розробленої ним мови програмування Lisp.

Історія

Прибирання сміття вперше застосував Джон Маккарті 1959 року в середовищі програмування на розробленій ним функціональній мові програмування Lisp. Згодом воно застосовувалося в інших системах програмування і мовах, переважно — у функційних та логічних. Необхідність збирання сміття в мовах цих типів обумовлена ​​тим, що структура таких мов робить украй незручним відстеження часу життя об'єктів у пам'яті й ручне керування нею. У цих мовах широко використовуються списки і засновані на них складні структури даних під час роботи програм постійно створюються, надбудовуються, розширюються, копіюються, і правильно визначити момент видалення того чи іншого об'єкта важко.

У промислових процедурних і об'єктних мовах прибирання сміття довго не використовувалася. Перевага віддавалася ручному керуванню пам'яттю, як більш ефективному та передбачуваному. Але з другої половини 1980-х років технологія збирання сміття стала використовуватися і в директивних (імперативних), і в об'єктних мовах програмування, а з другої половини 1990-х років усе більше число створюваних мов і середовищ, орієнтованих на прикладне програмування, містять механізм збору сміття або як єдиний, або як один з доступних механізмів керування динамічною пам'яттю. Нині^[коли?] вона використовується мовами Оберон, Java, Python, Ruby, Perl, C#, D, F# та іншими мовами.

Основний принцип, з яким працюють різні алгоритми збирання сміття, полягає в наступному:

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

Часто автоматичне збирання сміття протиставляють ручному керуванню пам'яттю, яке, на відміну від автоматичного, вимагає від розробника самому писати інструкції виділення пам'яті та її звільнення.

Проблеми ручного керування пам'яттю

Традиційним для директивних мов способом керування пам'яттю є ручний. Його сутність у такому:

• Для створення об'єкта в динамічній пам'яті програміст явно викликає команду виділення пам'яті. Ця команда повертає вказівник на виділену ділянку пам'яті, який зберігається і використовується для доступу до неї.
• До тих пір, поки створений об'єкт потрібен для роботи програми, програма звертається до нього через раніше збережений вказівник.
• Коли потреба в об'єкті зникає, програміст явно викликає команду звільнення пам'яті, передаючи їй вказівник на створений об'єкт.

У будь-якій мові, що допускає створення об'єктів у динамічній пам'яті, потенційно можливі дві проблеми: завислі вказівники і витоки пам'яті .

Завислий вказівник

Завислий вказівник — це вказівник, який залишається у використанні для посилання на об'єкт, який уже видалений. Після видалення об'єкта всі збережені в програмі посилання на нього стають «завислими». Пам'ять, займана раніше об'єктом, може бути передана операційній системі і стати недоступною, або бути використана для розміщення нового об'єкта в тій самій програмі. У першому випадку спроба звернутися по «повислого» вказівника призведе до спрацьовування механізму захисту пам'яті й аварійної зупинки програми, а в другому — до непередбачуваних наслідків.

Поява завислих посилань зазвичай стає наслідком неправильної оцінки часу життя об'єкта: програміст викликає команду видалення об'єкта до того, як його використання припиниться.

Витік пам'яті

Створивши об'єкт у динамічній пам'яті, програміст може не видалити його після завершення використання. Якщо на об'єкт немає посилань, він стає програмно недоступним, але продовжує займати пам'ять, оскільки команда його видалення не викликана. Ця ситуація і називається витоком пам'яті.

Якщо об'єкти, посилання на які губляться, створюються в програмі постійно, то витік пам'яті проявляється в поступовому збільшенні обсягу використовуваної пам'яті; якщо програма працює довго, обсяг використовуваної нею пам'яті постійно зростає, і через якийсь час відчутно сповільнюється робота системи (через необхідність під час будь-якого виділення пам'яті використовувати підкачування сторінок), або програма вичерпує доступний обсяг адресного простору і завершується з помилкою.

Вплив автоматичного збирання сміття на швидкодію

Дослідження впливу автоматичного збирання сміття на швидкодію програм для мов програмування, розроблених для застосування лише разом з автоматичним збиранням сміття (таких як Java, Objective Caml, Python тощо), ускладнюється браком можливості вимірювати швидкодію програми з ручним керуванням пам'яттю. Однак, у дослідженні Метью Герца та Емері Берґера порівняно швидкодію ручного керування пам'яттю та прибиральників сміття (як з копіюванням, так і без копіювання). Ці вимірювання довели, що найкращий за швидкодією прибиральник сміття може конкурувати за швидкодією з ручним керуванням пам'яттю, якщо йому надати досить багато пам'яті. Зокрема, з використанням уп'ятеро більшої пам'яті його швидкодія відповідає ручному варіанту. За наявності втричі більшої вільної пам'яті він працює в середньому на 17 % повільніше за ручне керування пам'яттю. А з використанням удвічі більшої пам'яті, швидкодія зменшується на 70 %. В умовах браку фізичної пам'яті використання своп-пам'яті вповільнює швидкодію прибиральника сміття в рази порівняно з ручним керуванням.

Вимоги до мови та системи

Щоб програма могла використовувати збирання сміття, необхідно виконання низки умов, що належать до мови, середовища виконання і самої розв'язуваної задачі.

Необхідність середовища виконання зі збирача сміття

Природно, для збору сміття необхідне динамічне середовище, що підтримує виконання програми, і наявність у цьому середовищі збирача сміття.

Підтримка з боку мови програмування

Збирач сміття може нормально функціонувати тільки тоді, коли він може точно відстежити всі посилання на всі створені об'єкти. Очевидно, якщо мова допускає перетворення посилань (вказівників) в інші типи даних (цілі числа, масиви байтів і так далі) на кшталт С/C++, відстежити використання таких перетворених посилань стає неможливо, і збирання сміття стає безглуздим — вона не захищає від «завислих» вказівників і витоків пам'яті. Тому мови, орієнтовані на використання збирання сміття, зазвичай істотно обмежують свободу використання вказівників, адресної арифметики, перетворень типів вказівників до інших типів даних. У частині з них узагалі немає типу даних «вказівник», у частині він є, але не допускає ні перетворень типу, ні зміни.

Технічна допустимість короткочасних уповільнень у роботі програм

Прибирання сміття виконується періодично зазвичай у заздалегідь невідомі моменти часу. Якщо припинення роботи програми на час, порівнянний із часом збирання сміття, може призвести до критичних помилок, використовувати в подібній ситуації збирання сміття, очевидно, не можна.

Наявність деякого резерву вільної пам'яті

Чим більше пам'яті доступно середовищі виконання, тим рідше запускається збирач сміття і тим ефективніше його робота. Робота збирача сміття в системі, де кількість доступної збирачеві пам'яті наближається до пікової потреби програми, може виявитися неефективною і непродуктивною. Чим менше надлишок пам'яті, тим частіше відбувається запуск збирача і тим більше часу витрачається на його виконання. Падіння продуктивності програми в такому режимі може виявитися занадто істотним.

Див. також

• Lisp — перша мова програмування з автоматичним збиранням сміття.
• Simula та Smalltalk — перші об'єктно-орієнтовані мови програмування також мали автоматичне збирання сміття.
• Java, C# — сучасні популярні мови програмування з автоматичним збиранням сміття.

Джерела

• Дональд Кнут. Fundamental Algorithms // The Art of Computer Programming. — 3rd. — Massachusetts : Addison–Wesley, 1997. — Т. 1. — 650 с. — ISBN 0-201-89683-4.(англ.)