Якщо значення біта invalid, то процес переривається і керування передається ОС і для обробки події сторінкової недостатньості.

Відшуковується необхідна сторінка у другорядній пам’яті і вільна сторінкова рамка в основній.

Потрібна сторінка загружається в вибрану сторінкову рамку.

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

Керування передається перерваному процесу.

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

Другорядна пам’ять, яка використовується при обміні сторінок по вимозі,- це високошвидкісний дисковий пристрій, яке часто називають обладнанням свопінгу (swap device), а частину використовуваного дискового простору – простором свопінгу (swap space).

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

Метод заміщення сторінок полягає в тому, що в основній пам’яті вибирається найменш важлива використовувана сторінка, яка називається сторінка-жертва (victim page), яка на деякий час переміщається в простір свопінгу, а на її місце завантажується сторінка, яку викликає сторінкова недостатність.

Обробка сторінкової недостатньості з врахуванням заміщення проводиться по наступному алгоритму:

виясняється місцезнаходження сторінки шляхом аналізу біта місцезнаходження;

якщо значення біту invalid, то йде пошук вільної сторінкової рамки;

якщо є вільна сторінкова рамка, то вона використовується;

якщо вільної сторінкової рамки нема, то використовується алгоритм заміщення, який вибирає сторінку-жертву;

сторінка-жертва переміщається в простір свопінгу і таблиця сторінок редагується;

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

Керування передається перерваному процесу. Приведений алгоритм заміщення потребує двохсторінкових переміщень:

сторінка-жертва переміщується в простір свопінга;

потрібна сторінка переміщається в сторінкову рамку, яка звільнилась.

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

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

Для практичного використання методу обміну сторінок по вимозі необхідні два алгоритми:

алгоритм розподілу сторінкових рамок (frame allocation algorithm);

алгоритм заміщення сторінок (page replacement algorithm).

5.3. Алгоритми розподілу сторінкових рамок

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

FIFO (first-in-first-out). Найбільш простим алгоритмом заміщення сторінок є алгоритм FIFO. Цей алгоритм асоціює з кожною сторінкою час, коли ця сторінка була поміщена в пам’ять. Для заміщення вибирається найбільш стара сторінка.

Врахування часу необов’язково, коли всі сторінки в пам’яті зв’язані в FIFO-чергу, а кожна сторінка, яка поміщається в пам’ять добавляється в хвіст черги.

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

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

Алгоритм LRU (least recently used). Алгоритм вибирає для заміщення ту сторінку, на яку не було посилання на протязі найдовшого періоду часу. Він асоціює з кожною сторінкою час останнього використання цієї сторінки. Для заміщення вибирається та сторінка, яка не використовувалась довше за інші. Зазвичай застосовуються два підходи при використанні цього алгоритму:

підхід на основі логічного годинника (лічильника) – асоціюють з кожним рядком таблиці поле „час використання”, а в CPU додається логічний годинник. Логічний годинник збільшує своє значення при кожному звертанні до пам’яті. Кожен раз, коли здійснюється посилання на сторінку, значення регістра логічного годинника копіюється в поле „час використання”. Заміняється сторінка з найменшим значенням в цьому полі шляхом сканування всієї таблиці сторінок. Сканування буде відсутнім, якщо використовується підхід на основі стеку;

підхід на основі стека номерів сторінок – стек номерів сторінок зберігає номери сторінок, впорядкованих в відповідності з історією їх використання, на „вершині” стеку розміщена щойно використана сторінка, а на „дні” довше за всіх не використовувана сторінка. Як тільки здійснюється посилання на сторінку, вона переміщається на вершину стека, а номера всіх сторінок переміщуються вниз.

Алгоритм LFU (least freqently used). Цей алгоритм заміняє ту сторінку, яка використовується найменш частіше. Спосіб упорядкування схожий на LRU.

Також можливий випадковий вибір сторінки. Такий алгоритм називається random – замінюється сторінка, яка вибирається випадково.

В більшості сучасних ОС використовується дисципліна заміщення сторінок LRU, як сама ефективна. Так, саме ця дисципліна використовується в OS/2 і Linux. Але в такій ОС, як Windows NT, розробники, прагнучи зробити систему максимально незалежною від апаратних можливостей процесора, пішли на відмову від цієї дисципліни і застосували правило FIFO.

6. Ієрархія запам'ятовуючих пристроїв. Принцип кешування даних

Пам'ять обчислювальної машини являє собою ієрархію ЗП, що відрізняються середнім часом доступу до даних, обсягом і вартістю збереження одного біта (мал. 27). Фундаментом цієї піраміди ЗП служить зовнішня