Головна

Алгоритми динамічного управління пам'яттю

  1.  Системи управління базами даних наступного покоління
  2.  I. Про органи управління промисловістю
  3.  I. Психологія управління як наука. 1 сторінка
  4.  I. Психологія управління як наука. 2 сторінка
  5.  I. Психологія управління як наука. 3 сторінка
  6.  I. Психологія управління як наука. 4 сторінка
  7.  I. Психологія управління як наука. 5 сторінка

при динамічному виділенні пам'яті запити на виділення пам'яті формуються під час виконання завдання. Динамічне виділення, таким чином, протиставляється статичному, коли запити формуються на етапі компіляції програми. В кінцевому підсумку, і ті, і інші запити нерідко обробляються одним і тим же алгоритмом виділення пам'яті в ядрі ОС. Але в багатьох випадках статичний виділення можна реалізувати набагато простішими способами, ніж динамічне. Головна складність тут в тому, що при статичному виділенні здається неприродною - і тому рідко потрібно - можливість відмовитися від раніше виділеної пам'яті. При динамічному ж розподілі часто потрібно надати можливість відмовлятися від запитаних блоків так, щоб звільнена пам'ять могла використовуватися для задоволення наступних запитів. Таким чином, динамічний розподільник замість простої кордону між зайнятою і вільною пам'яттю (якої досить в простих випадках статичного розподілу) змушений зберігати список можливо незв'язних областей вільної пам'яті, званий пулом або купою.

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

Залежно від розв'язуваної задачі використовуються різні стратегії пошуку вільних блоків пам'яті. Наприклад, програма може виділяти блоки однакового розміру або декількох фіксованих розмірів. Це сильно полегшує вирішення завдань дефрагментації і пошуку вільних ділянок ОЗУ.

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

Можливі також ситуації, коли деякі із зайнятих блоків можна перемістити по пам'яті - тоді є можливість проводити дефрагментацію пам'яті, переміщення зайнятих блоків пам'яті з метою об'єднати вільні ділянки. Наприклад, функцію realloco в ранніх реалізаціях системи UNIX можна було використовувати саме для цієї мети.

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

Втім, випадкові запити - далеко не найгірший варіант. Навіть не знаючи Деталей стратегії управління купою, досить легко побудувати програму, яка "зіпсує життя" багатьом поширеним алгоритмам.

Наведений приклад побудований на тому припущенні, що система виділяє нам блоки пам'яті, розмір яких відповідає запрошенням з точності до байта. Якщо ж мінімальна одиниця виділення дорівнює 32 байтам, ніякої зовнішньої фрагментації наш приклад не викличе: на кожен запит буде виділятися один блок. Але при цьому ми зіткнемося зі зворотним проблемою, яка називається внутрішньої фрагментацією: якщо система вміє виділяти тільки блоки, кратні 32 байтам, а нам реально потрібно 15 або 47 байт, то 17 байт на блок виявляться, втрачені.

Чим більше розмір одиниці виділення, тим менше нам загрожує фрагментація зовнішня, і тим більші втрати забезпечує фрагментація внутрішня. Величина втрат залежить від середнього розміру запрошуваного блоку. Груба оцінка свідчить про те, що в кожному блоці в середньому втрачається половина одиниці виділення, т. Е. Ставлення використаної пам'яті до втраченого

1 Ns

ної буде ---, де N- кількість виділених блоків, s - розмір еди-

2 N1

ниці виділення, а 7 - середній розмір блоку. Спростивши цю формулу, ми отримаємо вираз для величини втрат: ^ J, т. Е. Втрати лінійно зростають зі збільшенням розміру одиниці виділення.

Якщо середній розмір блоку порівняємо з одиницею виділення, наша формула втрачає точність, але все одно дає хорошу оцінку порядку величини втрат. Так, якщо s = 7, наша формула дає 50% втрат, що цілком узгоджується зі здоровим глуздом: якщо запитуваний блок трохи коротше мінімально можливого, втрачається тільки це "трохи"; зате якщо він трохи довше, то для нього відводиться два мінімальних блоку, один з яких втрачається майже весь. Точна величина втрат визначається розподілом запитуваних блоків по довжині, але ми вважаємо за краще залишити висновок точної формули цікавому читачеві.

