Операционные системы и сети ЭВМ Operating Systems and Networking презентация

(C) В.О. Сафонов, 2007
Виртуальная память
Мотивировка
Потребность в страничной организации
Создание процесса
Замена страницы
Размещение фреймов
Thrashing
Примеры ОС

(C) В.О. Сафонов, 2007
Мотивировка
Виртуальная память – отделение логической памяти пользователя от физической памяти.
Только часть программы требует размещения в памяти для исполнения.
Таким образом, логическое адресное пространство может быть намного больше, чем физическое.
Поддерживает совместное использование одного и того же адресного пространства более чем одним процессом (lightweight processes, etc.).
Допускает более эффективное создание процесса.
Виртуальная память может быть реализована с помощью:
Страничной организации по требованию
Сегментной организаци по требованию

(C) В.О. Сафонов, 2007
Виртуальная память больше, чем физическая память

(C) В.О. Сафонов, 2007
Страничная организация по требованию
Страница загружается в память, только если она реально требуется.
Меньший объем ввода-вывода
Меньший объем памяти
Более быстрая реакция системы
Система может обслуживать более число пользователей
Страница требуется => на нее есть ссылка
Неверная ссылка => прерывание
Страница отсутствует в памяти => подкачать ее в память

(C) В.О. Сафонов, 2007
Преобразование страничной памяти в непрерывное дисковое пространство

(C) В.О. Сафонов, 2007
Бит “valid – invalid”
С каждым элементом таблицы страниц связывается бит “valid/invalid”:
1 ⇒ страница в памяти, 0 ⇒ страница отсутствует в памяти.
Инициализация: для всех элементов таблицы страниц бит valid/invalid = 0.
Пример состояния таблицы страниц.
Если в процессе трансляции адреса бит “valid/invalid” в таблице страниц равен 0 => прерывание по отсутствию страницы в памяти (page fault).

(C) В.О. Сафонов, 2007
Пример таблицы страниц, в которой не все страницы присутствуют в памяти

(C) В.О. Сафонов, 2007
Отсутствие страницы в памяти
Если имеется ссылка на страницу, отсутствующую в памяти, первое же обращение по такой ссылке приведет к прерыванию и вызову ОС (ситуация page fault – отсутствие страницы)
ОС по таблицам определяет:
Неверная ссылка ⇒ прекращение работы программы.
Обычное отсутствие страницы в памяти.
Найти незанятый фрейм.
Считать содержимое страницы в данный фрейм.
Изменение таблиц; validation bit = 1.
Продолжение работы программы

(C) В.О. Сафонов, 2007
Этапы обработки ситуации отсутствия страницы в памяти

(C) В.О. Сафонов, 2007
Ситуация отсутствия свободного фрейма
Замена страницы – найти страницу, загруженную в память, но реально не используемую, и откачать ее.
алгоритм
Производительность – требуется алгоритм, приводящий к наименьшему возможному числу page faults.
Одна и та же страница может быть считана в память несколько раз

(C) В.О. Сафонов, 2007
Оценка производительности стратегии обработки страницы по требованию
Коффициент отказов страниц (Page Fault Rate) 0 ≤ p ≤ 1.0
Если p = 0 – отсутствие отказов страниц
Если p = 1, каждое обращение к странице приводит к отказу
Эффективное время доступа (Effective Access Time - EAT)
EAT = (1 – p) * время доступа к памяти
+ p * (время реакции на отказ
+ [время откачки страницы ]
+ время подкачки страницы
+ время рестарта)

(C) В.О. Сафонов, 2007
Создание процесса
Виртуальная память дает также преимущества при создании процессов:
- Совместное использование страниц процессами (Copy-on-Write)
- Отображение файлов в память (Memory-Mapped Files)

(C) В.О. Сафонов, 2007
Совместное использование страниц процессами
Принцип совместного использования страниц процессами (Copy-On-Write - COW) позволяет первоначально родительскому и дочернему процессам использовать одни и те же страницы памяти.
Если какой-либо процесс модифицирует разделяемую страницу, то только в этом случае данная страница копируется.
Принцип COW обеспечивает более эффективное создание процесса, так как копируются только модифицируемые страницы.
Свободные страницы распределяются из списка страниц, инициализированных нулями.

