Ізольовані списки вільних блоків

 

 

Інший важливий клас алгоритмів динамічного розподілу пам’яті зводиться до організації списків вільних блоків у структуру даних, що містить масив розмірів блоків, причому кожен елемент масиву пов’язаний зі списком описувачів вільних блоків. Пошук потрібного блоку зводиться до пошуку потрібного розміру в масиві та вибору елемента із відповідного списку. Таку технологію називають технологією ізольованих списків вільних блоків(segregated free lists) або ізольованою пам’яттю (segregated storage). Структура ізольованих списків вільних блоків забражена на рисунку 2.3.

Рисунок 2.3 Ізольовані списки вільних блоків

Проста ізольована пам’ять

У разі використання цього підходу поділу більших блоків не відбувається, щоб задовольнити запит на виділення блоку меншого розміру. Коли під час обслуговування запиту на виділення пам’яті з’ясовують, що список вільних блоків цього розміру порожній, видають запит операційній системі на розширення динамічної ділянки пам’яті (наприклад, через системний виклик brk()). Після цього виділені сторінки розбивають на блоки одного розміру, які й додають у відповідний список вільних блоків. У результаті сторінка пам’яті завжди містить блоки одного розміру.

Основними перевагами такого підходу є те, що немає необхідності зберігати для кожного об’єкта інформацію про його розмір. Тепер така інформація може бути збережена для цілої сторінки об’єктів, що особливо вигідно тоді, коли розмір об’єкта малий і на сторінці таких об’єктів міститься багато.

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

Ізольований пошук підходящого блока

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

Під час використання підходу точних списків підтримують масив списків для кожного можливого розміру блоку. Такий масив може бути досить великим, але достатньо зберігати тільки ті його елементи, для яких справді задані списки.

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

Підхід класів розмірів зі списками діапазонів зводиться до того, що в кожному списку містяться описувачі вільних блоків, довжина яких потрапляє в деякий діапазон. Це означає, що блоки у списку можуть бути різного розміру (у межах діапазону). Для пошуку у списку використовують алгоритм найкращого підходящого або першого підходящого.

 

 

Системи двійників

 

 

Система двійників (buddy system) – підхід до динамічного розподілу пам’яті, який дає змогу рідше розбивати на частини більші блоки для виділення пам’яті під блоки меншого розміру, знижуючи цим зовнішню фрагментацію. Вона містить у собі два алгоритми: виділення та вивільнення пам’яті. Розглянемо найпростішу бінарну систему двійників (binary buddy system).

У разі використання цієї системи пам’ять розбивають на блоки, розмір яких є степенем числа 2: 2К, L £ К £ U, де 2L – мінімальний розмір блоку; 2U – максимальний розмір блоку (він може бути розміром доступної пам’яті, а може бути й меншим).

Алгоритм виділення пам’яті

Опишемо принцип роботи алгоритму виділення пам’яті:

- Коли надходить запит на виділення блоку пам’яті розміру М, відбувається пошук вільного блоку підходящого розміру (такого, що 2К-1 £ М £ 2К). Якщо блок такого розміру є, його виділяють. У разі відсутності блоку такого розміру беруть блок розміру 2К+1 ділять навпіл на два блоки розміру 2К і перший із цих блоків виділяють; другий залишається вільним і стає двійником (buddy) першого. Робота алгоритму на цьому завершується.

- За відсутності блоку розміром 2К+1 беруть найближчий вільний блок, більший за розміром від М, наприклад блок розміру 2К+N. Він стає поточним блоком. Якщо немає жодного блоку, більшого за М, повертають помилку.

- Після цього починають рекурсивний процес розподілу блоку. На кожному кроці цього процесу поточний блок ділиться навпіл, два отриманих блоки стають двійниками один одного, після цього перший із них стає поточним (і ділиться далі), а другий залишають вільним і надалі не розглядають. Для блоку розміру 2K+N процес завершують через N кроків поділу отриманням двох блоків розміру 2К. Перший із цих блоків виділяють, другий залишають вільним. Внаслідок поділу отримують N пар блоків-двійників.

Для ілюстрації цього алгоритму наведено приклад на рисунку 2.4.

Припустимо, що в системі є вільний блок розміром 512 Кбайт (1) і надійшов запит на виділення блоку на 100 Кбайт (блоку А).

Ділимо блок на два по 256 Кбайт, з них перший робимо поточним, а другий залишаємо його двійником (2). Після цього знову ділимо перший блок на два по 128 Кбайт. Це – потрібний розмір, тому виділяємо для А перший із цих блоків, а другий залишаємо його двійником (3). Тепер маємо один вільний блок на 128 Кбайт (двійник виділеного блоку) і один – на 256 Кбайт. У результаті для блоку А виділено 128 Кбайт.

Тепер надходить запит на виділення блоку на 30 Кбайт (блоку В). У цьому разі найближчим за розміром більшим вільним блоком буде блок на 128 Кбайт; система розділить його на два двійники по 64 Кбайт (4), а потім перший з них – на два по 32 Кбайт. Це – потрібний розмір, тому для В буде виділено перший із цих блоків, а другий залишать його двійником (5). У результаті для блоку В виділено 32 Кбайт.

Нарешті, надходить запит на виділення блоку на 200 Кбайт (блоку С). У цьому разі є підходящий блок на 256 Кбайт, тому його негайно виділяють (6).

Алгоритм вивільнення пам’яті

Алгоритм вивільнення пам’яті використовує утворення двійників у процесі виділення пам’яті (насправді двійниками можуть вважатися будь-які два суміжні блоки однакового розміру).

- Заданий блок розміру 2К вивільняють.

- Коли цей блок має двійника і він вільний, їх об’єднують в один блок удвічі більшого розміру 2К+1.

- Якщо блок, отриманий на кроці 2, має теж двійника, їх об’єднують у блок розміру 2К+2.

- Цей процес об’єднання блоків повторюють доти, поки не буде отримано блок, для якого не знайдеться вільного двійника.

Розглянуто, як вивільняється пам’ять у наведеному раніше прикладі.

- Спочатку вивільнимо пам’ять з-під блоку В. Для нього є вільний двійник, тому їх об’єднують в один блок розміру 64 Кбайт.

- Для цього блоку також є вільний двійник (див. (4)), і їх теж об’єднують у блок розміру 128 Кбайт (7).

- Тепер вивільняють пам’ять з-під блоку С. Він вільних двійників не має, тому об’єднання не відбувається (8).

- Нарешті вивільняють пам’ять з-під блоку А. Його об’єднують із двійником у блок розміру 256 Кбайт, але в того теж є вільний двійник (вивільнений з-під С), його об’єднують з тим; у результаті знову виходить один вільний блок на 512 Кбайт (9).

 

Рисунок 2.4 Система двійників

Цей підхід за продуктивністю випереджає інші алгоритми динамічного розподілу, він особливо ефективний для великих масивів пам’яті. Головним його недоліком є значна внутрішня фрагментація (як можна помітити, у наведеному прикладі було виділено на 86 Кбайт пам’яті більше, ніж потрібно), тому для розподілу блоків малого розміру частіше використовують інші підходи, зокрема розглянуті раніше методи послідовного пошуку або ізольованих списків вільних блоків.