Ostep глава 19. Translations Lookaside Buffers: перевод

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

СУТЬ:
КАК УСКОРИТЬ ПЕРЕВОД АДРЕСОВ
Как мы можем ускорить перевод адресов и вообще избежать дополнительной ссылки на память, которая, по-видимому, требуется для подкачки? Какая аппаратная поддержка требуется? Какое участие ОС необходимо?

Когда мы хотим сделать все быстро, ОС обычно нуждается в некоторой помощи. И помощь часто приходит от старого друга ОС - аппаратного обеспечения. Чтобы ускорить перевод адресов, мы собираемся добавить то, что называется (по историческим причинам [CP78]) буфером lookaside, или TLB [CG68, C95]. TLB является частью блока управления памятью (MMU) и представляет собой просто аппаратный кэш часто используемых переводов виртуальных адресов в физические; таким образом, лучшим названием было бы кэш перевода адресов. После каждой ссылки на виртуальную память аппаратное обеспечение сначала проверяет TLB, чтобы увидеть, удерживается ли в нем желаемый перевод; если это так, то перевод выполняется (быстро) без необходимости сверяться с таблицей страниц (в которой есть все переводы). Из-за их огромного влияния на производительность TLB в реальном смысле делают виртуальную память возможной [C95].

Рис. 19.1 - Алгоритм потока управления TLB
Рис. 19.1 - Алгоритм потока управления TLB
Рис. 19.1 - Алгоритм потока управления TLB

19.1 Базовый алгоритм TLB

На рис. 19.1 показан примерный набросок того, как аппаратное обеспечение может обрабатывать преобразование виртуальных адресов, предполагая простую линейную таблицу страниц (т. е. таблица страниц представляет собой массив) и управляемый аппаратным обеспечением TLB (т. е. аппаратное обеспечение берёт на себя большую часть ответственности за доступ к таблице страниц; подробнее об этом мы расскажем ниже).

Алгоритм, которому следует аппаратное обеспечение, работает следующим образом: сначала извлекает номер виртуальной страницы (VPN) из виртуального адреса (строка 1 на рис. 19.1) и проверяет, содержит ли TLB перевод для этой VPN (строка 2). Если это так, у нас есть попадание TLB (TLB hit), что означает, что TLB содержит перевод. Успех! Теперь мы можем извлечь номер фрейма страницы (PFN) из соответствующей записи TLB, объединить его со смещением от исходного виртуального адреса и сформировать желаемый физический адрес (PA) и получить доступ к памяти (строки 5-7), предполагая, что проверки защиты не завершатся неудачей (строка 4).

Если процессор не найдет перевод в TLB (TLB miss), нам предстоит еще кое-что сделать. В этом примере аппаратное обеспечение обращается к таблице страниц, чтобы найти перевод (строки 11-12), и, предполагая, что ссылка на виртуальную память, сгенерированная процессом, является допустимой и доступной (строки 13, 15), обновляет TLB с переводом (строка 18). Этот набор действий является дорогостоящим, в первую очередь из-за дополнительной ссылки на память, необходимой для доступа к таблице страниц (строка 12). Наконец, после обновления TLB аппаратное обеспечение повторяет инструкцию; на этот раз перевод находится в TLB, и ссылка на память обрабатывается быстро.

TLB, как и все кэши, построен на предпосылке, что в общем случае переводы находятся в кэше (т. е. при поиске произойдёт TLB Hit). Если это так, то добавляются небольшие накладные расходы, так как TLB находится рядом с процессорным ядром и рассчитан на довольно быструю работу. Когда происходит промах, возникает высокая стоимость подкачки; для поиска перевода необходимо обратиться к таблице страниц и получить дополнительную ссылку на память (или больше, с более сложными таблицами страниц). Если это происходит часто, программа, скорее всего, будет работать заметно медленнее; доступ к памяти, по сравнению с большинством инструкций процессора, является довольно дорогостоящим, и события TLB miss приводят к большему количеству обращений к памяти. Таким образом, мы надеемся избежать событий TLB miss, насколько это возможно.

19.2 Пример: доступ к элементам массива

