- •1 Аналітична частина
- •1.1 Віртуальна пам’ять в Windows
- •1.2 Керування віртуальною пам’яттю
- •1.3 Структура віртуального адресного простору
- •1.4 Віртуальний адресний простір 32–бітних систем
- •1.5 Сторінковий файл
- •1.6 Апаратна підтримка
- •1.9 Сегментація пам’яті в захищеному режимі
- •1.7 Сегментна організація пам’яті в реальному режимі роботи мікро процесорів x86
- •1.8 Базові адреси та формування лінійних адрес
- •1.10 Функції системи управління пам’яттю
- •1.10.1 Найпростіші схеми управління пам’яттю
- •1.10.2 Схема з фіксованими розділами
- •1.10.3 Один процес в пам’яті
- •1.10.4 Оверлейна структура
- •1.10.5 Стопінг
- •1.10.6 Схема зі змінними розділами
- •1.10.7 Сторінкова пам’ять
- •1.11 Дескрипторні таблиці
- •1.11.1 Дескриптор
- •1.11.2 Глобальна дескрипторна таблиця
- •1.11.3 Дескрипторна таблиця переривань
- •1.11.4 Локальна дескрипторна таблиця
- •1.12 Стратегії управління сторінковою пам’яттю
- •1.13 Алгоритми заміщення сторінок
- •1.13.1 Алгоритм fifo. Виштовхування першої сторінки що прийшла
- •1.13.2 Аномалія Біледі (Belady)
- •1.13.3 Оптимальний алгоритм (opt)
- •1.13.4 Виштовхування сторінки що довше за все не використовувалася. Алгоритм lru
- •1.13.5 Виштовхування рідко використовуваної сторінки. Алгоритм nfu
- •1.14 Огляд способів і засобів вирішення поставлених задач
- •1.14.1 SoftPerfect ram Disk
- •1.15 Постановка задачі на розробку
- •1.16 Висновки
- •2 Аналіз вимог до програмного забезпечення створення засобів опису програми для побудови її автоматної моделі
- •2.1 Виділення первинних вимог
- •2.2 Виділення детальних вимог через uml–діаграми
- •2.2.1 Діаграма прецедентів
- •2.2.2 Діаграми діяльності
- •2.2.3 Діаграма станів
- •2.3 Висновки
- •3 Проектування програмного забезпечення створення засобів опису програми для побудови її автоматної моделі
- •3.1 Архітектурне проектування
- •3.1.1 Об’єктно орієнтована парадигма
- •3.1.2 Структурна ієрархія системи
- •3.1.3 Структурна схема системи
- •3.2 Детальне проектування
- •3.2.1 Діаграма класів
- •3.2.2 Діаграма послідовності
- •3.3 Висновки
- •4 Конструювання та тестування програмного забезпечення
- •4.1 Розробка інтерфейсу користувача
- •4.2 Кодування системи
- •4.2.1 Вибір мови програмування
- •4.2.2Опис розробки програмних компонентів
- •4.2.2.1 Модуль ядра
- •4.2.2.2 Модуль віджетів
- •4.2.2.3 Модуль алгоритмів заміщення
- •4.2.2.4 Модуль графічного інтерфейсу
- •4.3. Детальне тестування програмного засобу
- •4.4. Висновки
- •Висновки
- •Список використаних джерел
- •Текст програми
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) алгоритмами.
