Файл: Левковиц, Д. Структуры информационных массивов оперативных систем.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 19.10.2024

Просмотров: 77

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

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

ностью с о к р а щ а т ь длину цепочки исключением

записей

из подфайла .

 

Фактическое расположение записей в памяти

с про­

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

писи,

относящиеся к С ч е т # 1 ,

д о л ж н ы быть включены

в общую

логическую запись. В ней,

следовательно, дол­

ж н ы быть

у к а з а н ы записи цепочки Счет/Поручитель, две

записи

из

цепочки С ч е т / Н а к л а д н а я

и соответственно две

и три

записи, входящие в

цепочки

Н а к л а д и а я / С т р а с х .

П р и этом

возникает вопрос

о

логическом соотношении

м е ж д у записями типа Инвоп и Счет, связанных в этом

примере через две записи

типа Страсх. Метод, принятый

в системе General Electric

( L D S ) ,

позволяет обойти ре­

шение этих вопросов. Принято, что

к а ж д а я запись

(пря­

моугольник на рис. 3-2) является одновременно и

собст­

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

Однако последовательное размещение в памяти иерар­ хически связанных записей представляет некоторые пре­

имущества

при

обработке. Н а и б о л е е в а ж н о е

из них —

возможность

обрабатывать все записи в цепочке без

многократных

обращений к

процедурам

произвольного

доступа

или

сложной страничной организации .

Н а рис.

3-3

представлен

формат записи

(структура

данных)

с

у п р а в л я ю щ и м и

признаками,

необходимыми

д л я установления иерархических отношений в подфайле записей. Ф о р м а т допускает последовательное размеще­ ние в памяти всех иерархически взаимосвязанных запи-

54

сей подфайла . При этом предполагается, что нужные подфайлы были ранее включены в общую логическую запись. Д л я того чтобы уточнить вводимое представле­ ние, принята следующая терминология. Точка на рис. 3-1 или прямоугольник на рис. 3-2 называется Элементом

 

Имя Обобщения/Значение

Старшая

Индекс

записи

*Имя по'дзаписи/ЛС ccj

подэапись

•Имя подзаписи/ДС ßj

 

 

 

m

 

/ / / / / / / / / / / / / / / /

а.

Имя

Элемента/Значение

 

Индекс

элемента

*Имя подзаписи/ДСссг

Младшая

 

•

подвапись

•Имя подзаписц/ДС yz

 

 

Имя

Элемента/Значение

 

 

.4-4.4-4.

 

Имя

Элемента/Значение

Имя Элемента/Значение

•-/-4-4-4-4-i. 4-L 4-4-4-/—4. 4-4 -4

Имя Элемента/Значение

-4 J-4-4L/-4\ 4-4

^-4-4-4-Z -4- .ч f

Ядpec связи

остаточной

записи

Рис. 3-3. Иерархические управляющие признаки записи обобщенного формата.

(вообще говоря, о б о б щ а ю щ у ю запись можно считать Элементом по отношению к самой себе) . Все Элементы общего подфайла, как это указано прямоугольником на рис. 3-1 или цепочкой на рис. 3-2, собраны в подзапись.

Таким

образом, со всеми Элементами заданной подзапи-

си может быть связан общий формат . Логическая з а п и с ь ,

состоит

из последовательности подзаписей, возглавляе ­

мой подзаписью, содержащей единственную

Обобщаю ­

щую. Д а н н ы е логической записи в пределах

З У П Д раз ­

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

55

произвольно как но отношению к породившей его под-

записи, так и к предыдущей остаточной.

С т а р ш а я

обоб­

щ а ю щ а я 'Подзапиеь содержит оглавление

записей,

ука­

зывающее

с помощью

адресов связи

начало

цепочки

подзаписи, ведущей к О б о б щ а ю щ е й .

Этот

адрес

пред­

ставляет собой символ или косвенный

адрес

относитель­

но начала

логической

записи. К а ж д а я

подзапнсь

поиме­

нована, и имя это заносится в оглавление вместе с адре­ сом связи.

