Теорія операційної системи

:: Меню ::

Головна
Представлення даних в обчислювальних системах
Машинні мови
Завантаження програм
Управління оперативною пам'яттю
Сегментна і сторінкова віртуальна пам'ять
Комп'ютер і зовнішні події
Паралелізм з точки зору програміста
Реалізація багатозадачності на однопроцесорних комп'ютерах  
Зовнішні пристрої
Драйвери зовнішніх пристроїв
Файлові системи
Безпека
Огляд архітектури сучасних ОС

:: Друзі ::

Карта сайту
 

:: Статистика ::

 

 

 

 

 

Если у вас возникнут вопросы по изданию полиграфической продукции быстро качественно выполнить задачу любой сложности наша компания оказывает полиграфические услуги, производит полиграфию.
 

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

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

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

Чим більше розмір одиниці виділення, тим менше нам загрожує фрагментація зовнішня, і тим більші втрати забезпечує фрагментація внутрішня. Величина втрат залежить від середнього розміру запрошуваного блоку. Груба оцінка свідчить про те, що в кожному блоці в середньому втрачається половина одиниці виділення, тобто відношення зайнятої пам'яті до втраченої буде де N— кількість виділених блоків, s— розмір одиниці виділення, а — середній розмір блоку. Спростивши цю формулу, ми отримаємо вираження для величини втрат: ,т. е. втрати лінійно зростають із збільшенням розміру одиниці виділення.
Якщо середній розмір блоку порівнянний з одиницею виділення, наша формула втрачає точність, але все одно дає гарну оцінку порядку величини втрат. Так, якщо s = наша формула дає 50% втрат, що цілком узгоджується Із здоровим глуздом: якщо запрошуваний блок ледве коротше мінімально можливого, втрачається лише це "ледве"; зате якщо він ледве довший, то для нього відводиться два мінімальні блоки, один з яких втрачається майже весь. Точна величина втрат визначається розподілом запрошуваних блоків по довжині, але ми вважаємо за краще залишити виведення точної формули цікавому читачеві.
Варіанти алгоритмів розподілу пам'яті досліджувалися еше в 50-х року. Підсумки багатолітнього вивчення цієї проблеми приведені в [Кнут 2000] і багатьох інших підручниках.
Зазвичай всі вільні блоки пам'яті об'єднуються в двонаправлений зв'язаний список. Список має бути двонаправленим для того, щоб з нього у будь-який момент можна було витягувати будь-який блок. Втім, якщо всі дії з витягання блоку проводяться після пошуку, то можна злегка ускладнити процедуру пошуку і завжди зберігати покажчик на попередній блок. Це вирішує проблему витягання і можна обмежитися однонаправленим списком. Беда лише в тому, що багато алгоритмів при об'єднанні вільних блоків витягують їх із списку відповідно до адреси, тому для таких алгоритмів двонаправлений список гостро необхідний.
Пошук в списку може вестися трьома способами: до знаходження першого відповідного (first fit) блоку, до блоку, розмір якого щонайближче до заданому — найбільш відповідного (best fit) і, нарешті, до знаходження найбільшого блоку найменш відповідного (worst fit).
Використання стратегії worst fit має сенс хіба що у поєднанні з сортуванням списку по убуванню розміру. Це може прискорити виділення пам'яті (завжди береться перший блок, а якщо він недостатньо великий, ми з чистою совістю можемо повідомити, що вільної пам'яті немає), але створює проблеми при звільненні блоків: час вставки у відсортований список пропорційно Про (n) де n — розмір списку.
Поміщати блоки у відсортований масив ще гірше — час вставки стає Про (n + log(n)) і з'являється обмеження на кількість блоків. Використання хэш-таблиц або двійкових дерев вимагає накладних витрат і ускладнень програми, які себе у результаті не виправдовують. На практиці стратегія worst fit використовується при розміщенні простору у файлових системах, наприклад в HPFS, але жодного прикладу її використання для розподілу оперативної пам'яті авторові невідомо.
Найчастіше застосовують несортований список. Для знаходження найбільш відповідного ми зобов'язані переглядати весь список, тоді як перший відповідний може опинитися в будь-якому місці, і середній час пошуку буде менший. Наскільки менше — залежить від відношення кількості відповідних блоків до загальної кількості. (Читачі, знайомі з теорією вірогідності, можуть самостійно обчислити цю залежність.)
У спільному випадку best fit збільшує фрагментацію пам'яті. Дійсно, якщо ми знайшли блок з розміром більше заданого, ми повинні відокремити "хвіст" і помітити його як новий вільний блок. Зрозуміло, що в разі best fit середній розмір цього "хвоста" буде маленьким, і ми у результаті отримаємо велику кількість дрібних блоків, які неможливо об'єднати, оскільки простір між ними зайнятий.
У тих ситуаціях, коли ми розміщуємо блоки декількох фіксованих розмірів, цей недолік ролі не грає і стратегія best fit може виявитися виправданою. Проте бібліотеки розподілу пам'яті розраховують на обшпй випадок, і в них зазвичай використовуються алгоритми first fit.
при використанні first fit з лінійним двонаправленим списком виникає специфічна проблема. Якщо кожного разу переглядати список з одного і того ж місця, то великі блоки, розташовані ближче до початку, частіше віддалятимуться. Відповідно, дрібні блоки скупчуватимуться на початку списку, що збільшить середній час пошуку (мал. 4.6). Простий спосіб боротьби з цим явищем полягає в тому, щоб переглядати список то в одному напрямі, то в іншому. Радикальніший і ще простіший метод полягає в наступному: список делаєтся кільцем, і кожен пошук починається з того місця, де ми зупинилися минулого разу. У це ж місце додаються блоки, що визволилися. В результаті список дуже ефективно перемішується і жодного "антисортування" не виникає.

