Загальне завдання розподілу пам'яті й стратегії її рішення

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

Виникає загальне завдання розподілу пам'яті: Є список вільних областей пам'яті й список зайнятих областей різного розміру. Розробити й реалізувати оптимальний (за деяким критерієм) алгоритм виділення вільної суміжної ділянки пам'яті довжини n (слів або байтів).

Для рішення даного завдання застосовуються наступні стратегії: метод першого підходящого (first-fit), метод найбільш підходящого (best-fit) і метод найменш підходящого (worst-fit). Розглянемо кожну з них докладніше.

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

Метод найбільш підходящого: Вибирається зі списку найбільш підходяща вільна ділянка (мінімального розміру, не меншого, чим n). На відміну від попереднього методу, вимагає перегляду всього списку, якщо список не впорядкований по розміру областей. Застосування методу приводить до утворення частини, що залишилася, самого маленького розміру.

Метод найменш підходящого: Вибирається зі списку підходяща область найбільшого розміру. Чому найбільшого? Щоб уникнути фрагментації (проблема фрагментації докладно розглянута далі в даній лекції).

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

Фрагментація

Фрагментація – це дроблення пам'яті на дрібні не суміжні вільні області маленького розміру. Фрагментація виникає після виконання системою великої кількості запитів на пам'ять, таких, що розміри підходящих вільних ділянок пам'яті виявляються трохи більше, ніж необхідні. Наприклад, якщо є 100 суміжних вільних областей пам'яті по 1000 слів, те після виконання 100 запитів на пам'ять по 999 слів кожний у списку вільної пам'яті залишаться 1000 областей по одному слову.

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

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

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

Сторінкова організація (paging) – стратегія керування пам'яттю, при якій:

· логічна пам'ять ділиться на сторінки – суміжні області однакової довжини, звичайно – ступінь 2 (наприклад, 512 слів);

· фізична пам'ять, відповідно, ділиться на фрейми такого ж розміру;

· розподіл логічної пам'яті відбувається з точністю до сторінки;

· фізична пам'ять процесу може не бути безперервної;

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

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

Мети сторінкової організації - забезпечити можливість не суміжного розподілу фізичної пам'яті для процесів, а також розширити простір логічної пам'яті.

При сторінковій організації логічна адреса обробляється системою особливим образом – як структура (p, d): його старші розряди позначають номер сторінки, молодші – зсув усередині сторінки. Номер сторінки (p) трактується як індекс у таблиці сторінок, що відповідає елемент якої містить базову адресу початку сторінки у фізичній пам'яті. Зсув усередині сторінки (d) додається до її базової адреси. У результаті формується фізична адреса, переданий у пристрій керування пам'яттю.

Архітектура трансляції адрес при сторінковій організації зображена на рис. 16.3.

 

Архітектура трансляції адрес при сторінковій організації.

На рис. 16.4 наведено приклад сторінкової організації, що демонструє, що, на відміну від безперервної логічної пам'яті процесу, що відповідають фрейми сторінок в основній пам'яті можуть бути розташовані не суміжно: логічній сторінці 0 відповідає фрейм 1, сторінці 1 - фрейм 4, сторінці 2 - фрейм 3, сторінці 3 - фрейм 7.

 

Рис. 16.4. Приклад сторінкової організації.

На рис. 16.5 наведено інший можливий приклад сторінкової організації: логічну й фізичну пам'ять розбита на блоки по 4 сторінки підряд; у таблиці сторінок зберігається не номер сторінки, а номер блоку сторінок. Наприклад, в елементі 0 таблиці сторінок зберігається номер блоку 5, по якому адреса початку блоку обчислюється домножением умісту елемента таблиці сторінок на розмір блоку, рівний 4 (результат - 20).

Рис. 16.5. Приклад сторінкової організації блоками по 4 сторінки.

Використання списку вільних фреймів ілюструється на рис. 16.6.

 

Рис. 16.6. Список вільних фреймів.

Спочатку список складається з 5 фреймів. При уведенні в систему нового процесу з логічною пам'яттю з 4 сторінок, після завантаження процесу на згадку, послідовні логічні сторінки процесу розміщаються в перші за списком фізичних фреймах. У результаті в списку вільних фреймів залишається один елемент.

Захист пам'яті

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

Структура таблиці сторінок

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

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

При звичайної організації таблиці сторінок, логічна адреса (для 32-розрядної архітектури, при розмірі сторінки 4 кілобайти = 4096 байтів) розбивається на номер сторінки (20 біт) і зсув усередині сторінки (12 біт).

При дворівневій организації таблиці сторінок, таблиця сторінок верхнього рівня сама ділиться на сторінки, тому логічна адреса буде мати вигляд: (p1, p2, d), де p1 – індекс у зовнішній таблиці сторінок, p2 – зсув усередині сторінки для зовнішньої таблиці сторінок, d – зсув усередині сторінки (адресовану по внутрішній таблиці сторінок). При тих же припущеннях про архітектуру й розмір сторінки, p1 й p2 будуть займати по 10 біт.

Організація дворівневих таблиць сторінок зображена на рис. 16.9.

 

Рис. 16.9. Організація дворівневих таблиць сторінок.