Буфер поиска трансляции

В принципе каждый виртуальный адрес вызывает обращение к двум физи­ческим адресам: одно для выборки соответствующей записи из таблицы страниц и еще одно — для обращения к адресуемым данным. Следовательно, простая схема виртуальной памяти, по сути, удваивает время обращения к памяти. Для преодоления этой проблемы большинство реально использующихся схем вирту­альной памяти использует специальный высокоскоростной кэш для записейтаблицы страниц, который обычно называют буфером быстрого преобразования адреса, или простобуфером поиска трансляции (translation look aside buffer — TLB). Этот кэш функционирует так же, как и обычный кэш памяти (см. главу 1, "Обзор компьютерных систем") и содержит те записи таблицы страниц, которые использовались последними. Организация аппаратной поддержки использования TLB показана на рис. 8.7. Получив виртуальный адрес, процессор сперва просматривает TLB. Если требуемая запись найдена, процессор получает номер кадра и формирует реальный адрес. Если запись в TLB не найдена, то процессор использует номер страницы в качестве индекса для таблицы страниц процесса и просматривает соответствующую запись. Если бит присутствия в ней установлен, значит, искомая страница находится в основной памяти, и процессор просто получает номер кадра из записи таблицы страниц и формирует реальный адрес, одновременно внося использованную запись таблицы страниц в TLB. И, наконец, если бит присутствия не установлен, значит, искомой страницы в основной памяти нет, и процессор генерируетошибку обращения к странице. В этот момент подключается операционная система, которая загружает требуемую страницу в основную память и обновляет таблицу страниц.

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

Исходя из принципа локализации большинство обращений к виртуальной памяти, будут сосредоточены в недавно использованных страницах, и соответствующие записи будут находиться в кэше, так что с помощьюTLB повышается эффективность работы виртуальной памяти, что, например, показано при изучении VAX TLB [CLAR85, SATY81].

В организации TLB имеется ряд особенностей. Так, поскольку TLB содержит только некоторые из записей таблицы страниц, индексация записей в TLB на основе номера страницы не представляется возможной; вместо этого каждая запись TLB должна наряду с полной информацией из записи таблицы страниц включать также номер страницы. Процессор аппаратно способен одновременно опрашивать ряд записей TLB для определения того, какаяиз них соответствует заданному номеру страницы. Такая методика известна как ассоциативное отображение (associative mapping), в отличие от прямого отображения, или индексирования, применяемого для поиска в таблице страниц, как показано на рис. 8.9. Конструкция TLB должна также предусматривать способ организации записей в кэше и принятия решения о том, какая из старых записей должна быть удалена при внесении в кэш новой записи. Впрочем, этим вопросам следует уделять внимание при разработке любого аппаратного кэша. Однако они не входят в круг вопросов, рассматриваемых в нашей книге; заинтересованному читателю можно порекомендовать обратиться к специализированной литературе на эту тему (например, [STALOO]).

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

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

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

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

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

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

В табл. 8.2 приведены размеры страниц на разных машинах.

Таблица 8.2. Примеры размеров страниц

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

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

· Многопоточные приложения, приводящие к внезапным изменениям в пото­ке команд и обращениям к памяти, разбросанным по разным адресам.

Результативность поиска в TLB определенного размера с ростом размера процессов и уменьшением локализации снижается. При таком положении дел TLB может стать узким местом, ограничивающим производительность [CHEN92].

Один из способов повышения производительности TLB — использование большого TLB с большим количеством записей. Однако увеличение размера TLB связано с другими аспектами аппаратного решения вопросов обращения к памяти — такими, как размер кэша основной памяти и количество обращений к па­мяти при выполнении одной команды [TALL92], что заставляет сделать вывод о невозможности роста размера TLB такими же темпами, как и увеличение разме­ра основной памяти. Альтернативой может быть использование больших разме­ров страниц с тем, чтобы каждая запись в TLB ссылалась на большой блок па­мяти. Однако мы уже видели, что использование больших размеров страниц может привести к потере производительности.

Учитывая обстоятельства, рассмотренные нами ранее, ряд разработчиков пришли к использованию множественных размеров страниц [TALL92, KHAL93], и некоторые из микропроцессоров, такие, как MIPS R4000, Alpha, UltraSPARC и Pentium, поддерживают эту методику. Множественные размеры страниц обеспечивают необходимую для эффективного использования TLB гибкость. Большие непрерывные области адресного пространства процесса, например программный код, могут отображаться с использованием небольшого количества больших страниц, в то время как стеки потоков могут использовать для отображения страницы малого размера. Однако большинство коммерческих операционных систем все еще поддерживают только один размер страниц, независимо от способности аппаратного обеспечения работать со страницами разного размера. Причина этого отставания в том, что с размером страниц связано большое количество разнообразных аспектов операционных систем, и переход на множественный размер страниц оказывается очень сложным[GANA98].

Сегментация

Значение виртуальной памяти

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

Такая организация имеет ряд преимуществ по сравнению с несегментированным адресным пространством.

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

2. Программы могут изменяться и перекомпилироваться независимо от компиляции или компоновки всего множества программ (что осуществляется при использовании множественных сегментов).

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

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

Организация

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

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

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

Комбинация сегментации и страничной организации

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

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

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

На рис. 8.2,б предложены форматы записей таблицы сегментов и таблицы страниц. Как и ранее, запись таблицы сегментов содержит значение длины сегмента, а также поле с начальным адресом сегмента, которое теперь указывает на таблицу страниц. Биты присутствия и модификации в записи таблицы сегментов в данном случае не нужны, так как эти вопросы решаются на уровне страниц. Использование других управляющих битов может продолжаться, например, в упомянутых ранее целях совместного использования и защиты. Запись таблицы страниц — по сути, та же, что и использованная в системе с "чистой" страничной организацией. При наличии страницы в основной памяти (на что указывает бит присутствия) ее номер отображается в номер соответствующего кадра; бит модификации указывает, требуется ли перезапись страницы на диск при ее выгрузке из памяти. Как и ранее, могут использоваться и другие управляющие биты.

Защита и совместное использование

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

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

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

2. Программа может вызвать сервис из того же или более привилегированного кольца.