Мал. 4.6. Антисортування

Розробник програми динамічного розподілу пам'яті зобов'язаний вирішити ще одну важливу проблему, а саме — об'єднання вільних блоків. Дійсно, образливо, якщо ми маємо сто вільних блоків по одному кілобайту і не можемо зробити з них один блок в 100 кілобайт. Але якщо всі ці блоки розташовані в пам'яті один за іншим, а ми не можемо їх при цьому об'єднати — це просто принизливо.
Крім того, якщо ми уміємо об'єднувати блоки і бачимо, що об'єднаний блок обмежений зверху значенням brkievel то ми можемо, замість приміщення цього блоку в список, просто зменшити значення brkievel і, таким чином, повернути непотрібну пам'ять системі.
Уявимо собі спершу, що все, що ми знаємо про блок, — це його початкова адреса і розмір. Легко зрозуміти, що це дуже погана ситуація. Дійсно, для об'єднання блоку з сусідами ми повинні знайти їх в списку вільних, або ж переконатися, що там їх немає. Для цього ми повинні проглянути весь список. Як одну з ідей мозкового штурму можна висунути пропозицію сортувати список вільних блоків за адресою.
Набагато простіше запам'ятовувати в дескрипторі блоку покажчики на дескриптори сусідніх блоків. Трохи розвинувши цю ідею, ми приходимо до методу, який називається алгоритмом парних міток і полягає в тому, що ми додаємо до кожного блоку по два слова пам'яті. Саме слова, а не байта. Річ у тому, що потрібно додати досить місця, щоб зберігати в нім розмір блоку в байтах або словах. Звичайне таке число займає стільки ж місця, скільки і адреса, а розмір слова зазвичай дорівнює розміру адреси. На х86 в реальному режимі це не так, але це взагалі досить дивний процесор.
Отже, ми додаємо до блоку два слова — одне перед ним, інше після нього. У обидва слова ми записуємо розмір блоку. Виходить своєрідний дескриптор, який оточує блок. При цьому ми встановлюємо, що значення довжин будуть позитивними, якщо блок вільний, і негативними, якщо блок зайнятий. Можна сказати і навпаки, поважно лише потім дотримувати цю угоду (мал. 4.7).
Уявимо, що ми визволяємо блок з адресою addr. Вважаємо, що addr має типа word * і при додаванні до нього цілих чисел результуюча адреса відлічуватиметься в словах, як в мові С. Для того щоб перевірити, чи вільний сусід перед ним, ми повинні поглянути слово з адресою addr 2 . Якщо воно негативне, то сусід зайнятий, і ми повинні дати спокій йому (мал. 4.8). Якщо ж воно позитивне, то ми можемо легко визначити адресу початку цього блоку як addr - addr[-2].
Визначивши адресу початку блоку, ми можемо легко об'єднати цей блок з блоком addrнам потрібно лише скласти значення міток-дескрипторів і записати їх в дескриптори нового великого блоку. Нам навіть не потрібно буде додавати блок, що визволяється, в список і витягувати звідти його сусіда!