Чтобы прояснить работу TLB, давайте рассмотрим простую трассировку виртуальных адресов и посмотрим, как TLB может повысить свою производительность. В этом примере предположим, что у нас есть массив из 10-ти 4-байтовых целых чисел в памяти, начиная с виртуального адреса 100. Предположим далее, что у нас есть небольшое 8-битное виртуальное адресное пространство с 16-байтовыми страницами; таким образом, виртуальный адрес разбивается на 4-битный VPN (есть 16 виртуальных страниц) и 4-битное смещение (на каждой из этих страниц 16 байт).

На рис. 19.2 показан массив, размещенный на 16-ти 16-байтовых страницах системы. Как вы можете видеть, первая запись массива (a[0]) начинается с (VPN=06, offset=04); на эту страницу помещаются только три 4-байтовых целых числа. Массив переходит на следующую страницу (VPN=07), где следующие четыре записи (a[3] ... a[6]) найдены. Наконец, последние три записи массива из 10 записей (a[7] ... a[9]) расположены на следующей странице адресного пространства (VPN=08).

Теперь давайте рассмотрим простой цикл, который обращается к каждому элементу массива, что-то, что выглядело бы так в C:

Ostep глава 19. Translations Lookaside Buffers: перевод

Для простоты мы сделаем вид, что доступ к памяти, генерируемый циклом, осуществляется только к массиву (игнорируя переменные i и sum, а также сами инструкции). При обращении к первому элементу массива (a[0]) процессор увидит загрузку на виртуальный адрес 100. Аппаратное обеспечение извлекает VPN из этого (VPN=06) и использует его для проверки TLB на наличие допустимого перевода. Предполагая, что это первый раз, когда программа обращается к массиву, результатом будет TLB miss.

Следующий доступ к a[1], и здесь есть хорошие новости: TLB hit! Поскольку второй элемент массива упакован рядом с первым, он находится на той же странице; поскольку мы уже обращались к этой странице при обращении к первому элементу массива, перевод адресов уже загружен в TLB. И отсюда причина нашего успеха. Доступ к a[2] встречает аналогичный успех (еще один hit), потому что он тоже живет на той же странице, что и a[0] и a[1].

Рис. 19.2 - Пример: массив в крошечном адресном пространстве
Рис. 19.2 - Пример: массив в крошечном адресном пространстве
Рис. 19.2 - Пример: массив в крошечном адресном пространстве

К сожалению, когда программа обращается к а[3], мы сталкиваемся с еще одним событием TLB miss. Однако, еще раз, следующие записи (a[4] ... a[6]) вызовут TLB hit, так как все они находятся на одной странице в памяти.

Наконец, доступ к а[7] вызывает последний TLB miss. Аппаратное обеспечение еще раз обращается к таблице страниц, чтобы определить местоположение этой виртуальной страницы в физической памяти, и соответствующим образом обновляет TLB. Последние два доступа (a[8] и a[9]) получают преимущества этого обновления TLB; когда аппаратное обеспечение ищет в TLB их переводы, в результате появляются еще два события TLB hit.

Давайте подытожим активность TLB во время наших десяти обращений к массиву: miss, hit, hit, miss, hit, hit, hit, miss, hit, hit. Таким образом, наш коэффициент попадания TLB, который представляет собой количество обращений, деленное на общее количество обращений, составляет 70%. Хотя это не слишком высоко (на самом деле, мы хотим, чтобы процент попаданий приближался к 100%), он ненулевой, что может быть сюрпризом. Несмотря на то, что это первый раз, когда программа обращается к массиву, TLB повышает производительность из-за пространственной локализации. Элементы массива плотно упакованы в страницы (т. е. Они находятся близко друг к другу в пространстве), и, таким образом, только первый доступ к элементу на странице приводит к TLB miss.

Также обратите внимание на роль, которую играет размер страницы в этом примере. Если бы размер страницы был просто в два раза больше (32 байта, а не 16), доступ к массиву пострадал бы еще меньше и создал бы меньше промахов. Поскольку типичные размеры страниц больше похожи на 4 КБ, эти типы плотных обращений на основе массивов обеспечивают отличную производительность TLB, встречая только один промах на страницу обращений.

