Основи методів трансляції, купа
Купа використовується для зберігання значень, до яких може знадобитися доступ від моменту виділення для них пам'яті і до завершення програми. Не існує механізму мови, подібного виходу з блоку або функції, який зробить область пам'яті недоступною. На перший погляд схема розподілу для такої пам'яті повинна виділяти пам'ять від одного кінця лінійного простору до іншого, поки вільна пам'ять не будуть розподілені повністю. Може здатися, що при цьому ніяких проблем з перерозподілом або надмірним використанням пам'яті виникнути не повинно. У той же час даний підхід має істотний недолік, а саме: після першого повного розподілу пам'яті застосування наступного оператора, наприклад,
який спробує виділити чотири біта пам'яті і повернути покажчик на цю область, викличе помилку в програмі. Втім, перш ніж змиритися з цим, слід згадати, що область пам'яті може стати недоступною внаслідок таких операцій програми, як перепризначення покажчиків і т.д. Наприклад, виділене раніше простір може стати недоступним для змінної string після наступного присвоювання:
У той же час дана операція дозволяє отримати доступ до розглянутого простору деякої іншої змінної. Розглянемо результат виконання присвоювання
між двома зазначеними вище операторами. Вважаючи, що інші оператори, пов'язані з даними, відсутні, подібні дії призведуть до того, що змінною stringl буде доступно простір, виділене оператором malloc.
Оскільки, в загальному випадку, в процесі компіляції невідомо, як буде виконуватися програма, то при компіляції неможливо дізнатися, коли стане недоступною пам'ять, виділена оператором malloc. Це означає, що код для відновлення області купи не може бути згенерований в процесі компіляції, хоча недоступними можуть стати великі області, виділені в купі. Один із способів подолання такої проблеми полягає в тому, щоб програмісти (виходячи зі своїх знань про те, як буде виконуватися програма) передбачали момент, коли пам'ять купи стає недоступною, і вводили в вихідний код явні інструкції для перерозподілу пам'яті. Наприклад, в С для звільнення області пам'яті, відведеної змінної string, можна записати наступне:
У той же час даний підхід вимагає від програміста великого професіоналізму і відповідальності. Отже, будь-які автоматизовані методи звільнення пам'яті застосовувати небажано. У мові Java передбачається, що відповідальність за звільнення недоступною пам'яті має покладатися на реалізацію Java, а не на програміста; таким чином, будь-яка реалізація Java повинна мати відповідні механізми. Примітно, що на відміну від раніше описаних моделей пам'яті, Java зберігає в купі масиви. Все об'ектитакже зберігаються в купі.
У зв'язку з відновленням недоступних областей пам'яті існують два можливих методи управління купою:
• прибирання сміття (garbage collection);
• використання лічильників посилань (use of reference counters). Перший метод, мабуть, є більш популярним, але і більш необхідним. Перевага цього підходу полягає в тому, що до повного розподілу всього доступного простору пам'яті не виникає потреби у відновленні будь-якій його частині. Внаслідок цього в багатьох випадках для збору сміття часу взагалі не потрібно. Якщо (і коли) прибирання сміття все-таки потрібно, цей процес відбувається в дві фази:
• Фаза маркування, в якій (за допомогою введення значень в бітову карту) позначається пам'ять купи, доступна для змінних програми.
• Фаза стиснення, в якій весь доступний простір зсувається в один кінець купи, а пам'ять, що підлягає повторному використанню, утворює безперервний блок в іншому кінці купи. При цьому, зрозуміло, слід акуратно перевірити, щоб відповідним чином змінилися всі значення покажчиків.
З цих двох фаз фаза маркування найцікавіша і допускає менше альтернативних способів реалізації. Потрібні деякі засоби "маркування" осередків пам'яті, до яких при необхідності можуть звертатися змінні програми. Для цього може використовуватися бітова карта з достатнім числом бітовдля зіставлення з кожною клітинкою купи. Бітова карта не є частиною купи і розташовується окремо від неї. Кожен біт в бітової карті може приймати одне з двох значень:
0 - відповідна осередок пам'яті не доступна для змінних програми.
1 - відповідна комірка пам'яті доступна для змінних програми. B початку процесу складання сміття все елементи бітової карти мають значення 0, а при виконанні алгоритму різних елементів карти присвоюється значення 1. На завершення збирання сміття значення 1 отримають всі елементи бітової карти, які відповідають осередкам пам'яті, доступним для змінних програми.
Простий алгоритм збірки сміття використовує стек (званий стеком збірки сміття) і полягає в наступному:
1. Стек часу виконання лінійно проглядається, поки не буде виявлена змінна, яка вказує на Непомічені осередок купи. Це може бути або власне змінна, яка є покажчиком (в купу), або компонент записи, який є покажчиком. Надалі все осередки купи, на які вказують подібні змінні, маркіруютсяпосредством включення відповідних біт в бітову карту.
4. Третій крок повторюється до тих пір, поки звільниться стек збірки сміття, і всі покажчики в стеці часу виконання будуть оброблені описаним чином.
Оскільки на третьому кроці завжди маркуються непомічені осередки, то, врешті-решт, виконання алгоритму припиниться.
Описаний вище алгоритм є наочним, простим для розуміння і ефективним. Однак у нього є один істотний недолік - він нереальний, оскільки вимагає використання стека довільного розміру в момент найбільшої завантаженості пам'яті. Іншими словами, прибирання сміття просто не буде ініційована! Безумовно, ніхто не очікує, що чистка пам'яті буде виконуватися при відсутності простору для роботи. У той же час оскільки для збору сміття потрібно невеликий (і відомий) обсяг пам'яті, то при нестачі пам'яті її можна ініціювати в першу чергу. Фактично існує алгоритм збірки сміття з гранично малими запитами робочого простору:
1. Позначити всі осередки купи, на які прямо вказують значення з стека часу виконання.
Крім простору, необхідного для бітової карти, алгоритму також потрібні три змінні, що представляють:
• осередок, до якої йде звернення;
У той же час, з точки зору витрачається часу, цей алгоритм може бути вкрай неефективним. Зокрема, це може бути в тому випадку, коли в купі міститься багато зворотних покажчиків, і це є ціною за невикористання стека.
Компромісом між двома описаними алгоритмами буде алгоритм, що дотримується стратегії 1 при достатньо вільного місця і стратегії 2 - в протилежному випадку. Наприклад, якщо стек досить великий, то алгоритм може використовувати стек фіксірованногоразмера і дотримуватися першої стратегії. Як тільки при збільшенні стека стане реальною загроза його переповнення, з стека (з нижньої частини) може віддалятися одне значення. Віддалене таким чином нижнє значення стека запам'ятовується і використовується для початку другої фази алгоритму, яка багато в чому буде подібна збірці сміття 2.
В іншому добре відомому алгоритмі купа розглядається як деревоподібна структура з покажчиками від вершини до основи. Прибирання сміття починається з вершини дерева і йде у напрямку вниз. Замість використання стеків для запам'ятовування покажчиків, які потребують подальшої обробки, алгоритм використовує покажчики самого дерева, тимчасово звертаючи їх для забезпечення шляху повернення вгору по дереву. Цей алгоритм ефективніше ис точки зору часу, ис точки зору необхідної пам'яті.
Інші схеми очищення пам'яті включають різні схеми збірки сміття з урахуванням поколінь (generational garbage collection), в яких проводиться поділ:
• між глобальними об'єктами, які існують відносно довго ще до ініціації процесу складання сміття, і пам'ять для яких очищати не обов'язково;
• локальними об'єктами, які існують менше час, і пам'ять яких постійно потрібно повертати в доступну область.
Очевидно, що така схема зменшує час збірки сміття і може бути досить ефективною. В інших схемах для зменшення часу стиснення купи використовуються дві глобальні області. Посилання на деякі наводяться в розділі додаткової літератури в кінці розділу.
Який би метод збирання сміття не використовувався, може трапитися так, що програма просто вичерпає доступну пам'ять і буде змушена завершити роботу, якщо тільки система не дозволить цю проблему якимось іншим способом. Пам'ять програми може також обмежуватися за рахунок збирання сміття, якщо при використовуваному алгоритмі велика частина часу йде саме на чистку пам'яті - незабаром після завершення збирання сміття, коли програма вже здається готової до продовження роботи, купа знову переповнюється, що знову вимагає проведення очищення пам'яті. У такій ситуації службові витрати на проведення збирання сміття можуть бути дуже значними, і саме тут буде доречним альтернативний підхід - використання лічильників посилань. Цей метод дозволяє (досить часто) замінити непередбачувані витрати на збірку сміття витратами постійними і передбачуваними.
При використанні лічильників посилань робиться спроба очистити кожен елемент пам'яті купи відразу ж після припинення зверненні до нього. Кожна комірка пам'яті в купі має лічильник посилань, в якому фіксується число значень, які звертаються до даного осередку. Поява кожної нової змінної, що звертається до даного осередку, збільшує значення лічильника, а зникнення посилання зменшує його. Коли значення лічильника стає нульовим, осередок може бути повернута в область пам'яті, доступної для подальшого розподілу. Цей метод вдалий, але має деякі обмеження:
• Не може очищатися пам'ять, яка пов'язана зі структурами даних, подібними кільцевих списками.
• Постійні витрати, пов'язані з використанням лічильників посилань, можуть сильно зменшувати ефективність програм з гранично малими запитами щодо пам'яті.