Управление оперативной памятью

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

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

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

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

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

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

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

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

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

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

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

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

Страничное распределение Основные концепции: Виртуальное адр. пр-во виртуальная - страница K-3 K-2 K-1 × × × L-1 Пространство физической памяти Таблица страниц:

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

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

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

TLB (Translation Lookaside Buffer) TLB вирт. стр. физ. стр.... miss hit VP offset Вирт. адрес: fpoffset Физический адрес: Таблица страниц: Физическая память:...

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

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

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

Иерархическая организация таблицы страниц Остается проблема для 64-х разрядных вычислительных систем (иерархические решения => количество уровней неприемлемо).

Использование хэштаблиц Обычно используются для адресации Используется больше 32 разрядов. VP offset FP offset VP 1 FP 1 VP 2 FP 2 VPFP … … Физическая память f(VP) Хэш таблица Хэш функция

Инвертированные таблицы страниц PidVPOffset PidVP поиск: FP Offset Таблица страниц Проблема – поиск по таблице Использование хэширования

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

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

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

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

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

Замещение страниц Алгоритм LDU (Least Recently Used – «менее недавно» - наиболее давно используемая страница) Вариант возможной аппаратной реализации. Памяти N – страниц. Битовая матрица NxN (изначально все биты обнулены). При каждом обращении к i ой странице происходит присваивание 1 всем битам i ой строки и обнуление все битов i го столбца. Строка с наименьшим 2 ным кодом соответствует искомой странице.

Замещение страниц Алгоритм NFU (Not Frequently Used – редко использовавшаяся страница) Программная модификация LRU. Для каждой физической страницы 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 sizebase N seg Таблица сегментов offset > size да Прерывание нет base + offset Физический адрес

Сегменто-страничная организация памяти Основные концепции: N seg N page offset Необходимые аппаратные средства: Упрощенная модель Intel. селектор offset N seg локализация защита Таблицы локальных дескрипторов (сегменты доступные для данного процесса) LDT (Local Descriptor Table) Таблица глобальных дескрипторов (разделяемые между процессами сегменты) GDT (Global Descriptor Table) Каждая запись LDT и GDT – полная информация о сегменте (адрес базы, размер и т.д.). Виртуальный адрес:

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