Правильная ссылка на эту страницу
http://az-design.ru/Support/HardWare/IBM/D19790315Elc046.shtml

Управление большой виртуальной памятью при помощи индексов расстановки

УДК 681.327.2

Хаудек (М.Е.Houdek)
Отделение General Systems фирмы IBM (Рочестер, шт.Миннесота)

Митчел (G.R.Mitchell)
Отделение General Systems фирмы IBM (Рочестер, шт.Миннесота)

М.Е.Houdek, G.R.Mitchell. Hash index helps manage large virtual memory, pp. 111—113.

Алгоритм расстановки (или формирования перемешанных таблиц) позволяет эффективно адресовать виртуальную память, разделенную на сегменты и блоки. Описана адресация по индексам расстановки виртуальной памяти объемом до 281 триллиона байт «Системы/38».

Наиболее серьезным конструктивным решением при разработке «Системы/38» фирмы IBM было применение формата адреса с числом бит, достаточным для обращения ко всей основной и внешней памяти без повторного использования адреса. Такой формат гораздо лучше обеспечивает целостность данных, их защиту и секретность.

Очевидно, что 16-разрядного адреса, используемого во многих компьютерных малых системах, было недостаточно. Даже 24-разрядный адрес, часто используемый в более крупных системах для доступа к памяти емкостью 16 Мбайт, не обеспечивал нужной гибкости. Поэтому в «Системе/38» используется 48-разрядный адрес, что соответствует полю виртуальных адресов размером 281 триллион (281*1012) байт — в 16 миллионов раз больше, чем в «Системе/370».

Управление виртуальной памятью

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

Кадры и страницы. 48-разрядный адрес виртуальной памяти, используемый в «Системе/38», обозначает некоторую страницу некоторого сегмента области виртуа
Рис.1. Кадры и страницы. 48-разрядный адрес виртуальной памяти, используемый в «Системе/38», обозначает некоторую страницу некоторого сегмента области виртуальной памяти. Этот адрес преобразуется в более короткий адрес основной памяти, который определяет некоторый кадр в физической основной памяти.

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

Чтобы следить за размещением информации, система управления должна осуществлять преобразования неизменных адресов виртуальной памяти, указанных в программе пользователя, в машинные адреса и наоборот. Однако при традиционных методах преобразования для работы с виртуальной памятью объемом в 281 триллион байт, предусмотренной в «Системе/38», потребовались бы просмотровые таблицы размером миллиард байтов.

Вместо этого в «Системе/38» применяется двухуровневая схема преобразования с алгоритмом, который равномерно распределяет виртуальные адреса по существенно более короткому указателю-справочнику, используемому для задания адресов основной памяти. При виртуальной адресации область памяти делится на сегменты, которые затем подразделяются на блоки размером 512 байт, называемые страницами. Когда некоторая страница располагается в основной памяти компьютера, все 512 байт составляют так называемый кадр (frame). Задача преобразования состоит по сути в том, чтобы превратить адрес страницы в адрес соответствующего кадра.

Адресация страниц и байтов

Виртуальный адрес состоит из двух частей, одна из которых идентифицирует страницу и называется адресом страницы, а другая идентифицирует байт в пределах страницы и называется идентификатором байта (рис.1). Аналогично, первая часть адреса основной памяти идентифицирует кадр и называется идентификатором кадра. Вторая часть этого адреса, идентифицирующая байт в пределах кадра, идентична идентификатору байта виртуального адреса. Поэтому преобразования идентификатора байта не требуется.

Адрес страницы, однако, необходимо преобразовать в идентификатор кадра. Это делается при помощи двух таблиц. Первая из них, указатель страниц, содержит по одному элементу на каждый кадр основной памяти (рис.2). Значение индекса этого элемента непосредственно соответствует идентификатору кадра.

Преобразующий указатель

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

Однако последовательный просмотр всего указателя страниц каждый раз, когда транслируется виртуальный адрес, потребовал бы, вероятно, слишком много времени. В связи с этим индекс указателя страниц формируется при помощи второй таблицы, таблицы индексов расстановки или перемешивания (hash index table), и так называемого генератора расстановки (hash generator).

Генератор расстановки — это фактически первый этап преобразования (рис.3) — представляет собой алгоритм, который расставляет (перемешивает) определенные биты виртуального адреса, чтобы выбрать некоторый элемент из таблицы индексов расстановки. Этот элемент служит для перехода к элементам таблицы — указателя страниц.

Указатель-справочник. При поиске каких-либо данных в памяти та часть виртуального адреса, которая представляет адрес страницы, преобразуется алгоритмо
Рис.2. Указатель-справочник. При поиске каких-либо данных в памяти та часть виртуального адреса, которая представляет адрес страницы, преобразуется алгоритмом расстановки и сравнивается с содержимым указателя адресов страниц. Индекс совпавшего элемента становится затем идентификатором кадра, а идентификатор байта остается неизменным.

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

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

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

