Страничная память. Принципы функционирования ЭВМ

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

Страничная организация памяти относится к методам несмежного размещения процессов в основной памяти. Она позволяет свести к минимуму общую фрагментацию за счет полного устранения внешней фрагментации и минимизации внутренней фрагментации. Эта форма организации виртуальной памяти во многом похожа на сегментную. Основные различия заключаются в том, что все страницы, в отличие от сегментов, имеют одинаковые размеры, а разбиение виртуального адресного пространства процесса на страницы выполняется системой автоматически. Типичный размер страницы – несколько килобайт. Для процессоров Pentium, например, страница равна 4 Кб.

Все виртуальные адреса одного процесса относятся к единому линейному пространству, проще сказать, виртуальный адрес выражается одним числом, от 0 до некоторого максимума. Старшие разряды двоичного представления этого адреса определяют номер виртуальной страницы, а младшие разряды – смещение от начала страницы. Например, для страниц по 4 Кб смещение занимает 12 младших разрядов адреса.

Физическая память также считается разбитой на части, размеры которых совпадают с размером виртуальной страницы. Эти части называются физическими страницами или страничными кадрами (page frames). Таблица страниц процесса по структуре похожа на таблицу сегментов. Для каждой виртуальной страницы она содержит: режим доступа, флаг присутствия страницы в памяти, номер страничного кадра, флаг чистоты. Если страница отсутствует в памяти, ее данные сохраняются в файле подкачки, который в этом случае чаще называют страничным файлом (page file).

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

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

Управление замещением страниц в физической памяти строится по принципу загрузки по требованию (demand paging). Это означает, что когда программа только лишь планирует использование определенной области виртуальной памяти, соответствующие виртуальные страницы помечаются в таблице страниц как существующие, но находящиеся в данный момент на диске. Выделение страниц физической памяти не выполняется до тех пор, пока программа не обратится к одной из ячеек виртуальной страницы. При этом происходит аппаратное прерывание по отсутствию страницы в памяти. Это прерывание обрабатывает часть ОС, которая называется менеджером памяти. Менеджер должен выполнить следующие действия:

• найти свободную физическую страницу;
• если свободной страницы нет, то по определенному алгоритму выбрать занятую страницу, которая будет вытеснена на диск;
• если выбранная страница «грязная», т.е. ее содержимое изменялось после того, как она последний раз была прочитана с диска, то «очистить» страницу, т.е. записать ее в соответствующий блок страничного файла;
• на освободившуюся физическую страницу прочитать блок страничного файла, закрепленный за запрошенной виртуальной страницей;
• откорректировать таблицу страниц, пометив вытесненную страницу как отсутствующую в физической памяти, а прочитанную – как присутствующую и при этом «чистую»;
• повторить обращение к запрошенному виртуальному адресу.

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

Перемещение страниц по запросу

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

1. Программа может выполняться на ЦП, когда часть страниц находится в основной памяти, а часть во внешней;
2. В процессе выполнения новая страница не перемещается в основную память до тех пор, пока в ней не возникла необходимость.

Для учета распределения страниц между внешней и основной памятью каждая строка таблицы страниц дополняется битом местонахождения страницы (valid/invalid bit). В том случае если ЦП пытается использовать страницу, помеченную значением invalid, возникает событие, называемое страничной недостаточностью. Страничная недостаточность вызывает прерывание выполнения программы и передачу управления ОС. Реакция ОС на страничную недостаточность заключается в том, что необходимая страница загружается в основную память.

Основные этапы обработки страничной недостаточности:

1. ЦП, прежде чем осуществлять преобразование логического адреса в физический, проверяет значение бита местонахождения необходимой страницы.
2. Если значение бита invalid, то процесс прерывается и управление передается ОС для обработки события страничная недостаточность.
3. Отыскивается необходимая страница во вторичной памяти и свободная страничная рамка в основной.
4. Требуемая страница загружается в выбранную страничную рамку.
5. После завершения операции загрузки редактируется соответствующая строка таблицы страниц, в которую вносится базовый адрес и значение бита местонахождения – valid.
6. Управление передается прерванному процессу.

