фіксований розподіл
У більшості схем управління пам'яттю ми будемо вважати, що операційна система займає деяку фіксовану частину основної пам'яті і що інша частина основної пам'яті доступна для використання численних процесів. Найпростіша схема управління цією доступною пам'яттю - її розподіл на області з фіксованими межами.
розміри розділів
На рис. 7.2 показані два приклади фіксованого розподілу. Одна можливість полягає в використанні розділів однакового розміру. У цьому випадку будь-який процес, розмір якого не перевищує розмір розділу, може бути завантажений в будь-який доступний розділ. Якщо всі розділи зайняті і немає жодного процесу в стані готовності або роботи, операційна система може вивантажити процес з будь-якого розділу і завантажити інший процес, забезпечуючи тим самим процесор роботою.
При використанні розділів з однаковим розміром є дві проблеми.
Програма може бути занадто велика для розміщення в розділі. В цьому випадку програміст повинен розробляти програму, яка використовує оверлеї, з тим щоб в будь-який момент часу їй був потрібний тільки один розділ основної пам'яті. Там, де необхідно модуль, який в даний момент відсутня в основний пам'яті, призначена для користувача програма повинна сама завантажити цей модуль в розділ пам'яті програми (незалежно від того, чи є цей модуль кодом або даними).
Використання основної пам'яті при цьому вкрай неефективно. Будь-яка програма, незалежно від її розміру, займає розділ цілком. Так, в нашому прикладі програма розміром менше мегабайта все одно буде займати цілком розділ в 8 Мбайт; при цьому залишаються невикористаними 7 Мбайт блоку. Цей феномен появи невикористаної пам'яті через те, що завантажується блок за розміром менше розділу, називається внутрішньої фрагментацією (internal fragmentation).
Боротися з цими труднощами (хоча і не усунути повністю) можна за допомогою використання розділів різних розмірів (див. Рис. 7.2, б). У цьому випадку програма розміром 16 Мбайт може обійтися без оверлеїв, а розділи малого розміру дозволяють зменшити внутрішню фрагментацію при завантаженні програм малого розміру.
алгоритм розміщення
У тому випадку, коли розділи мають однаковий розмір, размещеніепроцессов в пам'яті представляє собою тривіальну завдання. Не має значення, в якому з вільних розділів буде розміщений процес. Якщо всі розділи зайняті процесами, які не готові до негайної роботі, будь-який з них може бути вивантажений для звільнення пам'яті для нового процесу. Ухвалення рішення про те, який саме процес слід вивантажити - завдання планувальника (про це ми поговоримо в частині 4, "Планування").
Коли розділи мають різні розміри, є два можливих підходи до призначення процесорів розділах пам'яті. Найпростіший шлях полягає в тому, щоб кожен процес розміщувався в найменшому розділі, здатному повністю вмістити даний процесс.1 У такому випадку для кожного розділу потрібно чергу планувальника, в якій зберігаються вивантажені з пам'яті процеси, призначені для даного розділу пам'яті (див. Рис. 7.3 , а). Гідність такого підходу полягає в тому, що процеси можуть бути розподілені між розділами пам'яті так, щоб мінімізувати внутрішню фрагментацію.
Хоча цей метод є оптимальним з точки зору окремого розділу, він не оптимальний з точки зору системи в цілому. Уявімо, що в системі, зображеній на рис. 7.2,6, в певний момент часу немає жодного процесу розміром від 12 до 16 Мбайт. В результаті розділ розміром 16 Мбайт буде пустувати, в той час як він міг би з успіхом використовуватися меншими процесами. Таким чином, кращим підходом є використання однієї черги для всіх, процесів (див. Рис. 7.3, б). У момент, коли потрібно завантажити процес в основну пам'ять, для цього вибирається найменший доступний розділ, здатний вмістити даний процес. Якщо всі розділи зайняті, слід прийняти рішення про звільнення одного з них. Мабуть, слід віддати перевагу процесу, що займає найменший розділ, здатний вмістити завантаження процес. Можна врахувати й інші фактори, такі, як пріоритет процесу або його стан (заблокований він або активний).
Використання розділів різного розміру в порівнянні з використанням розділів однакового розміру надає додаткову гнучкість даного методу. Крім того, схеми з фіксованими розділами відносно прості, пред'являють мінімальні вимоги до операційної системи; накладні витрати роботи процесора невеликі. Однак у цих схем є серйозні недоліки.
Кількість розділів, певне в момент генерації системи, обмежує кількість активних (НЕ призупинених) процесів.
Оскільки розміри розділів встановлюються заздалегідь, в момент генерації системи, невеликі процеси призводить до неефективного використання пам'яті. У середовищах, де заздалегідь відомі потреби в пам'яті всіх завдань, застосування описаної схеми може бути виправдано, але в більшості випадків ефективність цієї технології є вкрай низькою.
Фіксований розподіл в даний час практично не використовується. Прикладом успішної операційної системи з використанням даної технології може служити рання операційна система IBM для мейнфреймів OS / MFT (многозадачная з фіксованою кількістю завдань-Multiprogramming with a Fixed number of Tasks).
динамічний розподіл
алгоритм розміщення
Оскільки ущільнення пам'яті викликає додаткові витрати часу процесора, розробник операційної системи повинен прийняти розумне рішення про те, яким чином розміщувати процеси в пам'яті (образно кажучи, яким чином затикати дірки). Коли настає момент завантаження процесу в основний пам'ять і є кілька блоків вільної пам'яті достатнього розміру, операційна система повинна прийняти рішення про те, який саме вільний блок використовувати.
Можна розглядати три основних алгоритму - найкращий відповідний, перший відповідний, наступний відповідний. Всі вони, само собою зрозуміло, обмежені вибором серед вільних блоків розміру, досить великого для розміщення процесу. Метод найкращого відповідного вибирає блок, розмір якого найбільш близький до необхідного; метод першого підходящого перевіряє всі вільні блоки з початку пам'яті і вибирає перший достатній за розміром для розміщення процесу. Метод наступного відповідного працює так само, як і метод першого підходящого, однак починає перевірку з того місця, де було виділено блок в останній раз (після досягнення кінця пам'яті він продовжує роботу з її початку).
На рис. 7.5, а показаний приклад конфігурації пам'яті після ряду розміщень і вивантаження процесів з пам'яті. Останнім використаним блоком був Мок розміром 22 Мбайт, в якому був створений розділ в 14 Мбайт. На рис. 7,5,6 показано відмінність в технології найкращого, першого і наступного відповідного при виконанні запиту на виділення блоку розміром 16 Мбайт. Метод найкращого відповідного переглядає всі вільні блоки і вибирає найбільш близький за розміром блок в 18 Мбайт, залишаючи фрагмент розміром 2 Мбайт. Метод першого підходящого в даній ситуації залишає фрагмент вільної пам'яті розміром б Мбайт, а метод наступного відповідного - 20 Мбайт.
Який з цих методів виявиться найкращим, буде залежати від точної послідовності завантаження і вивантаження процесів і їх розмірів. Однак можна говорити про деякі узагальнених висновках (див. [BREN89], [SHOR75], [BAYS77]). Зазвичай алгоритм першого підходящого не тільки простіше, але і швидше і дає кращі результати. Алгоритм наступного підходящого, як правило, дає трохи гірше результати. Це пов'язано з тим, що алгоритм наступного відповідного виявляє схильність до більш частого виділення пам'яті з вільних блоків в кінці пам'яті. В результаті найбільші блоки вільної пам'яті (які зазвичай розташовуються в кінці пам'яті) швидко розбиваються на менші фрагменти і, отже, при використанні методу наступного відповідного ущільнення повинно виконуватися частіше. З іншого боку, алгоритм першого підходящого зазвичай засмічує початок пам'яті невеликими вільними блоками, що призводить до збільшення часу пошуку відповідного блоку в подальшому. Метод найкращого підходящого, всупереч своїй назві, виявляється, як правило, найгіршим. Так як він шукає блоки, найбільш близькі за розміром до необхідного, він залишає після себе безліч дуже маленьких блоків. В результаті, хоча при кожному виділенні даремно витрачається найменшу можливу кількість пам'яті, основна пам'ять дуже швидко засмічується безліччю дрібних блоків, які можуть задовольнити ні один запит (так що при цьому алгоритмі ущільнення пам'яті повинно виконуватися значно частіше).
алгоритм заміщення
У багатозадачній системі з використанням динамічного розподілу настає момент, коли всі процеси в основний пам'яті знаходяться в заблокованому стані, а пам'яті для додаткового процесу недостатньо навіть після ущільнення. Щоб уникнути втрат процесорного часу на очікування деблокування активного процесу, операційна система може вивантажити один з процесів з основної пам'яті, і, таким чином, звільнити місце для нового процесу, або процесу в стані готовності. Завдання операційної системи - визначити, який саме процес повинен бути вивантажений з пам'яті. Оскільки тема алгоритму заміщення буде детально розглядатися в зв'язку з різними схемами віртуальної пам'яті, поки що ми відкладемо обговорення цього питання.
система двійників
Як фіксоване, так і динамічний розподіл пам'яті мають свої недоліки. Фіксований розподіл обмежує кількість активних процесів і неефективно використовує пам'ять при невідповідності між розмірами розділів і процесів. Динамічний розподіл реалізується більш складно і включає накладні витрати по ущільненню пам'яті. Цікавим компромісом в цьому плані є система двійників ([KNUT97], [РБТЕ77]).
В системі двійників пам'ять розподіляється блоками розміром 2, до <К
21 - мінімальний розмір виділяється блоку пам'яті;
2и - найбільший розподіляється блок; взагалі кажучи, 2и є розмір всієї доступної для розподілу пам'яті.
Спочатку все доступне для розподілу простір розглядається як єдиний блок розміру 2u. При запиті розміром s, таким, що 2u-l void get_hole (int i)
if (i = = (U + 1))
<Ошибка>;
if (<Список 1 пуст>)
get_hоle (i + l);
<Разделить дыру на двойники>;
<Поместить двойники в списокi>;
>
<Взять первую дыру из спискаi>;
>
На рис. 7.6 наведено приклад використання блоку з початковим розміром 1 Мбайт. Перший запит А - на 100 Кбайт (для нього потрібно блок розміром 128 Кбайт); Для цього початковий блок ділиться на два двійника по 512 Кбайт. Перший з них ділиться на двійники розміром 256 Кбайт, і, в свою чергу, перший з який отримав при цьому поділі двійників також ділиться навпіл. Один з вийшов двійників розміром 128 Кбайт виділяється запитом А. Наступний запит У вимагає 256 Кбайт. Такий блок є в наявності і виділяється. Процес триває з поділом і злиттям двійників при необхідності. Зверніть увагу, що після звільнення блоку Е відбувається злиття двійників по 128 Кбайт в один блок розміром 256 Кбайт, який, в свою чергу, тут же зливається зі своїм двійником.
На рис. 7.7 показано уявлення системи двійників у вигляді бінарного дерева, безпосередньо після звільнення блоку В. Листя представляють поточний розподіл пам'яті. Якщо два двійника є листям, то принаймні один з них зайнятий; в іншому випадку вони повинні злитися в блок більшого розміру.