Основы AS/400

щего располагалось сто отделений, пронумерованных от 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 должен обратиться к диску и перенести запрошенную страницу в память. Необходимо также обновить таблицу страниц, чтобы отразить присутствие новой страницы в памяти. Конечно, для освобождения места под новую страницу компонент управления памятью должен удалить какую-то другую страницу.

Следующие три раздела содержат по-настоящему «острую» информацию, так что я пометил их тремя перцами.

В первом рассматривается процесс трансляции виртуального адреса в реальный и использование для этого записей таблицы страниц. Этот раздел предназначается тем читателей, которые любят «играть» с битами.