К а ж д а я

подзапнсь содержит последовательность эле­

ментарных

записей; при этом Элемент

идентифицируется

парой И м я

Элемента/Значение . И м я

Элемента

фактиче­

ски совпадает с именем подзаписи. Значения

позволяют

отличать один элемент от другого. Значения

Элементов

необязательно все различны, поскольку они могут при­ сваиваться независимо по мере появления в различных цепочках. Например, в терминах примера, представлен­ ного на рис. 3-2, все блоки, отмеченные как Страсх, вой­

дут

в подзапнсь Страсх,

о б р а з у я

три цепочки, две из ко­

торых связаны с записями типа

Н а к л а д н а я

и

одна —

Инвоп. По

сути дела, в смысле присвоения значений Эле­

ментам

(в

нашем случае Страсх) цепочки могут быть

в

системе

независимы.

Таким

образом, И м я

 

Элемен­

та/Значение, равное Страсх # 1 ,

присваивается

д в а ж д ы ,

поскольку

есть значения

Страсх

# 1 , связанные

соответ­

ственно

с

Н а к л а д н о й # 1

и Н а к л а д н о й # û . Оба

значе­

ния возникнут как различные Элементы внутри подзапи­ си с именем Страсх.

Согласно рис. 3-3 первая элементарная подзапнсь с начальным адресом ai содержит в индексе Элементов адрес связи у п р а в л я ю щ е й информации . Этот индекс при­

сутствует в

к а ж д о й элементарной

записи.

Он содержит

список пар

И м я Подзаписи/Адрес

связи,

причем Адрес

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

записи. Внутренние Адреса связи (типа LAyi)

на рис. 3-3

есть адреса цепочки,

у к а з ы в а ю щ и е

Элемент

той

ж е

под­

записи, к которой д о л ж е н быть присоединен

данный

Эле­

мент. Н а п р и м е р ,

в терминах

рис. 3-2 Элемент Страсх # 1

цепи Н а к л а д н а я

# 1

д о л ж е н

быть

присоединен

внутри

подзаписи к Элементу Страсх # 2 .

Внешний

Адрес

связи

56

(такой, как LAyi) на рис. 3-3 указывает либо на при­ соединение Старшей обобщающей записи к начальному Элементу или, при замыкании цепи, на заключительное присоединение Элемента к Обобщению. Индекс Адресов связи позволяет д л я всех Обобщений и Элементов эф ­

фективно

конструировать

соответствующую

иерархиче­

скую структуру.

 

 

 

 

Отметим два

случая,

когда ссылка д о л ж н а быть сде­

лана на

адрес,

который

не

может служить

относитель­

ным началом логической записи. Первый из них пред­ ставляет случай, когда ссылка д о л ж н а указывать на дру­ гую логическую запись. Например, согласно рис. 3-2, если бы запись Инвоп я в л я л а с ь полной логической за­ писью, а запись Страсх находилась внутри логической записи Счет, индекс записи, обобщающей подзапись Ин ­ воп, д о л ж е н содержать ссылку на фиктивную подзапись внутри логической записи Инвоп, которая в свою очередь

связана с

некоторым Элементом в логической записи

Счет. Этот

адрес

связи д о л ж е н

состоять

из ссылки, т. е.

абсолютного

адреса

записи

Счет #1

и

относительного

адреса данного Элемента внутри подзаписи.

_

Второй

 

тип

Абсолютного

Адреса

 

связи

относится

к у к а з а т е л я м

продолжения

(остаточной

записи) . Л ю б а я

подзапись,

логически

р а с ш и р я ю щ а я с я

за счет

присоеди­

нения остаточной записи, расположенной по произволь­

ному

адресу З У П Д ,

д о л ж н а

иметь

Абсолютный Адрес

связи

продолжения .

 

 

 

З а ш т р и х о в а н н ы е

области

(рис.

3-3) внутри каждого

Элемента и Обобщения можно рассматривать как под­

запись

с

единственным Элементом. Области эти содер­

ж а т

поля

