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

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

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

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

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

Добавлен: 19.10.2024

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

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

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

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

няется.

Тогда любое логическое в ы р а ж е н и е

из ключей

может

быть непосредственно декодировано справочником

ключей.

 

Инвертированные списки представляют собой записи

переменной длины, которые в целях удобства

логических

обращений д о л ж н ы быть упорядочены в монотонную по­

следовательность. Переменная

длина списков записей,

которая может быть различной,

а т а к ж е необходимость

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

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

описываемую

ниже частично

инвертированную систему.

Н а рис. 7-2

по

запросу

WY

находится

пересечение ин­

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

списков

по

адресу Ад.

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

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

получить

до начала выборки из

файла, равна единице

и число

произвольных обращений

к файлу т а к ж е

равно

единице.

 

 

 

 

Н а рис. 7-3

иллюстрируется эффективный способ

про­

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

логической обработки инвертированного

списка для систем с большим разбросом длин списков. Пусть необходимо логически переработать списки клю­

чей переменной длины

А,

В и С. Эти

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

списки записаны

в З У П Д

и состоят из

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

сти адресов всех

записей

файла, с о д е р ж а щ и х

ключи А,

В и С соответственно. К а ж д ы й список можно

рассматри­

вать как логическую запись, по длине

превосходящую

несколько физических

записей.

 

 

136

Ц е н т р а л ь н ый процессор имеет шесть областей памяти

(буферов) : две входные — пары

Вх. 1, Вх.

2 и Вх. 3, Вх.4

и выходную пару Вых. 1, Вых.

2.

 

На рис. 7-6 процессор изображен в виде прямоуголь­

ника, очерченного сплошной

линией.

Все переключе-

Рис. 7-3. Система с буферной памятью и логиче­ ская обработка инвертированных списков.

ния выполняются программно в процессоре, ломаные

линии символизируют передачу данных из

диска

в опе­

ративную память

или в обратном направлении.

Физи­

ческие записи от

двух

входных файлов

дублируются

во

входные буфера и

последовательно обрабатывают ­

ся

процедурами

логической обработки,

после

чего

137

р е з у л ь т и р у ю щ ие адреса,

продублированные

в

буфере,

передаются в один из двух

выходных

файлов

(FL

F2)

на

диске.

Последовательность

обработки

запроса

f(A,

В,

С)

показана

на

рисунке треугольниками . В н а ч а л е буфе­

ра

Вх. J

и

Вх.2 з а г р у ж а ю т с я

двумя записями

из

списка

А,

а Вх.

3

и

Вх.4

— из В (1).

Во время

загрузки

Вх.2

и

Вх.

4, Вх.

1

и Вх. 3

обрабатываются,

а

результаты пере­

даются

 

в

выходной

буфер

Вых.

1

и,

 

если необходимо,

в Вых.

2.

Н а п р и м е р ,

если

А

и

В

пересекаются,

то

для

Вх. 1 и Вх. 3 достаточно иметь буферную память

Вых. 1,

но

если

 

А

и

В

сливаются,

то

может

потребоваться

бу­

ф е р н а я

 

память Вых.

2. П р о г р а м м а

последовательно счи­

тывает записи из списков А и В и ведет перепись из вы­

ходных буферов Вых. 1 и Вых. 2 в файл

З У П Д

F (1).

После

того

как

А и

(или)

В

полностью

обработаны,

файл Fi переключается и становится входом для

буферов

Вх.

1,

Вх.

2

(2).

Список С

становится

вторым

входом

в Вх.

3,

Вх.4

(2),

а выходные

буфера Вых.

1,

Вых.

2

пере­

ключаются

на

файл

Fz(2).

Эта

процедура

может

быть

повторена д л я произвольного числа ключей любой про­

извольной длины . Главное

преимущество

инвертирован­

ного списка - по сравнению

с мультнсписковой

организа­

цией состоит в значительно

более эффективном

выполне­

нии процедур пересечения

или слияния

списков. При

выборке

списка

записей

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

обращение для

к а ж д о й записи,

входящей

в список,

заменяется

опера­

цией над

компактным,

упорядоченным

списком.

 

Таким

образом, из

справочника

передается в

точно­

сти столько адресов файла, сколько соответствует полно­

му булеву в ы р а ж е н и ю д л я ключей;

но при этом

д л я про­

верки условий

на

классификаторы

необходим произволь­

ный доступ

к

к а ж д о й записи. Более того, число

адресов,

полученных

при

обработке инвертированного

списка,

представляет собой более точную статистику поиска, чем

та,

которая может быть