(C) В.О. Сафонов, 2007
Файлы, отображаемые в память (memory-mapped files)
Ввод-вывод файлов, отображаемых в память, позволяет трактовать файловый ввод-вывод как обычное обращение к памяти путем отображения блока на диске в страницу памяти.
Первоначально файл читается с использованием запроса страниц по требованию. Часть файла размером с одну страницу читается из файла в физическую страницу (фрейм). Последующие чтения из файла и записи в файл трактуются как обычные обращения к памяти.
Это упрощает доступ к файлу, по сравнению с системными вызовами read() и write().
Это позволяет также нескольким процессам отображать в память один и тот же файл, по тому же принципу, как они совместно используют страницы.

(C) В.О. Сафонов, 2007
Файлы, отображаемые в память

(C) В.О. Сафонов, 2007
Замещение страниц
Предотвращение переполнения памяти: подпрограмма обслуживания отказов страниц дополняется поддержкой замещения страниц.
Используется бит модификации для сокращения времени передачи страниц – только модифицированные страницы откачиваются на диск.
Замещение страниц дополняет картину и стратегию разделения между виртуальной и физической памятью – большая виртуальная память может быть отображена на небольшую физическую память.

(C) В.О. Сафонов, 2007
Пример: замещение страниц

(C) В.О. Сафонов, 2007
Краткое изложение стратегии (алгоритма) замещения страниц
Найти, где размещается требуемая страница на диске.
Найти свободный фрейм:
- Если есть свободный фрейм, использовать его.
- Если нет свободных фреймов, использовать алгоритм замещения страниц для выбора фрейма-”жертвы”.
Прочитать содержимое требуемой страницы во вновь освобожденный фрейм. Модифицировать таблицы фреймов и страниц.
Продолжить выполнение процесса.

(C) В.О. Сафонов, 2007
Замещение страниц

(C) В.О. Сафонов, 2007
Алгоритмы замещения страниц
Необходимо добиваться уменьшения коэффициента отказов страниц p.
Оценка алгоритма может быть выполнена путем опробования его на конкретной строке обращений к памяти (строке запросов) и определения числа отказов страниц при данной строке запросов.
Во всех приводимых примерах из области страничной организации строка запросов имеет вид:
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.

(C) В.О. Сафонов, 2007
График зависимости числа отказов страниц от числа фреймов

(C) В.О. Сафонов, 2007
Алгоритм FIFO
(First-in-First-Out)
Строка запросов: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
3 фрейма (3 страницы могут быть одновременно в памяти для одного процесса)
(1, 2, 3) (4, 1, 2) (5, 3, 4)
9 отказов страниц
4 фрейма
(1, 2, 3, 4) (5, 1, 2, 3) (4, 5)
10 (!) отказов страниц
FIFO – алгоритм замещения => аномалия Belady
больше фреймов ⇒ меньше отказов страниц

(C) В.О. Сафонов, 2007
Пример замещения страниц по алгоритму FIFO

(C) В.О. Сафонов, 2007
Аномалия Belady при использовании алгоритма FIFO замещения страниц

(C) В.О. Сафонов, 2007
Оптимальный алгоритм замещения страниц
Замещается та страница, которая не использовалась в течение наибольшего периода времени.
Пример с четырьмя фреймами
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
(1 2 3 4)
4 5 - (всего) 6 отказов страниц
Определение (измерение) того, насколько эффективно работает алгоритм, позволило прийти именно к такому выводу.

(C) В.О. Сафонов, 2007
Пример использования оптимального алгоритма замещения страниц

(C) В.О. Сафонов, 2007
Алгоритм Least Recently Used (LRU)
Строка запросов: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
(1 2 3 4)
5 5 3
4
Реализация счетчиков:
Каждый элемент таблицы страниц содержит счетчик; каждый раз при обращении к странице через некоторый элемент таблицы страниц содержимое часов (clock) копируется в его поле счетчика.
Когда требуется изменение в конфигурации страниц, необходимо проанализировать поля счетчиков, чтобы определить, какую именно страницу заместить (ту, у которой содержимое поля счетчика меньше => требуется применить алгоритм поиска минимального элемента в массиве; сложность O(n), где n – длина таблицы страниц)

(C) В.О. Сафонов, 2007
Замещение страниц по алгоритму LRU

(C) В.О. Сафонов, 2007
Алгоритм LRU (продолжение)
Стековая реализация – хранить стек номеров страниц (в форме двухсвязного списка):
При обращении к странице:
Переместить ее в начало списка
Для этого требуется изменить 6 указателей
При замещении страниц не требуется поиска

(C) В.О. Сафонов, 2007
Использование стека для хранения информации о самых недавних обращениях к страницам