Метод замещения страниц

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

Обработка страничной недостаточности с учетом замещения:

1. Определяется местонахождение страницы путем анализа бита нахождения.
2. Если значение бита invalid, то разыскивается свободная страничная рамка.
3. Если имеется свободная страничная рамка, то она используется.
4. Если свободной страничной рамки нет, то используется алгоритм замещения, который выбирает страницу – жертву.
5. Страница – жертва перемещается в пространство свопинга и таблица страниц редактируется.
6. Требуемая страница загружается на место страницы – жертвы и соответствующим образом редактируется таблица страниц.

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

Алгоритм распределения страничных рамок

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

1. FIFO (first in first out). Этот алгоритм ассоциирует с каждой страницей время, когда эта страница была помещена в память. Для замещения выбирается наиболее старая страница. Алгоритм учитывает только время нахождения страниц в памяти, но не учитывает используемость страницы.
2. Алгоритм LRU (least recently used). Он выбирает для замещения ту страницу, на которую не было ссылок на протяжении длительного периода времени. Он ассоциирует с каждой страницей время последнего использования этой страницы. Замещается та страница, которая дольше всех не использовалась. Применяется два подхода при внедрении этого алгоритма:
1. Подход на основе логических часов – ассоциирует с каждой строкой таблицы поле «время использования», а в ЦП добавляются логические часы. Логические часы увеличивают значение при каждом обращении к памяти. Каждый раз когда осуществляется ссылка на страницу, значение регистра логических часов копируется в поле «время использования». Заменяется страница с наименьшим значением в отмеченном поле путем сканирования всей таблицы станиц.
2. Подход на основе стека номеров страниц – стек номеров страниц хранит номера страниц, упорядоченных в соответствии с историей их использования, на «вершине» стека располагается только что использованная страница, а на «дне» дольше всех не используемая страница. Как только осуществляется ссылка на страницу, она перемещается на вершину стека, а номера всех страниц сдвигаются вниз.

Лекция 13, Страничная организация памяти

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

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

На всех этапах подготовки программ, включая загрузку в память, программа представляется в виртуальных адресах , и лишь при выполнении машинной команды виртуальные адреса преобразуются в физические. Для каждой программы, выполняемой в мультипрограммном режиме, создается своя виртуальная память . Каждая программа использует одни и те же виртуальные адреса от нулевого до максимально большого в данной архитектуре.

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

Как отмечалось выше, при страничном представлении памяти виртуальный ( логический) адрес представляет собой номер виртуальной страницы и смещение внутри этой страницы. В свою очередь , физический адрес - это номер физической страницы и смещение в ней.

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

Перевод виртуальных адресов в физические проиллюстрирован на рис. 3.12 .

Рассмотрим пример преобразования адреса виртуальной страницы в адрес физической страницы . Пусть компьютер использует адресное пространство , предполагающее разбиение на страницы объемом V стр = 1I , и имеет оперативную память V ОЗУ = 3 страницы. Пусть на компьютере одновременно выполняются четыре программы, имеющие следующее количество страниц: V A = 2 , V B = 1 , V C = 3 , V D = 2 . Переключение между программами происходит через время кванта t k = 1 . Время выполнения каждой страницы любой программы составляет t = 2t k . Полагаем, что страницы программ загружаются в оперативную память по мере необходимости и по возможности в свободные области ОЗУ . Если вся память занята, то новая страница замещает ту, к которой дольше всего не было обращений.

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

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

Если каждая страница имеет объем 1000 адресуемых ячеек, то, например, в такте 9 обращение по виртуальному адресу 1100 программы A ( виртуальная страница 1, смещение в странице равно 100) приведет к обращению по физическому адресу 2100 ( физическая страница 2, смещение в физической странице такое же, как и в виртуальной, то есть 100).

Рассмотрим теперь применение этих общих принципов страничного преобразования адреса в микропроцессоре с архитектурой IA-32 при объеме страницы в 4 Кбайт.

