Файл: Левковиц, Д. Структуры информационных массивов оперативных систем.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.10.2024
Просмотров: 74
Скачиваний: 0
ключей. Поскольку процесс объединения или-группиров ки аналогичен традиционным библиотечным з а д а ч а м классификации и каталогизации, его можно представить себе как з а д а ч у автоматической классификации . По строенные на основе ее решения классификационные схе мы и тезаурус наравне с печатными каталогами могут быть полезны при формулировке запроса . В приложении 2 представлен достаточно эффективный алгоритм рас пределения по секторам. Алгоритм снабжен описанием использования такой классификационной иерархической системы и тезауруса в сочетании с системой поиска.
7-6. АВТОНОМНАЯ ГЕНЕРАЦИЯ ФАЙЛОВ СО СПИСКОВОЙ СТРУКТУРОЙ
В гл. '8 будут описаны |
методы |
оперативного |
обновле |
||||
ния |
файлов, |
хотя, как |
указывалось в г л . 3, |
не |
всякая |
||
система требует оперативного обновления (обычно |
в та |
||||||
ких |
системах |
данные обновления |
формируются |
в |
паке |
||
т ы ) . |
В этих |
системах, |
а т а к ж е в |
оперативно |
обновляю |
||
щихся системах обычно имеется возможность генери ровать и обновлять файл автономно, что экономически целесообразно. Интересно указать, что т а к а я процедура может быть доведена до конца без обращения к произ вольной выборке из З У П Д , поскольку она в основном состоит из сортировок. Процесс начинается со считыва ния ф а й л а записей с магнитной ленты. К а ж д а я запись имеет ключи, некоторым образом отделенные от других данных в записи. В целях дальнейшего изложения будем рассматривать в записи три различающиеся части: но мер д л я доступа, ключи и все остальные неключевые данные, включая классификаторы . В этом случае, как
показано на рис. |
7-7, файл со списковой структурой |
мо |
|
ж е т |
генерироваться серией сортировок. В верхнем левом |
||
углу |
д и а г р а м м ы |
показан входной файл, с о д е р ж а щ и й |
за |
писи формата, подобного тому, который ранее был пока зан на рис. 3-5, с тремя различающимися частями. Адрес
связи, который на рис. 3-5 присутствует |
при |
к а ж д о й |
па |
||
ре И м я ключа/Значение — единственная |
компонента |
за |
|||
писи, которая не содержится в этом входном |
файле . При |
||||
своение адреса является |
одной |
из функций |
программы . |
||
П о д к а ж д ы м символом |
ленты |
(рис. 7-7) |
перечисляются |
||
данные, содержащиеся в соответствующем поле записи. Подчеркиваемые данные являются ключами для сорти150
ровки файла . К а к видно из рисунка, входной файл пред полагается упорядоченным по номеру д л я доступа ( Н Д ) , который рассматривается как основной ключ ф а й л а в си стеме. С другой стороны, система может быть упорядо чена и по любому другому единичному ключу. В блока / каждой входной записи последовательно присваиваются
;
Присво |
|
|
|
|
Сортиров- |
N |
|
|
ение |
|
ГенерироВошив |
|
|||||
дисковых\ |
|
троен |
|
|
на по |
W |
W ^ ) |
|
адресов |
|
ключ/ДЯ/НДО |
ключ/ДЯ |
V _ é |
^ |
|||
НД* |
НД |
|
|
ключ/ДД/НД |
Ключ/ДД/НД |
|||
Ключи |
ДЙ |
|
|
|||||
Неключевые данные Ключи |
|
|
|
|
|
|
|
|
4 |
|
|
|
|
|
|
|
|
Конструирова |
|
|
|
|
|
Файл со |
||
ние справочни |
|
|
|
|
|
|||
ка ключей с |
|
|
|
|
щтавка |
списковой |
||
начальными |
|
Сорти |
|
структурой |
||||
адресами |
|
О |
ЯС и |
|
|
|
||
списков (НДС) |
|
ровка |
|
создание |
|
|
|
|
и длинами. О |
поНД |
|
ленты |
|
|
|
||
списнав(ДС). |
|
|
|
|
файла |
|
ДЯ |
|
Образование |
КЛЮЧ/ДЯІНЛ КЛЮЧ/ДЯ/НД |
|
|
|||||
всех адресов |
ЙС |
|
|
|
|
|
M |
|
связи (ДС) |
|
|
|
|
Ключи/ДС |
|||
|
|
|
|
|
||||
|
|
|
|
НД |
Неключевые данные |
|||
|
|
|
|
Ключи |
|
|
|
|
Ключ/НДС/дс |
неключевые данные |
|
|
|
||||
^Подчеркнутые данные указывают на ключ сортирооки
Рис. 7-7. Построение мультиспискового файла.
дисковые адреса, что позволяет разметить память для
адресов связи. Входные записи р а з м е щ а ю т с я |
на дорож |
|
ках диска. В конце каждой дорожки д о л ж н о |
быть |
оста |
новлено некоторое резервное пространство на тот |
слу |
|
чай, если файл д о л ж е н регулярно обновляться. Это |
про |
|
странство позволяет оперативно расширять записи без
перемещения и |
без переадресации данных |
этой записи, |
т а к как адрес |
любой заданной логической |
записи есть |
физический адрес дорожки этой записи плюс относитель ный адрес, у к а з ы в а ю щ и й положение логической записи на этой дорожке . Д л и н а записи указывается числом сим-
151
волов в таблице - оглавлении . Таким образом, нужная за пись становится доступной в результате серии последо вательных индексаций. Обычно в конце дорожки остав л я ю т 10%-ную резервную область. Кроме того, в мультисписковых системах при занесении записи стараются избегать ее расщепления на разные дорожки, за исклю чением того случая, когда запись требует более одной д о р о ж к и памяти для своего размещения . Поэтому, если
запись |
короче, чем одна д о р о ж к а , |
но ие может полно |
|
стью поместиться на оставшейся части, ее помещают |
на |
||
новой |
д о р о ж к е . Адрес логической |
записи, состоящий |
из |
номера модуля (физического номера дорожки) и отно
сительного |
адреса, на этой д и а г р а м м е мнемонически |
обо |
значается |
через Д А . После присвоения адресов на |
выхо |
де блока 1 формируется некоторая лента, упорядоченная
по Н Д и Д А . Кроме того, на этой ленте записаны |
ключи |
|
(без |
неключевых д а н н ы х ) . По данным этой ленты |
в бло |
ке 2 |
генерируются тройки ключ/адрес/номер д л я |
досту |
па, а в блоке 3 они сортируются по адресам внутри клю
ча. П о л у ч а е м а я |
лента затем входит в блок 4, где строит |
||
ся |
справочник |
ключей. |
Первый адрес, появляющийся |
в |
некоторой ключевой подпоследовательности, становит |
||
ся |
начальным |
адресом |
списка (НАС) д л я этого ключа |
в справочнике ключей. Число повторений ключа в под
последовательности |
есть |
длина |
списка ( Д С ) . |
Спра |
вочник генерируется |
как |
лента, |
с о д е р ж а щ а я |
тройки: |
к л ю ч / Н А С / Д С , упорядоченные по ключам . Эта лента по |
||||
следовательно обрабатывается одним из методов, опи
санных в гл. 4, |
д л я построения |
декодера . |
Если |
мульти |
|||
список |
с управляемой |
длиной |
ограничен |
максимальной |
|||
длиной |
списка, |
равной |
N, то первые Дозаписей внутри дан |
||||
ной |
ключевой |
подпоследовательности |
станут |
первым |
|||
списком, следующие N |
записей |
внутри |
той |
ж е |
ключевой |
||
подпоследовательности станут вторым списком, соответ:
ственные начальные адреса списков войдут |
в справоч |
||
ник, а длины списков д л я |
к а ж д о г о подсписка |
равны |
N, |
за исключением последнего |
списка, длина которого |
мо |
|
ж е т быть меньше, чем N. Если у п р а в л я ю щ и е |
параметры |
||
образуют таблицу вместо единой константы, то при про смотре этой таблицы к а ж д о м у ключу будет присвоено соответствующее значение длины списка. Если файл ор
ганизован по типу |
секторного мультисписка, то, посколь |
||
ку |
тройки |
внутри |
ключевой последовательности имеют |
при |
себе |
адрес внутри ключевого списка, производится |
|
152
п е р е д в и ж ка записей, собирающая все записи с адресами указанного сектора. Когда адрес ведет к новому секто ру, в справочнике ключей создается новый список. Д л и
на списка в этом случае может |
быть, конечно, различной |
|||
для к а ж д о г о |
секторного подсписка. |
|
||
К а ж д ы й |
адрес |
внутри некоторой ключевой |
подпо |
|
следовательности, |
следующий |
за начальным |
адресом |
|
списка, становится адресом связи и добавляется в каче
стве 'второго поля к тройке К л ю ч / Д А / Н Д |
в виде |
второй |
выходной ленты блока 4, т. е. адрес связи |
является |
адре |
сом поля предшествующих записей в выходной ленте блока 3. З а т е м эти записи сортируются по номерам для доступа в блоке 5 так, что их можно слить с начальным выходным файлом д л я формирования окончательного файла со списковой структурой. Такое соединение осу
ществляется в блоке 6, а адрес |
связи заключается в трой |
||
ку |
ключ/значение/адрес связи |
соответствующей |
записи. |
С |
помощью этого относительно |
простого процесса |
могут |
быть получены справочник ключей, файл данных со спи сковой структурой и любой из трех вариантов мультисписковой структуры.
В принципе структура инвертированного списка мо жет быть генерирована по схеме рис. 7-7, если прирав
нять длину |
списка единице. Однако модифицированная |
|||
форма |
этой |
процедуры |
более |
эффективна . |
Н а |
рис. |
7-8 показана |
схема |
конструирования файла |
для инвертированной списковой системы. Вход в эту схе
му тот ж е |
и содержит номер |
д л я доступа, |
ключи |
и не |
ключевые |
данные . В блоке / |
к а ж д о й записи |
файла |
при |
сваиваются дисковые адреса. В этом блоке можно полу
чить |
выходной |
файл со списковой структурой, поскольку |
|||||||
адрес |
связи |
в |
поле |
файла |
отсутствует. |
Следовательно, |
|||
заносимая |
на |
ленту |
запись |
содержит |
дисковые |
адреса |
|||
( Д А ) , номера |
д л я доступа |
( Н Д ) , |
ключи и |
неключевые |
|||||
данные . Наличие ключей в записи |
необязательно, потому |
||||||||
что, как было |
сказано ранее, полная расшифровка |
буле |
|||||||
вых выражений, составленных из |
ключей, |
производится |
|||||||
в справочнике ключей. Поэтому ключи потребуются в са
мой записи только тогда, когда желательно |
выполнить |
|||
некоторые другие вычисления, зависящие от |
значения |
|||
ключей, или при выводе необходимо напечатать |
значения |
|||
ключей. Дисковый адрес в файле необходимо |
присвоить |
|||
для того, чтобы программа, |
которая |
р а з м е щ а е т |
файл |
|
с выходной ленты на диске, |
могла бы |
правильно |
разме- |
|
153
стить записи на д о р о ж к а х |
и оставить неооходимую |
ре |
|
зервную зону. В качестве |
одного из способов адресации |
||
м о ж н о у к а з а т ь следующий: |
индексные номера, помещае |
||
мые перед сериями записей, |
у к а з ы в а ю т номера записей |
||
на одной и той ж е дорожке . |
При этом гарантируется, |
что |
|
вконце дорожки будет зарезервировано необходимое
свободное место. Б л о к / |
создает, кроме того, лепту с про |
|||||||
|
файл |
|
ЛЯ |
|
|
|
|
|
с инвертированной |
|
M |
|
|
|
|
|
|
списковой |
|
Ключи (необязательно) |
|
|
||||
структурой |
|
|
|
|||||
|
Неключевые данные |
|
|
|||||
|
Присвоение |
|
Генериро- |
|
X |
Сорти- |
.^—ч |
|
ной |
дисковых |
|
|
|||||
|
ваниепар*( |
)*• ровна |
- н |
/ * ® |
||||
адресов |
|
|||||||
^ФайлI |
|
ключ/ДА |
^ — з |
ключ/Дй |
4 — з |
|||
M |
(ДЙ) |
|
|
|
|
|
|
|
Ж |
|
ключ/Aft |
ключ/Дй |
|||||
ключи |
ключи |
|
|
|
|
|
|
|
Неключевые данные |
|
|
|
|
|
|
|
|
|
Построение |
|
СправочХ |
ключ Я |
|
|
||
|
справочника |
|
|
ЛЯ |
|
|
||
|
ключей |
|
ник |
) |
|
ДЙ |
|
|
|
инвертированного |
|
\ключей / |
|
ключ В |
|
|
|
|
списка |
|
|
|
|
ЛЯ |
|
|
|
|
|
|
|
|
Дй |
|
|
Рис. 7-8. |
Построение файла |
с инвертированной списковой |
струк |
|||||
|
|
|
турой. |
|
|
|
|
|
своенпымп адресами и ключами для дальнейшей обра
ботки. Так ж е , как и в случае мультисписковой |
конст |
рукции, в блоке 2 формируется лента с |
парами |
ключ/адрес. В блоке 3 эта лента сортируется по адресам внутри ключевой последовательности, в результате чего
получается размеченная |
выходная лента. И з |
этой |
ленты |
|
в блоке 4 формируется |
справочник |
ключей |
инвертиро |
|
ванного списка. Все адреса, которые |
появляются |
в дан |
||
ной ключевой подпоследовательности, табулируются, приобретая единственную ссылку на имя ключа, распо ложенную па выходе справочника ключей. Ф о р м а этой
таблицы у к а з а н а |
в выходной ленте блока 4. |
Декодер |
может быть любого |
типа из описанных в гл. 6, |
однако |
на выходе он должен адресовать список адресов пере менной длины. Вид списка показан на рис. 7-9. Н а этом
154