(MMU). Передача управления операционной системе происходит только тогда, когда страница отсутствует в памяти.

В прошлом это допущение было справедливо. Однако многие современные RISC-компьютеры, включая машины SPARC, MIPS, Alpha и HP PA, выполняют почти все страничное управление программно. На этих машинах записи TLB явно загружаются операционной системой. Когда поиск в ассоциативной памяти заканчивается неудачей (промах), диспетчер памяти, вместо того чтобы переключаться на таблицу страниц для поиска и выбора необходимой страницы, формирует ошибку TLB и передает проблему в руки операционной системы. Система должна найти страницу, удалить запись из буфера, ввести новую запись и перезапустить прерванную инструкцию. И конечно, все это должно быть сделано при помощи небольшого числа команд, поскольку промахи в буфере быстрого преобразования адреса случаются намного чаще, чем ошибки из-за отсутствия страниц.

Достаточно удивительно то, что если буфер имеет небольшой размер (скажем, 64 записи) с целью минимизации промахов, программное управление буфером, оказывается, является приемлемо результативным. Главная выгода здесь заключается в намного более простом устройстве диспетчера памяти, что освобождает достаточное количество пространства в микросхеме процессора для кэша и других устройств, способных повысить производительность. Программное управление буфером быстрого преобразования адреса обсуждается в [84].

Для подъема производительности на компьютерах, программно управляющих TLB, разрабатывались различные стратегии поведения. Один подход состоит в попытке уменьшить как частоту неудачного поиска в буфере, так и его стоимость, когда он все-таки случается [4]. Чтобы уменьшить вероятность неудачного поиска в TLB, иногда операционная система может интуитивно вычислить, какие страницы, возможно, будут использоваться следующими, и предварительно загрузить записи для них в буфер. Например, когда клиентский процесс посылает сообщение серверному процессу на той же самой машине, очень вероятно, что сервер вскоре должен будет начать работу. Зная это, система может также проверить, где находятся страницы кода сервера, данных и стека, пока прерывание обрабатывается, чтобы осуществить вызов send, и преобразовать их адреса из виртуальных в физические до того, как они смогут стать причиной ошибки TLB-буфера.

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

4.3.4. Инвертированные таблицы страниц

Традиционные таблицы страниц, тип которых мы описывали до сих пор, требуют по одной записи на каждую виртуальную страницу, так как они индексируются по номеру этой страницы. Если адресное пространство состоит из 2 байт с размером страницы 4096 байт, тогда в таблице страниц должно быть больше миллиона записей. Отсюда, таблица страниц будет занимать минимум 4 Мбайт. В достаточно больших системах это, вероятно, осуществимо.

Однако, поскольку 64-разрядные компьютеры встречаются все чаще, ситуация радикально меняется. Если теперь адресное пространство увеличилось до 2 байт с размером страницы 4 Кбайт, нам требуется таблица страниц с 2 записями. Если каждая запись равна 8 байтам, таблица займет больше 30 Тбайт. Выделение 30 Тбайт только для таблицы страниц нереально сейчас и не будет реальным когда-либо в будущем. Следовательно, для 64-разрядного страничного виртуального пространства необходимо другое рещение.

Одним из таких решений является инвертированная таблица страниц. В этой модели таблица содержит по одной записи на страничный блок в реальной памяти, а не на страницу в виртуальном адресном пространстве. Например, при 64-разрядных виртуальных адресах, размере страниц 4 Кбайт и 256 Мбайт оперативной памяти инвертированная таблица страниц потребует всего лишь 65 536 записей. Каждая запись отслеживает, что (процесс, виртуальная страница) расположено в данном страничном блоке.

Хотя инвертированные таблицы страниц экономят значительное количество места, по крайней мере, когда виртуальное адресное пространство намного превышает физическую память, они имеют серьезный недостаток: перевод виртуального адреса в физический значительно усложняется. Когда процесс п обращается к виртуальной странице р, аппаратное обеспечение не может больше найти физическую страницу, отталкиваясь от номера р как от индекса в таблице страниц. Вместо этого оно должно производить поиск записи (и, р) во всей инвертированной таблице страниц. Более того, этот поиск должен выполняться при каждом обращении к памяти, а не только при страничном прерывании. Операция поиска в таблице размером 64 К при каждой ссылке к памяти вовсе не увеличит скорость вашей машины.

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

Инвертированные таблицы страниц в настоящее время используются на некоторых рабочих станциях компаний IBM и Hewlett-Packard и будут встречаться все чаще, так как 64-разрядные мащины получают все более щирокое распространение.

Некоторые другие методы управления виртуальной памятью большого размера можно найти в [45, 78, 79].

4.4. Алгоритмы замещения страниц

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

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

4.4.1. Оптимальное замещение страниц

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

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

С этим алгоритмом связана только одна проблема: он невыполним. В момент страничного прерывания операционная система не имеет возможности узнать.