Основой страничного преобразования служит 32-разрядный линейный адрес , полученный на этапе сегментного преобразования логического адреса . Страничное преобразование выполняется при значении бита PG = 1 в управляющем регистре CR0 .

В этом случае старшие 20 разрядов линейного адреса фактически представляют собой номер виртуальной страницы . Однако при прямом одноступенчатом преобразовании этого номера в номер физической страницы необходима таблица из 2 20 элементов длиной 4 байта каждый (20-разрядный номер страницы плюс некоторая дополнительная информация ), т. е. 4 Мбайт. В мультипрограммной среде такая таблица может потребоваться для каждой задачи. Эта таблица должна постоянно храниться в оперативной памяти, чтобы существенно не увеличивать время формирования физического адреса . Для этих целей потребуется постоянное резервирование существенной части емкости ОЗУ , что на этапе появления первых ЭВМ на основе МП с архитектурой IA-32 было практически невозможно.

Вместо этого микропроцессор использует двухступенчатое страничное преобразование адреса . Корневая страница, называемая каталогом таблиц страниц (КТС), содержит 1024 32-разрядных элемента каталога таблиц страниц (ЭКТС - PDE page directory entry ). Каждый из них адресует подчиненную таблицу страниц (ТС), то есть всего допускается до 1024 подчиненных таблиц страниц. Каждая из таблиц страниц содержит 1024 32-разрядных элемента таблицы страниц (ЭТС - PTE page table entry ), каждый из которых и адресует физическую страницу. Таким образом, общее количество адресуемых физических страниц равно 2 20 , то есть все виртуальное адресное пространство (4 Кбайт * 2 20 элементов = 2 32 байт ). Каждая таблица занимает 1024 * 4 = 4 Кбайт, то есть ровно 1 страницу. Общий объем таблиц, используемых для страничного преобразования , не уменьшился, а даже несколько возрос за счет использования каталога таблиц страниц . Однако, во-первых, практически всегда в системе этот размер можно существенно уменьшить за счет того, что некоторые линейные адреса никогда не будут сформированы (а эту информацию дают таблицы дескрипторов сегментов), и для них не нужно создавать таблицу страниц. А во-вторых, в оперативной памяти должны постоянно находиться лишь каталог таблиц страниц и таблица страниц выполняемой в настоящее время программы. Остальные таблицы страниц могут временно храниться во внешней памяти.

Таким образом, преобразование линейного адреса в физический имеет вид, представленный на рис. 3.13 .

Старшие 20 разрядов линейного адреса разбиваются на два 10-разрядных поля: поле номера элемента каталога таблиц страниц и поле номера элемента таблицы страниц . Так как и каталог таблиц страниц , и каждая таблица страниц занимают ровно 1 страницу и выровнены по границе страницы, то младшие 12 разрядов их базового адреса равны нулю, и для определения их физического адреса достаточно 20-разрядного поля.

Для каталога таблиц страниц его 20-разрядный адрес находится в регистре управления CR3. КТС постоянно находится в памяти и не участвует в свопинге .

Старшие 20 разрядов физического адреса таблицы страниц извлекаются из ЭТС. Структуры элемента КТС и элемента ТС схожи (рис. 3.14).

Старшие 20 разрядов элемента дают базовый адрес таблицы страниц (в ЭКТС) или физической страницы (в ЭТС). Биты P , A , R/W и U/S имеют определенное сходство с аналогичными атрибутами дескриптора сегмента, другие биты имеют специфическое назначение.

Существуют две другие схемы организации виртуальной памяти:

· сегментная;

· сегментно-страничная.

Идеи сегментации изложены во введении к разделу 10. При сегментной организации виртуальный адрес по-прежнему является двумерным и состоит из двух полей - номера сегмента и смещения внутри сегмента. Заметим, что с точки зрения ОС сегменты являются логическими сущностями и их главное назначение хранение и защита однородной информации (кода, данных и т.д.).

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

