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

Он т а к ж е содержит идентификатор

запроса

ID,

дей­

ствие, условие, функции обработки, выходное

устрой­

ство и выходной формат. Мультиобрабатывающая

Ис­

полнительная

Программа

присваивает

к а ж д о м у

запросу

Область

Управления

Запросом

в реальном

масштабе

времени. В пределах этой области

р а з м е щ а ю т с я

пара­

метры запроса

и списковые адреса.

В

оперативных

системах

часто

желательно

иметь

хотя

бы

минимальную

возможность

вести диалог,

в х о ­

де которого Исполнительная

Программа

передает

через

программы ввода-вывода Т е р м и н а л у

пользователя от

Декодирующего

Справочника

допоисковую

статистику.

К а к

выше указывалось,

некоторые

формы

организации

чественной

допоисковой

статистики.

Следовательно,

если система

может вести

такой диалог,

некоторые ви­

тистики, продолжать ли

поиск в файле, модифицировать

ли запрос

или закончить

его. По

получении ответа

Ис­

полнительная

Программа

Поиска

может принять

соот­

со

стратегией просмотра ф а й л а

выполняет с

З У П Д

операцию произвольного чтения (или занесение)

записи,

после чего передает управление

системе поиска

файла

со

специфической привязкой к

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

QEA.

системы

поиска файла

от

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

Области

Управления

Запросом

QEA

в о з в р а щ а ю т с я

через

Испол­

нительную

Программу

Поиска к программе

вывода, где

они временно помещаются

в З У П Д с высокой скоростью

точный

файл

(Fe на рис. 1-3).

Программы

Помимо

Оперативной

Исполнительной

(блок

1.2 на

рис. 1-3)

система состоит из пяти

основных

являются

(1)

Интерпретатор Запроса,

(2)

Исполнитель­

ная

Программа

Поиска,

(3)

Декодирующий

Справоч­

ник

Ключей,

(4)

Подсистема

Поиска

файла

и (5)

Программа

В-В. В

оставшейся

части

книги

рассматри ­

ваются в

основном

Декодирующий

Справочник

Ключей

и Подсистема

Поиска

Файла

как

имеющие

непосред­

ственное

отношение

к

методам

организации

файла .

работ

(Multitask),

поэтому

ее

работа т а к ж е

будет

вкратце рассмотрена.

В целом оперативный поиск файла можно

рассмат­

ривать как двухступенчатый процесс. Первый

ш а г

сос­

тоит

в трансляции

ключей

с

помощью

Справочника

файла. Н а рис. 5-2 представлена

классификационная

диаг­

рамма

существующих методов

д л я выполнения

этих

двух

функций. В левой части

д и а г р а м м ы изображено

Декодирующего

Справочника

Ключей. Методы

эти

раз­

биваются на два класса, одни из них

относятся к

т а к

называемым методам

рандомизированного,

или

смешан­

ного, кодирования, другие выполняют

декодирование

согласно

дереву

или

справочной

таблице.

Рандомизиро ­

ванный

метод

имеет

несколько вариантов,

которые

функциональные

отличия. Первое из них заключается

в декодировании

Ключей

Постоянной

и

Переменной

длины. Н а естественном

языке полный

ключ

обычно

Первый из

них

состоит

ь выборке

из

ключа

фиксирован-

Декодирование

Поиск сайла

Управление

ключей по справочнику

— длиной

списка

Рандомизированный] Декодирование

Частичная

процесс

согласно

инверсия

декодирования

дереву

Инвертированны

Мультисписок

список

^/У/і

Разбцени.8

•'//,{ по сектора-м

КЛЮЧ

Ключ