Мал. 4.7. Парні мітки

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

Мал. 4.8. Об'єднання з використанням парних міток

Примітка
Це дійсно велика перевага, оскільки воно значно полегшує виявлення помилок роботи з покажчиками, про які в керівництві по Zortech C/c++ сказано, що "дослідні програмісти, почувши це слово [ помилка роботи з покажчиками — прим. авт.], бліднуть і ховаються під стіл" ([Zortech v3.xj).

Отже, якнайкращим з відомих універсальних алгоритмів динамічного розподілу пам'яті є алгоритм парних міток з об'єднанням вільних блоків в двонаправлений кільцевий список і пошуком за принципом first fit. Цей алгоритм забезпечує прийнятну продуктивність майже для всіх стратегій розподілу пам'яті, використовуваних в прикладних програмах.
Алгоритм парних міток був запропонований Дональдом Кнутом на початку 60-х. У третьому виданні класичної книги [Кнут, 2000], цей алгоритм приводиться під назвою "звільнення з дескрипторами кордонів". У сучасних системах використовуються і складніші структури дескрипторів, але завжди ставиться завдання забезпечити пошук сусідів блоку по адресному про' странству за фіксований час. У цьому сенсі, практично всі сучасні підпрограми динамічного виділення пам'яті (зокрема, реалізації стандартної бібліотеки мови З) використовують аналоги алгоритму парних міток. Інші відомі підходи або просто гірші, ніж цей, або проявляють свої переваги лише в спеціальних випадках.
Реалізація maiioc у бібліотеці GNU LIBC (реалізація стандартною біб-іотеки мови З в рамках freeware проекту GNU Not Unix) (приклад 4.3) використовує змішану стратегію: блоки розміром більше 4096 байт виділяються стратегією first fit з двозвязкового кільцевого списку з використанням щклічеського перегляду, а визволяються за допомогою методу, який в мазанном раніше сенсі схожий на алгоритм парних міток. Всі блоки, що виділяються образом, матимуть розмір, кратний 4096 байтам.
Блоки меншого розміру об'єднуються в черзі з розмірами, пропорційними мірам двійки, як в описаному далі алгоритмі близнят. Елементи цих черг називаються фрагментами (мал. 4.9). На відміну від алгоритму близнят, ми не об'єднуємо при звільненні парні фрагменти. Замість цього, ми розбиваємо 4-кілобайтний блок на фрагменти однакового розміру. Якщо, наприклад, наша програма зробить запити на 514 і 296 байт пам'яті, їй будуть передані фрагменти в 1024 і 512 байт відповідно. Під ці фрагменти будуть виділені повні блоки в 4 кілобайти, і усередині них буде виділено по одному фрагменту. При подальших запитах на фрагменти такого ж розміру використовуватимуться вільні фрагменти цих блоків. Поки хоч би один фрагмент блоку зайнятий, весь блок вважається зайнятим. Коли ж визволяється останній фрагмент, блок повертається в пул.
Описувачі блоків зберігаються не разом з самими блоками, а в окремому динамічному масиві _heapihfo. Описувач заводиться не на безперервну послідовність вільних байтів, а на кожних 4096 байт пам'яті (у прикладі 4.3 саме цього значення набуває константа BLOCKSIZE). Завдяки цьому ми можемо обчислити індекс описувача у _heapinfoпросто розділивши на 4096 зсув блоку, що визволяється, від початку пулу.
Для нефрагментованих блоків описувач зберігає достаток (занят-свободен) і розмір безперервної ділянки, до якої належить блок. Завдяки цьому, як і в алгоритмі парних міток, ми легко можемо знайти сусідів ділянки пам'яті, що визволяється, і об'єднати їх у велику безперервну ділянку.
Для фрагментованих блоків описувач зберігає розмір фрагмента, лічильник зайнятих фрагментів і список вільних. Крім того, всі вільні Фрагменти одного розміру об'єднані в спільний список — заголовки цих
списків зібрані в масив _f raghead.
Використовувана структура даних займає більше місця, чим вживана в Класичному алгоритмі парних міток, але скорочує об'єм списку вільних блоків і тому має вищу продуктивність. Середній об'єм блоку, що виділяється сучасними програмами для ОС спільного призначення, вимірюється багатьма кілобайтами, тому в більшості случа-ев підвищення накладних витрат пам'яті виявляється терпимо.

Мал. 4.9. Фрагменти в реалізації malloc з GNU LIBC

Приклад 4.3. Реалізація malloc/fгєє у GNU LIBC. Функція__default_morecore приведена в прикладі 4.1.

malloc.с
/* Розподільник пам'яті 'malloc'.
Copyright 1990, 1991, 1992 Free Software Foundation Написана в травні 1989 Mike Haertel.
GNU З Library є вільним програмним забезпеченням;
ви можете передавати іншим особам і модифікувати її у відповідності
з положеннями GNU General Public License версії 2 або (по вашому вибору) будь-якій пізнішій версії.
бібліотека GNU З поширюється в надії, що вона буде корисна, але БЕЗ ЯКИХ-НЕБУДЬ ГАРАНТІЙ; навіть без неявно передбачуваних гарантій
КОМЕРЦІЙНІЙ ЦІННОСТІ або ПРИДАТНОСТІ ДЛЯ КОНКРЕТНОЇ МЕТИ.
Детальніше за див. GNU General Public License.
ВИ повинні були отримати копію GNU General Public License
GNU З Library; див. файл COPYING. Якщо ви її не отримали, напишіть за адресою: Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
З автором можна зв'язатися по електронній пошті за адресою mike@ai.rait.edu, або Mike Haertel с/о Free Software Foundation. */
# ifndef _malloc_internal
#define _malloc_internal tinclude <malloc.h>
#endif
#ifdef __ELF_
ipragma weak malloc = __libc_malloc
#endif

/* Як дійсно отримати додаткову пам'ять. */
__ptr_t (*__morecore) __Р ((ptrdiff_t __size))
= __default_morecore_init;
/* Налагоджувальна функція (hook), що надається користувачем, для xmalloc' */
void (*__malloc_initialize_hook) __P ((void));
__ptr_t (*_malloc_hook) __P ((size_t __size)) ;
/* Покажчик на підставу першого блоку. */ char *_heapbase;
* Таблиця інформаційних записів про блоки. Розміщується
через align/__free (не malloc/free). */
malloc_info *_heapinfo;
/* Кількість інформаційних записів. */ static size_t heapsize;
/* Індекс пошуку в інформаційній таблиці. */ size_t _heapindex;
/* Обмежувач допустимих індексів в інформаційній таблиці */ size_t _heaplimit;
#if 1 /* Adapted from Mike */
/* Лічильник великих блоків, розміщених для кожного з розмірів
фрагментів. */
int _fragblocks[BLOCKLOG];
#endif
/* Списки вільних фрагментів по розмірах.
*/ struct list _fraghead[BLOCKLOG];
/* Інструментальні змінні.
*/ size_t __chunks_used; size_t _bytes_used; size_t _chunks_free; size_t _bytes_free;
/* Чи маємо ми досвід? */
/* Are you experienced? */
int malloc initialized;
/* Вирівняне розміщення. */
static __ptr_t align __P ((size_t));
static __ptr_t
align (size)
size_t size; {
__ptr_t result;
unsigned long int adj;
[result = (*__morecore) (size);
adj = (unsigned long int) ((unsigned long int) ((char *) result -
(char *) NULL)) % BLOCKSIZE; lit (adj != 0)
{
adj = BLOCKSIZE - adj; (void) (*_morecore) (adj); result = (char *) result + adj;
}
return result;
/* Набудувати все і запам'ятати, що у нас є. */
/* Set everything up and remember that we have.
*/ static int initialize _ P ( (void) ) ; static int initialize ()
{ if ( malloc initialize hook)
(*__malloc_initialize_hook) ();
heaps ize = HEAP / BLOCKSIZE;
_heapinfo = (malloc_info *) align (heapsize * sizeof (malloc_info) ) ;
if (_heapinfo == NULL)
return 0;
memset (_heapinfo, 0, heapsize * sizeof (malloc_info) ) ; _heapinfo [0] . f ree. size = 0;
_heapinfo[0].free. next = _heapinfo[0]. free.prev = 0; _heapindex = 0;
_heapbase = (char *) _heapinfo; __malloc_initialized = 1; return 1;
/* Отримати вирівняну пам'ять, ініціалізувавши
або нарощуючи таблицю описувачів купи в міру необхідності. static _ ptr_t morecore _ P ( (size_t) ) ; static _ ptr_t,шогесоге (size)
size_t size;
_ ptr_t result;
malloc_info *newinfo, *oldinfo;
size_t newsize;
result = align (size) ; if (result == NULL) return NULL;
/* Перевірити, чи потрібно нам збільшити таблицю описувачів. */ if ((size_t) BLOCK ((char *) result + size) > heapsize) I
newsize = heapsize;
while ( (size_t) BLOCK ((char *) result + size) > newsize)
newsize *= 2;
newinfo = (malloc_info *) align (newsize * sizeof (malloc_info) ) if (newinfo = = NULL) {
(* _ morecore) (-size); return NULL; }
memset (newinfo, 0, newsize * sizeof (malloc_info) ) ; memcpy (newinfo, _heapinfo, heapsize * sizeof (malloc_info) ) ; oldinfo = _heapinfo;
newinfo[BLOCK (oldinfo) ].busy. type = 0; newinfo [BLOCK (oldinfo) ] .busy. info. size
= BLOCKIFY (heapsize * sizeof (malloc_info) ) ; _heapinfo = newinfo; _free_internal (oldinfo) ; heapsize = newsize;
_heaplimit = BLOCK ((char *) result + size) ; return result; I
/* Виділити пам'ять з купи. */ ptr t
Глава 4. Управління оператівної
libcjnalloc (size) size_t size;
I
ptr_t result;
size t block, blocks, lastblocks, start; register size_t i; struct list *next;
/* Деякі програми викликають malloc (0) . Ми це допускаємо. */
lif °
if (size == 0)
return NULL; #endif
if (! malloc initialized) if ( '.initialize () ) return NULL;
if ( _ malloc_hook != NULL)
return (*__malloc_hook) (size) ;
if (size < sizeof (struct list) ) size = sizeof (struct list) ;
/* Визначити політику розміщення на підставі розміру запиту. */ if (size <= BLOCKSIZE / 2) {
/* Маленькі запити отримують фрагмент блоку.
Визначуваний двійковий логарифм розміру фрагмента.
*/ register size_t log = 1; — size; while ( (size /= 2) != 0)
/* Проглянути списки фрагментів на предмет вільного
фрагмента бажаного розміру. */ next = _f raghead[ log].next; if (next != NULL)
I
введення в операційні системи
/* Знайдені вільні фрагменти цього розміру.
Виштовхнути фрагмент із списку фрагментів і повернути його. Відновити лічильники блоку nfree і first.
*/ result = ( _ ptr_t) next; next->prev->next = next->next; if (next->next != NULL)
next->next->prev = next->prev; block = BLOCK (result); if
( — _heapinf про [block] .busy. info. frag. nfree != 0)
_heapinfo [block] .busy. info. frag. first = (unsigned long int)
((unsigned long int) ((char *) next->next — (char *) NULL) % BLOCKSIZE) » log;
/* Відновити статистику. */
++_chunks_used;
_bytes_used += 1 « log;
--_chunks_f ree ;
_bytes_free -= 1 « log; t
else
/* Немає вільних фрагментів бажаного розміру. Слід узяти новий блок; поділити його на фрагменти і повернути перший. */ result = _ libc_malloc (BLOCKSIZE) ; if (result == NULL)
return NULL; #if 1 /* Adapted from Mike */
++_fragblocks [log] ; #endif
/* Зв'язати всі фрагменти, окрім першого, в список вільних. */ for (i = 1; i < (size_t) (BLOCKSIZE » log); ++i) I
next = (struct list *) ((char *) result + (i « log)); next->next = _fraghead[log].next; next->prev = &_fraghead[log] ; next->prev->next = next; if (next->next ! = NULL) next->next->prev = next;
}
/* Ініціалізувати лічильники nfree і first для цього блоку. */ block = BLOCK (result); _heapinfо[block].busy.type = log;
_heapinfо[block].busy.info.frag.nfree = i — I; heapinfo[block].busy.info.frag.first = i — 1;
_chunks_free += (BLOCKSIZE » log) - 1;
_bytes_free += BLOCKSIZE - (1 « log); _bytes_used -= BLOCKSIZE - (1 « log);
} else
{
/* Великі запити отримують один або більше блоки.
Проглянути список вільних циклічно, починаючи з крапки, де ми були востаннє. Якщо ми пройдемо повний круг, не виявивши досить великого блоку, ми повинні будемо запитати ще пам'ять в системи. */
blocks = BLOCKIFY (size);
start = block = _heapindex;
while (_heapinfо[block].free.size < blocks)
block = _heapinfо[block].free.next; if (block = = start)
/* Необхідно узяти більше [пам'яті] в системи.
Перевірити, чи не буде нова пам'ять продовженням останнього вільного блоку; якщо це так, нам не треба буде запрошувати так багато.
*/ block = _heapinfo[0].free.prev; lastblocks = _heapinfо[block].free.size; if (_heaplimit != 0 && block + lastblocks == _heaplimit &&
(*__morecore) (0) == ADDRESS (block + lastblocks) &&
(morecore ((blocks - lastblocks) * BLOCKSIZE)) != NULL)
tif 1
/* Adapted from Mike */ Л
Звернете увагу, що morecore() може змінити
і дудіння в операційні системи
положення останнього блоку, якщо вона переміщає таблицю дескрипторів і стара копія таблиці зливається з останнім блоком. */ block = _heapinfo[0].free.prev;
_heapinfо[block].free.size += blocks — lastblocks; #else
_heapinfо[block].free.size = blocks; tendif
_bytes_free += (blocks - lastblocks) * BLOCKSIZE; continue; }
result = raorecore (blocks * BLOCKSIZE); if (result == NULL)
return NULL; block = BLOCK (result);
_heapinfо[block].busy.type = 0; _heapinfo[block].busy.info.size = blocks;
++ chunks used;

_bytes_used += blocks * BLOCKSIZE; return result;
/* У цій крапці ми [так або інакше] знайшли відповідний запис в списку вільних. Зрозуміти, як видалити те, що нам потрібне, із списку. */ result = ADDRESS (block); if (_heapinfо[block].free.size > blocks) {
/* Блок, який ми знайшли, має невеликий залишок
отже приєднати його задній кінець до списку вільних. */ _heapinfо[block + blocks].free.size
= _heapinfo[block].free.size - blocks; _heapinfo[block + blocks].free.next
= _heapinfо[block].free.next; _heapinfo[block + blocks].free.prev
= _heapinfо[block].free.prev;
_heapinfo[_heapinfo[block].free.prev].free.next = _heapinfo[_heapinfo[block].free.next].free.prev
= _heapindex = block + blocks
else
I^h
/* Блок точно відповідає нашому запиту, тому
просто видалити його із списку. */ _heapinfo[_heapinfo[block].free. next].free.prev
= _heapinf про [block] . free.prev; _heapinfo[_heapinfo[block].free.prev].free. next
= _heapindex = _heapinf про [block] . free. next; — chunksf ree ;
_heapinf про [block] .busy. type = 0;
_heapinf про [block] .busy . info. size = blocks;
++_chunks_used;
_bytes_used += blocks * BLOCKSIZE;
_bytes_free -= blocks * BLOCKSIZE;
return result;
free. з:
/* Визволити блок пам'яті, виділений "malloc1.
Copyright 1990, 1991, 1992 Free Software Foundation Написане в травні 1989 Mike Haertel.
GNU З Library є вільним програмним забезпеченням; ви можете перераспространять її і модифікувати її відповідно до положень GNU General Public License версії 2 або (по вашому вибору) будь-якій пізнішій версії.
Бібліотека GNU З поширюється в надії, що вона буде корисна, але БЕЗ ЯКИХ-НЕБУДЬ ГАРАНТІЙ; навіть без неявно передбачуваних гарантій
КОМЕРЦІЙНІЙ ЦІННОСТІ або ПРИДАТНОСТІ для КОНКРЕТНОЇ МЕТИ.
Детальніше за див. GNU General Public License.
З автором можна зв'язатися по електронній пошті за адресою mike@ai.mit.edu, або Mike Haertel с/о Free Software Foundation. */
#ifndef _malloc_internal #define _malloc_internal tinclude <malloc.h> tendif
#ifdef __ELF_
tpragma weak free = __libc_free
#endif
/^Предоставляемая користувачем налагоджувальна функція (hook) для 4free'. */ void (*__free_hook) __P ((__ptr_t __ptr));
/* Список блоків, вьщеленних memalign. */ struct alignlist *_aligned_blocks = NULL;
/* Повернути пам'ять в купу. Аналогічна 'free' але не викликає
__free_hook навіть якщо він визначений. */
void _free_internal (ptr)
__ptr_t ptr;
{
int type;
size_t block, blocks;
register size_t i;
struct list *prev, *next;
block = BLOCK (ptr);
type = _heapinfо[block].busy.type; switch (type) { case 0:
/* Зібрати якомога більше статистики якомога раніше. */ — chunks used;
-I—----
_bytes_used -= heapinfo [block] .busy. info. size * BLOCKSIZE; bytes_free += heapinfo [block] .busy. info. size * BLOCKSIZE;
/* Знайти вільний кластер, передуючий цьому в списку вільних .
Почати пошук з останнього блоку, до якого було звернення. Це може бути перевагою для програм, в яких виділення локальне. */ i = _heapindex; if (i > block)
while (i > block)
i = _heapinfo[i) . free.prev; else { do
i = __heapinfo[i] . free. next; while (i > 0 && i < block) ; i = _heapinfo [i] . free.prev; 1
/* Визначити, як включити цей блок в список вільних. */
if (block == i + _heapinfo[i]. free. size) {
/* Злити цей блок з його попередником. */ _heapinfo[i].free. size += _heapinfo [block] .busy. info. size/block = i;
else
/* Дійсно включити цей блок в список вільних. */
_heapinf про [block] . free. size = _heapinfo [block] .busy. info. size;
_heapinf про [block] .free. next = _heapinfo[i]. free. next;
_heapinf про [block] . free.prev = i;
_heapinfo[i].free. next = block;
_heapinf про [_heapinfo [block] .free. next] .free.prev = block;
++chunksfree;
/* Тепер, оскільки блок включений, перевірити, чи не можемо ми
злити його з його послідовником (виключаючи його послідовника із списку і складаючи розміри) . */
if (block + _heapinf про [block] . free. size == heapinfo [block] .free. next)
{ _heapinfo [block] .free. size
+= _heapinfo [_heapinfo [block] .free. next] . free. size; _heapinfo [block] .free. next
= _heapinfo[_heapinfo[block].free. next]. free. next ; _heapinf про [_heapinfo[block].free. next] .free. prev = block; — chunksf ree ;
/* Перевірити, чи не можемо ми повернути пам'ять системі. */
blocks = _heapinf про [block] .free. size;
if (blocks >= Final_free_blocks && block + blocks == _heaplimit
&& (*_morecore) (0) == ADDRESS (block + .blocks)) {
register size_t bytes = blocks * BLOCKSIZE; _heaplimit -= blocks;
(*__morecore) (-bytes); _heapinf про [_heapinf про [block] .free. prev] .free. next
= _heapinf про [block] . free. next; _heapinfo[_heapinfo[block].free. next].free. prev
= _heapinf про [block] . free. prev; block = _heapinf про [block] . free. prev; — _chunks_f ree ; _bytes_free -= bytes;
/* Встановити наступний пошук, стартувати з цього блоку. */
_heapindex = block; break;
default:
/* Зібрати деяку статистику. */
—_chunks_used; _bytes_used -= 1 « type; ++_chunks_free; bytes_free += 1 « type;
/* Отримати адресу першого вільного фрагмента в цьому блоці.
*/ prev = (struct list *) ((char *) ADDRESS (block) +
(_heapinfo[block].busy.info.frag.first « type));
#if 1 /* Adapted from Mike */
if (_heapinfо[block].busy.info.frag.nfree == (BLOCKSIZE » type) - 1
&& _fragblocks[type]> 1) #else
if (_heapinfо[block].busy.info.frag.nfree == (BLOCKSIZE » type) - 1)
#endif
lif 1 #endii
/* Якщо всі фрагменти цього блоку вільні, видалити їх із списку фрагментів і визволити повний блок. */ /* Adapted from Mike */
— _f ragblocks [type] ;
next = prev;
for (i = 1; i < (size_t) (BLOCKSIZE » type)
next = next->next; prev->prev->next = next; if (next != NULL)
next->prev = prev->prev; _heapinf про [block] .busy. type = 0; _heapinf про [block] .busy . info. size = 1;
/* Стежимо за точністю статистики.
*/ ++_chunks_used; _bytes_used += BLOCKSIZE; _chunks_free -= BLOCKSIZE » type; _bytes_free -= BLOCKSIZE;
libc free (ADDRESS (block));
I
else if ( heapinfо[block].busy.info.frag.nfree != 0)

/* Якщо деякі фрагменти цього блоку вільні, включити цей фрагмент в список фрагментів після першого вільного фрагмента цього блоку. */
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 <gnu-stabs . h>
#ifdef elf_alias
elf_alias (free, cfree) ;
#endif

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

Мал. 4.10. Виділення блоків фіксованих розмірів

На практиці, числа Фібоначчі не використовуються. Одній з причин, мабуть, є відносна складність обчислення такого Fi яке не менше необхідного розміру блоку. Інша причина — складність об'єднання вільних блоків з суміжними адресами в блок більшого розміру. Зате широке вживання знайшов алгоритм, який обмежує послідовні розміри блоків простішою залежністю — мірами числа 2: 512 байт, 1 Кбайт, 2 Кбайт і так далі Така стратегія називається алгоритмом близнят (мал. 4.11).
Одна з переваг цього методу полягає в простоті об'єднання блоків при їх звільненні. Адреса блоку-близнюка виходить простим інвертуванням відповідного біта в адресі нашого блоку. Потрібно лише перевірити, чи вільний цей близнюк. Якщо він вільний, то ми об'єднуємо братів в блок удвічі більшого розміру, і так далі Навіть в найгіршому випадку час пошуку не перевищує Про (log(Smax)-log(Smin)), де Smax і Smin позначають, відповідно, максимальний і мінімальний розміри використовуваних блоків. Це робить алгоритм близнят важко замінимим для ситуацій, в яких необхідний гарантований час реакції, — наприклад, для
завдань реального часу. Часто цей алгоритм або його варіанти використовуються для виділення пам'яті усередині ядра ОС.

Мал. 4.11. Алгоритм близнят

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


:: Реклама ::

светодиодное освещение птичника, agri b Техноблок, норд холодильное оборудование цена.

 

:: Посилання ::


 

 

 


Copyright © Kivik, 2017