Программисты, пишущие на языках низкого уровня должны иметь представление о сегментной организации, явным образом меняя значения сегментных регистров (это хорошо видно по текстам программ, написанных на Ассемблере). Логическое адресное пространство - набор сегментов. Каждый сегмент имеет имя, размер и другие параметры (уровень привилегий, разрешенные виды обращений, флаги присутствия). Пользователь специфицирует каждый адрес двумя величинами: именем сегмента и смещением. (В отличие от схемы пэйджинга, где пользователь задает только один адрес, который разбивается hardware на номер страницы и смещение, прозрачным для программиста образом.)

Каждый сегмент - линейная последовательность адресов от 0 до максимума. Различные сегменты могут иметь различные длины, которые могут меняться динамически (например, сегмент стека). В элементе таблицы сегментов помимо физического адреса начала сегмента (если виртуальный сегмент содержится в основной памяти) содержится длина сегмента. Если размер смещения в виртуальном адресе выходит за пределы размера сегмента, возникает прерывание.

Логический адрес - упорядоченная пара v=(s,d), номер сегмента и смещение внутри сегмента.

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

Рис. 11.2 Преобразование логического адреса при сегментной организации памяти.

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

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

Рис. 11.3 Формирование физического адреса при сегментно-страничной организации памяти.

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

Ассоциативная память.

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

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

Естественное решение - снабдить компьютер аппаратным устройством для отображения виртуальных страниц в физические без обращения к таблице страниц, то есть иметь небольшую, быструю кэш-память, хранящую необходимую на данный момент часть таблицы страниц. Это устройство называется ассоциативная память , иногда также употребляют термин ассоциативные регистры (иногда translation lookaside buffer (TLB)).

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

Отображение виртуальных страниц, хранимых в ассоциативной памяти, осуществляется быстро, однако кэш память является дорогостоящей и имеет ограниченный размер. Число записей в TLB от 8 до 2048.

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

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

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

Процент раз, когда номер страницы находится в ассоциативной памяти, называется hit (совпадение) ratio (пропорция, отношение). Таким образом, hit ratio - часть ссылок, которая может быть сделана с использованием ассоциативной памяти. Обращение к одним и тем же страницам повышает hit ratio.

Например, предположим, что для доступа к таблице страниц необходимо 100 нс, а для доступа к ассоциативной памяти 20 нс. С 90% hit ratio среднее время доступа - 0.9*20+0.1*100 = 28 нс.

Вполне приемлемая производительность современных ОС доказывает эффективность использования ассоциативной памяти. Высокое значение вероятности нахождения данных в ассоциативной памяти связано с наличием у данных объективных свойств: пространственной и временной локальности.

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

Иерархия памяти.

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

Рассмотренная нами схема трехуровневой памяти (ассоциативная, основная, вторичная) является частным случаем многоуровневой памяти. На пример, как показано на рис. 11.5, разновидности памяти могут быть организованы в иерархию по убыванию скорости доступа и возрастанию цены.

.

Рис. 11.5 Иерархия памяти компьютера

Считается, что затраты, связанные с переписью информации из одной памяти в другую окажутся меньше выигрыша в быстродействии, который получается за счет сокращения времени выборки из более быстрых слоев памяти. Информация о странице, которая находится в памяти верхнего уровня, хранится также на уровнях с большими номерами. Если процессор не обнаруживает нужную страницу на i-м уровне, он начинает искать ее на последующих уровнях. Когда нужная страница найдена, она переносится в более быстрые уровни. При этом происходит вытеснение какой-то старой страницы, обычно той, которая дольше всего не использовалась. Идея состоит в том, чтобы те страницы, которые чаще всего нужны в настоящее время, находились в более быстрых частях памяти. Эффективность такой схемы обусловлена все тем же свойством локальности (подробнее о локальности и связанным с ним понятием рабочего множества страниц будет рассказано в следующей главе). В результате среднее время доступа для многоуровневой схемы памяти оказывается весьма близким ко времени доступа первого уровня.

Размер страницы

