Управление оперативной памятью 1.Контроль состояния каждой единицы памяти (свободна/распределена) 2.Стратегия распределения памяти (кому, когда и сколько памяти должно быть выделено) 3.Выделение памяти (выбор конкретной области, которая должна быть выделена) 4.Стратегия освобождения памяти (процесс освобождает, ОС забирает окончательно или временно) Основные задачи

1.Одиночное непрерывное распределение 2.Распределение разделами 3.Распределение перемещаемыми разделами 4.Страничное распределение 5.Сегментное распределение 6.Сегментно-страничное распределение Управление оперативной памятью 1.Основные концепции 2.Необходимые аппаратные средства 3.Основные алгоритмы 4.Достоинства, недостатки Стратегии и методы управления План рассмотрения стратегий управления

Одиночное непрерывное распределение Основные концепции Реально используется Выделено, но не используется Доступно (выделено) ОС

Одиночное непрерывное распределение Регистр границ + режим ОС / режим пользователя Если ЦП в режиме пользователя попытается обратиться в область ОС, то возникает прерывание Алгоритмы: очевидны. 1.Часть памяти не используется 2.Процессом/заданием память занимается все время выполнения 3.Ограничение на размеры задания Достоинства: простота. Необходимые аппаратные средства Недостатки

ОС … Распределение неперемещаемыми разделами Основные концепции Раздел 1 Раздел 2 Раздел N … … … … N входных очередей (Вариант А) Одна очередь (Вариант B)

Распределение неперемещаемыми разделами 1.Два регистра границ 2.Ключи защиты (PSW) Необходимые аппаратные средства

Распределение неперемещаемыми разделами Модель статического определения разделов А.Сортировка входной очереди процессов по отдельным очередям к разделам. Процесс размещается в разделе минимального размера, достаточного для размещения данного процесса. В случае отсутствия процессов в каких-то подочередях неэффективность использования памяти. Алгоритмы

Распределение неперемещаемыми разделами Модель статического определения разделов Б.Одна входная очередь процессов 1.Освобождение раздела поиск (в начале очереди) первого процесса, который может разместиться в разделе. Проблема: большие разделы маленькие процессы 2.Освобождение раздела поиск процесса максимального размера, не превосходящего размер раздела. Проблема: дискриминация «маленьких» процессов 3.Оптимизация варианта 2. Каждый процесс имеет счетчик дискриминации. Если значение счетчика процесса K, то обход его в очереди невозможен Алгоритмы

Распределение неперемещаемыми разделами 1.Фрагментация 2.Ограничение размерами физической памяти 3.Весь процесс размещается в памяти возможно неэффективное использование 1.Простое средство организации мультипрограммирования 2.Простые средства аппаратной поддержки 3.Простые алгоритмы Достоинства Недостатки

Распределение перемещаемыми разделами Основные концепции Виртуальная память Процесс 4 (например, V = V 2 + ½ V 5 ) OC V 1 Процесс 1 V 2 Свободно V 3 Процесс 2 V 4 Процесс 3 V 5 свободно OC V 1 Процесс 1 V 3 Процесс 2 V 4 Процесс 3 V 2 V 5 свободно

Распределение перемещаемыми разделами 1.Регистры границ + регистр базы 2.Ключи + регистр базы Алгоритмы: Необходимые аппаратные средства

Распределение перемещаемыми разделами 1.Ограничение размером физической памяти 2.Затраты на перекомпоновку 1.Ликвидация фрагментации Достоинства Недостатки

Страничное распределение Основные концепции Виртуальное адресное пространство виртуальная страница Пространство физической памяти Таблица страниц 0 1X 2 4 … K – 3X K – 2X K – … L – 1

Страничное распределение Таблица страниц отображение номеров виртуальных страниц на номера физических. Основные концепции 1.Размер таблицы страниц (количество 4KB страниц при 32-х разрядной адресации ; любой процесс имеет собственную таблицу страниц) 2.Скорость отображения Проблемы

Страничное распределение 1.Полностью аппаратная таблица страниц (стоимость, полная перегрузка при смене контекстов, скорость преобразования) 2.Таблица страниц в ОЗУ + Регистр начала таблицы страниц в памяти (простота, управление смены контекстов, медленное преобразование) 3.Гибридные решения Необходимые аппаратные средства

Страничное распределение Размер и организация таблицы страниц ??? α присутствие/отсутствие β защита (чтение, чтение/запись, выполнение) γ изменения δ обращение (чтение, запись, выполнение) ε …………………….. Алгоритмы и организация данных Модельная структура записи таблицы страниц εδγβαНомер физической страницы

