якій пам'ять запущеної програми реалізується однорідним масивом, в той час як насправді операційна система виділяє пам'ять блоками у різних видах пам'яті, включаючи короткочасну (оперативну) і довгострокову (жорсткі диски , твердотільні накопичувачі) є віртуальна пам'ять.
Усередині операційної системи зазвичай відводиться пул вільної пам'яті, призначений для поточних потреб різних системних процесів. Цей пул підтримує тимчасові системні буфери, черги і блоки управління процесами. Так як операційна система зазвичай працює з реальними адресами, цей пул являє собою безперервний сегмент, динамічно розподілена між різними системними процесами.
Концепція динамічного розподілу пам'яті полягає у виборі відповідної стратегії розміщення. Розподіл являє собою прийняття рішення про те, в якому місці пам'яті повинна розташовуватися програма, щоб мінімізувати неиспользуемое адресний простір і гарантувати одночасне розміщення в пам'яті заданого числа користувачів. Зрозуміло, чим більше завдань, «готових виконуватися», буде розміщено в пам'яті, тим більша ймовірність найбільш ефективного використання системних ресурсів.
Визначаючи стратегію розміщення, ми розглядаємо пам'ять як упорядковане простір з m слів. Запити на розміщення або звільнення блоків пам'яті будуть постійно прагнути порушити цю впорядкованість. У цьому випадку конфігурація пам'яті буде нагадувати шахову дошку з порожніми ділянками, що чергуються з розподіленими блоками. Така конфігурація змінюється в часі залежно від обсягів пам'яті, що вказуються в запитах. Ефективний розподіл пам'яті передбачає мінімізацію розміру та кількості порожніх ділянок пам'яті.
Для стратегій розміщень вироблено правило «Правило 50%». Воно передбачає, що система знаходиться в рівновазі, якщо запити на розподіл і звільнення збалансовані між собою протягом заданого короткого проміжку часу. Інакше кажучи, в системі з m слів з розподіленими n сегментами буде приблизно h порожніх ділянок, де h одно n/2. Це випливає з того факту, що для даного сегменту простір, що примикає до його правого краю, буде пустимо протягом половини даного інтервалу часу і зайнятим сегментом протягом іншої половини. Ймовірність існування порожньої ділянки є р=1/2; наприклад, число сегментів, що мають порожнечу по своєму правому краю, є np=n/2=h.
Результат застосування цього правила цілком очевидний. Для скорочення часу роботи алгоритму розміщення ми повинні свідомо змиритися з присутністю в пам'яті порожніх ділянок великої величини. Це увелічівает обсяг невикористовуваної пам'яті. Однак було розраховано, що при сильному варіюванні розмірів порожніх ділянок частка обсяг невикористовуваної пам'яті може бути зменшена до 10%.
a) Алгоритм оптимального розміщення.
Цей алгоритм намагається задовольнити запит, виділяючи вільна ділянка мінімально можливого розміру. Створюється і підтримується список вільних ділянок, упорядкований за їх розмірами. Менеджер пам'яті при отриманні запиту на вільний простір переглядає список, підшукуючи ділянку з мінімальною величиною ЗАЛИШОК, що обчислюється таким чином:
РОЗМІР-ДІЛЯНКИ - ТРЕБУЕМЬІЙ-РОЗМІР - * ЗАЛИШОК
Тут ЗАЛИШОК - це вільний простір, яке залишається після задоволення запиту. Ідея алгоритму - мінімізувати обсяг вільного простору, що залишається після кожного розподілу. У системах, що здійснюють розподіл вільних ділянок на частини, ЗАЛИШОК порівнюється з деякою пороговою величиною для прийняття рішення: виробляти такий поділ чи ні.
б)
