Алгоритм FIFO. Виштовхування першої сторінки

Простий алгоритм. Кожній сторінці привласнюється тимчасова мітка. Реалізується це просто створенням черги сторінок, в кінець якої сторінки потрапляють, коли завантажуються у фізичну пам'ять, а з початку беруться, коли потрібно звільнити пам'ять. Для заміщення вибирається стара сторінка. На жаль, ця стратегія з достатньою вірогідністю приводитиме до заміщення активно використовуваних сторінок, наприклад сторінок коди текстового процесора при редагуванні файлу. Відмітимо, що при заміщенні активних сторінок все працює коректно, але page fault відбувається негайно.

Аномалія Біледі (Belady)

На перший погляд здається очевидним, що чим більше в пам'яті сторінкових кадрів, тим рідше матимуть місце page faults. Дивно, але це не завжди так. Як встановив Біледі з колегами, певні послідовності звернень до сторінок насправді приводять до збільшення числа сторінкових порушень при збільшенні кадрів, виділених процесу. Це явище носить назва "Аномалії Біледі" або "аномалії FIFO".

Система з трьома кадрами (9 faults) виявляється продуктивнішою, ніж з чотирма кадрами (10 faults), для рядка звернень до пам'яті 012301401234 при виборі стратегії FIFO.

Рис. 12.1. Аномалія Біледі: (a) - FIFO з трьома сторінковими кадрами; (b) - FIFO з чотирма сторінковими кадрами

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

Оптимальний алгоритм (OPT)

Одним з наслідків відкриття аномалії Біледі став пошук оптимального алгоритму, який при заданому рядку звернень мав би мінімальну частоту page faults серед всіх інших алгоритмів. Такий алгоритм був знайдений. Він простий: заміщай сторінку, яка не використовуватиметься протягом найтривалішого періоду часу.

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

Цей алгоритм легко описати, але реалізувати неможливо. ОС не знає, до якої сторінки буде наступне звернення. (Раніше такі проблеми виникали при плануванні процесів - алгоритм SJF).

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