TLB (Translation Lookaside Buffer) TLB miss hit Виртуальный адрес Физический адрес Таблица страниц Физическая память VPOffset Вирт. стр.Физ. стр. … … FPOffset

Иерархическая организация таблицы страниц Пример Проблема размер таблицы страниц. Объем виртуальной памяти современного компьютера 2 32 …2 64 байт V вирт. = 2 32 V стр. = 2 12 (4KB) Количество виртуальных страниц 2 20 (много) Решение использование многоуровневых таблиц страниц (2 х, 3 х, 4 х )

Иерархическая организация таблицы страниц Двухуровневая организация Индекс по «внешней» таблице страниц Смещение по странице, указанной через VP 1 VPOffset VP 1 VP 2 Offset 12

Иерархическая организация таблицы страниц Внешняя таблица страниц Таблица страниц второго уровня Физическая память VP 2 VP 1

Использование хэш-таблиц (функция расстановки) … … Физическая память f(VP) Хэш таблица Хэш функция VPOffset FPOffset VP 1 FP 1 VP 2 FP 2 VPFP

Инвертированные таблицы страниц поиск: FP Таблица страниц Проблема поиск по таблице ( хэширование ) Решение проблемы перезагрузки таблицы страниц при смене обрабатываемых ЦП процессов PIDVPOffset PIDVP FPOffset

Замещение страниц Проблема загрузки «новой» страницы в память. Необходимо выбрать страницу для удаления из памяти (с учетом ее модификации и пр.) Алгоритм NRU (Not Recently Used не использовавшийся в последнее время) Используются биты статуса страницы в записях таблицы страниц R обращение M изменение устанавливаются аппаратно обнуление программно (ОС)

Замещение страниц Алгоритм 1.При запуске процесса M и R для всех страниц процесса обнуляются 2.По таймеру происходит обнуление всех битов R 3.При возникновении страничного прерывания ОС делит все страниц на классы: Класс 0: Класс 1: Класс 2: Класс 3: 4.Случайная выборка страницы для удаления в непустом классе с минимальным номером M=0 R=0 M=1 R=0 M=0 R=1 M=1 R=1

Замещение страниц Стратегия: лучше выгрузить измененную страницу, к которой не было обращений как минимум в течение 1 «тика» таймера, чем часто используемую страницу

Замещение страниц Алгоритм FIFO «Первым прибыл первым удален» простейший вариант FIFO. Проблема «справедливости» 1.Выбирается самая «старая страница». Если R=0, то она заменяется 2.Если R = 1, то R обнуляется, обновляется время загрузки страницы в память (т.е. переносится в конец очереди). На п.1 Модификация алгоритма (алгоритм вторая попытка)

Замещение страниц Алгоритм «Часы» 1.Если R = 0, то выгрузка страницы и стрелка на позицию вправо 2.Если R = 1, то R обнуляется, стрелка на позицию вправо и на п.1

Замещение страниц Алгоритм NFU (Not Frequently Used редко использовавшаяся страница) Для каждой физической страницы i – программный счетчик Count i 0.Изначально Count i – обнуляется для всех i. 1.По таймеру Count i = Count i + R i Выбор страницы с минимальным значением Count i «помнит» старую активность при большой активности, возможно переполнение счетчика Недостатки

Замещение страниц Модификация NFU алгоритм старения Модификация: 1.Значение счетчика сдвигается на 1 разряд вправо 2.Значение R добавляется в крайний левый разряд счетчика

Сегментная организация памяти Виртуальное адресное пространство представляется в виде совокупности сегментов Каждый сегмент имеет свою виртуальную адресацию (от 0 до N – 1) Виртуальный адрес: Основные концепции

Сегментная организация памяти Виртуальный адрес: N seg Таблица сегментов offset > size да Прерывание нет base + offset Физический адрес NsegOffset Необходимые аппаратные средства sizebase

Сегментно-страничная организация памяти Основные концепции: NsegNpageOffset

Сегментно-страничная организация памяти Модельный пример (Intel): Таблицы локальных дескрипторов (сегменты доступные для данного процесса) LDT (Local Descriptor Table) Таблица глобальных дескрипторов (разделяемые между процессами сегменты) GDT (Global Descriptor Table) Каждая запись LDT и GDT – полная информация о сегменте (адрес базы, размер и т.д.). Виртуальный адрес: СелекторOffset NsegЛокализацияЗащита

Сегментно-страничная организация памяти Необходимые аппаратные средства Виртуальный адресЛинейный адресФизический адресP1P1 P2P2 offset использование селектора и содержимого таблиц LDT и GDT двухуровневая страничная организация