Дизайнеры ОС для существующих машин редко имеют возможность влиять на размер страницы. Однако для вновь создаваемых компьютеров решение относительно оптимального размера страницы является актуальным. Как и можно было ожидать нет одного наилучшего размера. Скорее есть набор факторов, влияющих на размер. Обычно размер страницы это степень двойки от 2**9 до 2**14 байт.

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

Как следует выбирать размер страницы? Во-первых, нужно учитывать размер таблицы страниц, здесь желателен большой размер страницы (страниц меньше, соответственно и таблица страниц меньше). С другой стороны память лучше утилизируется с маленьким размером страницы. В среднем половина последней страницы процесса пропадает. Необходимо также учитывать объем ввода-вывода для взаимодействия с внешней памятью и другие факторы. Проблема не имеет хорошего ответа. Историческая тенденция состоит в увеличении размера страницы. Как правило, размер страниц задается аппаратно, например, на Intel - это 4096 байт (или 4 Кбайт), на DEC PDP-11 - 8 Кбайт, на DEC VAX - 512 байт, на других архитектурах, таких как Motorola 68030, размер страниц может быть задан программно.

Итак, рассмотрены аппаратные особенности поддержки виртуальной памяти. Перейдем к ее программной поддержке.

Идея виртуальной памяти может быть реализована через механизм страничной организации. И виртуальная, и вся физическая память в логическом смысле делится на блоки одинакового размера, называемые страницами. Адрес, в этом случае интерпретируется так же, как и при блочной организации ОЗУ, старшие разряды задают номер страницы, а младшие – указывают слово (байт) на странице. Поскольку размеры страниц в виртуальной и физической памяти одинаковы, для формирования физического адреса достаточно преобразовать только номер страницы. Страница является базовой единицей информации, перемещаемой между ОЗУ и жестким диском по требованию механизма преобразования адресов. Преобразование адресов осуществляется через специальные таблицы, называемые страничными таблицами . Каждая программа имеет свою страничную таблицу. Процедура преобразования адреса показана на рис.13.

Возникает вопрос, где хранить страничные таблицы? Первое, что приходит на ум–в оперативной памяти. Однако, в этом случае любое обращение к ОЗУ превращается в два: первое обращение к таблице, второе–по физическому адресу за командой или данными. Производительность резко падает. Чтобы снизить потерю производительности часть страничной таблицы хранят в сверхоперативной памяти, называемой ассоциативный буфер быстрого преобразования адреса , буфер TLB (Translation Lookaside Buffer ) или адресный кэш. Обычно, это множественно-ассоциативный кэш, отличающийся от обычного тем, что информация хранится не блоками, а отдельными словами. Содержимое строки страничной таблицы называют дескриптор страницы, т.е. в строке TLB хранится один дескриптор. При поиске дескриптора страницы в ОЗУ номер виртуальной страницы используется как смещение, а при поиске в буфере TLB–в качестве тега.

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

При страничной организации предполагается, что виртуальная память – это непрерывный массив со сквозной нумерацией слов, что не всегда можно признать оптимальным. Обычно программа состоит из нескольких частей – кода, данных и стека. Так как заранее неизвестны длины этих составляющих, то удобно, чтобы при программировании каждая из них имела собственную нумерацию слов, начинающуюся с нуля. Для этого организуют систему сегментированной памяти, выделяя в виртуальном пространстве независимые линейные пространства переменной длины, называемые сегментами. Каждый сегмент представляет собой отдельную логическую единицу, содержащую однородную информацию и расположенную в адресном пространстве пользователя. Физическая память также разбивается на сегменты, с независимой адресацией слов внутри сегмента. Каждой составляющей программы выделяется сегмент памяти. И виртуальный, и физический адрес интерпретируется как номер сегмента и смещение внутри сегмента. Для преобразования виртуального адреса в физический используется сегментная таблица.