ИСПОЛЬЗУЙТЕ КЭШИРОВАНИЕ, КОГДА ЭТО ВОЗМОЖНО
Кэширование-один из самых фундаментальных методов повышения производительности в компьютерных системах, который используется снова и снова, чтобы сделать частые запросы быстрыми [HP06]. Идея аппаратных кэшей состоит в том, чтобы использовать преимущества локальности в ссылках на инструкции и данные. Обычно существует два типа локальности: временная локальность и пространственная локальность. В случае временной локализации идея заключается в том, что инструкция или элемент данных, к которым недавно был получен доступ, скорее всего, будут повторно доступны в ближайшее время в будущем. Подумайте о переменных цикла или инструкциях в цикле; к ним обращаются неоднократно с течением времени. С пространственной локальностью идея заключается в том, что если программа обращается к памяти по адресу x, она, скорее всего, скоро получит доступ к памяти рядом с x. Представьте себе здесь потоковую передачу через какой-то массив, доступ к одному элементу, а затем к следующему. Конечно, эти свойства зависят от точной природы программы и, следовательно, не являются жесткими и быстрыми законами, а скорее эмпирическими правилами.
Аппаратные кэши, будь то для инструкций, данных или переводов адресов, используют преимущества локальности, сохраняя копии памяти в небольшой, быстрой памяти на чипе. Вместо того, чтобы обращаться к (медленной) памяти для удовлетворения запроса, процессор может сначала проверить, существует ли ближайшая копия в кэше; если это так, процессор может быстро получить к ней доступ (т. е. За несколько циклов процессора) и избежать дорогостоящего времени, необходимого для доступа к памяти (много наносекунд).
Вы можете задаться вопросом: если кэши (например, TLB) настолько хороши, почему бы нам просто не сделать большие кэши и не хранить в них все наши данные? К сожалению, именно здесь мы сталкиваемся с более фундаментальными законами, такими как законы физики. Если вам нужен быстрый кэш, он должен быть небольшим, поскольку такие проблемы, как скорость света и другие физические ограничения, становятся актуальными. Любой большой кэш по определению является медленным. Таким образом, мы застряли с небольшими, быстрыми кэшами; остается вопрос, как лучше всего использовать их для повышения производительности.

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

Рис. 19.3 - Алгоритм потока управления TLB (обрабатывается средствами ОС)
Рис. 19.3 - Алгоритм потока управления TLB (обрабатывается средствами ОС)
Рис. 19.3 - Алгоритм потока управления TLB (обрабатывается средствами ОС)

19.3 Кто перехватывает TLB miss?

Один вопрос, на который мы должны ответить: кто обрабатывает TLB miss? Возможно два ответа: аппаратное обеспечение или программное обеспечение (ОС). В стародавние времена, аппаратное обеспечение имело сложные наборы инструкций (иногда называемые CISC) и люди которые создавали аппаратное обеспечение не особо доверяли этим коварным ребятам из мира операционных систем. По этим причинам аппаратное обеспечение брало на себя обработку TLB miss. Но для осуществления обработки, аппаратное обеспечение должно точно знать где в памяти расположены таблицы страниц (используя page-table base register из рисунка 19.1), а также их точный формат; при перехватывании miss, аппаратное обеспечение "проходит" таблицу страниц, находит корректную страницу в таблице и производит необходимые преобразования, обновляет TLB сделанной трансляцией адресов, и выполняет инструкцию. Пример старой архитектуры, в которой реализован аппаратно-управляемый TLB - это архитектура Intel x86, которая использует многоуровневые таблицы страниц фиксированного размера (смотри следующую главу для подробностей); на текущую страницу указывает регистр CR3 [I09].

Более современные архитектуры (MIPS R10k [H93] или SPARK v9 от Sun [WG00], обе RISK или reduced-instruction set computers) реализуют программно-управляемый TLB. Если происходит TLB miss, программы просто выбрасывают исключение (линия 11 на рисунке 19.3), которое останавливает поток инструкций, повышает уровень привилегий до режима ядра и переключается на trap handler. Как вы могли догадаться, trap handler - это код в ОС который создан для обработки событий TLB miss. В процессе работы, код находит трансляцию в таблице страниц, использует специальные "привилегированные" инструкции чтобы обновить TLB, и возвращается из trap; в этот момент, аппаратное обеспечение пытается повторно выполнить инструкцию (что приводит к TLB hit).

