Складальник сміття - це
Термінологія
З точки зору української мови більш коректно було б називати метод не «складанням», а «збором сміття» [1]. Проте, в українській мові усталене саме слово «збірка».
Складальник сміття в просторіччі іноді називають «сміттярем».
Прибирання сміття була вперше застосована Джоном Маккарті в 1959 році в середовищі програмування на розробленому ним функціональній мові програмування Лісп. Згодом вона застосовувалася в інших системах програмування і мовами, переважно - в функціональних і логічних. Необхідність складання сміття в мовах цих типів обумовлена тим, що структура таких мов робить вкрай незручним відстеження часу життя об'єктів в пам'яті і ручне управління нею. Широко використовуються в цих мовах списки і засновані на них складні структури даних під час роботи програм постійно створюються, надбудовуються, розширюються, копіюються, і правильно визначити момент видалення того чи іншого об'єкта важко.
У промислових процедурних і об'єктних мовах прибирання сміття довго не використовувалася. Перевага віддавалася ручного управління пам'яттю, як більш ефективному та передбачуваному. Але з другої половини 1980-х років технологія збирання сміття стала використовуватися і в директивних, і в об'єктних мовах програмування. В даний час вона використовується в багатьох мовах, зокрема в Oberon. Python, C #, D і іншими мовами.
Проблеми ручного управління пам'яттю
Традиційним для директивних мов способом управління пам'яттю є ручний. Його сутність в наступному:
- Для створення об'єкта в динамічної пам'яті програміст явно викликає команду виділення пам'яті. Ця команда повертає покажчик на виділену область пам'яті, який зберігається і використовується для доступу до неї.
- До тих пір, поки створений об'єкт потрібен для роботи програми, програма звертається до нього через раніше збережений покажчик.
- Коли потреба в об'єкті проходить, програміст явно викликає команду звільнення пам'яті, передаючи їй покажчик на видаляється об'єкт.
У будь-якій мові, що допускає створення об'єктів в динамічній пам'яті, потенційно можливі дві проблеми: висячі посилання (англ. Dangling pointer) і витоку пам'яті (англ. Memory leak).
висячі посилання
Поява висячих посилань зазвичай стає наслідком неправильної оцінки часу життя об'єкта: програміст викликає команду видалення об'єкта до того, як його використання припиниться.
витоку пам'яті
Механізм складання сміття
Основні принципи
Прибирання сміття - технологія, що дозволяє, з одного боку, спростити програмування, позбавивши програміста від необхідності вручну видаляти об'єкти, створені в динамічної пам'яті, з іншого - виправити завдану неправильним ручним керуванням пам'яттю помилки.
В системі із збіркою сміття обов'язок звільнення пам'яті від об'єктів, які більше не використовуються, покладається на середу виконання програми. Програміст лише створює динамічні об'єкти і користується ними, він може не турбуватися про видалення об'єктів, оскільки це робить за нього середу. Для здійснення збору сміття до складу середовища виконання включається спеціальний програмний модуль, званий «збирачем сміття». Цей модуль періодично запускається, визначає, які з створених в динамічної пам'яті об'єктів більш не використовуються і звільняє займану ними пам'ять.
Періодичність запуску збирача сміття визначається особливостями системи. Складальник може працювати у фоновому режимі, запускаючись при неактивності програми (наприклад, коли програма простоює, чекаючи введення даних користувачем). Складальник сміття запускається безумовно, перериваючи виконання програми, коли чергову операцію виділення пам'яті виявляється неможливо виконати через те, що вся доступна пам'ять вичерпана.
Хоча, в загальному випадку, неможливо точно визначити момент, коли об'єкт був використаний в останній раз і більше не потрібен, збирачі сміття використовують консервативні оцінки, що дозволяють визначити, що в майбутньому об'єкт гарантовано не буде використовуватися.
досяжність об'єкта
Зазвичай критерієм того, що об'єкт ще використовується, є наявність посилань на нього. Якщо в системі немає більше посилань на даний об'єкт, то він, очевидно, не може бути використаний програмою, а отже, може бути видалений. Цей критерій використовується більшістю сучасних збирачів сміття і називається ще досяжністю об'єкта.
Неформально можна задати наступне рекурсивне визначення досяжного об'єкту:
Таке визначення не є теоретично найкращим, тому що в число досяжних, згідно з ним, потрапляють і ті об'єкти, які ніколи не будуть використані, але на які поки ще існують посилання. Оптимальним було б вважати недосяжним об'єкт, до якого в процесі подальшої роботи програми не буде жодного звернення, однак виявлення таких об'єктів неможливо, оскільки зводиться до алгоритмічно нерозв'язною завданню про зупинення (для цього достатньо припустити, що деякий об'єкт X буде використаний в тому і тільки в тому випадку, якщо успішно завершиться програма P).
Простий алгоритм визначення досяжних об'єктів, «алгоритм позначок» (Mark and Sweep), полягає в наступному:
Інший варіант алгоритму визначення досяжності - звичайний підрахунок посилань. Його використання уповільнює операції присвоювання посилань, але зате визначення досяжних об'єктів тривіально - це всі об'єкти, значення лічильника посилань яких перевищує нуль. Без додаткових уточнень цей алгоритм, на відміну від попереднього, що не видаляє циклічно замкнуті ланцюжки вийшли з ужитку об'єктів, що зберегли посилання один на одного.
Стратегії збірки сміття
Як тільки визначено безліч недосяжних об'єктів, збирач сміття може звільнити пам'ять, зайняту ними, і залишити решту як є. Також можна після звільнення пам'яті перемістити всі або частину залишків об'єктів в інші області пам'яті, оновивши разом з цим все посилання на них. Ці два варіанти реалізації називаються, відповідно, непереміщуваними і переміщує.
Обидві стратегії мають як переваги, так і недоліки:
Швидкість виділення і звільнення пам'яті- Непереміщуваними збирач сміття швидко звільняє пам'ять (оскільки ця операція зводиться до позначки відповідних блоків пам'яті як вільних), але витрачає більше часу на її виділення (оскільки пам'ять фрагментируется і при виділенні необхідно знайти в карті пам'яті потрібну кількість блоків відповідного розміру).
- Переміщає складальник вимагає порівняно більше часу на етапі складання сміття (витрачається додатковий час на дефрагментацію пам'яті і зміна всіх посилань на переміщувані об'єкти), зате переміщення дозволяє використовувати надзвичайно простий і швидкий (O (1)) алгоритм виділення пам'яті. При дефрагментації об'єкти пересуваються так, щоб розділити всю пам'ять на дві великі області - зайняту і вільну, і зберігається покажчик на їх кордон. Для виділення нової пам'яті достатньо лише перемістити цю межу, повернувши шматок з початку вільної пам'яті.
покоління об'єктів
Як показує практика, нещодавно створені об'єкти частіше стають недосяжними, ніж об'єкти, існуючі тривалий час. Відповідно до цією закономірністю багато сучасних збирачі сміття поділяють всі об'єкти на кілька поколінь - серій об'єктів з близьким часом існування. Як тільки пам'ять, виділена одному з поколінь, закінчується, в цьому поколінні і в усіх більш «молодих» проводиться пошук недосяжних об'єктів. Всі вони видаляються, а що залишилися переводяться в більш «старе» покоління.
Використання поколінь скорочує час циклу збірки сміття, оскільки зменшується число переглядаються в ході складання об'єктів, однак цей метод вимагає від середовища виконання відстеження посилань між різними поколіннями.
Вимоги до мови і системі
Щоб програма могла використовувати збірку сміття, необхідно виконання ряду умов, що відносяться до мови, середовищі виконання і самої розв'язуваної задачі.
проблеми використання
Всупереч часто зустрічається твердженнями, наявність збірки сміття зовсім не звільняє програміста від всіх проблем управління пам'яттю.
Гідності й недоліки
У порівнянні з ручним керуванням пам'яттю прибирання сміття безпечніше, оскільки вона запобігає витоку пам'яті і виникнення висячих посилань через несвоєчасне видалення об'єктів. Інший позитивний момент - спрощення самого процесу програмування. Як говорилося вище, програміст не може повністю ігнорувати питання управління пам'яттю і при наявності збирача сміття, але витрати на управління пам'яттю в цьому випадку все-таки істотно менше.
Однак у багатьох випадках системи зі складанням сміття демонструють меншу ефективність, як за швидкістю, так і за обсягом використовуваної пам'яті (що неминуче, так як збирач сміття споживає ресурси і потребує деякого надлишку вільної пам'яті для нормальної роботи).
Управління пам'яттю в конкретних мовах і системах
Прибирання сміття часто протиставляється ручного управління пам'яттю, при якому програміст явно вказує, коли і які області пам'яті треба звільнити. Однак є мови, в яких використовується комбінація двох методів управління пам'яттю, так само як є й інші технології вирішення тієї ж фундаментальної проблеми (наприклад, en: region inference).
Деякі мови програмування вимагають використання механізму збору сміття у відповідності зі своєю специфікацією (C #), інші - з причин ефективності реалізації (наприклад, формальні мови для лямбда-числення) - ці мови називаються мовами зі складанням сміття. Багато мови зі складанням сміття не мають можливостей для явного ручного видалення об'єктів (наприклад, оператора delete), завдяки чому виникнення висячих посилань виключається в принципі, а збирач сміття лише займається видаленням об'єктів, на які немає посилань з програми.
Деякі мови (наприклад, Modula-3) дозволяють використовувати як ручне управління пам'яттю так і збірку сміття в одному додатку - використовуючи дві окремі купи.