сообщена дальнему

терминалу

до

н а ч а л а фактического

поиска в файле . Н а

основе этой

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

138

7-3. МУЛЬТИСПИСКОВАЯ ОРГАНИЗАЦИЯ С УПРАВЛЯЕМОЙ ДЛИНОЙ СПИСКА

Одним из недостатков системы последовательных спи­ сков является низкая скорость отклика в тех ситуациях, когда пересечения в списках редки, а поиск по списку

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

Н а п р и м е р ,

при

поиске

по

списку,

из

2 000

записей

с

1%-ным пересечением общее

время

по­

иска

д л я

20

записей составляет

200 сек

(при среднем

времени

обращения к З У П Д

1О0 млсек),

в то

время

как

время доступа к 20 записям в системе с инвертирован­

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

пересече­

ние

списков

2 сек.

Насколько критична разница м е ж д у

200

сек

и

2

сек

(плюс пересечения списков)

зависит от

выходных

устройств

и случайного распределения

пересе­

чений в списке. П и ш у щ а я

машинка со скоростью

печати

10—15

символов

в

секунду

при необходимости

печатать

к а ж д у ю

запись

из

более чем 150 символов

с

приблизи­

тельно равномерным распределением записей по списку печатала бы непрерывно. Если записи собраны в конце

списка, при

печати возникнет н а ч а л ь н а я

з а д е р ж к а при­

близительно

в 3 мин. Операции с Э Л Т

могут оказаться

неустойчивыми, поскольку интересующая нас запись мо­

жет

высвечиваться

приблизительно

0,5

мин, в

течение

которых поиск по списку продолжается . Однако

другие

выбранные

записи,

сбрасываемые

через

несколько се­

кунд

н а ж а т и е м

кнопки,

могут не иметь

достаточно

боль­

ших

перекрывающихся

интервалов

времени

на

 

поиск.

Это

выразится

в отсутствии отклика

на

н а ж а т и е

кнопки,

причем время

о ж и д а н и я может варьироваться

от

нуля

до десятых

долей

секунд. Т а к а я характеристика

отклика

процессора

могла

бы вызвать з а д е р ж к и

в

работе

А Ц П У

(скорость печати 100—1 200 строк

в минуту), если записи

не длинные. Отсюда следует, что

периферийные

устрой­

ства

и условия эксплуатации системы могут свести на

нет

преимущества, представляемые организацией

файла

или

З У П Д . В таком случае проектировщику следует ру­

ководствоваться скорее экономическими критериями, чем функциональными.

Мультисписковую организацию можно довольно лег­ ко модифицировать, используя преимущества модульной структуры З У П Д . Н а схеме рис. 7-4 длина списка мультисписковой системы ограничивается з а р а н е е фиксиро­ ванным числом, которое в рассматриваемом случае рав­ но четырем. Когда длина списка превосходит четыре,

139

отк р ы ва ется новый список, начальный адрес которого помещается в список таких адресов на выходе справоч­ ника ключей для соответствующего ключа, точнее (см. рис. 7-4), используется адресное обозначение, указываю­ щее, в котором из четырех секторов начинается список. Например, список W из семи записей разбивается на список длиной в четыре и список длиной в три записи. Первый начинается в нулевом секторе, шестая запись

W

X

Y

z

Д-1.3/3

яаэм

as/*

Я17M

я из/г

 

яг.5/г

 

 

 

Сектор О

 

 

 

Макси­

 

 

 

 

мальная

 

 

 

 

длина

списка

 

 

 

равна

4

 

Рис 7-4. Мультисписковая организация файла с управ­

ляемыми

длинами списков.

 

 

 

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

как

А0.6;

второй список

начинается

в 1-м секторе записью

AI.9.

Схематически

на

рис. 7-4

изображена та ж е

последовательность, что

и на

рис. 7-1.

Обрыв списка указан пунктиром; фактически семь эле­

ментов

списка W

теперь содержатся в двух различных

списках.

 

Если

секторы

на д и а г р а м м е определить как индиви­

дуальные дисковые модули, а две или более списковые записи (следующие по выборке) находятся в разных модулях (т. е. разных секторах), процедуры доступа по спискам можно совместить. Совмещение автоматически управляется резидентной частью операционной системы, программой ввода-вывода, обычно выполняемой постав­ щиком оборудования . Если, например, запрос содержит

конъюнкцию WX,

будет выбран Х-список, состоящий из

шести записей, в то время как список W содержит семь

записей. Список X реализован в файле в виде двух под­

списков, к а ж д ы й

из которых начинается в другом мо-

140

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