Реалізація динамічного керування пам'яттю в LINUX

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

Мінімізувати час, необхідне на управління пам'яттю

Максимально збільшити доступну пам'ять для загального використання (мінімізувати її непродуктивні витрати на управління)

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

Раніше менеджери пам'яті використовували стратегію розподілу, що базується на heap (простір для динамічного виділення пам'яті). У цьому методі великий блок пам'яті (званий heap) використовується для забезпечення пам'яттю призначених для користувача цілей. Коли користувачам потрібно блок пам'яті, вони просять шматок пам'яті необхідного розміру. Менеджер heap перевіряє доступну пам'ять (використовуючи спеціальний алгоритм) і повертає блок. Окремі алгоритми використовують при цьому пошуку first - fit (що перший, що зустрічається в heap блок, який відповідає запиту) і best - fit (блок в heap, що найбільш відповідає запиту). Коли користувачі закінчують використовувати пам'ять, вони повертають її в heap.

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

Інший підхід, що називається buddy memory allocation, -- швидший метод, який ділить пам'ять на розділи з розміром, кратним мірі 2, і намагається розподілити запити пам'яті, використовуючи підхід best - fit. Коли користувач звільняє пам'ять, перевіряється блок buddy, щоб побачити усі суміжні вільні сусідні блоки. Ці блоки, якщо вони є, об'єднуються для мінімізації фрагментації. Цей алгоритм дещо ефективніший за тимчасовими характеристиками, але внаслідок використання підходу best - fit може непродуктивно витрачати пам'ять.

Ця стаття сфокусована на описі механізмів, що надаються ядром Linux для управління пам'яттю і, зокрема, на механізмах, що надаються slab allocation.

Кеш slab

Розподільник пам'яті slab, використовуваний в Linux, базується на алгоритмі, уперше введеному Джефом Бонвиком (Jeff Bonwick) для операційної системи SunOS. Розподільник Джефа будується навколо об'єкту кешування. Усередині ядра значна кількість пам'яті виділяється на обмежений набір об'єктів, наприклад, дескриптори файлів і інші загальні структурні елементи. Джеф грунтувався на тому, що кількість часу, необхідна для ініціалізації регулярного об'єкту в ядрі, перевищує кількість часу, необхідну для його виділення і звільнення. Його ідея полягала в тому, що замість того, щоб повертати пам'ять, що звільнилася, до загального фонду, залишати цю пам'ять в стані, що проініціалізував, для використання в тих же цілях. Наприклад, якщо пам'ять виділена для mutex, функцію ініціалізації mutex (mutex_init) необхідно виконати тільки один раз, коли пам'ять уперше виділяється для mutex. Подальші розподіли пам'яті не вимагають виконання ініціалізації, оскільки вона вже має потрібний статус від попереднього звільнення і звернення до деконструктору.

У Linux розподільник slab використовує ці і інші ідеї для створення розподільника пам'яті, який ефективно використовуватиме і простір, і час.

Малюнок 1 ілюструє верхній рівень організації структурних елементів slab. На найвищому рівні знаходиться cache_chain, який є пов'язаним списком кешів slab. Це корисно для алгоритмів best - fit, які шукають кеш, що найбільш відповідає розміру потрібного розподілу (здійснюючи ітерацію за списком). Кожен елемент cache_chain -- це посилання на структуру (звана cache (кеш)). Це визначає сукупність об'єктів заданого розміру, які можуть використовуватися.

Малюнок 1. Головні структури розподільника slab

Кожен кеш містить список slab 'ов, які є суміжними блоками пам'яті (зазвичай сторінки). Існує три slab:

slabs_full

Slab 'ы, які розподілені повністю.

slabs_partial

Slab 'ы, які розподілені частково.

slabs_empty

Slab 'ы, які є порожніми або не виділені під об'єкти.

Зверніть увагу, що slab 'ы в списку slabs_empty -- основні кандидати на reaping. Це процес, за допомогою якого пам'ять, використовувана slab 'ами, забезпечує повернення в операційну систему для подальшого використання.

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

Оскільки об'єкти розподіляються і звільняються з slab, окремі slab можуть переміщатися між списками slab 'ов. Наприклад, коли усі об'єкти в slab витрачені, вони переміщаються зі списку slabs_partial в список slabs_full. Коли slab повний і об'єкт звільняється, він переміщається зі списку slabs_full в список slabs_partial. Коли звільняються усі об'єкти, вони переміщаються зі списку slabs_partial в список slabs_empty.

Мотивація до використання slab

Розподільник кеша slab має деякі переваги в порівнянні з традиційною схемою управління пам'яттю. По-перше, ядра зазвичай покладаються на виділення маленьких об'єктів, які розподіляються безліч разів впродовж роботи системи. Це забезпечується розподільником кеша slab через кешування об'єктів схожих розмірів, таким чином уникаючи проблем фрагментації, що часто зустрічаються. Розподільник slab також підтримує фрагментацію загальних об'єктів, таким чином уникаючи необхідності повторно ініціалізувати об'єкти для тієї ж мети. Нарешті, розподільник slab підтримує вирівнювання апаратного кеша і coloring, який дозволяє об'єктам з різними кешами займати ті ж самі рядки кеша для збільшення використання кеша і кращої продуктивності

Контрольні запитання

1. У чому полягає сутність динамічного керування пам'яттю?
2. Опишіть механізм дії Кеша slab
3. У чому полягає мотивація до використання slab?

Лутература

Електроний ресурс http://www.ibm.com/developerworks/ru/library/l-linux-slab-allocator/index.html?ca=drs - ru