Недостатком такого подхода является то, что неодинаковый размер сегментов приводит к неэффективному использованию ОП. Так, если ОП заполнена, то при замещении одного из сегментов требуется вытеснить такой, размер которого не менее размера нового. При многократном повторе подобных действии в ОП остается множество свободных участков, недостаточных по размеру для загрузки полного сегмента. Решением проблемы служит сегментно-страничная организация памяти. В ней размер сегмента выбирается не произвольно, а задается кратным размеру страницы. Сегмент может содержать любое, но обязательно целое число страниц, даже если одна из страниц заполнена частично. Возникает определенная иерархия в организации доступа к данным, состоящая из трех ступеней: сегмент, страница, слово. Этой структуре соответствует иерархия таблиц, служащих для перевода виртуальных адресов в физические. В сегментной таблице перечисляются все сегменты данной программы с указанием начальных адресов страничных таблиц. Количество страничных таблиц равно числу сегментов и любая из них определяет расположение каждой из страниц сегмента в памяти, которые могут располагаться не подряд – часть страниц может находиться в ОП, а часть – во внешней. Структуру виртуального адреса и процесс преобразования его в физический адрес иллюстрирует рис. 14. Для получения физического адреса необходим доступ к сегментной и одной из страничных таблиц, поэтому преобразование адреса может занимать много времени. Снижают эти затраты времени применением ассоциативных буферов преобразования адресов (TLB). Поскольку количество сегментов одной программы невелико, сегментная таблица активной (выполняемой в данное время) программы целиком располагается в ассоциативном буфере, а сам буфер представляет собой полностью ассоциативную память.

Страничная память - способ организации виртуальной памяти , при котором единицей отображения виртуальных адресов на физические является регион постоянного размера (т. н. страница ). Типичный размер страницы - 4096 байт, для некоторых архитектур - до 128 КБ .

Поддержка такого режима присутствует в большинстве 32-битных и 64-битных процессоров. Такой режим является классическим для почти всех современных ОС, в том числе Windows и семейства UNIX . Широкое использование такого режима началось с процессора VAX и ОС VMS с конца 1970-х годов (по некоторым сведениям, первая реализация). В семействе x86 поддержка появилась с поколения 386, оно же первое 32-битное поколение.

Решаемые задачи [ | ]

Концепции [ | ]

Адрес, используемый в машинном коде, то есть значение указателя, называется «виртуальный адрес».

Адрес, выставляемый процессором на шину, называется «линейный адрес» (который позже преобразуется в физический).

Запись таблицы страниц обычно содержит в себе следующую информацию:

Число записей в одной таблице ограничено и зависит от размера записи и размера страницы. Используется многоуровневая организация таблиц, часто 2 или 3 уровня, иногда 4 уровня (для 64-разрядных архитектур).

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

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

Старшие биты виртуального адреса указывают на номер записи в каталоге, средние - номер записи в таблице, младшие (адрес внутри страницы) попадают в физический адрес без трансляции.

Формат записей таблиц, их размер, размер страницы и организация таблиц зависит от типа процессора, а иногда и от режима его работы.

Исторически x86 использует 32-битные PTE, 32-битные виртуальные адреса, 4-КБ страницы, 1024 записи в таблице, двухуровневые таблицы. Старшие 10 битов виртуального адреса - номер записи в каталоге, следующие 10 - номер записи в таблице, младшие 12 - адрес внутри страницы.

Начиная с Pentium Pro, процессор поддерживает страницы размером 4 МБ. Однако, чтобы система и программы, запущенные в ней, могли использовать страницы такого размера, технология 4-МБ страниц (hugepages) должна быть соответствующим образом активирована, а приложение настроено на использование страниц такого размера.

В архитектуре x86_64 возможно использовать страницы размером 4 килобайта (4096 байтов), 2 мегабайта, и (в некоторых AMD64) 1 гигабайт.

Если обращение к памяти не может быть оттранслировано через TLB, то микрокод процессора обращается к таблицам страниц и пытается загрузить PTE оттуда в TLB. Если и после такой попытки сохранились проблемы, то процессор исполняет специальное прерывание, называемое «отказ страницы » (page fault). Обработчик этого прерывания находится в подсистеме виртуальной памяти ядра ОС.