Конец цепочки

Признак «конец цепочки» может встретиться раньше, чем будет обнаружено совпадение,— это свидетельствует о том, что данной страницы в основной памяти нет. В таком случае специальная программа обращается к каналу ввода-вывода, и переписывает страницу, соответствующую заданному виртуальному адресу, из внешней дисковой памяти в оновную память, а также обновляет указатель страниц. Канал ВВ использует полный 48-разрядный виртуальный адрес и аналогичный способ преобразования, чтобы сформировать физический адрес для соответствующего дискового накопителя.

Такой двухуровневый процесс индексации ускоряет преобразование, но лишь в случае достаточно малой длины цепочек страниц. Использование увеличенной таблицы индексов расстановки приводит к увеличению числа цепочек страниц в указателе страниц и, следовательно, к уменьшению числа элементов в цепочке. Таким образом, большая таблица индексов расстановки улучшает характеристики преобразователя, поскольку при этом приходится просматривать меньшее число элементов указателя страниц.

Равномерное распределение

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

Анализ различных способов равномерного распределения показал, что среднее число анализируемых элементов указателя страниц N зависит от отношения R размеров таблицы индексов расстановки и указателя страниц:

N = 1 + V2R.

Например, если размер таблицы индексов расстановки вдвое превышает размер указателя страниц, то среднее число проверяемых элементов составит 1,25.

Алгоритм расстановки, требуемый для равномерного распределения, зависит от того, каким образом присваиваются виртуальные адреса. В случае «Системы/38» следует учитывать, что пространство виртуальных адресов разделяется на независимые области адресов, называемые сегментами. Каждый сегмент содержит несколько страниц, поэтому адрес страницы, входящий в виртуальный адрес, разбивается на два идентификатора (рис.4), один из которых обозначает сегмент, а другой — страницу в этом сегменте.

Точное определение. При обработке виртуального адреса адрес страницы делится на две части, одна из которых определяет конкретный сегмент в области вир
Рис.4. Точное определение. При обработке виртуального адреса адрес страницы делится на две части, одна из которых определяет конкретный сегмент в области виртуальных адресов, а другая — конкретную страницу. Идентификатор байта определяет один байт в данной странице.

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

Генератор. Поскольку в «Системе/38» предусматриваются два типа сегментов, имеются и два идентификатора сегментов. Значение расстановки вырабатывается
Рис.5. Генератор. Поскольку в «Системе/38» предусматриваются два типа сегментов, имеются и два идентификатора сегментов. Значение расстановки вырабатывается при помощи схемы Исключающее ИЛИ, на вход которой поступают идентификаторы больших и малых сегментов и в обратном порядке биты идентификатора страницы.

Кроме того, «Система/38» имеет два типа сегментов — малые сегменты, размером около 65 тыс. байт, и большие сегменты, размером около 16 млн. байт. Поэтому идентификатор сегментов виртуальной памяти далее разделяется на идентификаторы больших и малых сегментов. Таким образом, для обеспечения эффективного вызова данных при такой системе виртуальной памяти требуется специальный способ преобразования получающегося неравномерного распределения виртуальных адресов в равномерное распределение элементов таблицы индексов расстановки.

Такое преобразование должен выполнять алгоритм, применяемый в генераторе расстановки. Алгоритм должен также гарантировать, что последовательные страницы и последовательные малые и большие сегменты не попадут в одно и то же место таблицы индексов расстановки. В конце концов существует относительно высокая вероятность того, что при поиске информации будет производиться обращение именно к последовательным страницам или сегментам.

Алгоритм расстановки, применяемый в «Системе/38», удовлетворяет этим требованиям (рис.5). Он определяет вход в таблицу индексов расстановки при помощи схемы Исключающее ИЛИ, на которую поступают в обратном порядке биты идентификатора страницы и младшие биты идентификаторов малых сегментов й больших сегментов.

Приспособляемость

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

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

Выходные данные:

Журнал "Электроника" том 52, No.06 (558), 1979г - пер. с англ. М.: Мир, 1979, стр.39

Electronics Vol.52 No.6 March 15, 1979 A. McGraw-Hill Publication

М.Е.Houdek, G.R.Mitchell. Hash index helps manage large virtual memory, pp. 111—113.

Раздел: МЕТОДЫ, СХЕМЫ, АППАРАТУРА

Тема:     Вычислительная техника





Дата последнего изменения:
Thursday, 21-Aug-2014 09:10:44 MSK


Постоянный адрес статьи:
http://az-design.ru/Support/HardWare/IBM/D19790315Elc046.shtml