Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
report (1).doc
Скачиваний:
0
Добавлен:
01.07.2025
Размер:
946 Кб
Скачать
☆

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

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

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

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

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

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

(b) – FIFO з чотирма сторінковими кадрами

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

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

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

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

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

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

1.13.4 Виштовхування сторінки що довше за все не використовувалася. Алгоритм lru

Одним з наближень до алгоритму OPT є алгоритм, що виходить з евристичного правила, що недавнє минуле – гарний орієнтир для прогнозування найближчого майбутнього.

Ключова відмінність між FIFO і оптимальним алгоритмом полягає в тому, що один дивиться назад, а інший вперед. Якщо використовувати минуле для апроксимації майбутнього, має сенс заміщати сторінку, яка не використовувалася протягом самого довгого часу. Такий підхід називається least recently used алгоритм (LRU). Робота алгоритму проілюстрована на рис. 1.8.

1.8 – Приклад роботи алгоритму LRU

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

Як оптимальний алгоритм, так і LRU не страждають від аномалії Біледі. Існує клас алгоритмів, для яких при одному і тому ж рядку звернень безліч сторінок в пам’яті для n кадрів завжди є підмножиною сторінок для n + 1 кадру. Ці алгоритми не виявляють аномалії Біледі і називаються стековими (stack) алгоритмами.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]