Понятие виртуальной памяти 2 6 3

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

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

Одна из привлекательных сторон дискового кэша в том, что связанные с ним преимущества могут быть получены без изменений в имеющемся аппаратном и программном обеспечении. Многие серийно выпускаемые дисковые кэши интегрированы в состав дисковых ЗУ. В качестве примера можно привести модель 23 системы IBM 3880, в состав которой входят дисковые ЗУ со встроенным контроллером кэш-памяти и кэш-памятью емкостью от 8 до 64 Мбайт. Дисковая кэш-память применяется и в персональных ВМ.

Дисковая кэш-память обычно включает в себя средства для обнаружения и исправления ошибок. Так, в уже упоминавшейся модели 23 системы IBM 3880 имеются средства для обнаружения тройных ошибок (одновременного появления ошибок в трех разрядах) и исправления одиночных, двойных и большинства тройных ошибок. Более ранняя модель 13 той же системы имела кэш-память емкостью 4-8 Мбайт и умела обнаруживать двойные и исправлять одиночные ошибки. В обеих моделях замещение информации в кэше производится в соответствии с алгоритмом минимального предыдущего использования (LRU).

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

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

Для большинства типичных применений ВМ характерна ситуация, когда размещение всей программы в ОП невозможно из-за ее большого размера. В этом, однако, и нет принципиальной необходимости, поскольку в каждый Момент, времени «внимание» машины концентрируется на определенных сравнительно небольших участках программы. Таким образом, в ОП достаточно хранить только используемые в данный период части программ, а остальные части могут располагаться на внешних ЗУ (В ЗУ). Сложность подобного подхода в том, что процессы обращения к ОП и В ЗУ существенно различаются, и это усложняет задачу программиста. Выходом из такой ситуации было появление в 1959 году идеи виртуализации памяти [88], под которой понимается метод автоматического управления иерархической памятью, при котором программисту кажется, что он имеет дело с единой

2 6 4 Глава 5. Память

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

В рамках идеи виртуализации памяти ОП рассматривается как линейное пространство N адресов, называемое физическим пространством памяти. Для задач, где требуется более чем N ячеек, предоставляется значительно большее пространство адресов (обычно равное общей емкости всех видов памяти), называемое виртуальным пространством, в общем случае не обязательно линейное. Адреса виртуального пространства называют виртуальными, а адреса физического пространства — физическими. Программа пишется в виртуальных адресах, но поскольку для её выполнения нужно, чтобы обрабатываемые команды и данные находились в ОП, требуется, чтобы каждому виртуальному адресу соответствовал физический. Таким образом, в процессе вычислений необходимо, прежде всего, переписать из ВЗУ в ОП ту часть информации, на которую указывает виртуальный адрес (отобразить виртуальное пространство на физическое), после чего преобразовать виртуальный адрес в физический (рис. 5.30).

Рис. 5.30. Отображение виртуального адреса на физический

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

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

Целям преобразования виртуальных адресов в физические служит страничная организация памяти. Ее идея состоит в разбиении программы на части равной величины, называемые страницами. Размер страницы обычно выбирают в пределах 4- 8 Кбайт, но так, чтобы он был кратен емкости одного сектора магнитного диска. Виртуальное и физическое адресные пространства разбиваются на блоки размером в страницу. Блок основной памяти, соответствующий странице, часто называют страничным кадром или фреймом (page frame). Страницам виртуальной и физической памяти присваивают номера. Процесс доступа к данным по их виртуальному адресу иллюстрирует рис .5.31.

Понятие виртуальной памяти 2 6 5

Рис. 5.31. Страничная организация виртуальной памяти

Центральный процессор обращается к ячейке, указав ее виртуальный адрес ф, состоящий из номера виртуальной страницы и смещения относительно ее начала. Этот адрес поступает в систему преобразования адресов 2, с целью получения из него физического адреса ячейки в основной памяти 3. Поскольку смещение в виртуальном и физическом адресе одинаковое, преобразованию подвергается лишь номер страницы. Если преобразователь обнаруживает, что нужная физическая страница отсутствует в основной памяти (произошел промах или страничный сбой), то нужная страница считывается из внешней памяти и заносится в ОП (4, 5).

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

