Послідовний пошук підходящого блоку
Розглянемо конкретні підходи до реалізації динамічного розподілу пам’яті. Спочатку зупинимося на алгоритмах, які зводяться до послідовного перегляду вільних блоків системи і вибору одного з них. Такі алгоритми відомі досить давно і докладно описані в літературі [41, 44, 109]. До цієї групи належать алгоритми найкращого підходящого (best fit), першого підходящого (first fit), наступного підходящого (next fit) і деякі інші, близькі до них. Ця група алгоритмів дістала назву алгоритми послідовного пошуку підходящого блоку (sequential fits).
Алгоритм найкращого підходящого
Алгоритм найкращого підходящого зводиться до виділення пам’яті із вільного блоку, розмір якого найближчий до необхідного обсягу пам’яті. Після такого виділення у пам’яті залишатимуться найменші вільні фрагменти. Структури даних вільних блоків у цьому випадку можуть об’єднуватися у список, кожний елемент якого містить розмір блоку і покажчик на наступний блок. Під час вивільнення пам’яті має сенс поєднувати суміжні вільні блоки.
Рис. 10.2.Алгоритм найкращого підходящого
Основною особливістю розподілу пам’яті відповідно до цього алгоритму є те, що при цьому залишаються вільні блоки пам’яті малого розміру (їх називають «ошурками», sawdust), які погано розподіляються далі. Однак, практичне використання цього алгоритму свідчить, що цей недолік суттєво не впливає на його продуктивність.
Алгоритм першого підходящого
|
|
|
Алгоритм першого підходящого полягає в тому, що вибирають перший блок, що підходить за розміром (рис. 10.3). Структури даних для цього алгоритму можуть бути різними: стек (LIFO), черга (FIFO), список, відсортований за адресою. Алгоритм зводиться до сканування списку і вибору першого підхожого блоку. Якщо блок значно більший за розміром, ніж потрібно, він може бути розділений на кілька блоків. Різні модифікації цього алгоритму на практиці виявляють себе по-різному.
Так, алгоритм першого підходящого, який використовує стек, зводиться до того, що вивільнений блок поміщають на початок списку (вершину стека). Такий підхід простий у реалізації, але може спричинити значну фрагментацію. Прикладом такої фрагментації є ситуація, коли одночасно виділяють більші блоки пам’яті на короткий час і малі блоки – на довгий. У цьому разі вивільнений великий блок буде, швидше за все, відразу використаний для виділення пам’яті відповідно до запиту на малий обсяг (і після цього не вивільниться найближчим часом).
Рис. 10.3. Алгоритм першого підходящого
З іншого боку, така проблема не виникає, якщо список вільних блоків організовують за принципом FIFO (вільні блоки додають у кінець цього списку) або впорядковують за адресою. Ці модифікації алгоритму першого підходящого використовують найчастіше.
|
|
|
Порівняння алгоритмів послідовного пошуку підходящого блоку
З погляду фрагментації алгоритми найкращого підходящого та першого підходящого практично рівноцінні (фрагментацію за умов реального навантаження підтримують приблизно на рівні 20 %). Такий результат може здатися досить несподіваним, оскільки в основі цих алгоритмів лежать різні принципи. Можливе пояснення полягає в тому, що у разі використання алгоритму першого підходящого список вільних блоків згодом стає впорядкованим за розміром (блоки меншого розміру накопичуються на початку списку), тому для невеликих об’єктів (а саме такі об’єкти здебільшого виділяє розподілювач) він працює майже так само, як і алгоритм найкращого підходящого.
Алгоритм першого підхожого звичайно працює швидше, оскільки пошук найкращого підходящого вимагає перегляду всього списку вільних блоків.
Головним недоліком алгоритмів послідовного пошуку вільних блоків є їхня недостатня масштабованість у разі збільшення обсягу пам’яті. Що більше пам’яті, то довшими стають списки, внаслідок чого зростає час їхнього перегляду.
Дата добавления: 2018-04-05; просмотров: 1084; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!