1.13 Алгоритми заміщення сторінок

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

• знайти деяку зайняту сторінку основної пам’яті;

• перемістити в разі потреби її вміст у зовнішню пам’ять;

• переписати в цей сторінковий кадр вміст потрібної віртуальної сторінки із зовнішньої пам’яті;

• належним чином модифікувати необхідний елемент відповідної таблиці сторінок;

• продовжити виконання процесу, якому ця віртуальна сторінка знадобилася.

Зауважимо, що при заміщенні доводиться двічі передавати сторінку між основною та вторинної пам’яттю. Процес заміщення може бути оптимізовано за рахунок використання біта модифікації (один з атрибутів сторінки в таблиці сторінок). Біт модифікації встановлюється комп’ютером, якщо хоча б один байт був записаний на сторінку. При виборі кандидата на заміщення перевіряється біт модифікації. Якщо біт не встановлений, немає необхідності переписувати дану сторінку на диск, її копія на диску вже є. Подібний метод також застосовується до read–only–сторінкам, вони ніколи не модифікуються. Ця схема зменшує час обробки page fault.

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

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

Ефективність алгоритму звичайно оцінюється на конкретній послідовності посилань до пам’яті, для якої підраховується число виникаючих page faults. Ця послідовність називається рядком звернень (reference string). Ми можемо генерувати рядок звернень штучним чином за допомогою датчика випадкових чисел або використати трасування конкретної системи. Останній метод дає занадто багато посилань, для зменшення числа яких можна зробити дві речі:

• для конкретного розміру сторінок можна запам’ятовувати тільки їх номери, а не адреси, на які йде посилання;

• кілька поспіль посилань на одну сторінку можна фіксувати один раз.

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