Варіанти алгоритмів розподілу пам'яті досліджувалися ще в 50-і роки. I Підсумки багаторічного вивчення цієї проблеми наведені в [Кнут 2000] та багатьох інших підручниках.

Зазвичай всі вільні блоки пам'яті об'єднуються в двонаправлений зв'язаний список. Список повинен бути двонаправленим для того, щоб з нього в будь-який момент можна було витягти будь-який блок. Втім, якщо всі дії по вилученню блоку виробляються після пошуку, то можна злегка ускладнити процедуру пошуку і завжди зберігати покажчик на попередній блок. Це вирішує проблему вилучення і можна обмежитися односпрямованим списком. Біда тільки в тому, що багато алгоритми при об'єднанні вільних блоків витягують їх зі списку відповідно до адреси, тому для таких алгоритмів двонаправлений список конче потрібна. Пошук в списку може вестися трьома способами: до знаходження першого підходящого (first fit) блоку, до блоку, розмір якого найближче до заданого - найбільш підходящого (best fit), і, нарешті, до знаходження найбільшого блоку, найменш придатного (worst fit).

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

Поміщати блоки в відсортований масив ще гірше - час вставки стає О (л + log (fl)) і з'являється обмеження на кількість блоків. Використання хеш-таблиць або довічних дерев вимагає накладних витрат і ускладнень програми, які себе в підсумку не виправдовують. На практиці стратегія worst fit використовується при розміщенні простору в файлових системах, наприклад в HPFS, але жодного прикладу її використання для розподілу оперативної пам'яті автору невідомо. Найчастіше застосовують несортоване список. Для пошуку найвідповіднішого ми зобов'язані переглядати весь список, в той час як перший відповідний може виявитися в будь-якому місці, і середній час пошуку буде менше. Наскільки менше - залежить від відношення кількості відповідних блоків до загальної кількості. (Читачі, знайомі з теорією ймовірності, можуть самостійно обчислити цю залежність.) У загальному випадку best fit збільшує фрагментацію пам'яті. Дійсно, якщо ми знайшли блок з розміром більше заданого, ми повинні відокремити "хвіст" і позначити його як новий вільний блок. Зрозуміло, що в разі best fit середній розмір цього "хвоста" буде маленьким, і ми в результаті отримаємо велику кількість дрібних блоків, які неможливо об'єднати, так як простір між ними зайнято.

У тих ситуаціях, коли ми розміщуємо блоки декількох фіксованих розмірів, цей недолік ролі не грає і стратегія best fit може виявитися виправданою. Однак бібліотеки розподілу пам'яті розраховують на загальний випадок, і в них зазвичай використовуються алгоритми first fit.

При використанні first fit з лінійним двонаправленим списком виникає специфічна проблема. Якщо кожен раз переглядати список з одного і того ж місця, то великі блоки, розташовані ближче до початку, будуть частіше віддалятися. Відповідно, дрібні блоки будуть накопичуватися на початку списку, що збільшить середній час пошуку. Простий спосіб боротьби з цим явищем полягає в тому, щоб переглядати список то в одному напрямку, то в іншому. Більш радикальний і ще простіший метод полягає в наступному: список робиться кільцевим, і кожен пошук починається з того місця, де ми зупинилися минулого разу. В цей же місце займуть звільнилися блоки. В результаті список дуже ефективно перемішується і ніякої "антісортіровкі" не виникає.

Розробник програми динамічного розподілу пам'яті зобов'язаний вирішити ще одну важливу проблему, а саме - об'єднання вільних блоків. Дійсно, прикро, якщо ми маємо сто вільних блоків по одномукілобайту і не можемо зробити з них один блок в 100 кілобайт. Але якщо всі ці блоки розташовані в пам'яті один за іншим, а ми не можемо їх прицьому об'єднати - це просто принизливо.

Крім того, якщо ми вміємо поєднувати блоки, і бачимо, що об'єднання блок обмежений зверху значенням brkievel, то ми можемо, замість приміщення цього блоку в список, просто зменшити значення brkievel і, таким чином, повернути непотрібну пам'ять системі.

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