Пришло время обсудить некоторые важные детали. Во-первых, инструкция return-from-trap должна отличаться от той которую мы видели при обработке системных вызовов. В последнем случае, return-from-trap должна вернуть выполнение инструкции в операционную систему после возвращения из trap, что похоже на возврат из процедуры, за которым следует немедленное выполнение следующих инструкций. В первом случае, когда происходит возврат из TLB miss-handling trap, аппаратное обеспечение должно возвратить выполнение в инструкцию которая вызвала trap; это возвращение позволяет инструкции снова выполняться, т.к. в этот раз произойдёт TLB hit. Таким образом, в зависимости от того как trap или exception были инициированы, аппаратное обеспечение должно сохранять другой PC при обработке trap в операционной системе, для корректного возвращения выполнения, когда это потребуется.

RISC против CISC
В 1980-х, в сообществе архитекторов, происходила великая битва. На одной стороне был лагерь CISC, что означает Complex Instruction Set Computing; на другой стороне был RISC или Reduced Instruction Set Computing [PS81]. На острие копья за архитектуру RISC выступал David Patterson из Berkley и John Hennessy из Stanford (также они соавторы знаменитой книги [HP06]), также позже John Cocke был номинирован на премию Тьюринга за раннюю работу над RISK [CM00].
Набор инструкций CISC содержал в себе множество инструкций, каждая из которых относительно мощная. Например, вы могли увидеть операцию копирования строки которая принимает два указателя и длину и копирует байты из источника в место назначения. Идея CISC в том, что инструкции должны быть высокоуровневыми примитивами, что позволило бы делать ассемблерные языки легче в использовании, и сделать код более компактным.
Набор инструкций RISC прямо противоположный. Ключевой идеей RISC является то, что инструкции это всего лишь цели для компилятора, и всем компиляторам в действительности нужно будет несколько простых примитивов которые они могут использовать для генерации высокопроизводительного кода. Таким образом, адепты RISC, проповедовали уничтожение максимально возможного числа инструкций из аппаратного обеспечения (в особенности микрокода), и сделать оставшееся унифицированным и быстрым.
По началу чипы RISC оказали огромное влияние, т.к. были заметно быстрее [BC91]; много бумаги было исписано; пара компаний было создано (MIPS и Sun). Тем не менее, со временем, производители CISC такие как Intel включили множество техник RISC в ядро своих процессоров, например добавили ранние конвейерные этапы которые трансформировали сложные инструкции в микро-инструкции которые могли потом быть обработаны в RISC-like манере. Такие инновации, плюс возрастающее количество транзисторов на каждом чипе, позволили CISC оставаться конкурентоспособным. В результате дебаты сошли на нет, и сегодня оба типа процессоров исполняют инструкции одинаково быстро.

Во-вторых, когда выполняется TLB miss-handling code, операционная система должна быть чрезвычайно осторожной для того чтобы не спровоцировать бесконечную цепь TLB miss. Для этого существует множество решений; например вы можете хранить обработчики TLB miss в физической памяти (где они не мапятся на память и соответственно не нуждаются в трансляции адресов), или зарезервировать некоторые области в TLB для постоянных трансляций и использовать некоторые из этих областей для самих обработчиков; эти трансляции (wired translations) всегда провоцируют TLB hit.

TLB VALID BIT != PAGE TABLE VALID BIT
Общая ошибка это приравнивание бита валидности из TLB с битом валидности в таблице страниц. В таблице страниц, когда page-table entry (PTE) помечен невалидным, это означает то что страница небыла выделена процессом, и не должна быть доступна корректно-работающей программе. Обычное поведение когда происходит попытка доступа к невалидной странице - это вызвать trap в ОС, который убьёт процесс.
Бит валидности в TLB, напротив, просто указывает, имеет ли запись TLB допустимую трансляцию адреса. Когда система загружается, например, общее начальное состояние для каждой записи TLB помечается невалидным, т.к. нет адресов для трансляций. Когда виртуальная память становится доступной, и программы начинают выполнение и осуществление доступа к их виртуальной памяти, TLB медленно заполняется, и таким образом валидные значения вскоре заполняют кэш.
Бит валидности TLB крайне полезен при переключениях контекста, на что мы обратим внимание далее. Устанавливая все записи TLB невалидными, система может быть уверена в том что процесс который должен быть запущен не использует случайно трансляции от прошлых процессов.

