Особливості розробки розподілювачів пам’яті
Розподілювач пам’яті (memory allocator) – частина системної бібліотеки або ядра системи, відповідальна за динамічний розподіл пам’яті.
Головним завданням такого розподілювача є відстеження використання процесом ділянок пам’яті в конкретний момент. Основними цілями роботи розподілювача є мінімізація втраченого внаслідок фрагментації простору і витрат часу на виконання операцій (ці характеристики є основними критеріями порівняння алгоритмів розподілу пам’яті). При цьому розподілювач має враховувати принцип локальності (блоки пам’яті, які використовуються разом, виділяються поруч один з одним).
Сучасні розподілювачі пам’яті не можуть задовольнити всі ці вимоги і є певною мірою компромісними рішеннями. Доведено, що для будь-якого алгоритму розподілу пам’яті А можна знайти алгоритм В, що за відповідних умов буде кращим за продуктивністю, ніж А. На практиці, однак, можуть бути розроблені алгоритми, які використовують особливості поведінки реальних програм і працюють в основному добре.
Звичайні розподілювачі не можуть контролювати розмір і кількість використовуваних блоків пам’яті: цим займаються процеси користувача, а розподілювач просто відповідає на їхні запити. Крім того, розподілювач не може займатися дефрагментацією пам’яті (переміщенням її блоків для того щоб зробити вільну пам’ять неперервною), оскільки для нього недопустимо змінювати покажчики на пам’ять, виділену процесові користувача (цей процес має бути впевнений у тому, що адреси, які він використовує, не змінюватимуться без його відома). Якщо було ухвалене рішення про виділення блоку пам’яті, цей блок залишається на своєму місці доти, поки застосування не вивільнить його явно. Розподілювач фактично має справу тільки із вільною пам’яттю, основне рішення, яке він має приймати – де виділити наступний потрібний блок.
|
|
|
Фрагментація у разі динамічного розподілу пам’яті
Динамічний розподіл пам’яті може спричиняти зовнішню та внутрішню фрагментацію. Саме ступінь фрагментації є основним критерієм оцінки розподілювачів пам’яті. Фрагментація виникає з двох причин.
Різні об’єкти мають різний час життя (якщо об’єкти, що перебувають у пам’яті поруч, вивільняються в різний час). Розподілювачі пам’яті можуть використати цю закономірність, виділяючи пам’ять так, щоб об’єкти, які можуть бути знищені одночасно, розташовувалися поруч.
Різні об’єкти мають різний розмір. Якби всі запити вимагали виділення пам’яті одного розміру, зовнішньої фрагментації не було б (цього ефекту домагаються, наприклад, при використанні сторінкової організації пам’яті). Для боротьби із внутрішньою фрагментацією більшість розподілювачів пам’яті розділяють блоки пам’яті на менші частини, виділяють одну з них і далі розглядають інші частини як вільні. Крім того, часто використовують злиття сусідніх вільних блоків, щоб задовольняти запити на блоки більшого розміру.
|
|
|
Структури даних розподілювачів пам’яті
Найпростіший підхід до динамічного розподілу пам’яті реалізований у системному виклику brk(). Він може бути виконаний надзвичайно ефективно, тому що для його реалізації достатньо зберегти покажчик на початок вільної динамічної ділянки пам’яті та збільшувати його після кожної операції виділення пам’яті (рис. 10.1). На жаль, реалізувати вивільнення пам’яті на основі такого виклику неможливо, оскільки воно не може бути виконане послідовно в порядку, зворотному до виділення пам’яті. У результаті після вивільнення пам’яті в ній з’являтимуться «діри» (зовнішня фрагментація).
Рис. 10.1. Зміна розміру динамічної ділянки пам’яті
Покажчик, який використовується brk(), є найпростішим прикладом структури даних розподілювача пам’яті.
Складніші розподілювачі потребують складніших структур даних. Відстеження вільного простору у пам’яті може відбуватися за допомогою бітових карт, де кожний біт відповідає ділянці пам’яті (якщо він дорівнює одиниці, ця ділянка пам’яті зайнята, якщо нулю – вільна), або зв’язних списків зайнятих і вільних ділянок пам’яті, де кожний елемент списку містить індикатор зайнятості ділянки пам’яті та довжину цієї ділянки.
Дата добавления: 2018-04-05; просмотров: 1115; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!