Отже, найбільш відповідальною дією менеджера пам'яті є виділення кадру оперативній пам'яті для розміщення в ній віртуальної сторінки, що знаходиться в зовнішній пам'яті. Нагадаємо, що ми розглядаємо ситуацію, коли розмір віртуальної пам'яті для кожного процесу може істотно перевершувати розмір основної пам'яті. Це означає, що при виділенні сторінки основній пам'яті з великою вірогідністю не вдасться знайти вільний сторінковий кадр. В цьому випадку операційна система відповідно до закладених в неї критеріїв винна:
знайти деяку зайняту сторінку основної пам'яті;
перемістити у разі потреби її вміст в зовнішню пам'ять;
переписати в цей сторінковий кадр вміст потрібної віртуальної сторінки із зовнішньої пам'яті;
належним чином модифікувати необхідний елемент відповідної таблиці сторінок;
продовжити виконання процесу, якому ця віртуальна сторінка знадобилася.
Відмітимо, що при заміщенні доводиться двічі передавати сторінку між основною і вторинною пам'яттю. Процес заміщення може бути оптимізований за рахунок використання біта модифікації (один з атрибутів сторінки в таблиці сторінок). Біт модифікації встановлюється комп'ютером, якщо хоч би один байт був записаний на сторінку. При виборі кандидата на заміщення перевіряється біт модифікації. Якщо біт не встановлений, немає необхідності переписувати дану сторінку на диск, її копія на диску вже є. Подібний метод також застосовується до read-only-страницам, вони ніколи не модифікуються. Ця схема зменшує час обробки page fault.
Існує велика кількість різноманітних алгоритмів заміщення сторінок. Всі вони діляться на локальних і глобальних. Локальні алгоритми, на відміну від глобальних, розподіляють фіксоване або таке, що динамічно настроюється число сторінок для кожного процесу. Коли процес витратить всі призначені йому сторінки, система видалятиме з фізичної пам'яті одну з його сторінок, а не із сторінок інших процесів. Глобальний же алгоритм заміщення у разі виникнення виняткової ситуації задовольниться звільненням будь-якої фізичної сторінки, незалежно від того, якому процесу вона належала.
Глобальні алгоритми мають ряд недоліків. По-перше, вони роблять одні процеси чутливими до поведінки інших процесів. Наприклад, якщо один процес в системі одночасно використовує велику кількість сторінок пам'яті, то решта всіх застосувань в результаті відчуватиме сильне уповільнення через нестачу кадрів пам'яті для своєї роботи. По-друге, некоректно працююче застосування може підірвати роботу всієї системи (якщо, звичайно, в системі не передбачено обмеження на розмір пам'яті, що виділяється процесу), намагаючись захопити більше пам'яті. Тому в багатозадачній системі іноді доводиться використовувати складніші локальні алгоритми. Застосування локальних алгоритмів вимагає зберігання в операційній системі списку фізичних кадрів, виділених кожному процесу. Цей список сторінок іноді називають резидентним безліччю процесу. У одному з наступних розділів розглянутий варіант алгоритму підкачки, заснований на приведенні резидентної множини у відповідність так званому робочому набору процесу.
Ефективність алгоритму зазвичай оцінюється на конкретній послідовності посилань до пам'яті, для якої підраховується число тих, що виникають page faults. Ця послідовність називається рядком звернень (reference string). Ми можемо генерувати рядок звернень штучним чином за допомогою датчика випадкових чисел або трасуючи конкретну систему. Останній метод дають дуже багато посилання, для зменшення числа яких можна зробити дві речі:
для конкретного розміру сторінок можна запам'ятовувати тільки їх номери, а не адреси, на які йде посилання;
декілька підряд посилань, що йдуть, на одну сторінку можна фіксувати один раз.
Як вже мовилося, більшість процесорів мають прості апаратні засоби, що дозволяють збирати деяку статистику звернень до пам'яті. Ці засоби зазвичай включають два спеціальні прапори на кожен елемент таблиці сторінок. Прапор посилання (reference битий) автоматично встановлюється, коли відбувається будь-яке звернення до цієї сторінки, а вже розглянутий вище прапор зміни (modify битий) встановлюється, якщо проводиться запис в цю сторінку. Операційна система періодично перевіряє установку таких прапорів, для того, щоб виділити активно використовувані сторінки, після чого значення цих прапорів скидаються.
Розглянемо ряд алгоритмів заміщення сторінок.