1.10.6 Схема зі змінними розділами

В принципі, система свопінгу може базуватися на фіксованих розділах. Більш ефективною, однак, видається схема динамічного розподілу або схема зі змінними розділами, яка може використовуватися і в тих випадках, коли всі процеси цілком містяться в пам’яті, тобто за відсутності свопінгу. У цьому випадку спочатку вся пам’ять вільна і не розділена заздалегідь на розділи. Знову надходить задачі виділяється строго необхідна кількість пам’яті, не більше. Після вивантаження процесу пам’ять тимчасово звільняється. Після закінчення деякого часу пам’ять – змінне число розділів різного розміру (рис. 1.4). Суміжні вільні ділянки можуть бути об’єднані.

Рис. 1.4 – Динаміка розподілу пам’яті між процесами (сірим кольором показана невживана пам’ять)

В який розділ поміщати процес? Найбільш поширені три стратегії.

– Стратегія першого підходящого (First fit). Процес поміщається в перший відповідний за розміром розділ.

– Стратегія найбільш підходящого (Best fit). Процес поміщається в той розділ, де після його завантаження залишиться менше всього вільного місця.

– Стратегія найменш придатного (Worst fit). При приміщенні в найбільший розділ в ньому залишається достатньо місця для можливого розміщення ще одного процесу.

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

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

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

Статистичний аналіз показує, що припадають в середньому 1/3 пам’яті! Це відоме правило 50% (дві сусідніх вільних ділянки на відміну від двох сусідніх процесів можуть бути об’єднані).

Одне з рішень проблеми зовнішньої фрагментації – організувати стиск, тобто переміщення всіх зайнятих (вільних) ділянок у бік зростання (спадання) адрес, так, щоб вся вільна пам’ять утворила безперервну область. Цей метод іноді називають схемою з переміщуваними розділами. В ідеалі фрагментація після стиснення має бути відсутня. Стиснення, однак, є дорогою процедурою, алгоритм вибору оптимальної стратегії стиснення дуже важкий і, як правило, стиснення здійснюється в комбінації з вивантаженням і завантаженням за іншими адресами.