данных и ассоциативных связей, формат кото­

рых

рассмотрен

ниже . Н а рис. 3-4

и з о б р а ж е н а

структу­

ра данных д л я примера, приведенного в табл . 3-2. При ­

нято,

что

записи

типа

Счет,

Поручитель, Н а к л а д н а я и

Страсх

(см. табл . 3-2)

включаются

в одну логическую

запись с Именем

Обобщения Счет, а запись Инвоп сама

является

полной

логической

записью. С т а р ш а я

запись

содержит

И м я Обобщения Счет и Значение #'1.

Индекс

указывает

относительное начальное положение к а ж д о й

подзаписи,

п р и н а д л е ж а щ е й цепочке с з а д а н н ы м Обобще ­

нием. Примем, что все Элементы находятся в некотором

низшем иерархическом состоянии относительно Старшей

записи, хотя

некоторая Э л е м е н т а р н а я запись может и не

быть связана

со Старшей непосредственно внутри иерар-

57

хин. П е р в а я запись типа Н а к л а д н а я

начинается по

адре­

су ai. Первы м

элементом

записи

является

запись

На ­

к л а д н а я

# 1 , и м е ю щ а я

оба типа связи. Связь

по

цепочке

содержит

имя

старшей

дл я подзаписи

(Счет) и

индекс

присоединения

к

другому

элементу той ж е

подзаписи,

а именно аг. П о

адресу аз

расположен

второй

элемент

цепочки ( Н а к л а д н а я ) ,

содержащи й

ссылку на И м я Обоб­

щения Счет и Адрес связи, указывающи й на начало ло­

гической записи, а именно

Обобщающе й Старшей запи­

си. Н а этом оканчивается

цепочка С ч е т / Н а к л а д н а я .

Поскольку запись Н а к л а д н а я т а к ж е служит Обобще ­ нием, связь с соответствующей подзаписыо, в данном случае Страсх, осуществляется внешним адресом связи.

Запись

Н а к л а д н а я

#'1 , таким

образом,

связана

с Страсх

# 1 через уь где цепочка

Н а к л а д н а я / С т р а с х

со­

здается

через связи

Н а к л а д н а я

(у%— Н а к л а д н а я )

оц,

з а м ы к а ю щ и е цепочку. Цепочка Счет/Поручитель начи­ нается в обобщающей подзаписи Счет #'1 и выражаетс я

адресами связи

Поручитель/ßi — Счет/Рг—Счет/fia —

адрес продолжения

0250 — Поручитель/0 . Согласно схе­

ме объем памяти, первоначально отведенный дл я подза­ писи Поручитель, оказался недостаточным и поэтому за­

пись Поручитель # 3 пришлось

поместить по

другому

адресу, а именно

0250. Поскольку

Поручитель

# 2

через

ß2 соединяется

с

Поручитель # 3

по цепи

Счет/Поручи­

тель, в записи

Поручитель # 2

появляется

относительный

Адрес связи Рз, по которому

записан абсолютный

адрес

продолжения 0250. Таким образом, ß 3 действует как кос­ венный адрес.

Запись Инвоп содержит лишь обобщение для Инвоп #18 и единственную ссылку на подзапись Страсх ai, представляющую косвенный адрес ссылки на элемент

Страсх по ОІОО/уг- С помощью

индекса

младшей

записи

Страсх # 2 (по уг)

цепочка Инвоп/Страсх

имеет

адрес

связи продолжения

уз, откуда

с помощью

косвенного

адреса у6 происходит возврат

к записи

Инвоп.

 

Описанная выше

структура

ф а й л а

лежит на

пересе­

чении схем, представленных на рис. 3-1 и 3-2. Заметим, что все три схемы относятся к схемам программной реа­

лизации

информационной

структуры,

представленной

в табл .

3-2, и

к а ж д а я из

них сохраняет

все

з а д а н н и г

иерархические

соотношения. Основное достоинство дан­

ной структуры

состоит в том, что при одном

обращении

с произвольным

доступом

для обработки

в оперативную

58

Смотрите также файлы