Герой мав звичку складати недопалки в шкіряний кисет і вживати їх для виготовлення нових самокруток. Таким чином, згідно з велінням невблаганного закону середніх чисел, якусь частину цього тютюну він курив протягом багатьох років.
Т. Пратчетт
При динамічному виділенні пам'яті запити на виділення пам'яті формуються під час виконання завдання. Динамічне виділення, таким чином, протиставляється статичному. коли запити формуються на етапі компіляції програми. В кінцевому підсумку, і ті, і інші запити нерідко обробляються одним і тим же алгоритмом виділення пам'яті в ядрі ОС. Але в багатьох випадках статичний виділення можна реалізувати набагато більш простими способами, ніж динамічне. Головна складність тут в тому, що при статичному виділенні здається неприродною - і тому рідко потрібно - можливість відмовитися від раніше виділеної пам'яті. При динамічному ж розподілі часто потрібно надати можливість відмовлятися від запитаних блоків так, щоб звільнена пам'ять могла використовуватися для задоволення наступних запитів. Таким чином, динамічний розподільник замість простої кордону між зайнятою і вільною пам'яттю (якої досить в простих випадках статичного розподілу) змушений зберігати список можливо незв'язних областей вільної пам'яті, званий пулом або купою.
Багато послідовності запитів пам'яті і відмов від неї можуть привести до того, що вся доступна пам'ять буде розбита на блоки маленького розміру, і спроба виділення великого блоку завершиться невдачею, навіть якщо сума довжин доступних маленьких блоків набагато більше необхідної. Це явище називається фрагментацією пам'яті (рис. 4.3). Іноді використовують більш точний термін - зовнішня фрагментація (що таке внутрішня фрагментація буде розказано далі). Крім того, велика кількість блоків вимагає тривалого пошуку. Існує також багато дрібних труднощів різного роду. На щастя, людство займається проблемою розподілу пам'яті вже давно і знайдено багато хороших або прийнятних рішень.
Залежно від розв'язуваної задачі використовуються різні стратегії пошуку вільних блоків пам'яті. Наприклад, програма може виділяти блоки однакового розміру або декількох фіксованих розмірів. Це сильно полегшує вирішення завдань дефрагментації і пошуку вільних ділянок ОЗУ.
Можливі ситуації, коли блоки звільняються в порядку, зворотному тому, в якому вони виділялися. Це дозволяє звести виділення пам'яті до ск-вої структурі, т. Е. Фактично, повернутися до простого запам'ятовування кордону між зайнятою і вільною пам'яттю.
Можливі також ситуації, коли деякі із зайнятих блоків можна перемістити по пам'яті - тоді є можливість проводити дефрагментацію пам'яті. переміщення зайнятих блоків пам'яті з метою об'єднати вільні ділянки. Наприклад, функцію realloc () в ранніх реалізаціях системи UNIX можна було використовувати саме для цієї мети.
Мал. 4.3. зовнішня фрагментація
У стандартних бібліотечних функціях мов високого рівня, таких як
malloc / free / realloc в С, new / dispose в Pascal і т. д. як правило, використовуються алгоритми, розраховані на найбільш загальний випадок: програма запитує блоки випадкового розміру у випадковому порядку і звільняє їх також випадковим чином.
Втім, випадкові запити - далеко не найгірший варіант. Навіть не знаючи деталей стратегії управління купою, досить легко побудувати програму, яка "зіпсує життя" багатьом поширеним алгоритмам (приклад 4.2).
Приклад 4.2. Приклад послідовності запитів пам'яті
while (TRUE) void * bl = malloc (random (10)); / * Випадковий розмір від 0 до 10 байт * / void * Ь2 = malloc (random (lO) +10); Л. від 10 до 20 байт * /
if (И == NULL Ь2 == NULL) / * Якщо пам'яті немає * /
break; / * Вийти з циклу * /
free (b1);
void * Ьз = malloc (150);
/ * Швидше за все, пам'ять не буде виділена * /
В результаті виконання такої програми вся доступна пам'ять буде "порізана на локшину": між будь-якими двома вільними блоками буде розміщений зайнятий блок меншого розміру (рис. 4.4)
Мал. 4.4. Результат роботи програми прикладу 4.2
На щастя, приклад 4.2 має штучний характер. У реальних програмах така ситуація зустрічається рідко, і часто виявляється прошу виправити програму, ніж вносити зміни в універсальний алгоритм управління купою.
Наведений приклад побудований на тому припущенні, що система виділяє нам блоки пам'яті, розмір яких відповідає запрошенням з точністю до байта. Якщо ж мінімальна одиниця виділення дорівнює 32 байтам, ніякої зовнішньої фрагментації наш приклад не викличе: на кожен запит буде виділятися один блок. Але при цьому ми зіткнемося зі зворотним проблемою, яка називається внутрішньої фрагментацією: якщо система вміє риделять тільки блоки, кратні 32 байтам, а нам реально потрібно 15 або 47 байт, то 17 байт на блок виявляться втрачені (рис. 4.5).
Мал. 4.5. Внутрішня фрагментація
Мал. 4.6. Антісортіровка
Мал. 4.7. парні мітки
Мал. 4.8. Об'єднання з використанням парних міток
Примітка
Це дійсно велика перевага, тому що воно значно полегшує виявлення помилок роботи з покажчиками, про які в керівництві по Zortech C / C ++ сказано, що "досвідчені програмісти, почувши це слово [помилка роботи з покажчиками - прим. Авт.], Бліднуть і ховаються під стіл "([Zortech v3.xj).
Мал. 4.9. Фрагменти в реалізації malloc з GNU LibC
Приклад 4.3. Реалізація malloc / fгее в GNU LibC. Функція __default_morecore приведена в прикладі 4.1.
/ * Якщо деякі фрагменти цього блоку вільні, включити цей фрагмент в список фрагментів після першого вільного фрагмента цього блоку. * /
next = (struct list *) ptr;
next-> next = prev-> next;
next-> prev = prev;
prev-> next = next;
if (next-> next! = NULL) next-> next-> prev = next;
++_heapinfо [block] .busy.info.frag.nfree;
else
/ * У цьому блоці немає вільних фрагментів, тому включити цей фрагмент в список фрагментів і анонсувати, що це перший вільний фрагмент в цьому блоці. * /
prev = (struct list *) ptr;
_heapinfo [block] .busy. info. frag. nfree = 1;
_heapinfo [block] .busy. info. frag. first = (unsigned long int)
((Unsigned long int) ((char *) ptr - (char *) NULL)% BLOCKSIZE »type); prev-> next = _fraghead [type] .next; prev-> prev = _fraghead [type]; prev-> prev-> next = prev; if (prev-> next! = NULL)
prev-> next-> prev = prev;
break;
/ * Повернути пам'ять в купу. * / Void
_ Libc_free (ptr) _ ptr_t ptr; register struct alignlist * 1;
if (ptr == NULL) return;
for (1 = _aligned_blocks; 1! = NULL; 1 = l-> next) if (l-> aligned == ptr)
l-> aligned = NULL;
/ * Позначити елемент списку як вільний. * /
ptr = l-> exact;
break;
if (_ free_hook! = NULL) (* _ free_hook) (ptr);
else
_free_internal (ptr);
#include
#ifdef elf_alias
elf_alias (free, cfree);
#endif
До основних недоліків цього алгоритму відноситься неможливість оцінки часу пошуку відповідного блоку, що робить його неприйнятним для завдань реального часу. Для цих задач потрібно алгоритм, який здатний за фіксоване (бажано, невелика) час або знайти відповідний блок пам'яті, або дати обгрунтовану відповідь про те, що відповідного блоку не існує.
Найпростіше вирішити цю задачу, якщо нам потрібні блоки декількох фіксованих розмірів (рис. 4.10). Ми об'єднуємо блоки кожного розміру в свій список. Якщо в списку блоків необхідного розміру нічого немає, ми дивимося в список блоків більшого розміру. Якщо там щось є, ми розрізаємо цей блок на частини, одну віддаємо запитуючої програмою, а другу. Правда, якщо розміри необхідних блоків не кратні один одному, що ми будемо робити із залишком?
Для вирішення цієї проблеми нам необхідно ввести будь-яке обмеження на розміри виділених блоків. Наприклад, можна зажадати, щоб ці розміри дорівнювали числам Фібоначчі (послідовність цілих чисел, в якій Fi + 1 = Fi + Fi-1. У цьому випадку, якщо нам потрібно Fi байт, а в наявності є тільки блок розміру Fi + 1. Ми легко можемо отримати два блоки - один необхідного розміру, а інший - Fi-1. який теж не пропаде. так, будь-яке обмеження на розмір призведе до внутрішньої фрагментації, але так чи велика ця плата за гарантований час пошуку блоку?
Мал. 4.10. Виділення блоків фіксованих розмірів
Мал. 4.11. алгоритм близнюків
Існують і більш складні варіанти застосування описаного вище підходу. Наприклад, пул вільної пам'яті Novell Netware складається з 4 черг з кроком 16 байт (для блоків розмірами 16, 32, 48, 64 байта), 3 черг з кроком 64 байта (для блоків розмірами 128, 192, 256 байт) і п'ятнадцяти черг з кроком 256 байт (від 512 байт до 4 Кбайт). При придбанні більшого розміру виділяється цілком сторінка. Цікаво, що можливості роботи в режимі реального часу, властиві цій витонченої стратегії, в Netware практично не використовуються.
Наприклад, якщо драйвер мережевого інтерфейсу при отриманні чергового пакета даних виявляє, що у нього немає вільних буферів для його прийому, він не намагається виділити новий буфер стандартним алгоритмом. Замість цього, драйвер просто ігнорує прийшли дані, лише збільшуючи лічильник втрачених пакетів. Окремий системний процес стежить за станом цього лічильника і тільки при перевищенні ним деякого порога за деякий інтервал часу виділяє драйверу новий буфер.
Подібний підхід до призначених для користувача даних може здатися цинічним, Але треба згадати, що при передачі даних по мережі можливі і інші Причини втрати пакетів, наприклад псування даних через електромагнітних Перешкод. Тому всі мережеві протоколи високого рівня передбачають кошти пересилки пакетів в разі їх втрати, якими б причинами ця втрата не була викликана. З іншого боку, в системах реального часу ігнорування даних, які ми все одно не в змозі прийняти і обробити, - досить часто використовувана, хоча і не завжди прийнятна стратегія.