Прибирання сміття 1

У програмуванні прибирання сміття [1] (англ. Garbage collection) - одна з форм автоматичного управління пам'яттю. Спеціальний процес, званий складальником сміття (англ. Garbage collector), періодично звільняє пам'ять, видаляючи об'єкти, які вже не будуть затребувані додатками.

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

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

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

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

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

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

Механізм складання сміття

Основні принципи

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

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

Періодичність запуску збирача сміття визначається особливостями системи. Складальник може працювати у фоновому режимі, запускаючись при неактивності програми (наприклад, коли програма простоює, чекаючи введення даних користувачем). Складальник сміття запускається безумовно, перериваючи на час своєї роботи виконання програми, коли чергову операцію виділення пам'яті виявляється неможливо виконати через те, що вся доступна пам'ять вичерпана. Після звільнення пам'яті перервана операція виділення пам'яті відновлюється, і програма продовжує виконуватися далі. Якщо ж виявляється, що звільнити пам'ять неможливо, середовище виконання зупиняє програму з повідомленням про помилку «Недостатньо пам'яті».

досяжність об'єкта

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

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

Неформально можна задати наступне рекурсивне визначення досяжного об'єкту:

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

Алгоритм виставлення прапорів

Простий алгоритм визначення досяжних об'єктів, «алгоритм позначок» (Mark and Sweep), полягає в наступному:

Алгоритм підрахунку посилань

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

Стратегії збірки сміття

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

Обидві стратегії мають як переваги, так і недоліки

Швидкість виділення і звільнення пам'яті непереміщуваними збирач сміття швидше звільняє пам'ять (оскільки ця операція зводиться до позначки відповідних блоків пам'яті як вільних), але витрачає більше часу на її виділення (оскільки пам'ять фрагментируется, і при виділенні необхідно знайти в пам'яті потрібну кількість блоків відповідного розміру) . Переміщає складальник вимагає порівняно більше часу при зборі сміття (витрачається додатковий час на дефрагментацію пам'яті і зміна всіх посилань на переміщувані об'єкти), зате переміщення дозволяє використовувати надзвичайно простий і швидкий (O (1)) алгоритм виділення пам'яті. При дефрагментації об'єкти пересуваються так, щоб розділити всю пам'ять на дві великі області - зайняту і вільну, і зберігається покажчик на їх кордон. Для виділення нової пам'яті достатньо лише перемістити цю межу, повернувши шматок з початку вільної пам'яті. Швидкість доступу до об'єктів в динамічній пам'яті Об'єкти, поля яких використовуються спільно, що переміщає складальник дозволяє розміщувати в пам'яті недалеко один від одного. Тоді вони найімовірніше виявляться в кеші процесора одночасно, що зменшить кількість звернень до відносно повільного ОЗУ. Сумісність з чужорідним кодом переміщатися збирач сміття викликає труднощі при використанні коду, який не контролюється системою автоматичного управління пам'яттю (такий код називається стороннім (англ. Foreign) в традиційній термінології або некерованим (англ. Unmanaged) в термінології Microsoft). Покажчик на пам'ять, виділену в системі з непереміщуваними збирачем, можна просто передати чужорідного коду для використання, утримуючи хоча б одну звичайну посилання на об'єкт, щоб складальник його не вилучив. Переміщає складальник змінює положення об'єктів в пам'яті, синхронно змінюючи все посилання на них, але поміняти посилання в чужорідному коді він не може, в результаті передані чужорідного коду посилання після переміщення об'єкта стануть некоректними. Для роботи з чужорідним кодом використовуються різні спеціальні прийоми, наприклад, pinning - явна блокування об'єкта, що забороняє його переміщення під час збірки сміття.

покоління об'єктів

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

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

інші механізми

Незмінні об'єкти (англ. Immutable objects) Наприклад, java.lang.String в Java. Як тільки рядку присвоїли якесь значення, її вже не можна міняти. Підпрограми передаватимуть посилання на цей рядок один одному, і коли все посилання зникнуть, рядок буде знищена складальником сміття. Фіналізатор фіналізатор вказує, що робити, коли об'єкт потрапляє під збирач сміття. Зазвичай фіналізатор пишуть для обгорток над об'єктами операційної системи (файлами. Мережевими сокетами); вони автоматично закривають відповідний об'єкт. Оскільки об'єкт до збору може «провисеть» в пам'яті досить довго, хороша манера програмування - закрити файл або сокет вручну, командою на зразок close ().

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

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

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

Гідності й недоліки

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

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

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

Підтримка в деяких імперативних мовах автоматичного виклику деструктора (C ++ [3]. Ада. Delphi), а також більш проста, ніж збірка сміття, технологія використання «розумних посилань» (відстеження кількості посилань на об'єкт безпосередньо в ньому і автоматичне видалення при видаленні останньої посилання , як це зроблено в технології COM) значно знижує ймовірність витоків, дозволяючи концентрувати небезпечні місця всередині реалізації класу, при цьому не вимагаючи зайвих ресурсів, хоча і вимагає при цьому більш високої кваліфікації програміста. Звичайно, писати код звільнення ресурсів все одно доведеться, але автоматичні деструктори дадуть впевненість, що цей код обов'язково зголоситься. Втім, для найбільш часто використовуваних ресурсів у всіх популярних мовах, що підтримують автодеструктори, вже є автоматичні обгортки, які самі закривають ресурс, завдяки чому турбота про ресурсах стає чи не простіше, ніж з непередбачуваним складальником сміття.

Істотне зручність від збірки сміття виникає тоді, коли динамічно створені об'єкти живуть тривалий час, кілька разів дублюються, а посилання на них передаються між різними ділянками програми. У таких програмах в загальному випадку досить складно безпомилково визначити місце, де об'єкт перестав використовуватися і його можна видаляти. Оскільки саме така ситуація складається при широкому використанні динамічно змінюваних структур даних (списки, дерева, графи), збірка сміття є необхідною в широко використовують такі структури функціональних і логічних мовах, типу Хаскелл. Лиспа або Прологу. Використання збірки сміття в традиційних імперативних мовах (заснованих на структурної парадигми, можливо, доповненої об'єктними засобами) визначається бажаним співвідношенням між простотою і швидкістю розробки програм і ефективністю її виконання.

Управління пам'яттю в конкретних мовах і системах

Прибирання сміття часто протиставляється ручного управління пам'яттю, при якому програміст явно вказує, коли і які області пам'яті треба звільнити. Однак є мови, в яких використовується комбінація двох методів управління пам'яттю, так само як є й інші технології вирішення тієї ж фундаментальної проблеми (наприклад, en: region inference).

Деякі мови програмування вимагають використання механізму збору сміття у відповідності зі своєю специфікацією (Java. C #. Eiffel), інші - з причин ефективності реалізації (наприклад, формальні мови для лямбда-числення) - ці мови називаються мовами зі складанням сміття. Багато мови зі складанням сміття не мають можливостей для явного ручного видалення об'єктів (наприклад, оператора delete), завдяки чому виникнення висячих посилань виключається в принципі, а збирач сміття лише займається видаленням об'єктів, на які немає посилань з програми.

Деякі мови (наприклад, Modula-3) дозволяють використовувати як ручне управління пам'яттю, так і складання сміття в одному додатку - використовуючи дві окремі купи.