Набагато простіше запам'ятовувати в дескрипторі блоку покажчики на дескриптори сусідніх блоків. Трохи розвинувши цю ідею, ми приходимо до методу, який називається алгоритмом парних міток і полягає в тому, ми додаємо до кожного блоку по два слова пам'яті. Саме слова НЕ байта. Справа в тому, що потрібно додати досить місця, що зберігати в ньому розмір блоку в байтах або словах. Зазвичай таке число займає стільки ж місця, скільки і адреса, а розмір слова зазвичай дорівнює розміру адреси. На х86 в реальному режимі це не так, але це взагалі досить дивний процесор.

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

Уявімо, що ми звільняємо блок з адресою addr. Вважаємо, addr має тип word *, і при додаванні до нього цілих чисел результуюча адреса буде відраховуватися в словах, як в мові С. Для то щоб перевірити, чи вільний сусід перед ним, ми повинні подивитися слово з адресою addr - 2. Якщо воно негативно, то сусід зайнятий, і ми повинні залишити його в спокої. Якщо ж воно позитивно, то ми можемо легко визначити адресу початку цього блоку як addr - addr [-2].

Визначивши адресу початку блоку, ми можемо легко об'єднати цей блок: блоком addr, нам потрібно тільки скласти значення міток-дескрипторів записати їх в дескриптори нового великого блоку. Нам навіть не потрібно буде додавати звільняється блок в список і витягувати звідти його сусіда!

Схожим чином приєднується і сусід, що стоїть після нього. Єдина відмінність полягає в тому, що цього сусіда все-таки потрібно вставляти зі списку вільних блоків.

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

Отже, найкращим з відомих універсальних алгоритмів динамічного розподілу пам'яті є алгоритм парних міток з об'єднанням вільних блоків в двонаправлений кільцевий список і пошуком за принципом first fit. Цей алгоритм забезпечує прийнятну продуктивність майже для всіх стратегій розподілу пам'яті, використовуваних в прикладних програмах.

Алгоритм парних міток був запропонований Дональдом Кнутом на початку 60-х. У третьому виданні класичної книги [Кнут, 2000], цей алгоритм наводиться під назвою "звільнення з дескрипторами кордонів". У сучасних системах використовуються і більш складні структури дескрипторів, але завжди ставиться завдання забезпечити пошук сусідів блоку по адресного простору за фіксований час. У цьому сенсі, практично всі сучасні підпрограми динамічного виділення пам'яті (зокрема, реалізації стандартної бібліотеки мови С) використовують аналоги алгоритму парних міток. Інші відомі підходи або просто гірше, ніж цей, або проявляють свої переваги тільки в спеціальних випадках.

реалізація malloc в бібліотеці GNU LibC (реалізація стандартної бібліотеки мови С в рамках freeware проекту GNU Not Unix) (приклад 4.3) використовує змішану стратегію: блоки розміром більше 4096 байт виділяються стратегією first fit з двусвязного кільцевого списку з використанням циклічного перегляду, а звільняються за допомогою методу, який в зазначеному раніше сенсі схожий на алгоритм парних міток. Всі виділені таким чином блоки матимуть розмір, кратний 4096 байт. Блоки меншого розміру об'єднуються в черзі з розмірами, пропорційними ступенями двійки, як в описаному далі алгоритмі близнюків. Елементи цих черг називаються фрагментами. На відміну від алгоритму близнюків, ми не об'єднуємо при звільненні парні фрагменти. Замість цього, ми розбиваємо 4-кілобайтовий блок на фрагменти однакового розміру. Якщо, наприклад, наша програма зробить запити на 514 і 296 байт пам'яті, їй будуть передані фрагменти в 1024 і 512 байт відповідно. Під ці фрагменти будуть виділені повні блоки в 4 кілобайти, і всередині них буде виділено по одному фрагменту. При повторних запитів на фрагменти такого ж розміру будуть використовуватися вільні фрагменти цих блоків. Поки хоча б один фрагмент блоку зайнятий, весь блок вважається зайнятим. Коли ж звільняється останній фрагмент, блок повертається в пул.

