Купа (пам'ять)

Купа (англ. heap) в інформатиці та програмуванні — назва структури даних, за допомогою якої реалізовано динамічно розподілювану пам'ять програми.

Розмір купи — розмір пам'яті, виділеної операційною системою (ОС) для зберігання купи (під купу).

Принцип роботи

При запуску процесу ОС виділяє пам'ять для розміщення купи. Надалі пам'ять для купи (під купу) може виділятися динамічно.

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

Пам'ять купи можна розділити на зайняту (виділену програмі за допомогою функцій, подібних malloc()) і вільну (зайняту або вже звільнену з допомогою функцій, подібних free()).

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

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

Функція, подібна malloc() виконує приблизно такі дії:

• переглядає список зайнятих/вільних областей пам'яті, розміщених в купі, в пошуках вільної області відповідного розміру;
• у разі нестачі вільної пам'яті може запитати додаткову пам'ять у ОС;
• додає знайдену область в список зайнятих областей (або позначає область як зайняту);
• повертає покажчик на початок області пам'яті;
• якщо з тих чи інших причин виділити пам'ять не вдалося, повідомляє про помилку (наприклад, malloc() повертає NULL).

Функція, подібна free()виконує приблизно такі дії:

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

Програма може бути впевнена в тому, що між викликами функцій, подібних malloc() і free()область пам'яті, позначена як зайнята, не буде виділена повторно. Після виклику функції, подібної free()область пам'яті буде звільнена і надалі може використовуватися повторно або може бути віддана ОС. Використання вказівника на звільнену область пам'яті буде приводити до збоїв або непередбачуваної роботи програми.

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

Купа являє собою безперервну область пам'яті, поділену на зайняті і вільні області (блоки) різного розміру.

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

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

Кількість елементів, що входять в список зайнятих/вільних областей купи, може бути зменшено шляхом злиття елементів, що містять інформацію про наступні одну за іншою областях. Це дозволить зменшити час обходу списку.

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

Приклад реалізації

Створення декількох списків для зберігання інформації про областях однакових або близьких розмірів. Вибір списку в залежності від розміру області.

Дивись також

• Динамічна пам'ять
• NULL

Функції стандартної бібліотеки мови C

• malloc()
• free()