Взаємодія з диском підчас керування пам'яттю. Поняття підкачування. Проблеми реалізації підкачування сторінок.

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

Реалізація підкачування використовує правило «дев’яносто до десяти». Ідеальною реалізацією керування пам’яттю є надання кожному процесові пам’яті, за розміром порівнянної із жорстким диском, а за швидкістю доступу - з основною пам’яттю. Головні проблеми:

Які сторінки потрібно завантажити із диска і в який час?

прийнята в цій системі стратегія вибірки сторінок.

Яку сторінку потрібно вивантажити на диск, коли вільних фреймів у основній пам’яті більше немає?

Для цього створюють стратегії заміщення сторінок

Де у фізичній пам’яті мають розміщуватися сторінки процесу?

Для цього створюють стратегія розміщення.

Яким чином організувати керування резидентною множиною?

Головне завдання такого керування — забезпечити, щоб у резидентній множині були тільки сторінки, які дійсно потрібні процесу.

Взаємодія потоків. Взаємодія потоків у Linux

Бібліотеки підтримки потоків Linux (LinuxThreads і NPTL) надають програмам користувача набір синхронізаційних примітивів, визначених стандартом POSIX (м’ютекси, умовні змінні, семафори, блокування читання-загшсування, бар’єри).

Крім того, у NPTL допускають використання цих примітивів у поєднанні з відображуваною або розподілюваною пам’яттю для реалізації міжпроцесової синхронізації.

Описані примітиви реалізовані на основі базових механізмів синхронізації, доступних через системні виклики (у ядрі версії 2.6 до них належать ф’ютекси). Крім того, код ядра може використовувати спеціальні механізми синхронізації, доступні тільки у ядрі.

Основи технології віртуальної пам'яті. Асоціативна пам'ять

У швидкодіючій пам’яті (швидшій, ніж основна пам’ять) створюють набір із кількох елементів (різні архітектури відводять під асоціативну пам’ять від 8 до 2048 елементів). Кожний елемент кеша трансляції відповідає одному елементу таблиці сторінок. Тепер під час генерування фізичної адреси спочатку відбувається пошук відповідного елемента таблиці в кеші (в ІА-32 — за полем каталогу, полем таблиці та зсуву), і якщо він знайдений, стає доступною адреса відповідного фрейму, що негайно можна використати для звертання до пам’яті. Якщо ж у кеші відповідного елемента немає, то доступ до пам’яті здійснюють через таблицю сторінок, а після цього елемент таблиці сторінок зберігають в кеші замість найстарішого елемента (рис. 8.9).

На жаль, у разі перемикання контексту в архітектурі ІА-32 необхідно очистити весь кеш, оскільки в кожного процесу є своя таблиця сторінок, і ті ж самі номери сторінок для різних процесів можуть відповідати різним фреймам у фізичній пам’яті. Очищення кеша трансляції є дуже повільною операцією, якої треба всіляко.

ЕКЗАМЕНАЦІЙНИЙ БІЛЕТ № 21

Взаємодія з диском підчас керування пам'яттю. Заміщення сторінок. Оцінка алгоритмів заміщення сторінок.

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

Поки процеси використовують свої сторінки звичайним чином (на 50 %), всі вони будуть виконуватися в основній пам’яті без проблем. Але завжди може виникнути ситуація, коли процеси зажадають більше пам’яті, ніж їм це потрібно в середньому Що більше процесів одночасно виконується в системі, то вища ймовірність виникнення такої ситуації. За відсутності вільного фрейму в пам’яті ОС має вибрати, яку сторінку вилучити із пам’яті для того щоб вивільнити місце для нової сторінки. Процес цього вибору визначає стратегія заміщення сторінок. Коли сторінка, яку вилучають, була змінена, необхідно вивантажити її на диск для відображення цих змін, коли ж вона залишилася незмінною (наприклад, це була сторінка із програмним кодом), цього робити не потрібно. Для індикації того, чи була сторінка змінена, використовують біт модифікації сторінки М (про нього йшлося в розділі 9.3.1).

Яку саме сторінку потрібно вилучати із пам’яті, визначає алгоритм заміщення сторінок (page replacement algorithm). Вибір такого алгоритму відчутно впливає на продуктивність системи, тому що вдало підібраний алгоритм зменшує кількість сторінкових переривань, а невдала його реалізація може її значно збільшити (якщо вилучити часто використовувану сторінку, то вона незабаром може знову знадобитися і т. д.). Навіть невеликі поліпшення в методах заміщення сторінок можуть спричинити великий загальний виграш у продуктивності.

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

Ось який вигляд матиме алгоритм завантаження сторінки з урахуванням заміщення сторінок.

Знайти вільний фрейм у фізичній пам’яті:

а) якщо вільний фрейм є, використати його (перейти до кроку 2);

б) якщо вільного фрейму немає, використати алгоритм заміщення сторінок для того щоб знайти фрейм-жертву (victim frame);

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

Знайти потрібну сторінку на диску.

Прочитати потрібну сторінку у вільний фрейм (якщо раніше були виконані

кроки б і в п. 1, цим фреймом буде той, котрий щойно вивільнився).

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

Критерієм для порівняння алгоритмів заміщення звичайно є рівень сторінкових переривань: що він нижчий, то кращим вважають алгоритм. Оцінку алгоритму здійснюють через підрахунок кількості сторінкових переривань, які виникли внаслідок його запуску для конкретного набору посилань на сторінки у пам’яті. Набір посилань на сторінки подають рядком посилань (reference string) із номерами сторінок. Такий рядок можливо згенерувати випадково, а можна отримати відстеженням посилань на пам’ять у реальній системі (у цьому разі даних може бути зібрано дуже багато). Групу із кількох посилань, що йдуть підряд, на одну й ту саму сторінку в рядку відображають одним номером сторінки, оскільки такий набір посилань не може спричинити сторінкового переривання.

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