Описувачі блоків зберігаються не разом з самими блоками, а в окремому динамічному масиві _heapinfо. Описувач заводиться не так на безперервну послідовність вільних байтів, а на кожні 4096 байт пам'яті (в прикладі 4.3 саме це значення приймає константа blocksize). Завдяки цьому ми можемо обчислити індекс описателя в _heapinfо, просто розділивши на 4096 зміщення вивільняється блоку від початку пулу. Для нефрагментовані блоків описувач зберігає стан (зайнятий-вільний) і розмір безперервної ділянки, до якого належить блок. Завдяки цьому, як і в алгоритмі парних міток, ми легко можемо знайти сусідів вивільняється ділянки пам'яті і об'єднати їх у великій безперервний ділянку.

Для фрагментованих блоків описувач зберігає розмір фрагмента, лічильник зайнятих фрагментів і список вільних. Крім того, всі вільні Фрагменти одного розміру об'єднані в загальний список - заголовки цих списків зібрані в масив _fraghead.

Використовувана структура даних займає більше місця, ніж застосовувана в Класичному алгоритмі парних міток, але скорочує обсяг списку свободах блоків і тому має більш високу продуктивність. Середній о6'ем блоку, що виділяється сучасними програмами для ОС загального призначення, вимірюється багатьма кілобайтами, тому в більшості випадків підвищення накладних витрат пам'яті виявляється терпимо.

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

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

Для вирішення цієї проблеми нам необхідно ввести будь-яке обмеження на розміри виділених блоків. Наприклад, можна зажадати, щоб ці розміри дорівнювали числам Фібоначчі (послідовність цілих чисел, в якій Fi+1 = Ft + Fi-1). У цьому випадку, якщо нам потрібно Ft байт, а в наявності є тільки блок розміру Fi+1, ми легко можемо отримати два блоки - один необхідного розміру, а інший - Fi-1 який теж не пропаде. Так, будь-яке обмеження на розмір приведе до внутрішньої фрагментації, але так чи велика ця плата за гарантований час пошуку блоку?

На практиці, числа Фібоначчі не використовуються. Однією з причин, по-видимому, є відносна складність обчислення такого Ft , яке менше необхідного розміру блоку. Інша причина - складність об'едіненіясвободних блоків із суміжними адресами в блок більшого розміру. Зате широке застосування знайшов алгоритм, який обмежує послідовні розміри блоків більш простою залежністю - ступенями числа 2: 512 байт, 1 Кбайт, 2 Кбайт і т. Д. Така стратегія називається алгоритмом близнюків.

Одна з переваг цього методу полягає в простоті об'єднання блоків при їх звільненні. Адреса блоку-близнюка виходить простим інвертуванням відповідного біта в адресі нашого блоку. Потрібно тільки перевірити, чи вільний цей близнюк. Якщо він вільний, то ми об'єднуємо братів в блок вдвічі більшого розміру, і т. Д. Навіть у найгіршому випадку час пошуку не перевищує О (log (Smax) -log (Smjn)), Де Sтах і Smin позначають, відповідно, максимальний і мінімальний розміри використовуваних блоків. Це робить алгоритм близнюків важко замінним для ситуацій, в яких необхідно гарантоване час реакції - наприклад, для завдань реального часу. Часто цей алгоритм або його варіанти використовується для виділення пам'яті усередині ядра ОС.

Існують і більш складні варіанти застосування описаного вище підходу. Наприклад, пул вільної пам'яті Novell Netware складається з 4 черг з кроком 16 байт (для блоків розмірами 16, 32, 48, 64 байта), 3 черг з кроком 64 байта (для блоків розмірами 128, 192, 256 байт) і п'ятнадцяти черг з кроком 256 байт (від 512 байт до 4 Кбайт). При придбанні більшого розміру виділяється цілком сторінка. Цікаво, що можливості роботи в режимі реального часу, властиві цій витонченої стратегії, в Netware практично не використовуються.

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

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




 Історія операційних систем |  Онтогенез повторює філогенез |  Основні функції операційних систем |  Системи віртуальних машин |  Системи реального часу |  Сімейства операційних систем |  Вибір операційної системи |  відкриті системи |  Подання текстових даних |  подання зображень |

© um.co.ua - учбові матеріали та реферати