Глава 4 (1085728), страница 5
Текст из файла (страница 5)
Запись, место которой определяется по индексу в таблице страниц верхнего уровня, выдает адрес или номер страничного блока таблицы страниц второго уровня. Запись 0 в таблице страниц первого уровня указывает на таблицу страниц для текста программы, запись 1 указывает на таблицу страниц для данных, запись 1023 указывает на таблицу страниц для стека. Другие (заштрихованные) записи не используются. Поле РT2 теперь используется как индекс в выбранной таблице второго уровня для поиска номера страничного блока самой страницы.
В качестве примера рассмотрим 32-разрядный адрес 0х00403004 (4 206 596 в десятичном виде), который соответствует байту 12 292 в данных. У этого виртуального адреса РT1=1, РT2=2 и Offset=4. Диспетчер памяти сначала использует поле РП, чтобы по индексу в таблице страниц верхнего уровня получить запись 1, которая соответствует адресам от 4 до 8 М. Затем он воспользуется полем РT2, чтобы по индексу из только что найденной таблицы второго уровня извлечь запись 3, которая соответствует адресам от 12 288 до 16 383 внутри своего участка размером 4 М (то есть абсолютным адресам от 4 206 592 до 4 210 687). Эта запись содержит номер физического блока страницы, содержащей виртуальный адрес 0х00403004. Если данная страница не находится в памяти, бит Присутствия/отсутствия в записи таблицы страниц будет равен нулю, что приведет к страничному прерыванию. Если страница в памяти, то номер страничного блока, взятый из таблицы страниц второго уровня, присоединяется к смещению (4), создавая физический адрес. Этот адрес выставляется на шину и передается памяти.
Следует отметить одну интересную деталь на рис. 4.12. Хотя адресное пространство содержит больше миллиона страниц, фактически нужны только четыре таблицы: таблица верхнего уровня и таблицы нижнего уровня для памяти от 0 до 4 М, от 4 до 8 М и для верхних 4 М. Битам Присутствия/отсутствия для 1021 записи таблицы страниц верхнего уровня присвоено значение 0, что вызовет страничное прерывание при любом обращении к ним. Если это происходит, то операционная система заметит, что процесс пытается обратиться к области памяти, не предполагающей ссылок на нее, и предпримет соответствующее действие, например пошлет ему сигнал или уничтожит его. В описанном выше примере мы выбрали круглые значения для различных величин и выбрали размер поля РT1, равный размеру поля РT2, но в реальной практике, конечно, возможны другие цифры.
Система двухуровневой таблицы на рис. 4.12 может быть расширена для трех, четырех и больше уровней. Дополнительные уровни дадут большую гибкость, но сомнительно, что следует усложнять систему больше, чем до трех уровней.
Структура элемента таблицы страниц
Теперь от структуры таблиц страниц в целом мы перейдем к деталям отдельного элемента записи таблицы. Точная структура элемента в значительной мере зависит от машины, но виды представленной информации примерно одни и те же. На рис. 4.13 мы привели образец записи в таблице страниц. Ее длина изменяется от компьютера к компьютеру, но 32 бита — это наиболее распространенный размер. Наиболее важным полем является Номер страничного блока. Прежде всего, задачей отображения страниц является определение этой величины. За этим полем следует бит Присутствия/отсутствия. Если этот бит равен 1, запись имеет силу и может использоваться. Если он равен 0, виртуальная страница, которой соответствует эта запись, в данный момент отсутствует в памяти. Обращение к записи в таблице страниц, у которой этому биту присвоено нулевое значение, приводит к страничному прерыванию.
Биты Защиты говорят о том, какие разрешены виды доступа к этой странице. В простейшей форме это поле содержит один бит, равный 1 для чтения/записи и равный 0 только для чтения. Более сложные схемы имеют три бита, по одному для допуска каждой из операций чтения, записи и выполнения страницы.
Биты Изменения и Обращения отслеживают использование страницы. Когда страница записывается, аппаратура автоматически устанавливает бит Изменение. Этот бит учитывается, когда операционная система решает освободить страничный блок. Если страница в нем была изменена (то есть она «грязная»), то ее новая версия должна быть переписана на диск. Если она не была модифицирована (то есть страница «чистая»), ее можно просто удалить из памяти, так как все еще действительна копия на диске. Этот бит иногда называют грязным битом, так как он отражает состояние страницы.
Бит Обращения устанавливается всякий раз, когда происходит обращение к странице для чтения или записи. Его значение помогает операционной системе при выборе страницы для удаления из памяти, когда случается ошибка из-за отсутствия страницы. Страницы, не использующиеся в данный момент, являются лучшими кандидатами, чем находящиеся в работе. Этот бит играет важную роль в нескольких алгоритмах перемещения страниц, которые мы изучим позже в этой главе.
Наконец, последний бит позволяет запретить кэширование страницы. Это свойство важно для страниц, отображающихся не на память, а на регистры устройств. Если операционная система находится в цикле ожидания ответа от некоторого устройства ввода-вывода, которому была только что дана команда, существенно, чтобы аппаратура продолжала получать слово из устройства, а не использовало старую копию, находящуюся в кэш-памяти. При помощи этого бита кэширование можно отключить. Машины, имеющие отдельное пространство адресов ввода-вывода и не использующие отображения регистров ввода-вывода на память, не нуждаются в этом бите.
Заметим, что адрес места на диске, в котором хранится страница тогда, когда она не находится в памяти, не является частью таблицы страниц. Причина очень проста. Таблица страниц содержит только ту информацию, которая нужна аппаратуре для перевода виртуального адреса в физический. Информация, необходимая операционной системе для обработки страничных прерываний, хранится в программных таблицах внутри операционной системы. Аппаратуре она не нужна.
Буферы быстрого преобразования адреса (TLB)
В большинстве схем со страничной организацией памяти таблицы страниц хранятся в памяти из-за их значительного размера. Потенциально такое устройство оказывает колоссальное влияние на производительность. Рассмотрим, например, команду процессора, копирующую содержимое одного регистра в другой. В отсутствие страничной организации памяти эта команда приводит только к одному обращению к памяти для выборки самой команды. Если же память организована постранично, то будут необходимы дополнительные ссылки для доступа к таблице страниц. Так как скорость выполнения команд в основном ограничена скоростью, с которой центральный процессор выбирает команды и данные из памяти, необходимость двух обращений к таблице страниц на одну ссылку к памяти уменьшает производительность на 2/3. При таких условиях никто не стал бы использовать этот метод.
Разработчики компьютеров многие годы размышляли об этой проблеме и в результате придумали решение. Оно основано на наблюдении, что большинство программ склонно делать огромное количество обращений к небольшому количеству страниц, а не наоборот. Таким образом, в таблице страниц только малая доля записей читается интенсивно, остальная часть едва ли вообще используется.
В результате принятого решения компьютер снабжается небольшим аппаратным устройством, служащим для отображения виртуальных адресов в физические без прохода по таблице страниц. Это устройство, называемое буфером быстрого преобразования адреса (TLB — Translation Lookaside Buffer) или иногда ассоциативной памятью, продемонстрировано в табл. 4.1. Оно обычно находится внутри диспетчера памяти и состоит из нескольких записей. В этом примере их восемь, но фактически записей редко бывает больше 64. Каждая запись содержит информацию об одной странице, а именно: номер виртуальной страницы, бит, устанавливаемый при изменении страницы, код защиты (разрешения на чтение/ запись/выполнение) и номер физического страничного блока, в котором расположена эта страница. Эти поля однозначно соответствуют полям в таблице страниц. Еще один бит служит признаком того, действительна ли запись (то есть используется ли она в данный момент) или нет.
Пример, который мог бы сформировать TLB-буфер, изображенный на рис. 4.14, — это циклический процесс, располагающийся в виртуальных страницах 19, 20 и 21, поэтому эти записи в буфере на рис. 4.14 имеют защитные коды для чтения и выполнения. Основные данные, используемые в настоящее время (скажем, обрабатываемый массив), находятся в страницах 129 и 130. Страница 140 содержит индексы, требующиеся для вычислений массива. И наконец, в страницах 860 и 861 находится стек.
Теперь рассмотрим, как же функционирует буфер быстрого преобразования адреса (TLB). Когда виртуальный адрес представляется диспетчером памяти для отображения, аппаратура сначала убеждается в том, что номер его виртуальной страницы присутствует в буфере TLB путем сравнения адреса со всеми записями одновременно (то есть параллельно). Если найдено имеющее силу совпадение и обращение не нарушает биты защиты, страничный блок берется прямо из буфера TLB, без перехода к таблице страниц. Если номер виртуальной страницы присутствует в буфере TLB, но инструкция пытается записать что-то на страницу, доступную только для чтения, формируется ошибка защиты точно так же, как это происходило бы из самой таблицы страниц.
Интересная ситуация получается, если номер виртуальной страницы не находится в буфере быстрого преобразования адреса. Диспетчер памяти обнаруживает отсутствие страницы и выполняет обычный поиск в таблице страниц. Затем он удаляет одну из записей из буфера TLB и заменяет ее только что найденной записью из таблицы страниц. Таким образом, если эта страница снова вскоре будет затребована, во второй раз поиск окажется успешным, а не неудачным. Когда запись удаляется из буфера быстрого преобразования адреса, бит изменения копируется в запись таблицы страниц в памяти. Другие величины уже находятся там. Когда буфер TLB загружается из таблицы страниц, все поля берутся из памяти.
Программное управление буфером TLB
До сих пор мы предполагали, что каждая машина со страничной виртуальной памятью имеет таблицы страниц, распознаваемые аппаратным обеспечением и буфером быстрого преобразования адреса. При таком устройстве управление буфером TLB и обработка его ошибок выполняются полностью аппаратурой диспетчера памяти (MMU). Передача управления операционной системе происходит только тогда, когда страница отсутствует в памяти.
В прошлом это допущение было справедливо. Однако многие современные RISC-компьютеры, включая машины SPARC, MIPS, Alpha и HP PA, выполняют почти все страничное управление программно. На этих машинах записи буферы TLB явно загружаются операционной системой. Когда происходит неудачный поиск в буфере TLB, диспетчер памяти вместо того, чтобы переходить к таблице страниц для поиска и выбора необходимой страницы, формирует ошибку буфера TLB и передает проблему в руки операционной системы. Система должна найти страницу, удалить запись из буфера TLB, ввести новую запись и перезапустить прерванную инструкцию. И, конечно, все это должно быть сделано при помощи небольшого числа команд, потому что неудачи поиска в буфере быстрого преобразования адреса происходят намного чаще, чем ошибки из-за отсутствия страниц.
Достаточно удивительно то, что если буфер TLB имеет небольшой размер (скажем, 64 записи) для понижения частоты неудачных пропусков, программное управление буфером, оказывается, является приемлемо результативным. Главная выгода здесь заключается в намного более простом устройстве диспетчера памяти, что освобождает достаточное количество пространства в микросхеме процессора для кэша и других устройств, способных повысить производительность. Для улучшения производительности на машинах, программно управляющих буфером TLB, разрабатывались различные стратегии поведения. Один подход состоит в попытке уменьшить как частоту неудачного поиска в буфере, так и его стоимость, когда он все-таки случается . Чтобы уменьшить вероятность неудачного поиска в буфере TLB, иногда операционная система может интуитивно вычислить, какие страницы, возможно, будут использоваться следующими и предварительно загрузить записи для них в буфер TLB. Например, когда клиентский процесс посылает сообщение серверному процессу на той же самой машине, очень вероятно, что сервер вскоре должен будет начать работу. Зная это, система может также проверить, где находятся страницы кода сервера, данных и стека, пока прерывание обрабатывается, чтобы осуществить вызов send, и преобразовать их адреса из виртуальных в физические до того, как они смогут стать причиной ошибки TLB-буфера.
Обычный путь обработки неудачного поиска в буфере TLB, аппаратно или программно — это переход в таблицу страниц и выполнение операции индексации, чтобы определить место страницы, к которой происходит обращение. При осуществлении этого поиска программно возникает проблема, заключающаяся в том, что страницы, содержащиеся в таблице страниц, могут отсутствовать в буфере быстрого преобразования адреса, что вызовет дополнительные ошибки буфера TLB во время обработки. Их количество можно уменьшить, поддерживая большой (например, 4 Кбайт) программный кэш записей буфера TLB с фиксированным расположением в памяти, чьи страницы всегда хранятся в буфере TLB. Если сначала проверять программный кэш, операционная система может в значительной степени снизить количество неудачных поисков в буфере TLB.
Инвертированные таблицы страниц
Традиционные таблицы страниц, тип которых мы описывали до сих пор, требуют по одной записи на каждую виртуальную страницу, так как они индексируются по номеру этой страницы. Если адресное пространство состоит из 232 байт с размером страницы 4096 байт, тогда в таблице страниц должно быть больше миллиона записей. При этом таблица страниц будет занимать минимум 4 Мбайт. В достаточно больших системах это, вероятно, выполнимо.
Однако поскольку 64-разрядные компьютеры встречаются все чаще, ситуация радикально меняется. Если теперь адресное пространство увеличилось до 264 байт с размером страницы 4096 байт, нам требуется таблица страниц с 252 записями. Если каждая запись равна 8 байтам, таблица займет больше 30 Тбайт. Выделение 30 Тбайт только для таблицы страниц нереально сейчас и не будет реальным когда-либо в будущем. Следовательно, для 64-разрядного страничного виртуального пространства необходимо другое решение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
