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

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

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

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

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

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

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

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

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

Висячий вказівник

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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