Добавлен: 29.10.2018
Просмотров: 48069
Скачиваний: 190
236
Глава 3. Управление памятью
Другой крайностью является конструкция, при которой вся таблица страниц может
целиком находиться в оперативной памяти. При этом аппаратуре нужно иметь лишь
один регистр, указывающий на начало таблицы страниц. Такая конструкция позволяет
отображению виртуальной памяти на физическую меняться при переключении кон-
текста путем перезагрузки всего лишь одного регистра. Здесь, разумеется, есть и не-
достаток, поскольку для считывания записей таблицы страниц во время выполнения
каждой команды требуется одно или несколько обращений к памяти, что существенно
замедляет работу.
Буферы быстрого преобразования адреса
Теперь рассмотрим широко используемую систему, призванную ускорить страничную
организацию памяти и обрабатывать большие виртуальные адресные пространства,
отталкиваясь от прежней схемы. Отправной точкой для большинства оптимизиру-
ющих технологий является содержание таблицы страниц в памяти. Потенциально
такая конструкция оказывает сильное влияние на производительность. Рассмотрим,
к примеру, однобайтную команду, копирующую один регистр в другой. При отсутствии
страничной организации эта команда осуществляет лишь одно обращение к памяти
для извлечения самой команды. При страничной организации памяти понадобится
как минимум еще одно обращение к памяти для доступа к таблице страниц. Поскольку
скорость выполнения обычно ограничена скоростью, с которой центральный процессор
может извлечь инструкцию и данные из памяти, необходимость осуществления при
каждом обращении к памяти двух обращений снижает производительность вдвое. При
таких условиях использовать страничную организацию памяти никто не станет.
Разработчики компьютерных систем были знакомы с этой проблемой много лет и на-
конец придумали решение, которое основывалось на том наблюдении, что большинство
программ склонны большинство своих обращений направлять к небольшому количе-
ству страниц, а не наоборот. Поэтому интенсивному чтению подвергается лишь неболь-
шая часть записей таблицы страниц, а остальная часть практически не используется.
Найденное решение состояло в оснащении компьютеров небольшим устройством для
отображения виртуальных адресов на физические без просмотра таблицы страниц.
Состояние этого устройства, названного буфером быстрого преобразования адреса
(Translation Lookaside Buffer (TLB)), которое иногда еще называют ассоциативной
памятью
, показано в табл. 3.1. Зачастую это устройство находится внутри диспетчера
памяти и состоит из небольшого количества записей. В данном примере их 8, но их
количество редко превышает 64. Каждая запись содержит информацию об одной
странице, включающую номер виртуальной страницы, бит, устанавливающийся при
модификации страницы, код защиты (разрешение на чтение, запись и выполнение)
и физический страничный блок, в котором расположена страница. Эти поля имеют
точное соответствие полям в таблице страниц, за исключением номера виртуальной
страницы, который в таблице страниц не нужен. Еще один бит показывает задейство-
ванность страницы (то есть используется она или нет).
Пример, который мог бы сформировать TLB, показанный в табл. 3.1, — это цикли-
ческий процесс, занимающий виртуальные страницы 19, 20 и 21, поэтому их записи
в TLB имеют коды защиты, разрешающие чтение и исполнение. Основные данные,
используемые в этот момент (скажем, обрабатываемый массив), занимают страницы
129 и 130. Страница 140 содержит индексы, используемые при вычислениях, произво-
димых с элементами массива. И наконец, стек занимает страницы 860 и 861.
3.3. Виртуальная память
237
Таблица 3.1. Буфер быстрого преобразования адреса, используемый для ускорения
страничного доступа к памяти
Задействована
Виртуальная
страница
Изменена
Защищена
Страничный
блок
1
140
1
RW
31
1
20
0
R X
38
1
130
1
RW
29
1
129
1
RW
62
1
19
0
R X
50
1
21
0
R X
45
1
860
1
RW
14
1
861
1
RW
75
Теперь рассмотрим работу TLB. Когда диспетчеру памяти предоставляется для преоб-
разования виртуальный адрес, аппаратура сначала проверяет, не содержится ли номер
его виртуальной страницы в TLB, одновременно (то есть параллельно) сравнивая его
значение со всеми записями. Для этого потребуется специальное оборудование, име-
ющееся у всех диспетчеров памяти с TLB-буферами. Если будет найдено соответствие
и биты защиты не будут препятствовать доступу, номер страничного блока будет взят
непосредственно из TLB, без обращения к таблице страниц. Если номер виртуальной
страницы присутствует в TLB, но команда пытается осуществить запись в страницу,
предназначенную только для чтения, генерируется ошибка защиты.
Нас интересует, что же произойдет, если номер виртуальной страницы не будет найден
в TLB. Диспетчер памяти обнаруживает его отсутствие и осуществляет обычный по-
иск в таблице страниц. Затем он выселяет одну из записей в TLB, заменяя ее только
что найденной записью из таблицы страниц. Поэтому, если вскоре эта страница будет
востребована снова, то во второй раз она уже будет найдена в TLB. Когда запись удаля-
ется из TLB, бит модификации копируется обратно в таблицу страниц, находящуюся
в памяти. Другие значения, за исключением бита ссылки, там уже присутствуют. Когда
TLB загружается из таблицы страниц, все поля берутся из памяти.
Программное управление буфером TLB
До сих пор мы предполагали, что каждая машина со страничной виртуальной памятью
имеет таблицы страниц, распознаваемые аппаратурой, плюс TLB. При такой конструк-
ции управление TLB и обработка TLB-ошибок осуществляется исключительно обо-
рудованием диспетчера памяти. Прерывания, передающие управление операционной
системе, происходят, только если страница отсутствует в памяти.
В былые времена такое предположение вполне соответствовало действительности. Но
многие современные RISC-машины, включая SPARC, MIPS и (теперь уже ставшие
историей) HP PA, осуществляют практически все управление страницами программ-
ным образом. На этих машинах записи TLB загружаются операционной системой
явным образом. Когда нужная запись в TLB отсутствует, диспетчер памяти, вместо
того чтобы обращаться к таблицам страниц для поиска и извлечения сведений о нуж-
ной странице, просто генерирует TLB-ошибку и подбрасывает проблему операционной
системе. Система должна отыскать страницу, удалить запись из TLB, внести новую
запись и перезапустить команду, вызвавшую ошибку. И разумеется, все это долж-
238
Глава 3. Управление памятью
но быть сделано с использованием минимума команд, поскольку ошибка отсутствия
записи в TLB случается намного чаще, чем ошибка отсутствия страницы в таблице.
Как ни странно, но при умеренно большом TLB (скажем, 64 записи) программное
управление этим буфером оказывается вполне эффективным средством снижения
количества ошибок отсутствия нужной записи. Основным преимуществом такого
управления является существенное упрощение диспетчера памяти, освобождающее
большую площадь микросхемы центрального процессора под кэш и другие функцио-
нальные узлы, способные повысить производительность. Программное управление
TLB рассмотрено в работе Uhlig et al., 1994.
Для улучшения производительности на машинах, осуществляющих программное
управление TLB, в давние времена были разработаны различные стратегии. В одном
из подходов прилагались усилия как по сокращению ошибок отсутствия нужных
записей в TLB, так и по уменьшению издержек при возникновении этих ошибок
(Bala et al., 1994). Иногда для сокращения количества ошибок отсутствия нужных
записей в TLB операционная система может воспользоваться своей интуицией для
определения того, какие из страниц, скорее всего, будут востребованы в следующую
очередь, и заранее загрузить касающиеся их записи в TLB. Например, когда клиент-
ский процесс отправляет сообщение серверному процессу на той же самой машине,
высока вероятность того, что сервер вскоре также будет задействован. Располагая
этими сведениями во время обработки системного прерывания, занимающегося от-
правкой (send), система может заодно с этим проверить, присутствуют ли в карте
отображения страницы кода, данных и стека сервера, и отобразить их до того, как
появятся предпосылки для возникновения ошибки TLB.
Обычный способ аппаратной или программной обработки ошибки TLB заключается
в переходе к таблице страниц и осуществлении операций индексации для определения
местоположения затребованной страницы. Проблема выполнения этого поиска про-
граммным способом состоит в том, что страницы, содержащие таблицу страниц, могут
отсутствовать в TLB, что может стать причиной дополнительных TLB-ошибок в про-
цессе обработки. От этих ошибок можно избавиться за счет использования довольно
большого (например, 4 Кбайт) программного кэша записей TLB в фиксированном
месте, сведения о странице которого всегда содержатся в TLB. При первой проверке
программного кэша операционная система может существенно сократить количество
TLB-ошибок.
При использовании программного управления TLB важно понять разницу между раз-
личными видами ошибок отсутствия записей. Программная ошибка отсутствия проис-
ходит, когда страница, к которой идет обращение, отсутствует в TLB, но присутствует
в памяти. Для ее устранения требуется лишь обновление TLB и не требуется выполне-
ние операций ввода-вывода с обращением к диску. Обычно устранение программной
ошибки отсутствия требует 10–20 машинных команд и может быть завершено за не-
сколько наносекунд. В отличие от нее аппаратная ошибка отсутствия происходит, ког-
да сама страница отсутствует в памяти (и, разумеется, запись о ней отсутствует в TLB).
Для получения страницы требуется обращение к диску, занимающее в зависимости от
используемого диска несколько миллисекунд. Аппаратная ошибка отсутствия обраба-
тывается почти в миллион раз медленнее, чем программная. Просмотр отображения
в иерархии таблиц страниц называется просмотром таблиц страниц (page table walk).
Фактически дела обстоят еще хуже. Ошибка отсутствия носит не только программ-
ный или аппаратный характер. Некоторые ошибки отсутствия имеют по сравнению
3.3. Виртуальная память
239
с другими ошибками отсутствия больше программный (или больше аппаратный)
характер. Например, при просмотре таблицы страниц нужная страница в таблице
страниц процесса отсутствует, и программа, таким образом, сталкивается с ошибкой
отсутствия страницы. В данной ситуации существуют три возможности. Во-первых,
страница фактически может находиться в памяти, но отсутствовать в таблице страниц
процесса. Например, страница может быт взята с диска другим процессом. В таком
случае нужно вместо нового обращения к диску просто соответствующим образом
отобразить страницу в таблицах страниц. Это скорее программная ошибка отсут-
ствия страницы, известная как легкая ошибка отсутствия страницы (minor page
fault). Во-вторых, если страницу нужно брать с диска, это будет считаться серьезной
ошибкой отсутствия страницы. В-третьих, вполне возможно, что программа просто
обратилась по неверному адресу и в TLB вообще не нужно добавлять никакого ото-
бражения. В таком случае операционная система обычно прекращает выполнение
программы с выдачей ошибки сегментации. И только в этом случае программа дей-
ствительно делает что-то неправильно. Во всех остальных случаях ценой некоторой
потери производительности все автоматически исправляется оборудованием и/или
операционной системой.
3.3.4. Таблицы страниц для больших объемов памяти
Буферы TLB могут использоваться для увеличения скорости преобразования вирту-
альных адресов в физические при обычной системе хранения таблицы страниц в памя-
ти. Но этим проблемы не исчерпываются. Возникают проблемы обслуживания очень
больших виртуальных адресных пространств. Далее будут рассмотрены два способа,
позволяющие справиться с этими проблемами.
Многоуровневые таблицы страниц
В качестве первого подхода рассмотрим использование многоуровневой таблицы стра-
ниц, простой пример которой показан на рис. 3.12. В его левой части (на фрагменте а)
показан 32-разрядный виртуальный адрес, разбитый на 10-битное поле PT1, 10-битное
поле PT2 и 12-битное поле смещения. Поскольку под смещение отведено 12 бит, стра-
ницы имеют размер 4 Кбайт и их общее количество составляет 2
20
.
Секрет метода использования многоуровневой таблицы страниц заключается в от-
казе от постоянного хранения всех таблиц страниц в памяти. В частности, вообще не
должны храниться те таблицы, в которых нет необходимости. Предположим, к примеру,
что процессу требуются 12 Мбайт: нижние 4 Мбайт памяти — для текста программы,
следующие 4 Мбайт — для данных и верхние 4 Мбайт — для стека. Между верхней
границей данных и дном стека образуется огромная неиспользуемая дыра.
На рис. 3.12, б показано, как работает двухуровневая таблица страниц. Слева по-
казана таблица страниц верхнего уровня, содержащая 1024 записи, соотносящиеся
с 10-битным полем PT1. Когда диспетчеру памяти предоставляется виртуальный
адрес, то сначала он извлекает поле PT1 и использует его значение в качестве ин-
декса для таблицы страниц верхнего уровня. Каждая из этих 1024 записей в таблице
страниц верхнего уровня представляет 4 Мбайт, поскольку все 4-гигабайтное (то
есть 32-разрядное) виртуальное адресное пространство было разбито на фрагменты
по 4096 байт.
240
Глава 3. Управление памятью
Рис. 3.12. Многоуровневая таблица страниц: а — 32-разрядный адрес с двумя полями
таблиц страниц; б — двухуровневая таблица страниц
Из записи, место которой определяется путем индексирования таблицы страниц верх-
него уровня, извлекается адрес или номер страничного блока таблицы страниц второго
уровня. Запись 0 таблицы страниц верхнего уровня указывает на таблицу страниц
для текста программы, запись 1 — на таблицу страниц для данных, а запись 1023 — на
таблицу страниц для стека. Другие (закрашенные) записи не используются. Поле PT2
теперь используется в качестве индекса на выбранную таблицу страниц второго уровня,
предназначенного для поиска номера страничного блока для самой страницы.
В качестве примера рассмотрим 32-разрядный виртуальный адрес 0x00403004
(4 206 596 в десятичном формате), который соответствует 12 292-му байту внутри
области данных. Этот виртуальный адрес соответствует PT1 = 1, PT2 = 2 и смещение
равно 4. Диспетчер памяти сначала использует PT1 для обращения по индексу к та-