Система управління пам’яттю
Система управління пам'яттю повинна перш за все "знати", які осередки наявної в її розпорядженні пам'яті вільні, а які - зайняті. Методи обліку вільної пам'яті ґрунтуються або на принципі бітової картки, або на принципі списків вільних блоків
Пам'ять завжди виділяється блоками – тобто. обов'язково безперервними послідовностями суміжних осередків. Блоки можуть бути фіксованою або змінною довжиною. Фіксований розмір блоку набагато зручніше для управління: у цьому випадку вся доступна для розподілу пам'ять розбивається на "кадри", розмір кожного з яких дорівнює розміру блоку, і будь-який вільний кадр підходить для задоволення будь-якого запиту. На жаль, лише обмежене коло реальних завдань може бути зведене до блоків фіксованої довжини.
Однією з проблем, які повинні братися до уваги при управлінні пам'яттю, є проблема фрагментації пам'яті. Вона полягає у виникненні "дір" - ділянок пам'яті, які не можуть бути використані. Розрізняються діри внутрішні та зовнішні. Внутрішня діра - частина виділеного блоку, що не використовується, вона виникає, якщо розмір виділеного блоку більше за запитаний. Внутрішні дірки характерні виділення пам'яті блоками фіксованої довжини. Зовнішня діра - вільний блок, який у принципі міг би бути виділений, але розмір його занадто малий задоволення запиту. Зовнішні дірки характерні виділення блоками змінної довжини. Управління пам'яттю має бути збудовано таким чином, щоб мінімізувати сумарний обсяг дірок.
Завдання утилізації значно ускладнюється у системах, де немає явного звільнення пам'яті: тоді систему лягає завдання визначення те, які динамічні структури чи його елементи не потрібніпрограмісту. Один із методів вирішення цього завдання передбачає, що система не приступає до звільнення пам'яті доти, доки вільної пам'яті зовсім не залишиться. Потім усі зарезервовані блоки перевіряються та звільняються ті з них, які більше не використовуються. Такий метод називається "складанням сміття". Програма, складання сміття викликається тоді, коли немає можливості задовольнити деякий приватний запит на пам'ять, або коли розмір доступної області пам'яті став меншим за деякий заздалегідь визначений кордон. Алгоритм складання сміття зазвичай буває двоетапним. На першому етапі здійснюється маркування (помітка) всіх блоків, на які вказує хоча б один покажчик. На другому етапі всі невідзначені блоки повертаються у вільний список, а мітки стираються. Важливо, щоб у момент увімкнення збирача сміття всі вказівники були встановлені на ті блоки, на які вони повинні вказувати. Якщо необхідно в деяких алгоритмах застосовувати методи з тимчасовим неузгодженістю покажчиків, необхідно тимчасово відключити збирач сміття - поки є таке неузгодженість. Один із найсерйозніших недоліків методу складання сміття полягає в тому, що витрати на нього збільшуються в міру зменшення розмірів вільної області пам'яті.
Інший метод – звільняти будь-який блок, як тільки він перестає використовуватись. Він зазвичай реалізується у вигляді лічильників посилань - лічильників, у яких записується, скільки покажчиків цей блок є у час. Коли значення лічильника дорівнює 0, відповідний блок виявляється недоступним і, отже, не використовується. Блок повертається до вільного списку. Такий метод запобігає накопиченню сміття, що не вимагає великої кількості оперативних перевірок під час обробки даних. Однак і цей метод маєпевні вади. По-перше, якщо зарезервовані блоки утворюють циклічну структуру, то лічильник посилань кожного з них не дорівнює 0, коли всі зв'язки, що йдуть ззовні блоків циклічну структуру, будуть знищені. Це призводить до появи сміття. Існують різні можливості усунути цей недолік: заборонити циклічні та рекурсивні структури; відзначати циклічні структури прапорцями, та обробляти їх особливим чином; вимагати, щоб будь-яка циклічна структура завжди мала головний блок, лічильник циклів якого враховував тільки посилання від елементів, розташованих поза циклом, і щоб доступ до всіх блоків цієї структури здійснювався тільки через нього. По-друге, потрібні зайві витрати часів та пам'яті на ведення лічильників посилань.
Практична ефективність методів залежить від багатьох параметрів, таких як частота запитів, статистичний розподіл розмірів блоків, що запитуються, спосіб використання системи - групова обробка або стратегія обслуговування при управлінні обчислювальним центром.
У стандартних бібліотеках мов високого рівня, таких як malloc/free/realloc в C, new/dispose в Pascal і т.д., як правило, використовуються алгоритми, розраховані на гірший випадок: програма вимагає блоки випадкового розміру у випадковому порядку та звільняє їх також випадковим чином. Можливий, правда, більш неприємний випадок:
void * b1 = malloc (random (10));
/* Випадковий розмір від 0 до 10 байт */
void * b2 = malloc (random (10) + 10);
/*. від 10 до 20 байт */
if(b1 == NULL && b2 == NULL) /* Якщо пам'яті немає */
break; /* вийти із циклу */
void * b3 = malloc (150);
/* Швидше за все, пам'ять не буде виділено */
Внаслідок виконання такої програми вся доступна пам'ятьбуде "порізана на локшину": між будь-якими двома вільними блоками буде розміщений зайнятий блок меншого розміру. На щастя, приклад 4носить штучний характер. У звичайних програмах така ситуація зустрічається рідко, і часто виявляється простіше виправити програму, ніж вносити зміни до універсального алгоритму управління купою.
Зазвичай усі вільні блоки пам'яті поєднуються у двонаправлений зв'язаний список. Список має бути двоспрямованим для того, щоб з нього у будь-який момент можна було витягти будь-який блок. Втім, якщо всі дії щодо вилучення блоку проводяться після пошуку, то можна злегка ускладнити процедуру пошуку і завжди зберігати покажчик на попередній блок. Це вирішує проблему вилучення і можна обмежитися однонаправленим списком. Біда тільки в тому, що багато алгоритмів при об'єднанні вільних блоків витягують їх зі списку відповідно до адреси, тому для таких алгоритмів двонаправлений список гостро необхідний
При першому погляді проблему виникає бажання відсортувати список за розміром блоку. Насправді це безглуздо: час пошуку в сортованому списку покращується всього вдвічі в порівнянні з несортованим (ось у масиві або в дереві - зовсім інша справа), зате додається час вставки в список, пропорційний O(n), де n - розмір список. Поміщати блоки в сортований масив ще гірше - час вставки стає і з'являється обмеження кількості блоків. Використання хеш-таблиць або двійкових дерев потребує великих накладних витрат і ускладнень програми, які не виправдовують себе. Тому використовують несортований список.
Пошук у списку може вестись двома способами: до знаходження першого відповідного (first fit) блоку або до блоку, розмір якого найближчий до заданого - найбільшпридатного (best fit). Для знаходження найбільш відповідного ми повинні переглядати весь список, в той час як перший підходящий може опинитися в будь-якому місці, і середній час пошуку буде меншим. Наскільки менше – залежить від відношення кількості відповідних блоків до загальної кількості. (Читачі, знайомі з теорією ймовірності, можуть самостійно вирахувати цю залежність).
Крім того, у загальному випадку best fit збільшує фрагментацію пам'яті. Дійсно, якщо ми знайшли блок з розміром більше заданого, ми повинні відокремити "хвіст" і помітити його як новий вільний блок. Зрозуміло, що у випадку best fit середній розмір цього хвоста буде маленьким, і ми отримаємо велику кількість дрібних блоків, які неможливо об'єднати, оскільки простір між ними зайнятий.
Під час використання first fit з лінійним двонаправленим списком виникає специфічна проблема. Якщо кожного разу переглядати список з одного місця, великі блоки, розташовані ближче до початку, будуть частіше видалятися. Відповідно, дрібні блоки матимуть тенденцію накопичуватись на початку списку, що збільшить середній час пошуку. Простий спосіб боротьби з цим явищем у тому, щоб переглядати список то одному напрямі, то іншому. Більш радикальний і ще простіший метод полягає в тому, що список робиться кільцевим, і пошук кожен починається з того місця, де ми зупинилися минулого разу. У це ж місце додаються блоки, що звільнилися. В результаті список дуже ефективно перемішується і ніякого антисортування не виникає.
У ситуаціях, коли ми розміщуємо блоки декількох фіксованих розмірів, алгоритми best fit виявляються кращими. Однак бібліотеки розподілу пам'яті розраховують на найгірший випадок, і в них зазвичай використовуються алгоритмиперший fit.
У разі роботи з блоками декількох фіксованих розмірів напрошується таке рішення: створити для кожного типорозміру свій список. Це позбавляє програміста необхідності вибирати між first і best fit, усуває пошук у списках як явище. коротше, вирішує одразу багато проблем.
Алгоритм близнюків значно знижує фрагментацію пам'яті та різко прискорює пошук блоків. Найбільш важливою перевагою цього підходу є те, що навіть у найгіршому випадку час пошуку не перевищує , де позначають відповідно максимальний і мінімальний розміри використовуваних блоків. Це робить алгоритм близнюків важкозамінним для ситуацій, коли необхідний гарантований час реакції - наприклад, для завдань реального часу. Часто цей алгоритм або його варіанти використовуються виділення пам'яті всередині ядра ОС. Наприклад, функція kmalloc, що використовується в ядрі ОС Linux, заснована саме на алгоритмі близнюків.
Розробник програми динамічного розподілу пам'яті має вирішити ще одну важливу проблему, саме - об'єднання вільних блоків. Справді, прикро, якщо ми маємо сто вільних блоків по одному кілобайту і не можемо зробити з них один блок сто кілобайт. Але якщо всі ці блоки розташовані в пам'яті один за одним, а ми не можемо їх при цьому поєднати - це просто принизливо. Крім того, якщо ми вміємо поєднувати блоки і бачимо, що об'єднаний блок обмежений зверху значенням brklevel, то ми можемо замість поміщення цього блоку в список просто зменшити значення brklevel і, таким чином, повернути непотрібну пам'ять системі.
Розглянемо способи вирішення цієї проблеми. Один спосіб згадувався в описі алгоритму близнюків, але він придатний лише в окремих випадках.
Набагато простіше запам'ятовувати в дескрипторі блоку вказівники надескриптори сусідніх блоків Трохи розвинувши цю ідею, ми приходимо до методу, який згадувався на початку розділу. Цей метод називається алгоритмом парних міток і полягає в тому, що ми додаємо до кожного блоку два слова пам'яті.