Некоторые процессоры (MIPS) не имеют обращающегося к таблице микрокода, и генерируют отказ страницы сразу после неудачи поиска в TLB, обращение к таблице и её интерпретация возлагаются уже на обработчик отказа страницы. Это лишает таблицы страниц требования соответствовать жёстко заданному на уровне аппаратуры формату.

Причины отказа страницы (page fault ):

• не существует таблицы, отображающей данный регион,
• PTE не имеет взведённого флага «страница отображена»,
• попытка обратиться из пользовательского режима к странице «только для ядра»,
• попытка записи в страницу «только для чтения»,
• попытка исполнения кода из страницы «исполнение запрещено».

Обработчик отказов в ядре может загрузить нужную страницу из файла или же из области подкачки (см. свопинг), может создать доступную на запись копию страницы «только для чтения», а может и возбудить исключительную ситуацию (в терминах UNIX - сигнал SIGSEGV) в данном процессе.

Каждый процесс имеет свой собственный набор таблиц страниц. Регистр «каталог страниц» перегружается при каждом переключении контекста процесса. Также необходимо сбросить ту часть TLB, которая относится к данному процессу.

В большинстве случаев ядро ОС помещается в то же адресное пространство, что и процессы, для него резервируются верхние 1-2 гигабайта 32-битного адресного пространства каждого процесса. Это делается с целью избежать переключения таблиц страниц при входе в ядро и выходе из него. Страницы ядра помечаются как недоступные для кода режима пользователя.

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

Так как память ядра одинакова у всех процессов, соответствующие ей TLB не нужно перегружать после переключения процесса. Для этой оптимизации x86 поддерживает флаг «глобальный» у PTE.

Отображаемые в память файлы [ | ]

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

Это приводит к возможности лёгкой реализации отображенных в память файлов. Концептуально это то же, что выделение памяти и чтение в неё отрезка файла, с той разницей, что чтение осуществляется неявно «по требованию», выраженному отказом страницы при попытке обращения к ней.

Вторым преимуществом такого подхода является - в случае отображения «только для чтения» - разделение одной и той же физической памяти между всеми процессами, отображающими данный файл (выделенная же память своя у каждого процесса).

Третьим преимуществом является возможность «забывания» (discard) некоторых отображенных страниц без выгрузки их в область подкачки, обязательной для выделенной памяти. В случае повторной потребности в странице она может быть быстро загружена из файла снова.

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

Отображаемые в память файлы используется в ОС Windows, а также ОС семейства UNIX, для загрузки исполняемых модулей и динамических библиотек. Они же используются утилитой GNU grep для чтения входящего файла, а также для загрузки шрифтов в ряде графических подсистем.

Страничная и сегментная виртуальная память [ | ]

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

Наличие таких концепций в программировании уменьшает применимость арифметики указателей и приводит к огромным проблемам с переносимостью кода с/на такие архитектуры. Так, например, значительная часть ПО с открытым кодом изначально разрабатывалась для бессегментных 32-битных платформ со страничной памятью и не может быть перенесена на сегментные архитектуры без серьёзной переработки.

Кроме того, сегментные архитектуры имеют тяжелейшую проблему SS != DS, широко известную в начале 1990-х годов в программировании под 16-битные версии Windows. Эта проблема приводит к затруднениям в реализации динамических библиотек, ибо они имеют свой собственный DS, и SS текущего процесса, что приводит к невозможности использования «ближних» указателей в них. Также наличие своего собственного DS в библиотеках требует устанавливающих правильное значение DS заплаток (MakeProcInstance) для обратных вызовов из библиотеки в вызвавшее приложение.

Виртуальная память и дисковый кэш [ | ]

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

Совершенно очевидно, что данная структура является уже готовым дисковым кэшем. Использование её в качестве кэша также решает проблему когерентности файла, доступного через read/write, и его же, отображённого в память.

Таким образом, пути кэшированного ввода-вывода в дисковый файл (FsRtlCopyRead в Windows и аналогичная ей generic_file_read() в Linux) реализуются как копирования данных в физические страницы, отображенные на файл.