Главным преимуществом программно-управляемых решений является гибкость: операционная система может использовать любую структуру данных которую хочет для реализации таблицы страниц, без необходимости замены аппаратного обеспечения. Другое преимущество это простота, как видно в TLB control flow (линия 11 рис. 19.3, в сравнении с линиями 11-19 рис 19.1) . Аппаратное обеспечение не делает много при срабатывании TLB miss: просто вызывает exception и позволяет обработчику TLB miss в операционной системе делать работу.

19.4 Контент TLB. Что в нём?

Давайте взглянем на контент аппаратного TLB более детально. Обычный TLB может иметь 32, 64 или 128 вхождений и быть, что называется, fully associative. В основном это значит, что любая полученная трансляция может быть где угодно в TLB, и то, что аппаратное обеспечение будет параллельно искать запись во всём пространстве TLB чтобы найти желаемую запись. Запись в TLB может выглядеть так:

Ostep глава 19. Translations Lookaside Buffers: перевод

Обратите внимание, что и VPN, и PFN присутствуют в каждой записи, так как перевод может оказаться в любом из этих местоположений (в аппаратных терминах TLB известен как полностью ассоциативный кэш). Аппаратное обеспечение выполняет параллельный поиск записей, чтобы проверить, есть ли совпадение.

Дополнительный интерес представляют "other bits". Например, TLB обычно содержит бит валидности (valid bit), который отвечает на вопрос о том имеет ли запись допустимый перевод адресов или нет. Также обычно присутствуют биты защиты (protection bits), которые определяют то как к страницам (в таблице страниц) осуществляется доступ. Например, кодовые страницы (code pages) могут быть помечены как read and execute, в то время как страницы куч могут быть помечены как read and write. Также может существовать множество других полей, включая address-space-identifier, dirty bit, и так далее; смотри ниже для более подробной информации.

19.5 Проблемы TLB: переключения контекста

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

Чтобы понять ситуацию лучше, давайте взглянем на пример. Когда один процесс (Р1) запущен, предполагается что TLB кеширует трансляции связанные с ним, т.е. они приходят из таблицы страниц процесса Р1. Предположим, в рамках данного примера, что 10-я виртуальная страница Р1 мапится на физический фрейм 100.

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

Ostep глава 19. Translations Lookaside Buffers: перевод

В TLB изображённом выше, мы имеем следующую проблему: VPN 10 транслируется на PFN 100 (P1) или PFN 170 (P2), но аппаратное обеспечение не может понять связь между записью и процессом. Таким образом нам нужно сделать больше работы для того чтобы TLB корректно и эффективно поддерживал виртуализацию между множеством процессов. Таким образом возникает сложность:

КАК УПРАВЛЯТЬ КОНТЕНТОМ TLB ПРИ ПЕРЕКЛЮЧЕНИИ КОНТЕКСТА
При переключении контекста между процессами, трансляции в TLB последнего запущенного процесса не имеют смысла для вновь запушенного процесса. Что нужно сделать аппаратному обеспечению или ОС чтобы решить эту проблему?

Есть несколько возможных решений этой проблемы. Одна возможность это просто сбросить (flush) весь TLB при переключении контекста, так чтобы он быть пуст перед запуском следующего процесса. В программно-зависимых системах, этого можно достигнуть с помощью явной (и привилегированной) инструкции отданной аппаратному обеспечению; в аппаратно-зависимом TLB, flush может быть принят когда регистр основанный на таблице страниц изменён (обратите внимание, что ОС должна изменить PTBR при переключении контекста в любом случае). Есть подход при котором операция flush просто устанавливает все биты валидности в 0, что в сущности, тоже что очистить кеш полностью.

