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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 оптимальний алгоритм;

 алгоритм найдовше невикористаними;

 алгоритм "першим увійшов - першим вийшов";

 часовий алгоритм.

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Стратегії управління сторінковою пам'яттю	\|	Оптимальний алгоритм (OPT)

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.147 сек.