Файл: Левковиц, Д. Структуры информационных массивов оперативных систем.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.10.2024
Просмотров: 83
Скачиваний: 0
|
|
|
|
|
|
Т а б л и ц а |
6-7 |
Время |
декодирования |
для рандомизатора, |
изображенного |
||||
|
|
. |
на рис. 6-4 |
|
|
|
|
|
|
|
Уровень |
Время (симво |
Номинальное |
||
Компоненты |
|
лическое) |
значение |
(сред- |
|||
|
|
|
|
|
|
'нее), млсек |
|
Раидомизировать ключ |
Рандомизатор |
0 |
|
0 |
|
||
Подвод головок |
|
|
Р |
|
85 |
|
|
Задержка при повороте |
|
|
4.R |
|
12,5 |
||
Считывание с дорожки |
|
|
R |
|
25 |
|
|
Обработка |
записи |
|
Косвенная |
0 |
|
0 |
|
|
|
|
адресация |
|
|
|
|
Потерянный |
оборот |
|
|
R |
|
25 |
|
Считывание с дорожки |
|
|
R |
|
25 |
|
|
Обработка |
записи |
|
Выходной |
0 |
|
0 |
|
|
|
|
уровень |
|
|
|
|
Сумма |
|
|
|
|
|
172,5 |
|
К этим формулам мы вернемся в конце гл. 8, где бу |
|||||||
дет вычислено общее время поиска |
и обновления файла . |
||||||
Замети м также , |
что |
если в З У П Д не |
предусмотрена |
||||
аппаратная проверка в виде немедленного чтения после
записи, |
то к общему |
времени |
доступа |
к |
З У П Д добав - |
||
|
|
|
|
|
|
Т а б л и ц а |
6-8 |
Время |
декодирования |
для рандомизатора, |
изображенного |
||||
|
|
на рис. 6-5 |
|
|
|
|
|
Компоненты |
|
Время |
(симво |
Номинальное |
|||
Уровень |
лическое) |
значение |
(сред |
||||
|
|
|
|
|
|
нее), млсек |
|
Раидомизировать ключ |
Рандомизатор |
0 |
|
0 |
|
||
Подвод головок |
|
Р |
|
85 |
|
||
Задержка при повороте |
|
|
|
|
12,5 |
||
Считывание с дорожки |
|
R . |
|
25 |
|
||
Обработка |
записи |
Косвенная |
0 |
|
0 |
|
|
|
|
адресация |
|
|
|
|
|
Сумма |
|
|
Р + |
1,5Я |
122,5 |
||
9* |
|
|
|
|
|
ІЗІ |
|
ля е тся |
время R, |
затраченное па |
один |
полный |
оборот |
диска |
( б а р а б а н а ) . |
В приложении |
3 для |
каждого |
из опи |
санных аппаратных средств указывается наличие этого (аппаратного) свойства. Те устройства, которые его не имеют (например, пакет дисков I B M 2311), необходимо модифицировать, вводя запрограммированное чтение за
писанных данных, выполняемое |
на следующем |
обороте. |
||
Таким образом, |
с учетом возможности обновления |
дере |
||
ва в формулы |
(6-11) — (6-12в) |
добавляется |
R |
(для |
устройств без аппаратной проверки) .
ГЛАВА СЕДЬМАЯ
МЕ Т О ДЫ О Р Г А Н И З А Ц И И ПОИСКА ФАЙЛА
Вгл. 6 описан двухступенчатый процесс, включающий
декодирование и поиск файла, и указано, что обе состав
л я ю щ и е процесса поиска |
относительно независимы. |
В качестве доказательства |
этой независимости в гл. 6 |
представлено детальное описание декодеров. Описание декодера содержит лишь минимальные ссылки на орга низацию данных файла . В случае рандомизированного алгоритма (см. рис. 6-5) возникло ограничение на схему структуры файла . Таким образом, опираясь на крите рии, выделенные в гл. 7, проектировщик располагает от носительно полной свободой в выборе декодера .
Всвою очередь выбор структуры данных файла ие зависит от декодера.
Внастоящей главе противопоставляются методы ор ганизации файла по способу последовательного списка
(мультисписка) и инвертированного списка. Д а л е е опи сывается способ, представляющий собой некоторый про
межуточный вариант, названный мультисписком |
с управ |
ляемой длиной списка. Н а рис. 5-2 представлены |
три пе |
речисленных типа организаций файла . Отдельно будет рассмотрен другой тип, отличающийся от стандартных
списковых |
структур, названный |
секторной |
структурой |
||||
файла . Все структуры |
иллюстрируются |
серией диаграмм |
|||||
(рис. 7-1—7-5). Развитие от структуры |
последовательно |
||||||
го |
списка |
к структуре |
инвертированного списка, а |
так |
|||
ж е |
взаимоотношения |
с секторной |
системой |
можно |
про |
||
следить |
на одном и том ж е |
примере списка из четырех |
||
ключей. |
Н и ж е |
описываются |
процедуры, |
генерирующие |
эти структуры, |
и приводятся |
временные |
оценки. |
|
132
7-1. МУЛЬТИСПИСКОВАЯ ОРГАНИЗАЦИЯ ФАЙЛА
На рис. 7-1 запись фиксированной длины, представляю щая собой выход справочника ключей, содержит тройку
Ключ |
( ф р а г м е н т ) / Н а ч а л ь н ы й адрес |
списка/Длина |
спис |
||
ка. В зависимости от того, разрешена ли |
неоднознач |
||||
ность |
в записи данных или |
при декодировании, на выходе |
|||
справочника используется |
полное |
значение |
ключа |
или |
|
его фрагмент. Начальный адрес списка представлен на
Ключ/Начальныйільный адрес списка/Длина списка^
Справочник
ключей
(выходной
уровень)
|
|
Файл |
|
|
списковой |
|
|
I структуры |
|
|
в памяти с |
|
|
произвольным |
|
|
доступом |
СектарЗ |
|
|
Рис. 7-1. Мультисшісковая организация файла. |
||
диаграммах символически |
как А п , где |
п есть адрес |
внешней памяти. Записи в |
поле файла |
представлены |
точками в последовательности начиная с адреса, ука занного в выходном уровне справочника ключей. Таким
образом, список |
W начинается |
по |
адресу |
Л 6 и |
содержит |
||||||||
семь записей. К а к указано |
на диаграмме, |
вторая |
запись |
||||||||||
списка |
W т а к ж е |
содержит |
ключ |
X |
(пересечение |
клю |
|||||||
чей). Эта запись |
не имеет в д и а г р а м м е помеченного |
адре |
|||||||||||
са, поскольку она не стоит во |
главе |
списка |
(заголовок |
||||||||||
списка А' находится по адресу |
А3). Однако |
запись |
по |
||||||||||
адресу |
А а содержит |
адрес |
связи |
на |
указанную |
запись, |
|||||||
содержащую ключ W, как это показано в формате запи |
|||||||||||||
си |
на |
рис. 3-5. |
|
|
|
|
|
|
|
|
|
|
|
|
Адрес связи, |
у к а з ы в а ю щ и й |
на |
вторую |
запись |
списка |
|||||||
W |
(а |
т а к ж е списка |
ключа |
X), |
записан т а к ж е |
по |
А 3 , по |
||||||
скольку запись содержит ключ X. Таким образом, если |
|||||||||||||
запрос |
содержит |
конъюнкцию |
WY |
по этому |
файлу, |
то |
|||||||
133
д е к о д и р у ю щ ий |
справочник ключей декодирует как W, так |
||||||
и Y и |
отметит |
на |
выходе справочника |
соответствующие |
|||
длины |
списков. Поскольку список У короче |
(четыре за |
|||||
писи), |
чем список W (семь записей), то поиск в файле |
||||||
велся бы по списку Y и потребовал |
бы |
в области |
файла |
||||
четыре |
обращения |
с произвольным |
доступом. |
Каждая |
|||
переданная в |
оперативную память |
запись |
проверялась |
||||
бы на условие конъюнкции с W, которое согласно нашей схеме выполняется только для записи по адресу Ад.
Если запись содержит д л я к а ж д о г о ключа два |
адреса |
|||
связи: один |
у к а з ы в а ю щ и й па |
последующую |
запись |
|
в списке, |
а другой — на предыдущую, соответствующая |
|||
списковая |
структура называется |
двунаправленной |
(коль |
|
цевой) . Т а к а я |
структура позволяет осуществить |
общую |
||
схему просмотра файла, включая циклы, в то время как односторонний последовательный список может органи зовывать циклы только присоединением последней запи си списка к первой, что ие очень эффективно. Кольцевой список, кроме того, улучшает временные характеристики обновления и распределения памяти. Однако во всех рас смотренных аспектах с точки зрения возможности по строения циклов, обновления, распределения памяти си стема с инвертированным списком вполне адекватна . При построении информационно-поисковых систем обычно
нет необходимости вводить списки кольцевой |
структуры. |
|||
А поскольку |
списковые |
издержки |
памяти |
при этом |
удваиваются, в |
тех случаях, когда хотят использовать |
|||
преимущества |
кольцевой |
структуры, |
предпочтительней |
|
организация инвертированного списка, имеющая те же издержки памяти, что и система с последовательным списком.
Самый |
существенный |
недостаток |
последовательного |
|||||
мультисписка |
состоит в |
|
необходимости |
выборки |
из |
|||
З У П Д и |
переноса в оперативную память |
всех записей |
||||||
кратчайшего |
в конъюнкции |
запроса |
списка. Д а л е е |
все |
||||
считанные |
записи д о л ж н ы |
|
быть просмотрены |
процессо |
||||
ром. Однако часть списка, |
удовлетворяющая |
запросу |
||||||
(в нашем |
примере WY), |
может оказаться |
намного |
ко |
||||
роче. В приведенном выше примере отношение объема
системных |
поисков к |
объему |
выборки |
из З У П Д |
равно |
|||
1/4. Практически, |
если длины |
списков |
достигают не |
|||||
скольких |
сотен |
(или |
т ы с я ч ) , |
а конъюнкции |
содержат |
|||
много ключей, |
отношение это |
может оказаться |
порядка |
|||||
нескольких сотьіх |
или |
д а ж е тысячных, |
что крайне |
неэф- |
||||
134 ~
фективно. Эта неэффективность находит свое отражение в низких характеристиках допоисковой статистики вы
борки. Д л я |
априорной оценки |
в |
качестве |
б л и ж а й ш е й |
||||||
верхней |
грани |
числа |
выборок, |
выполняемых |
мульти- |
|||||
списковой системой, принимается |
для конъюнкции |
за |
||||||||
проса длина самого короткого списка, а для |
логической |
|||||||||
суммы |
произведений — сумма |
таких длин. Д р у г и е |
опи |
|||||||
сываемые структуры |
позволяют |
получить |
значительно |
|||||||
более благоприятную допоисковую статистику. |
|
|
||||||||
Основными преимуществами мультисписковой орга |
||||||||||
низации |
файла |
являются |
программная простота |
его |
||||||
реализации |
и гибкость при обновлении. |
|
|
|
||||||
|
7-2. ОРГАНИЗАЦИЯ ФАЙЛА ПО МЕТОДУ |
|
|
|||||||
|
|
ИНВЕРТИРОВАННОГО |
СПИСКА |
|
|
|
||||
На рис. |
7-2 |
иллюстрируется |
схема организации |
файла |
||||||
с помощью инвертированного списка. Согласно этой схе
ме все виды связей исключаются из поля |
ф а й л а и вклю- |
||||||
Rs |
W |
X |
|
У |
|
z |
|
Дід |
Яз |
ят |
Яз |
Я,! |
% |
|
|
Й7 |
% |
л7 |
яго |
«и |
Яі7 |
Л}7 |
|
"я |
% |
я» |
|
% |
Ягг |
|
|
йа |
|
'и |
|
hi |
% |
|
|
Сенторо |
|
|
|
|
|
|
|
Сектор1 |
|
|
|
Л ' |
•> |
|
|
|
|
|
|
|
hs |
||
|
|
|
|
|
|
|
|
Секторг |
|
hi |
• |
»hz |
|
|
ho' |
|
|
|
•% |
|
h |
о |
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
3 |
СектарЗ |
|
• hl |
|
|
Я35а |
||
|
|
|
|
|
|||
Рис. 7-2. Организация файла с инвертиро ванным списком.
чаются в выходную информацию справочника ключей. Обычно это приводит к значительному увеличению объе ма справочника по сравнению с мультисписковой си стемой. Однако общий объем памяти не возрастает, поскольку адреса связи более не присутствуют в файле
135