Хеширование
Хеширование
Хеширование всегда было концепцией, трудной для объяснения. Хеш-функция AS/ 400 сначала выполняет над несколькими старшими и младшими разрядами VPN операцию «Исключающее или». Затем между полученным значением и разрядами маски из специального регистра, содержащего размер страничной таблицы, выполняется операция «И». Наконец, для результата и реального адреса страничной таблицы выполняется операция «Или», которая и дает 52-разрядный реальный адрес в страничной таблице. Очень мало людей по-настоящему понимает, зачем и как работает хеш-функция. Тем не менее, желающих проникнуть в ее секреты всегда было достаточно.
Несколько лет назад, раздумывая нет тем, как объяснить хеширование раз-вв" работчикам System/38, я бродил по магазину Sears в Рочестере. Чуть раньше ш я отправил заказ в отдел продаж по каталогу и хотел узнать, был ли он полу-
чен. Когда я поинтересовался об этом в столе заказов, у меня спросили две последние цифры моего телефона. Я назвал: «83». На стене за спиной служа-
щего располагалось сто отделений, пронумерованных от 00 до 99. Работник магазина вытащил стопку бумаги из отделения 83 и начал искать мой заказ. После того как заказ был найден, мне сказали, что выписанный товар еще не
получен. Я немедленно выпалил в ответ: «У Вас только что произошла страничная ошибка». Сотрудник Sears ничего не понял и был несколько удивлен. Зато я внезапно осознал, как объяснить хеширование.
Sears использовал хеш-функцию для отслеживания полученных заказов, точно так же, как мы отслеживаем, какие страницы находятся в памяти. Было решено уникально идентифицировать клиента по имени и номеру телефона. Вместо того, чтобы хранить запись о каждом клиенте, который мог бы сделать заказ, компания решила хранить записи только о тех клиентах, которые сделали заказ, но еще не забрали его. Для ускорения поиска сотрудник выбрал только часть полной идентификации клиента — две последние цифры телефонного номера. Таким образом, все сделанные заказы были отсортированы по этим двум последним цифрам. Чтобы получить информацию о выполнении заказа, необходимо было в поисках имени заказчика просмотреть лишь одно из 100 отделений.
Функция, использовавшаяся Sears (выбор двух последних цифр телефонного номера), давала достаточно равномерное распределение заказов по ста отделениям, то есть для поиска в каждом из отделений требовалось примерно одинаковое количество времени. Если бы, например, Sears использовал первые две цифры телефонного номера, то некоторые отделения были бы просто забиты, а остальные — пусты (почти в каждой местности большинство телефонов начинается одинаково), так что выбор первых двух цифр дал бы плохое распределение. Аналогично, комбинация операций, используемых для создания хеш-кода в AS/400, гарантирует равномерное распределение по «отделениям» таблицы страниц.
В AS/400 эквивалент отделения Sears — группа записей страничной таблицы (PTEG). Каждая PTEG содержит восемь записей таблицы (PTE). Алгоритм хеширования определяет одну из таких PTEG. Затем, необходимо просмотреть восемь записей группы, чтобы найти VPN, совпадающий с VPN транслируемого виртуального адреса. Данный поиск необходим, так как на одну и ту же PTEG отображается много виртуальных адресов. Аналогичная ситуация в Sears — одни и те же две цифры могут быть последними в телефонных номерах нескольких клиентов. Номер отделения говорит лишь о том, что все заказы в данном отделении принадлежат людям, телефонные номера которых заканчиваются на две эти цифры. Для того чтобы найти заказ конкретного клиента, необходимо просмотреть все заказы в отделении.
Число сделанных, но не полученных клиентами заказов может изменяться в течение дня, и Sears пришлось это учесть. Они использовали фиксированное число отделений с переменным числом записей в каждом. AS/400 тоже использует фиксированное число отделений, но как мы только что видели, число записей в отделении также фиксировано. Данный VPN может быть, а может и не быть найден в одном из восьми PTE. Если число записей не умещается в PTEG, то используется вторичная таблица страниц, которая содержит переменное число записей.
В большинстве реализаций AS/400 количество PTEG равно, как минимум, половине общего количества реальных страниц памяти. Учитывая, что в каждой PTEG 8 записей, таблица данного размера способна отображать в четыре раза больше страниц, чем может поместиться в память. Другими словами, среднее число используемых PTE на PTEG равно лишь двум. Это среднее значение подразумевает, что функция хеширования обеспечивает равномерное распределение по всем PTEG. Впрочем, могут возникнуть и ситуации, когда на одну или несколько PTEG будет приходиться более восьми записей. В таких случаях, дополнительные записи хранятся во вторичной таблице страниц. Представьте себе, что одно из отделений Sears слишком переполнено, и все заказы в нем не помещаются. Тогда некоторые из заказов необходимо хранить не в отделении, а где-то еще. Это «где-то еще» и есть эквивалент вторичной таблицы страниц.
В AS/400 если PTE не найдена ни в первичной, ни во вторичной таблице страниц, значит в памяти ее нет, и мы имеем дело со страничной ошибкой. Компонент управления памятью SLIC должен обратиться к диску и перенести запрошенную страницу в память. Необходимо также обновить таблицу страниц, чтобы отразить присутствие новой страницы в памяти. Конечно, для освобождения места под новую страницу компонент управления памятью должен удалить какую-то другую страницу.
Следующие три раздела содержат по-настоящему «острую» информацию, так что я пометил их тремя перцами.
В первом рассматривается процесс трансляции виртуального адреса в реальный и использование для этого записей таблицы страниц. Этот раздел предназначается тем читателей, которые любят «играть» с битами.
Следующий раздел описывает, как SLIC или транслятор могут управлять доступом к памяти каждой страницы. Такое управление требуется многоканальным RISC-процессорам с многоуровневой памятью, выполняющим операции с памятью не в том порядке, в какой они следуют в потоке команд. В архитектуре PowerPC имеется четыре бита управления режимами, которые могут использоваться программами, и я кратко опишу их, несмотря на то, что тема может показаться очень сложной.
Наконец, третий раздел касается защиты доступа к странице. Каждая страница может рассматриваться как страница чтения/записи, страница только для чтения или недоступная страница, в зависимости от текущего состояния процессора и ключей защиты в таблице сегментов и страничной таблице. Это тема также крайне сложна.
Итак, если Вам хочется чего-то более «острого», чем предыдущие несколько разделов. то попробуйте один из следующих трех или их все.