Операционные системы/Управление оперативной памятью
Материал из eSyr's wiki.
(Новая: Основные задачи управления ОП: #'''Контроль состояния каждой единицы памяти''' (свободна/распределена). ...) |
(→Алгоритм NRU (Not Recently Used – не использовавшийся в последнее время)) |
||
| Строка 188: | Строка 188: | ||
#При запуске процесса M и R для всех страниц процесса обнуляются | #При запуске процесса M и R для всех страниц процесса обнуляются | ||
#По таймеру происходит обнуление всех битов R | #По таймеру происходит обнуление всех битов R | ||
| - | #При возникновении страничного прерывания ОС делит все | + | #При возникновении страничного прерывания ОС делит все страницы на классы: |
#*Класс 0: R=0; M=0; - не читался и не изменялся. | #*Класс 0: R=0; M=0; - не читался и не изменялся. | ||
#*Класс 1: R=0; M=1; | #*Класс 1: R=0; M=1; | ||
Текущая версия
Основные задачи управления ОП:
- Контроль состояния каждой единицы памяти (свободна/распределена). Система должна обладать информацией о том, какая единица памяти свободна, какая занята, кем и почему. Соответственно, эта функция совместно обеспечивается как аппаратурой компьютера, так и программным обеспечением ОС. ОС создает для этих целей специальные таблицы.
- Стратегия распределения памяти. Надо выбрать правила, по которым принимать решения: когда, кому и сколько памяти должно быть выделено.
- Выделение памяти. Принятие решения о выделении конкретного объема памяти для потребителя.
- Стратегия освобождения памяти (процесс освобождает, ОС “забирает” окончательно или временно). Одна из самых важных функций. Выбор стратегии, на основании которой система принимает решения о том, сколько и где памяти надо отобрать на время (при появлении более приоритетного процесса) или навсегда.
Поговорим о стратегиях и методах управления. Рассмотрим целый сектор различных методов. Некоторые старые стратегии управления памятью используются и сейчас, например в мобильных телефонах.
Стратегии и методы управления:
- Одиночное непрерывное распределение.
- Распределение разделами.
- Распределение перемещаемыми разделами.
- Страничное распределение.
- Сегментное распределение.
- Сегменто-страничное распределение.
План рассмотрения стратегий управления:
- Основные концепции.
- Необходимые аппаратные средства (необходимое аппаратное обеспечение).
- Основные алгоритмы.
- Достоинства, недостатки.
[править] Одиночное непрерывное распределение
ОП делится на 2 области. В одной находится ОС, другая предназначена для задач пользователя (предполагается однопроцессная система).
Необходимые аппаратные средства:
- Регистр границ + режим ОС / режим пользователя (В регистре границ находится граница между ОС и пользовательской частью ОП)
Если ЦП в режиме пользователя попытается обратиться в область ОС, то возникает прерывание.
В режиме ОС мы можем обращаться в любую точку ОП, если мы находимся в пользовательском режиме, то запрошенный адрес сравнивается с содержимым регистра границ, и , если он окажется меньше, т.е. мы хотим обратиться в часть ОП, занятую под ОС, то выдается прерывание.
Алгоритм – процесс заканчивается, мы меняем на следующий.
Достоинства: простота. Недостатки (они следуют из организации):
- Часть памяти просто не используется (внешняя фрагментация).
- Процессом/заданием память занимается все время выполнения. Внутренняя фрагментация заключается в том, что вся область памяти, которую процесс занимает, занимается процессом на всё время его выполнения. Это означает, что достаточно большие области памяти, которые заняты процессом, не используются, т.к. обычно управление достаточно локализовано. Т.е. неэффективность работы с памятью.
- Ограничение на размеры процесса. Т.е. загрузить в эту систему процесс, превосходящий область памяти, мы не можем.
[править] Распределение неперемещаемыми разделами
Суть: Есть ОС и оставшаяся физическая память. Оставшуюся физическую память делим на конкретное количество разделов. В каждом может быть свое задание и свой процесс. Внутри каждого раздела все аналогично рассмотренному выше примеру.
Необходимые аппаратные средства:
- Необходимо наличие 2 регистров границ, т.к. необходимо обеспечить корректность как по отношению к другим пользовательским разделам, так и по отношению к ОС.
- Ключи защиты (PSW). Каждый раздел имеет свой ключ защиты, который проверяется при всех операциях чтения\записи.
Недостатки:
- Перегрузка регистра границ при каждой смене контекста;
- Сложности при использовании каналов/процессоров ввода/вывода. Если процесс попытается читать не из своей области, то это тяжело отловить. Эту проблему решают Ключи защиты.
Алгоритмы: Модель статического определения разделов.
А. Много входных очередей процессов.
Сортировка входной очереди процессов по отдельным очередям к разделам. Вся очередь процессов разбивается на к очередей, с каждой из которых связан свой раздел. Процесс размещается в разделе минимального размера, достаточного для размещения данного процесса. В случае отсутствия процессов в каких-то под очередях – неэффективность использования памяти.
Недостаток: Может возникнуть ситуация, когда очередь больших процессов пуста, а в очереди маленьких процессов очень много процессов. А перегрузить мы не сможем.
Б. Одна входная очередь процессов.
- При освобождении раздела – поиск (в начале очереди) первого процесса, который может разместиться в разделе. Проблема: большие разделы маленькие процессы. Это несправедливо по отношению к большим процессам.
- При освобождении раздела – поиск процесса максимального размера, не превосходящего размер раздела. Проблема: дискриминация “маленьких” процессов.
- Оптимизация варианта 2. Каждый процесс имеет счетчик дискриминации. Если значение счетчика процесса >= K, то обход его в очереди невозможен.
Достоинства:
- Простое средство организации мультипрограммирования.
- Простые средства аппаратной поддержки.
- Простые алгоритмы.
Недостатки:
- Внешняя Фрагментация.
- Ограничение размерами физической памяти как внутри одного раздела, так и в целом
- Весь процесс размещается в памяти – возможно неэффективное использование и внутренняя фрагментация.
[править] Распределение перемещаемыми разделами
Система имеет фиксированное количество разделов. Через некоторое время ее использования начинается внешняя фрагментация.
Решение: перемещение разделов и освобождение одного большого куска. Но это требует очень больших затрат.
Необходимые аппаратные средства:
- Регистры границ + регистр базы
- Ключи + регистр базы
Алгоритмы: Аналогично предыдущему.
Достоинства:
- Потенциальная ликвидация внешней фрагментации
Недостатки:
- Внутренняя фрагментация
- Ограничение размером физической памяти
- Затраты на перекомпоновку. Операция освобождения одного большого куска ОП очень тяжела.
[править] Страничное распределение
См. :
Содержимое таблицы страниц определяет соответствие виртуальной памяти физической для выполняющейся в данный момент программы/процесса. Соответствие определяется следующим образом: i-я строка таблицы соответствует i-й виртуальной странице. При замене процесса таблицу надо менять.
Проблемы:
- Размер таблицы страниц (количество 4кб страниц при 32-х разрядной адресации – 1000000. Таблица должна иметь миллион строк, а таблицу надо перегружать каждый раз при смене контекстов. Любой процесс имеет собственную таблицу страниц).
- Скорость отображения. Эта проблема, фактически, следует из проблемы 1.
Возможные аппаратные средства:
- Полностью аппаратная таблица страниц, которая будет находится в виде сверхоперативной памяти. Все преобразования будут проходить очень быстро (проблемы: стоимость, полная перегрузка при смене контекстов + скорость преобразования).
- Альтернативное решение - организация таблицы страниц на ОП. В этом случае нам нужен аппаратный регистр начала таблицы, и переключение с контекста на контекст будет осуществляться очень хорошо и быстро, просто изменением содержимого регистра начала таблицы. При этом мы получим многократное увеличение количества обращений в память. И, как минимум, мы потеряем 100% эффективности. Понятно, что часть проблем будут минимизированы за счет работы КЭШ, но все равно это будет неэффективно. Но зато это просто и дешево.
- Гибридные решения. Т.е. те, которые имеют и программную и аппаратную составляющую.
[править] Поля таблицы страниц
Предположим, что таблицы страниц индексируются по номерам соответствующих виртуальных страниц. Содержимое каждой записи – информация о соответствующей виртуальной странице.
Поля таблицы страниц:
- α – присутствие/отсутствие. Если этот признак установлен, то это означает, что в поле «номер физической станицы» находится та самая физическая страница, к которой мы обращаемся. Если отсутствует, то возможны 2 варианта: либо эта страничка запрещена для данного процесса, либо она разрешена, но сама страница в это время откачена во внешнюю память. Но в любом случае, если есть элемент отсутствия, то при обращении к этой строчке происходит прерывание.
- β – поле защиты (чтение, чтение/запись, выполнение). Когда процессор доходит до таблицы страниц, он уже знает, с какой целью он получает этот адрес. Либо этот адрес есть операнд, куда мы хотим записать, либо этот адрес есть операнд, из которого мы хотим считать информацию, либо этот адрес есть операнд команды, которую я хочу выбрать и выполнить (goto адрес). Соответственно это поле обеспечивает защиту. Т.е. в зависимости от того, с какой целью процессор обращается к этой строчке, и содержимого этой строчки (а содержимое могут быть коды, которые разрешают чтение, или чтение/запись, или выполнение, или запрещают их – так же как в ФС), то при нарушении происходит прерывание.
- γ – признак изменения (модификации). Если мы в эту страничку писали, то этот признак будет установлен. Этот признак устанавливается обычно аппаратно – автоматически. Снимается он либо аппаратно, либо программно ОС.
- δ – обращение (чтение, запись, выполнение). Когда мы обратились либо за чтением, либо за записью и т.д.
- ε – признак блокировки кэширования. Я заказал обмен: прочесть информацию с внешнего устройства на какую-то страницу, в конечном итоге физическую станицу. А на самом деле Ν страниц у меня находится в КЭШе. Как разрешить эту коллизию? Внешнее устройство кинет информацию в физическую память, а на самом деле я работаю с КЭШем, а потом из КЭШа я это переобновлю и все потеряется. Для того, чтобы можно было синхронизовать эту вещь, используется блокировка кэширования.
[править] TLB буфер
Для разрешения всех коллизий, связанных со скоростью, размерами и прочим, используются гибридные решения. И, в частности, одно из решений основывается на TLB буферах.
TLB (Translation Lookaside Buffer) – буфер быстрого преобразования адресов. В процессоре есть буфер (небольшой), который используется в качестве КЭШ таблицы страниц.
Структура буфера: Каждая запись содержит те же поля, что и таблица страниц. TLB буфер – буфер оперативной памяти. Поиск идет параллельно: за одну операцию просматривается наличие всей таблицы.
Мы мимеем виртуальный адрес, в котором традиционно есть поле «виртуальная страница» и есть поле «смещение». Процессор выбирает поле «виртуальная страница» и обращается к TLB буферу. Если мы фиксируем факт попадания, то в этом случае автоматически происходит замена поля виртуальной страницы на содержимое поля физической страницы – так мы получили физический адрес со всеми вытекающими параметрами, которые могут находиться в TLB. Если мы фиксируем промах, то в этом случае происходит прерывание, управление передается ОС. И ОС уже программно находит необходимую строчку и обновляет TLB буфер и соответственно дообрабатывает команду преобразования виртуального адреса в физический.
[править] Иерархическая организация таблицы страниц
Проблема – размер таблицы страниц.
Объем виртуальной памяти современногокомпьютера - 232,…264 Пример: Vстр. = 212 (4Kb) => Количество виртуальных страниц – 220 (много) Решение – использование многоуровневых таблиц страниц (2х, 3х, 4х)
[править] Многоуровневая организация
Современные системы используют многоуровневую организацию таблицы страниц.
Пример: двухуровневая организация.
Система разделяет VP на 2 подполя: VP1 - индекс по внешней таблице страниц, а VP2 – смещение по странице, на которую указывает VP1. >4 уровней иерархии считается не целесообразно.
Суть многоуровневости достаточно простая: если мы имеем виртуальный адрес следующей структуры (на слайде): смещение 4кб и 20-ти разрядный адрес, то система разделяет поле виртуальной странички на два подполя. 1-е подполе – это индекс по внешней таблице страниц, через этот индекс мы попадаем на страничку, в которой находится продолжение описания этой таблицы; 2-е поле – это смещение по этой странице. Т.е. мы имеем внешнюю таблицу, по VP1 мы индексируемся и соответственно по содержимому этой таблицы попадаем на некоторую страницу, в которой находится часть таблицы страниц 2-го уровня. И по VP2 мы проходим смещение по этой странице и в соответствующем элементе получаем номер физической страницы. Этих уровней может быть 2, 3, 4. Больше 4-х считается нецелесообразным. Для 64-х разрядных машин таких уровней если их реализоввывать должно быть не менее 7, что совсем нецелесообразно.
[править] Использование хэш-таблиц
ХЭШ функции изначально использовались при организации таблицы имен.
ХЭШ – функция берет номер виртуальной страницы и по этому номеру виртуальной страницы имеется некоторая функция, которая определяет номер записи хэш-таблицы. С этой записью связан список виртуальных страниц с их физическими страницами, которые имеют одинаковое значение хэш-функции. Это означает, что при преобразовании мы берем виртуальную страницу и фактически автоматически попадаем на этот самый список. Дальше по этому списку мы можем дойти до искомой страницы и получаем физическую страницу. Если в списке нет, то это означает, что и странички такой нет.
[править] Инвертированные таблицы страниц
Используется в более развитых системах, системах аппаратно поддерживающих pid обрабатываемого процесса.
Каждая строка таблицы соответствует конкретной физической странице.
Проблема – поиск по таблице. Решение – использование хэширования
[править] Замещение страниц
Проблема загрузки «новой» страницы в память, если свободных мест в памяти нет. Необходимо выбрать страницу для удаления из памяти (с учетом ее модификации пр.)
[править] Алгоритм NRU (Not Recently Used – не использовавшийся в последнее время)
Используются биты статуса страницы. R – обращение, М – модификация. Устанавливаются аппаратно при обращении или модификации.
Алгоритм:
- При запуске процесса M и R для всех страниц процесса обнуляются
- По таймеру происходит обнуление всех битов R
- При возникновении страничного прерывания ОС делит все страницы на классы:
- Класс 0: R=0; M=0; - не читался и не изменялся.
- Класс 1: R=0; M=1;
- Класс 2: R=1; M=0;
- Класс 3: R=1; M=1;
- Случайная выборка страницы для удаления в непустом классе с минимальным номером
[править] Алгоритм FIFO (First In, First Out – первым пришел, первым ушел)
Стратегия: лучше выгрузить измененную страницу, к которой не было обращений как минимум в течение 1 «тика» таймера, чем часто используемую страницу.
ОС фиксирует время размещения страницы. Наиболее старую страницу удаляем (т.е. FIFO), но это может быть неправильно, т.к. старая может часто использоваться, а новая - редко. Поэтому используется модификация этотого алгоритма (алгоритм вторая попытка). R – бит обращения. 1.Выбирается самая «старая страница». Если R=0, то она заменяется 2.Если R=1, то R – обнуляется, обновляется время загрузки страницы в память (т.е. переносится в конец очереди). На п.1
[править] Алгоритм «Часы»
Алгоритм аналогичен предыдущему, только все страницы связаны в кольцевой список. Существует указатель (стрелка) на текущую страницу.
[править] Алгоритм LRU (Least Recently Used – «менее недавно» - наиболее давно используемая страница)
Пусть в памяти N – страниц. Составляется битовая матрица NxN (изначально все биты обнулены). При каждом обращении к iой странице происходит присваивание 1 всем битам iой строки и обнуление всех битов iго столбца. Строка с наименьшим двоичным числом соответствует искомой странице.
[править] Алгоритм NFU (Not Frequently Used – редко использовавшаяся страница)
Развитие предыдущего алгоритма. Для каждой физической страницы заводится программный счетчик, который изначально обнулен. По таймеру к счетчикам прибавляется признак доступа (R).
В момент принятия решения выбирается страница с минимальным значением счетчика. Это все решается программно.
Недостаток – если процесс поработал и «сидит без дела», то удалить его не удастся, а он не работает. Модификация:
- Значение счетчика сдвигается на 1 разряд вправо.
- Значение R добавляется в крайний левый разряд счетчика.
[править] Достоинства и недостатки страничной памяти
Достоинства:
- нет проблемы внешней фрагментации
- никак не ограничены размерами физической памяти, т.е. мы часть страниц можем всегда держать во вне и через прерывания их закачивать, когда они нам нужны
Недостатки:
- проблема принятия решений об организации таблицы страниц
- при страничной организации памяти адресное пространство представляет одну модель от 0 до Ν. Т.е. мы работаем с одним пространством адресации в этом процессе. В некоторых ситуациях это бывает не очень удобно.
[править] Сегментная организация памяти
Основные концепции:
- Виртуальное адресное пространство представляется в виде совокупности сегментов
- Каждый сегмент имеет свою виртуальную адресацию (от 0 до N-1)
- Виртуальный адрес: <номер_сегмента, смещение>
Необходимые аппаратные средства для организации сегментной памяти достаточно концептуально просты. Это таблица сегментов, по которой при вычислении физического адреса из виртуального мы можем индексироваться по номеру сегмента. Соответственно, каждая запись таблицы сегментов содержит размер сегмента и адрес начала сегмента.
- «+» простота реализации
- «+» размер таблицы сегментов может быть много меньше размера таблицы страниц
- «-» наличие внешней фрагментации
- «-»сегмент рассматривается как единое целое
Преобразование происходит достаточно просто: мы индексируемся по таблице, получаем запись, после этого сравниваем смещение с размером сегмента:
- если смещение выходит за пределы размера – происходит прерывание,
- иначе мы к значению базы прибавляем смещение и получаем физический адрес.
[править] Сегменто - страничная организация памяти
Необходимые аппаратные средства: упрощенная модель Intel.
Есть две таблицы: таблица локальных дескрипторов (сегменты, доступные для данного процесса) LDT (Local Descriptor Table) и таблица глобальных дескрипторов (сегменты, разделяемые между процессами сегменты) GDT (Global Descriptor Table).
Виртуальный адрес содержит 2 поля: селектор и смещение. Селектор содержит информацию о номере сегмента и о локализации. Поле локализация указывает, в какой из двух таблиц надо искать.
По LDT и GDT и виртуальному адресу мы вычисляем линейный адрес. Линейный адрес имеет двухуровневую страничную организацию. По этим параметрам мы вычисляем физический адрес.
При использовании алгоритма сегментно\страничной организации к плюсам страничной прибавляются плюсы сегментной.
