Основы операционных систем, Карпов В.Е. (Лекция №10, 2019)

YOUTUBE · 27.11.2025 05:56

Ключевые темы и таймкоды

Введение в виртуальную память

0:08

Виртуальная память — ключевой механизм в современных вычислительных системах.
Она освобождает программиста от необходимости учитывать объём оперативной памяти.

Принципы виртуальной памяти

0:36

Логическое адресное пространство разбито на участки, которые отображаются на физическое адресное пространство.
Связывание адресов происходит на этапе выполнения.
В оперативной памяти размещается только необходимая часть логического адресного пространства.

Организация виртуальной памяти

2:50

Сегментная и страничная организации памяти могут использоваться для отображения логического адресного пространства.
Отображение не является полностью непрерывным.

Преимущества виртуальной памяти

5:30

Упрощение разработки программ благодаря отсутствию необходимости учитывать объём памяти.
Увеличение количества одновременно выполняемых программ.
Повышение эффективности мультипрограммирования и среднесрочного планирования.

Недостатки виртуальной памяти

7:22

Подкачка данных из вторичной памяти замедляет работу системы.
В системах реального времени виртуальная память не используется из-за увеличения времени отклика.

Реализация виртуальной памяти

9:03

Виртуальная память возможна только при отказе от линейного непрерывного размещения физической памяти.
Для сегментных, страничных и сегментно-страничных схем организация виртуальной памяти возможна с минимальными изменениями.

Страничная организация памяти

9:35

Логический адрес разбивается на смещение внутри страницы и номер страницы.
Таблица страниц используется для построения физического адреса.
Добавляются атрибуты: бит наличия страницы в памяти и бит модификации страницы.

Роль битов в виртуальной памяти

11:29

Бит наличия страницы в памяти обязателен для построения виртуальной памяти.
Бит модификации страницы улучшает эффективность работы виртуальной памяти.
Бит наличия страницы подтверждает, что информация о номере кадра верна.

Бит модификации и подкачка страниц

12:39

Бит модификации указывает, изменялась ли страница после её загрузки в оперативную память.
Если страница не изменялась, нет необходимости переписывать её обратно во вторичную память.
Без бита модификации процесс подкачки будет менее эффективным.

Исключительная ситуация пейдж фолд

14:15

Пейдж фолд возникает, когда процессор не может завершить выполнение команды из-за отсутствия страницы в оперативной памяти.
Процессор прекращает выполнение команды и сохраняет контекст.
Управление передаётся коду операционной системы для обработки ситуации.

Обработка пейдж фолда

15:56

Код операционной системы сохраняет оставшийся контекст и регистры.
Необходимая страница подкачивается в память.
После подкачки и исправления таблицы страниц восстанавливается контекст и выполняется команда.

Стратегии управления виртуальной памятью

17:30

Стратегия выборки: подкачка по запросу или с упреждением.
Стратегия размещения: выбор свободных кадров в физической памяти.
Стратегия замещения: определение, какую страницу убрать из памяти при отсутствии свободных кадров.

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

20:46

Локальные алгоритмы: каждый процесс использует только свои кадры памяти.
Глобальные алгоритмы: процессы могут использовать кадры других процессов или операционной системы.
Локальные алгоритмы проще в понимании и реализации, но глобальные влияют на работу всей системы.

Цели и параметры планирования

23:22

Цель алгоритмов: минимизировать количество пейдж фолдов.
Параметр планирования: строка обращений процесса к памяти.
Строка обращений записывает номера страниц, к которым обращается процесс.

Сокращение строки запросов

25:13

Многократные подряд идущие обращения к одной и той же странице не учитываются при анализе работы виртуальной памяти.
Подряд идущие одинаковые номера страниц заменяются одним номером для сокращения строки запросов.

Алгоритм FIFO

26:35

Алгоритм FIFO «first in, first out» выталкивает из памяти страницу, которая первой попала в неё.
Для анализа работы алгоритма используется таблица, где каждая колонка соответствует элементу в сокращённой строке запросов, а каждая строка — содержимому кадра памяти.

Пример работы алгоритма FIFO

27:29

При отсутствии свободных кадров памяти алгоритм выталкивает страницу с наибольшим номером.
Пример с строкой запросов 0123014 показывает, как алгоритм обрабатывает пейдж-фолты и перемещает страницы между кадрами памяти.

Анализ количества пейдж-фолтов

31:09

Для строки запросов из 12 элементов алгоритм FIFO генерирует 9 пейдж-фолтов при трёх кадрах памяти.
Увеличение количества кадров до четырёх не приводит к снижению количества пейдж-фолтов, а даже увеличивает их число.

Аномалия Беледи

34:12

Аномалия Беледи заключается в том, что увеличение количества кадров памяти может привести к увеличению числа страничных нарушений.
График показывает, что при увеличении количества кадров количество нарушений сначала уменьшается, но затем увеличивается.

Стековые алгоритмы

36:18

Стековые алгоритмы не проявляют аномалии Беледи.
Стековые алгоритмы определяются как такие, для которых набор страниц в памяти для n кадров всегда является подмножеством набора страниц для n+1 кадра.

Алгоритм OPT

37:13

Алгоритм OPT «optimal» является оптимальным стековым алгоритмом.
При необходимости вытолкнуть страницу из памяти алгоритм OPT выбирает ту, к которой дольше всего не будут обращаться.