Очищая TLB при каждом переключении контекста, мы теперь имеем рабочее решение, т.к. процесс никогда случайно не столкнётся с ошибочной трансляцией в TLB. Однако вот цена такого решения: каждый раз когда процесс запускается, он провоцирует события TLB miss при попытке получить данные из памяти. Если ОС переключается между процессами часто, цена может быть высокой.

Чтобы снизить эти накладные расходы, некоторые системы вводят аппаратную поддержку для реализации общего доступа к TLB между переключениями контекста. В частности, некоторые аппаратные системы поставляют в TLB поля address space identifier (ASID). Вы можете думать об ASID как о идентификаторе процесс (PID), но он имеет меньше бит (8 бит для ASID против 32 бит для PID).

Если мы возьмём наш TLB из примера выше и добавим ASIDs, процессы смогут обмениваться TLB: только поле ASID нужно для идентификации идентичных переводов. Вот изображение кеша TLB с добавленным полем ASID:

Ostep глава 19. Translations Lookaside Buffers: перевод

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

Кроме того, вы, возможно, также подумали о другом случае, когда две записи TLB удивительно похожи. В этом примере есть две записи для двух разных процессов с двумя разными VPN, которые указывают на одну и ту же физическую страницу:

Ostep глава 19. Translations Lookaside Buffers: перевод

Такая ситуация может возникнуть, например, когда два процесса совместно используют страницу (например, кодовую страницу). В приведенном выше примере процесс 1 совместно использует физическую страницу 101 с процессом 2; P1 сопоставляет эту страницу с 10-й страницей своего адресного пространства, в то время как P2 сопоставляет ее с 50-й страницей своего адресного пространства. Совместное использование кодовых страниц (в двоичных файлах или общих библиотеках) полезно, поскольку оно уменьшает количество используемых физических страниц, тем самым уменьшая накладные расходы на память.

19.6 - Проблема: политика замены

Проблема которую мы должны разобрать - это замена кеша. Она касается любого кеша, в том числе и TLB. Когда мы создаём новую запись в TLB, нам нужно перезаписать какую-то старую запись, таким образом возникает вопрос: какую конкретную запись перезаписывать?

КАК СПРОЕКТИРОВАТЬ ПОЛИТИКУ ЗАМЕНЫ КЕША ДЛЯ TLB
Какая запись в TLB должна быть перезаписана когда мы добавляем новую запись в TLB? Цель в том, чтобы минимизировать miss rate (или максимизировать hit rate) и таким образом улучшить производительность.

Мы изучим такие политики подробнее когда будем решать проблему сброса страниц памяти на диск; здесь мы просто осветили несколько типичных политик. Один из распространённых подходов - это перезаписать наименее используемую запись (least-recently-used, LRU). Другое типичное решение - это использование случайной политики удаления, которая удаляет запись из кеша случайным образом. Такая политика проста и позволяет избежать крайних случаев; например, “разумная” политика, такая как LRU, ведет себя совершенно необоснованно, когда программа перебирает n + 1 страниц с TLB размером n; в данном случае, LRU будем генерировать TLB miss на каждую попытку доступа, случайная политика будет лишена таких недостатков.

19.7 Реальная запись TLB

Наконец, давайте кратко рассмотрим реальный TLB. Этот пример из архитектуры MIPS R4000 [H93], современной системы которая используем программно-управляемый TLB; слегка упрощённая запись MIPS TLB представлена на рисунке 19.4

MIPS R4000 поддерживает 32-битное адресное пространство со страницами по 4KB. Таким образом мы можем ожидать 20-ти битный VPN и 12-ти битное смещение в нашем виртуальном адресном пространстве. Однако, как вы можете видеть в TLB, для VPN существует только 19 бит; как оказалось, адреса пользователей будут поступать только из половины адресного пространства (остальное зарезервировано для ядра), и, следовательно, требуется только 19 бит VPN. VPN преобразуется в 24-битный физический номер кадра (PFN) и, следовательно, может поддерживать системы с объемом основной памяти до 64 ГБ (физической) (2^24 4 КБ страниц).