Такая организация кэша является единственной в Windows, эта ОС вообще не имеет классического блочного кэша диска. Метаданные файловых систем кэшируются путём создания лже-файлов (IoCreateStreamFileObject) и создания страничного кэша для них.

Соображения безопасности [ | ]

Первоначально архитектура x86 не имела флага «страница недоступна на исполнение» ().

Поддержка данного флага появилась в архитектуре x86 как часть режима PAE (Physical Address Extension) в поколении Pentium 4, под большим давлением со стороны специалистов по безопасности (см. архивы NTBugTraq). Установка данного флага на страницах стека и кучи (heap) позволяет реализовать аппаратно защиту от исполнения данных, что делает невозможной работу многих разновидностей вредоносного ПО, в том числе, например, злонамеренную эксплуатацию многих брешей в Internet Explorer (брешь декабря 2008 года, см. MS knowledge base, не может быть задействована в случае включенной DEP).

Поддержка PAE в Windows, дающая возможность включения защиты от исполнения данных , появилась в Windows 2000, она включена по умолчанию в серверных версиях Windows и отключена в клиентских.

Поддержка памяти свыше 4 ГБ в Windows [ | ]

Устройства PCI, в том числе память видеоплаты, обычно поддерживают только 32-битные адреса. Следовательно, им должны быть выданы физические адреса ниже отметки 4 ГБ. Эта «апертура» уменьшает объём видимой физической памяти ниже отметки 4 ГБ до примерно 3,2 ГБ. Остальная часть физической памяти переотображается контроллером выше отметки 4 ГБ.

Для любого обращения к памяти свыше отметки 4 ГБ (то есть более чем примерно 3,2 ГБ) требуется поддержка контроллером (то есть северным мостом чипсета) такой конфигурации. Современные чипсеты (например, Intel G33) такую поддержку имеют.

Также требуется настройка BIOS под названием memory remapping , отображающая регион на .

Процессор x86 вне режима PAE использует 32-битные PTE и физические адреса, то есть ему не доступно ничто, находящееся выше отметки 4 ГБ (см. также PSE-36 об одном из вариантов обхода данного ограничения). Таким образом, для использования памяти более, чем примерно 3,2 ГБ в ОС она должна поддерживать PAE. Для Windows - это опция загрузки, для Linux - опция построения ядра.

Кроме того, Microsoft принудительно отключила поддержку физических адресов выше 4 ГБ по политико-маркетинговым соображениям в следующих ОС:

Поддержка физических адресов выше 4 ГБ имеется в следующих версиях:

• всe 64-битные версии,
• 32-битная Windows Vista SP1 (поддержка включена по умолчанию, но её подключение нередко может требовать набора команд в командной строке),
• 32-битный Windows Server 2003, отличный от Web Edition,
• 32-битный Windows Server 2008.

Таким образом, для того, чтобы использовать память выше 3,2 ГБ в Windows, нужны:

• поддержка чипсетом,
• правильные настройки BIOS,
• правильная версия Windows,
• правильная опция загрузки (с поддержкой PAE),
• поддержка 36-битного адресного пространства драйверами устройств.

Тем не менее, даже в «урезанной» версии Windows, не поддерживающей адреса выше 4 ГБ, имеет смысл всегда использовать PAE, ибо (см. выше) защита от исполнения данных (DEP) тоже требует PAE. При включении PAE может перестать работать небольшая часть ПО, например, эмулятор windows mobile. Согласно официальной версии Microsoft, введение 4-ГБ ограничения адресного пространства связано с отсутствующей или плохой поддержкой 36-битного адресного пространства некоторыми драйверами устройств, это следует иметь в виду, по причине аппаратных ограничений или неподходящих драйверов невозможно подключить PAE на версиях, имеющих поддержку физических адресов выше 4 ГБ. Возможность включения или выключения PAE не зависит от драйверов, но, если драйвер какого-то старого PCI оборудования не поддерживает правильно физические адреса, не умещающиеся в 32 бита, то данное устройство будет работать неверно и может привести к зависанию всего компьютера.