Виртуальное пространство полностью описывается двумя таблицами (рис. 5.32): страничной таблицей и картой диска (будем считать, что вторичная память реализована на магнитных дисках). Таблица страниц определяет, какие виртуальные страницы находятся в основной памяти и в каких физических фреймах, а карта диска содержит информацию о секторах диска, где хранятся виртуальные страницы на диске. '"

Число записей в страничной таблице (СТ) в общем случае равно количеству виртуальных страниц. Каждая запись содержит поле номера физической страницы (НФС) и четыре признака: V, R, М и А.

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

266 Глава5. Память

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

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

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

Поскольку в ОП находятся лишь копии страниц, а их оригиналы хранятся на диске, необходимо обеспечить идентичность подлинников и копий. В ходе вычислений содержимое отдельных страниц может изменяться, что фиксируется путем установки в единицу признака модификации М. При удалении страницы из ОП проверяется состояние признака М. Если М = 1, то перед удалением страницы из основной памяти ее необходимо переписать на диск, а при М =0 этого можно не делать.

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

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

Способ реализации СТ жизненно важен для эффективности техники виртуальной адресации, поскольку каждое обращение к памяти предполагает обраще-

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

Понятие виртуальной памяти 267

ние к страничной таблице. Наиболее быстрый способ — хранение таблицы в специально выделенных для этого регистрах, но от него приходится отказываться при большом объеме СТ. Остается практически один вариант — выделение страничной таблице области основной памяти, несмотря на то что это приводит к двухкратному увеличению времени доступа к информации. Чтобы сократить это время, в состав ВМ включают дополнительное ЗУ, называемое буфером быстрого преобразования адреса (TLB — Translation Look-aside Buffer), или буфером ассоциативной трансляции, или буфером опережающей выборки и представляющее собой кэш-память. При каждом преобразовании номера виртуальной страницы в номер физической страницы результат заносится в TLB: номер физической страницы в память данных, а виртуальной — в память тегов. Таким образом, в TLB попадают результаты нескольких последних операций трансляции адресов. При каждом обращении к ОП преобразователь адресов сначала производит поиск в памяти тегов TLB номера требуемой виртуальной страницы. При попадании адрес соответствующей физической страницы берется из памяти данных TLB. Если в TLB зафиксирован промах, то процедура преобразования адресов производится с помощью страничной таблицы, после чего осуществляется запись новой пары «номер виртуальной страницы — номер физический страницы» в TLB. Структура TLB показана на рис. 5.33.


Номер виртуальной страницы	V	R	М	А	Номер физической страницы



	1 1 1 1

Память тегов Память данных

Рис. 5.3 3. Структура буфера быстрого преобразования адресов

Буфер преобразования адресов обычно реализуется в виде полностью ассоциативной или множественно-ассоциативной кэш-памяти с высокой степенью ассоциативности и временем доступа, сопоставимым с аналогичным показателем для кэш-памяти первого уровня (L1). Число входов у типовых TLB невелико (64-256). Так, TLB микропроцессора Pentium III имеет 64 входа при размере страницы 4 Кбайт, что позволяет получить быстрый доступ к адресному пространству в 256 Кбайт.

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

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

268 Глава 5. Память

ной таблицы и лишь затем производится обращение к нужной таблице. О достигаемом эффекте можно судить из следующего примера. Пусть адресная шина ВМ имеет ширину 32 бита, а размер страницы равен 4 Кбайт. Тогда количество виртуальных страниц, а следовательно, и число входов в единой страничной таблице составит 2²⁰. При двухуровневой организации можно обойтись одной страницей первого уровня на 1024 (2¹⁰) входов и 1024 страничными таблицами на такое же число входов.

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

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

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

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

Понятие виртуальной памяти 26 9

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

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

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

Организация защиты памяти

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