{риксированнои

переменной

длины

длины

Представ­

Рандомизи­

Полное

Однозначная

ленный

значение

выборка

выборкой

рованный

ключа

Рис. 5-2. Двухступенчатый процесс выборки.

ыого набора символов или битов. Частным случаем та­

кого

преобразования,

используемого

во

многих

систе­

мах,

является

простое

усечение

ключа

до

заданного

числа символов. При втором способе

ключ

подвергается

некоторой

рандомизированной

обработке,

переводящей

его

в

область,

представляемую

фиксированным

числом

битов.

При

использовании

ключей , переменной

длины

т а к ж е

существуют д в а

подхода.

При

первом

из них

используется полное

значение

ключа.

Другой

состоит

у в том,

чтобы

найти

для

каждого

ключа

однозначную

вого

слова ту минимальную

часть, которая

необходима

д л я

того,

чтобы отличить его от всех

других

ключей си­

стемы. В

терминах объема

памяти

последний способ

Может окаааться фактически таким

же

экономичным,

как метод

ключей

фиксированной

длины,

обеспечивая

в то ж е время совершенно однозначное

декодирование.

Однако, как мы увидим ниже, метод

этот

достаточно

сложен как дл я построения декодирующего

дерева, так

и для его

обновления и,

возможно,

обладает какими-

либо другими нежелательными свойствами.

Цель создания

методов

классификации состоит в том,

чтобы на

к а ж д о м

уровне

предоставить

проектировщику

личий в

свойствах декодеров.

Эти свойства будут рас­

смотрены

в гл. 6. Здесь ж е в

связи с описанием дерева

зированный подход предъявляет

меньшие

требования

к З У П Д

(иногда вовсе никаких), чем дерево. С другой

стороны,

дерево

обладает сканирующим

свойством

в области

ключа,

необходимым

при выполнении опера­

дами в большинстве случаев сопоставимы.

На втором уровне

метод дерева ветвится на вариан-'

ты работы с ключами

фиксированной и переменной дли­

ны; издержки следует

отнести исключительно за счет

вызвать при декодировании неоднозначность,

требую­

щую последующего просмотра полного значения

ключа

либо с помощью

другого субсправочника

(что сводится

к расходованию

дополнительной

п а м я т и ) ,

либо

за счет

времени поиска

в файле записей

(что снижает

эффек­

тивность) .

нию программирования

и выдвигает дополнительные

требования к

памяти

З У П Д .

Б о л ь ш а я

часть

про­

ектировщиков

предпочитает схему

с

ключами фиксиро­

ванной длины

из-за ее

простоты

и

еще

потому,

что

фективности

не

существенны.

Н а третьем

уровне

принятия решения

в

варианте

с ключами

переменной

длины возникает

з а д а ч а

выбора

памяти, но

сложней

дл я

программирования .

Кроме

того, если

необходим

поиск

в окрестности

значения

мощью

усечения

такую возможность

предоставляет,

в то в р е м я как любые

другие

методы

выборки

или

рандомизация ключа ее не содержат .

Второй ша г оперативного процесса

поиска,

как это

указано в правой части рис. 5-2, состоит

в поиске

файла.

В а ж н е й ш е й характеристикой организации файла для

оперативного

поиска

является

процесс,

описанный

в гл. 1 и 3

как

логическое разбиение.

Пусть

каждая

запись

ф а й л а

записана

в З У П Д

один

раз, и

при

этом

бого

из ее ключей. Одновременно мы хотели

бы

полу­

чить

доступ ко всем другим записям, с о д е р ж

а щ и м

этот

ванные

списковыми

структурами

[Л. 7]. Эти методы опи­

саны

в

литературе

как

последовательные списки

(threaded

list [Л. 8]), узловые

списки [Л. 9] и

последова­

тельные

мультисписки

(Multilist [Л. 10]). С

появлением

З У П Д

дл я выполнения

загрузки

и поиска

списковых

дов. Н а и б о л е е

общей среди этих структур является по­

следовательный

мультисписок

или мультисписковая сис­

тема Prywes и Gray; эти методы

мы будем в дальнейшем

лок.

Последовательный список характеризует

каждый

ключ

единственным

адресом З У П Д ,

полученным

на вы­

ходе

Декодирующего

Справочника

Ключей; этим адре­