Работа алгоритма ОПТ

38:04

Алгоритмы работают одинаково до исчерпания свободных кадров памяти.
При обращении к странице с номером четыре возникает пейдж-фолт, так как нет свободных кадров.
Страница с номером три замещается на страницу с номером четыре.

Оптимизация алгоритма ОПТ

38:53

Обращение к страницам 0, 1 и 2 не вызывает пейдж-фолтов.
Исключительная ситуация возникает только при обращении к странице с номером три.
Для завершения строки запросов требуется шесть пейдж-фолтов.

Ограничения оптимального алгоритма

40:14

Оптимальный алгоритм требует предварительного знания о будущих запросах, что на практике невозможно.
В реальной жизни мы видим только часть строки запросов, что делает оптимальный алгоритм нереализуемым.

Алгоритм ЛЕРУ

42:22

Алгоритм ЛЕРУ замещает страницу, к которой дольше всего не обращались.
Пример работы алгоритма: при пейдж-фолте страница с номером два заменяется на страницу с номером четыре.

Недостатки алгоритма ЛЕРУ

44:17

Алгоритм может приводить к повторным пейдж-фолтам из-за неправильного выбора страницы для замещения.
Количество пейдж-фолтов может быть больше, чем у алгоритма ОПТ.

Другие алгоритмы замещения страниц

46:36

Алгоритм НФУ: выбрасывает страницу, к которой реже всего обращались.
Алгоритм «второй шанс»: страница, дольше всего не обращавшаяся, получает второй шанс, прежде чем быть выброшенной.

Явление трэшинга

49:05

Трэшинг возникает, когда количество пейдж-фолтов превышает время выполнения реальных команд.
Локальные алгоритмы не могут предотвратить трэшинг внутри одного процесса.
Глобальный трэшинг может повлиять на всю систему.

График использования процессора

50:27

График показывает зависимость процента использования процессора от степени мультипрограммирования.
Неопытные системные администраторы могут увеличивать степень мультипрограммирования, что приводит к росту загрузки процессора.
При увеличении количества процессов возникает проблема нехватки кадров физической памяти.

Проблема нехватки кадров

52:09

При нехватке кадров процессы сталкиваются с исключениями пейдж-фолт.
Процессы выстраиваются в очередь к устройству вторичной памяти для подкачки страниц.
Процент использования процессора резко падает.

Определение трэшинга

53:37

Трэшинг возникает, когда больше времени уходит на подкачку и откачку страниц, чем на реальное выполнение команд.
Ситуация трэшинга резко снижает производительность системы.
Локальные алгоритмы замещения страниц не позволяют бороться с трэшингом.

Глобальные алгоритмы замещения

54:38

Глобальные алгоритмы позволяют перераспределять кадры между процессами.
Неаккуратное перераспределение может привести к остановке системы.
Глобальные алгоритмы сложнее локальных и требуют более глубокого понимания.

Концепция рабочих множеств

55:36

Концепция рабочих множеств основана на принципе локальности: программа работает с небольшим количеством адресов в памяти.
Рабочее множество — это набор страниц, активно используемых вместе длительное время.
Процесс перемещается между рабочими множествами во время выполнения.

Алгоритм Деннинга

58:47

Алгоритм Деннинга предлагает выделять процессу столько кадров, сколько страниц в рабочем множестве.
Это предотвращает трэшинг, так как в рабочее множество собираются необходимые страницы.
Важно определить момент попадания в рабочее множество и его размер.

Определение рабочего множества

1:00:09

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

Выбор параметра дельта

1:02:02

Выбор параметра дельта — сложная проблема, влияющая на эффективность алгоритмов.
Слишком маленькое окно не позволит обнаружить рабочее множество, а слишком большое — не даст определить его размер.
При бесконечном значении окна размер рабочего множества будет определяться как количество всех страниц в логическом адресном пространстве процесса.

Введение в алгоритм границ

1:03:01

Алгоритм границ проще алгоритма с концепцией рабочего множества.
Идея алгоритма: изменение количества кадров для процесса и отслеживание частоты пейдж-фолтов.
График показывает зависимость частоты пейдж-фолтов от количества выделенных кадров.

Минимальное количество кадров

1:03:58

При слишком маленьком количестве кадров частота пейдж-фолтов становится бесконечной.
Пример с двухадресной архитектурой: для выполнения команды требуется три адреса, но при двух кадрах команда не может быть выполнена.

Влияние количества кадров на частоту пейдж-фолтов

1:04:53

Если все три страницы не находятся в памяти, выполнение команды невозможно, что приводит к бесконечной частоте пейдж-фолтов.

Пороговые границы и управление кадрами

1:05:33

По мере увеличения числа кадров частота пейдж-фолтов уменьшается.
Верхняя граница: неприемлемое число пейдж-фолтов, ниже которой частота считается приемлемой.
Нижняя граница: добавление новых кадров не приводит к существенному уменьшению частоты пейдж-фолтов.
Увеличение или уменьшение числа кадров позволяет поддерживать частоту пейдж-фолтов между верхней и нижней границей.

Заключение

1:07:21

Детали реализации алгоритма можно найти в книге Таненбаума.
Завершение обсуждения управления памятью в операционных системах.
Анонс следующей темы: файлы и файловые системы.