home | login | register | DMCA | contacts | help | donate |      

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Э Ю Я


my bookshelf | genres | recommend | rating of books | rating of authors | reviews | new | форум | collections | читалки | авторам | add
fantasy
space fantasy
fantasy is horrors
heroic
prose
  military
  child
  russian
detective
  action
  child
  ironical
  historical
  political
western
adventure
adventure (child)
child's stories
love
religion
antique
Scientific literature
biography
business
home pets
animals
art
history
computers
linguistics
mathematics
religion
home_garden
sport
technique
publicism
philosophy
chemistry
close

реклама - advertisement



Хеширование

Основы AS|400

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

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

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


Трансляция адреса виртуальный—реальный | Основы AS|400 | Запись страничной таблицы