Есть ещё несколько интересных битов в MIPS TLB. Мы видим глобальный бит (G), который используется для страниц глобально доступных между процессами. Также, если глобальный бит установлен, ASID игнорируется. Мы также видим 8-ми битовый ASID, который ОС может использовать для того чтобы различать адресные пространства (как описано выше).

Рисунок 19.4: запись в MIPS TLB
Рисунок 19.4: запись в MIPS TLB
Рисунок 19.4: запись в MIPS TLB
RAM не всегда RAM (Закон Куллера - Culler's Law)
Термин random-access memory или RAM, подразумевает что вы можете получить доступ к любой части RAM с равной скоростью. В основном, думать о RAM таким образом нормально из-за существующих особенностей аппаратного обеспечения/ОС типа TLB. Доступ к конкретной странице памяти может быть ресурсоёмким, если к запрашиваемой странице ещё не осуществлялся доступ и перевод адреса не хранится в TLB. Прекрасно если читателю удастся запомнить совет по реализации: RAM не всегда RAM. Иногда получая случайный доступ в своём адресном пространстве, особенно если количество страниц к которым нужно получить доступ превышает размер TLB, может привести к серьёзному замедлению производительности. Потому что один из наших консультантов, David Culler, всегда указывал на то что TLB является источником множества проблем производительности, мы называем этот закон в его честь: Culler's Law

Один вопрос для вас, что ОС должна сделать если запущено больше 256 (2^8) процессов одновременно. В конце записи мы видим 3 Coherence (C) бита, которые определяют как страница кеширована аппаратным обеспечением (что немного выходит за рамки статьи); dirty бит который устанавливается когда страница записывается (мы увидим его применение позже); valid бит который говорит аппаратному обеспечению что запись валидна. В записи также есть поле page mask (не представлено на изображении), которое поддерживает несколько размеров страниц; мы увидим позже почему использование страниц большего размера может быть полезным. Несколько из 64 битов не используются (закрашены серым на диаграмме).

MIPS TLB обычно имеет 32 или 64 таких записи, большинство из них используются пользовательскими процессами во время выполнения. Несколько зарезервированы для ОС. Wired регистр может использоваться ОС для указания точного количества зарезервированных для ОС слотов; ОС использует зарезервированный мапинг для кода и данных к которым хочет получить доступ в критических ситуациях, в местах где TLB miss инициировать проблематично (напр. в обработчике TLB miss).

Т.к. MIPS TLB программно-управляемый, нужны инструкции для обновления TLB. MIPS поддерживает 4 таких инструкции: TLBP, которая используется TLB чтобы убедиться в том, что какая-то конкретная трансляция присутствует в кеше; TLBR, которая считывает содержимое записи TLB в регистры; TLBWI, которая перезаписывает какую-то конкретную запись TLB; и TLBWR, которая перезаписывает случайную запись TLB. ОС использует эти инструкции для управления содержимым TLB. Это, конечно, критично т.к. эти инструкции привелегированные; представьте что пользовательский процесс может сделать если изменит содержимое TLB (подсказка: почти все, что угодно, включая захват машины, запуск собственной вредоносной “ОС” или даже исчезновение Солнца с небосвода).

19.8 Выводы

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

Однако TLB не делает мир радужным для каждой существующей программы. В частности, если количество страниц, к которым программа обращается за короткий промежуток времени, превышает количество страниц, которые помещаются в TLB, программа будет генерировать большое количество TLB miss и, таким образом, работать немного медленнее. Мы называем это явление превышением охвата TLB (TLB coverage), и это может быть довольно серьезной проблемой для некоторых программ. Одним из решений, как мы обсудим в следующей главе, является поддержка больших размеров страниц; сопоставляя ключевые структуры данных с областями адресного пространства программы, которые сопоставляются большими страницами, можно увеличить эффективный охват TLB. Поддержка больших страниц часто используется такими программами, как система управления базами данных (СУБД), которые имеют определенные структуры данных, как большие, так и с произвольным доступом. Еще одна проблема TLB, о которой стоит упомянуть: доступ к TLB может легко стать узким местом в конвейере ЦП, в частности, с тем, что называется физически индексированным кэшем (physically-indexed cache). С таким кэшем преобразование адресов должно происходить до того, как будет получен доступ к кэшу, что может немного замедлить процесс. Из-за этой потенциальной проблемы люди изучили всевозможные хитроумные способы доступа к кэшам с виртуальными адресами, что позволяет избежать дорогостоящего этапа перевода в случае попадания в кэш. Такой виртуально-индексированный кэш (virtually-indexed cache) решает некоторые проблемы с производительностью, но также вводит новые проблемы в конструкцию оборудования. Более подробную информацию см. В обзоре Wiggins's fine survey [W03].

Ccылки

[BC91] “Performance from Architecture: Comparing a RISC and a CISC with Similar Hardware Organization” by D. Bhandarkar and Douglas W. Clark. Communications of the ACM, September 1991. A great and fair comparison between RISC and CISC. The bottom line: on similar hardware, RISC was about a factor of three better in performance

[CM00] “The evolution of RISC technology at IBM” by John Cocke, V. Markstein. IBM Journal of Research and Development, 44:1/2. A summary of the ideas and work behind the IBM 801, which many consider the first true RISC microprocessor.

[C95] “The Core of the Black Canyon Computer Corporation” by John Couleur. IEEE Annals of History of Computing, 17:4, 1995. In this fascinating historical note, Couleur talks about how he invented the TLB in 1964 while working for GE, and the fortuitous collaboration that thus ensued with the Project MAC folks at MIT.

[CG68] “Shared-access Data Processing System” by John F. Couleur, Edward L. Glaser. Patent 3412382, November 1968. The patent that contains the idea for an associative memory to store address translations. The idea, according to Couleur, came in 1964.

[CP78] “The architecture of the IBM System/370” by R.P. Case, A. Padegs. Communications of the ACM. 21:1, 73-96, January 1978. Perhaps the first paper to use the term translation lookaside buffer. The name arises from the historical name for a cache, which was a lookaside buffer as called by those developing the Atlas system at the University of Manchester; a cache of address translations thus became a translation lookaside buffer. Even though the term lookaside buffer fell out of favor, TLB seems to have stuck, for whatever reason

[H93] “MIPS R4000 Microprocessor User’s Manual”. by Joe Heinrich. Prentice-Hall, June 1993. Available: http://cag.csail.mit.edu/raw/ . documents/R4400 Uman book Ed2.pdf A manual, one that is surprisingly readable. Or is it?

[HP06] “Computer Architecture: A Quantitative Approach” by John Hennessy and David Patterson. Morgan-Kaufmann, 2006. A great book about computer architecture. We have a particular attachment to the classic first edition

[I09] “Intel 64 and IA-32 Architectures Software Developer’s Manuals” by Intel, 2009. Available: http://www.intel.com/products/processor/manuals. In particular, pay attention to “Volume 3A: System Programming Guide” Part 1 and “Volume 3B: System Programming Guide Part 2”.

[PS81] “RISC-I: A Reduced Instruction Set VLSI Computer” by D.A. Patterson and C.H. Sequin. ISCA ’81, Minneapolis, May 1981. The paper that introduced the term RISC, and started the avalanche of research into simplifying computer chips for performance.

[SB92] “CPU Performance Evaluation and Execution Time Prediction Using Narrow Spectrum Benchmarking” by Rafael H. Saavedra-Barrera. EECS Department, University of California, Berkeley. Technical Report No. UCB/CSD-92-684, February 1992.. A great dissertation about how to predict execution time of applications by breaking them down into constituent pieces and knowing the cost of each piece. Probably the most interesting part that comes out of this work is the tool to measure details of the cache hierarchy (described in Chapter 5). Make sure to check out the wonderful diagrams therein.

[W03] “A Survey on the Interaction Between Caching, Translation and Protection” by Adam Wiggins. University of New South Wales TR UNSW-CSE-TR-0321, August, 2003. An excellent survey of how TLBs interact with other parts of the CPU pipeline, namely hardware caches.

[WG00] “The SPARC Architecture Manual: Version 9” by David L. Weaver and Tom Germond. SPARC International, San Jose, California, September 2000. Available: www.sparc.org/ standards/SPARCV9.pdf. Another manual. I bet you were hoping for a more fun citation to end this chapter.