Фрэнк Солтис - Основы AS/400

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

Рисунок 8.4. Этапы трансляции адреса (режим активных тегов)

На рисунке 8.4 представлены этапы трансляции адреса в режиме активных тегов. Старшие 40 разрядов эффективного адреса называются идентификатором эффективного сегмента (ESID), а младшие 24 — смещением. Как показано на рисунке, смещение подразделяется на страничное и байтовое. Каждое из полей смещения имеет длину 12 разрядов. Страничное смещение задает страницу сегмента, а байтовое — байт страницы.

Первый шаг процесса трансляции — создание идентификатора виртуального сегмента (VSID). В режиме активных тегов это просто ESID. Виртуальный адрес, как и эффективный, имеет размер 64 разряда и включает 24-разрядное смещение. VSID и страничное смещение виртуального адреса составляют номер виртуальной страницы (VPN). На рисунке 8.4 видно, что VPN имеет длину 52 разряда. VPN используется для определения номера реальной страницы (RPN) по таблице страниц. RPN — это номер страничного фрейма в памяти, а не номер страницы на диске. Байтовое смещение всегда передается от эффективного адреса виртуальному и затем реальному без изменений. Оно задает байт на 4-килобайтной странице и никогда не участвует в процессе трансляции.

Для сравнения на рисунке 8.5 показаны этапы трансляции адреса в режиме неактивных тегов. Данный механизм трансляции не используется в AS/400, но все же полезно представлять себе как сходство, так и различие трансляции адреса в AS/400 и в таких ОС, как AIX. В данном случае, ESID используется для обращения к таблице сегментов, из которой извлекается VSID. Обращение к таблице страниц, которое мы скоро рассмотрим, в режимах активных и неактивных тегов выполняется одинаково. Следует также отметить размер полей адреса. В режиме неактивных тегов порции смещения (поля страницы и байта) эффективного и виртуального адреса равны 28 разрядам, в режиме активных тегов — 24. 28 разрядов были выбраны в соответствии с числом разрядов смещения в прежней 32-разрядной архитектуре Power и по-прежнему используются на некоторых процессорах RS/6000.

Рисунок 8.5. Этапы трансляции адреса (режим неактивных тегов)

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

В AS/400 трансляция виртуального адреса в реальный, использующая таблицу страниц, более важна, чем трансляция сегментов, так как большинство эффективных адресов обходят таблицу сегментов.

Таблица страниц — структура данных в памяти, содержащая RPN. При построении таблицы страниц в большинстве отличных от AS/400 реализаций виртуальной памяти, каждой странице виртуальной памяти соответствует одна запись в таблице. Номер виртуальной страницы — VPN — используется как индекс в таблице страниц для выбора одной из записей. Выбранная запись содержит номер реальной страницы — RPN, который затем становится частью реального адреса.

Описанная структура страничных таблиц используется многими системами, например System/370. Предположим, что у нас есть компьютер с 32-разрядным виртуальным адресом и 4-килобайтной страницей. Размер VPN для этого адреса — 20 разрядов. Если далее предположить, что одна запись страничной таблицы занимает 4 байта, то размер всей таблицы составит 4 МБ. Такая таблица очень велика, но все-таки приемлема для систем с большими объемами памяти. Однако, если виртуальный адрес больше 32 разрядов (48 или 64), то размер обычной страничной таблицы становится неприемлемо большим.

System/38 была первой из массовых вычислительных систем, где использовалась инвертированная таблица страниц. В такой таблице содержится по одной записи на каждую реальную страницу (страничный фрейм) памяти, а не на каждую виртуальную страницу памяти, расположенную на диске. Общий размер такой инвертированной таблицы прямо зависит от размера памяти. Чем больше память, тем больше размер таблицы, но доля памяти, занятая таблицей остается неизменной.

Самое сложное в инвертированной таблице страниц — нахождение нужной записи. Теперь нельзя напрямую использовать VPN как индекс в таблице, так как нет однозначного соответствия между VPN и записью таблицы. Необходим какой-то иной способ. Прием, используемый в AS/400, заключается в применении к VNP для определения записи страничной таблицы хеш-функции.

Хеширование всегда было концепцией, трудной для объяснения. Хеш-функция AS/ 400 сначала выполняет над несколькими старшими и младшими разрядами VPN операцию «Исключающее или». Затем между полученным значением и разрядами маски из специального регистра, содержащего размер страничной таблицы, выполняется операция «И». Наконец, для результата и реального адреса страничной таблицы выполняется операция «Или», которая и дает 52-разрядный реальный адрес в страничной таблице. Очень мало людей по-настоящему понимает, зачем и как работает хеш-функция. Тем не менее, желающих проникнуть в ее секреты всегда было достаточно.

Несколько лет назад, раздумывая нет тем, как объяснить хеширование раз-вв" работчикам System/38, я бродил по магазину Sears в Рочестере. Чуть раньше ш я отправил заказ в отдел продаж по каталогу и хотел узнать, был ли он полу-

чен. Когда я поинтересовался об этом в столе заказов, у меня спросили две последние цифры моего телефона. Я назвал: «83». На стене за спиной служа-

щего располагалось сто отделений, пронумерованных от 00 до 99. Работник магазина вытащил стопку бумаги из отделения 83 и начал искать мой заказ. После того как заказ был найден, мне сказали, что выписанный товар еще не

получен. Я немедленно выпалил в ответ: «У Вас только что произошла страничная ошибка». Сотрудник Sears ничего не понял и был несколько удивлен. Зато я внезапно осознал, как объяснить хеширование.

Sears использовал хеш-функцию для отслеживания полученных заказов, точно так же, как мы отслеживаем, какие страницы находятся в памяти. Было решено уникально идентифицировать клиента по имени и номеру телефона. Вместо того, чтобы хранить запись о каждом клиенте, который мог бы сделать заказ, компания решила хранить записи только о тех клиентах, которые сделали заказ, но еще не забрали его. Для ускорения поиска сотрудник выбрал только часть полной идентификации клиента — две последние цифры телефонного номера. Таким образом, все сделанные заказы были отсортированы по этим двум последним цифрам. Чтобы получить информацию о выполнении заказа, необходимо было в поисках имени заказчика просмотреть лишь одно из 100 отделений.