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

1. Операционные системы и сети ЭВМ Operating Systems and Networking Лекция 18

Сафонов Владимир Олегович,
профессор кафедры информатики,
руководитель лаборатории
Java-технологии
НИИММ СПбГУ
Email: [email protected]

2. Виртуальная память

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

3. Мотивировка

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

4. Виртуальная память больше, чем физическая память

(C) В.О. Сафонов, 2007
4

5. Страничная организация по требованию

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

6. Преобразование страничной памяти в непрерывное дисковое пространство

(C) В.О. Сафонов, 2007
6

7. Бит “valid – invalid”

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

8. Пример таблицы страниц, в которой не все страницы присутствуют в памяти

(C) В.О. Сафонов, 2007
8

9. Отсутствие страницы в памяти

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

10. Этапы обработки ситуации отсутствия страницы в памяти

(C) В.О. Сафонов, 2007
10

11. Ситуация отсутствия свободного фрейма

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

12. Оценка производительности стратегии обработки страницы по требованию

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

13. Создание процесса

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

14. Совместное использование страниц процессами

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

15. Файлы, отображаемые в память (memory-mapped files)

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

16. Файлы, отображаемые в память

(C) В.О. Сафонов, 2007
16

17. Замещение страниц

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

18. Пример: замещение страниц

(C) В.О. Сафонов, 2007
18

19. Краткое изложение стратегии (алгоритма) замещения страниц

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

20. Замещение страниц

(C) В.О. Сафонов, 2007
20

21. Алгоритмы замещения страниц

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

22. График зависимости числа отказов страниц от числа фреймов

(C) В.О. Сафонов, 2007
22

23. Алгоритм 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
23

24. Пример замещения страниц по алгоритму FIFO

(C) В.О. Сафонов, 2007
24

25. Аномалия Belady при использовании алгоритма FIFO замещения страниц

(C) В.О. Сафонов, 2007
25

26. Оптимальный алгоритм замещения страниц

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

27. Пример использования оптимального алгоритма замещения страниц

(C) В.О. Сафонов, 2007
27

28. Алгоритм 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
28

29. Замещение страниц по алгоритму LRU

(C) В.О. Сафонов, 2007
29

30. Алгоритм LRU (продолжение)

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

31. Использование стека для хранения информации о самых недавних обращениях к страницам

(C) В.О. Сафонов, 2007
31

32. Q & A

Q&A
Вопросы и ответы
(C) В.О. Сафонов, 2007
32