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

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

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

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

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

Добавлен: 19.10.2024

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

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

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

д у л е . Поисковая система выработает команду ввода-вы­ вода по отношению к обоим адресам Х-спнска, а именно АО.З и А 1.9. После этого функция операциононй системы

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

модулей и приоритетом требования

ввода-вывода. Если

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

ввода-

вывода ни один из модулей не был использован,

начина­

ется

одновременная установка

начала (head positioning)

к а к

для АО.З, так и для А 1.9

с последующим считыва­

нием записей. Таким образом,

происходит

параллельный

поиск по двум подспискам списка

X. При

этом

полное

время поиска выразится приблизительно временем че­

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

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

доступа

вместо

шести­

кратного. П р е д п о л о ж и м

далее,

что

/Y-список просматри­

вается

как в подсписке

АО.З, так и в А 1.9

и что как АО.З,

т а к и следующий за ним адрес

по

списку (нулевой сек­

тор)

выбраны

и обработаны

до

получения

доступа

к А 1.9.

Пусть,

кроме того, выработана

команда

ввода-

вывода для третьей записи списка, расположенной в 1-м секторе. Операционная система автоматически помещает это требование в магазин, где оно хранится до тех пор,

пока не будет получен доступ

к А 1.9 и не

передана за­

пись, т. е. программирование

структуры

файла такого

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

входных

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

К а к

будет показано ниже, генерирование списковой

структуры такого типа может быть запрограммировано так ж е легко, как мультисписок на рис. 7-1. Фактически, мультисписковая структура с управляемой длиной спи­ ска является обобщенной списковой структурой, по от­ ношению к которой мультисписковая система и система инвертированного списка представляются частными слу­ чаями, первая с управляемой длиной списка, равной бесконечности, вторая—• единице. Процедура генерирова­ ния этих списковых структур, описанная ниже, включает параметризацию длины списка, организованную так, что файл может быть в любое время перестроен с новым значением у п р а в л я ю щ е й длины списка и, следовательно, другой степенью инверсии. Вместо одного параметра можно ввести таблицу у п р а в л я ю щ и х длин в зависимости от ключа. Например, часто употребляемые ключи д о л ж ­ ны иметь более короткие списки (т. е. большую степень

141

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

ответствии

с

новым

состоянием

таблицы .

Такая

процедура

о б л а д а л а бы тогда способностью к адаптации.

В

качестве

второго

примера

 

рассмотрим

запрос X

или У, который требует поиска как по списку X, так и по

списку

Y.

Поисковая система сформирует команды вво­

да - вывода

для

доступа

к записям

А0.9,

АО.З и А 1.9. Пусть

далее

эти

команды выработаны

в

описанной

последова­

тельности

и операционная система

приступает

к

выпол­

нению требования доступа к нулевому модулю для адре­ са А0.9 и к 7-му модулю для А 1.9. Таким образом, поиск части Z-списка и У-списка совмещен. Когда в оператив­ ной памяти исследуется первая запись У-списка по адре­ су АО.9, система вначале сформирует команду вводавывода с целью получения доступа к следующему эле­

менту списка Y, указанному адресом

связи внутри

запи­

си

А0.9.

Запись эта расположена,

как

указывает

дна-

грамма, в 1-м секторе. Следовательно, выдается

команда

для

получения доступа

к записи в 1-м

модуле. Если

к это­

му времени система еще находится

в

процессе

получе­

ния

доступа или чтения записи А0.9

из Х-спнска, то

команда

ввода -вывода

д л я второго

элемента

У-списка

помещается операционной системой в магазин. Нулевой модуль освобождается, и в порядке занесения операци­ онной системой в магазин индуцируется поиск в другой части .Y-списка, начинающегося по адресу АО.З. Следо­ вательно, в поиске по двум подспискам Х-списка про­

изойдет

перекрытие.

К а к только

первый

элемент под­

списка X,

с о д е р ж а щ и й

адрес А 1.9,

считан в

оперативную

память, в соответствии с адресом связи этой записи фор­

мируется команда ввода-вывода для получения

доступа

к следующей записи, которая о к а з а л а с ь во 2-м

секторе.

После этого может выполняться поиск по У-списку, кото­

рый был

з а д е р ж а н

до освобождения

1-го модуля. К это­

му времени процедуры поиска п о в е е м

трем спискам, тре­

бующим

доступа

к модулям 0,1

и

2, перекрываются.

М а к с и м а л ь н о в о з м о ж н а я степень

перекрывания обычно

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

142

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

дим

поиск по полному списку (кратчайшему в конъюнк­

ции)

и,

за

исключением полностью

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

файла,

при

поиске на стадии справочника

пересечения

не

рассматриваются . Однако время поиска при этом

всегда

меньше, чем д л я неуправляемого

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

так

как

оно

зависит во-первых от

модульности З У П Д ,

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

Оперативное формирование файлов с такой списко­ вой структурой выполняется без обращений к устройст­

вам с произвольным доступом. Оперативное

обновление

файлов, которое

в некоторых

случаях т а к ж е

можно рас­

сматривать

как

процедуру

формирования,

разумеется,

использует

З У П Д , и требование такой процедуры накла ­

дывает свои ограничения на структуру файла, которые будут рассмотрены в гл. 8.

7-4. ПОСЕКТОРНЫЕ РАЗБИЕНИЯ

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

длине

списка

в

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

необязательно ведут

к улучшению свойств обработки

файла .

 

 

Д р у г о е решение

состоит

в

определении

логических

границ секторов

З У П Д , в

которые записи

помещаются

согласно некоторой

стратегии размещения . Д а ж е если за­

писи

з а г р у ж а ю т с я

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

секторы

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

разбиение, которое

может быть

использовано вместе

или

в соединении с другими у п р а в л я ю щ и м и списковыми

па­

раметрами . Н и ж е исследуется

тип разбиения файла,

на­

зываемый на рис.

5-2 посекторными разбиениями .

 

143

Рис. 7-5 иллюстрирует

посекторное

разбиение, со­

д е р ж а щ е е мультисписковую структуру файла . С

другой

стороны, его можно рассматривать к а к

модификацию

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

при которой

список

вместо

ограничения по длине локализован внутри сектора. От­

сюда

и название

метода секторного

мультисписка. Тот

ж е подход применим

к методу

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

списка.

 

 

 

W

 

:<

 

У

 

2

 

 

 

 

n

as/3

Й

аз/г

Я

0.3/!

Я 1.7/2

 

 

 

 

яі.2/?.

/л; ѵ з

Й1Л/2

Я2.2/д

 

 

 

 

R2.SU

я

2.0/1

Я2.1/1

ЯЗ.7/1

 

 

 

 

Л 35/7

 

 

 

 

 

 

 

 

 

СекторО

\

 

\яо.з

 

\

 

J

 

 

 

 

 

 

 

 

 

 

 

 

 

Сектор !

 

 

 

 

 

 

nu

 

 

 

 

 

 

 

 

 

 

 

 

 

Сектор2

 

 

 

 

 

 

Д2.3\Яг-°

 

 

 

 

 

 

-?

 

 

 

 

\

 

 

 

 

 

 

 

 

 

-

- V - -

 

 

Сектор3

 

 

 

 

 

 

 

&

 

 

 

 

іязл

 

 

 

 

A3.5

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис. 7-5.

Организация файла с секторным

 

 

 

 

 

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

 

 

 

 

П ри этом в начале сектора появился бы

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

ный

список для

данного

сектора.

 

 

 

 

Поскольку,

как показано

на рис.

7-4,

номер

сектора

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

щений к

З У П Д

и

как

следствие д л я улучшения

допо-

исковой

статистики.

XZ. Просмотр

 

 

Рассмотрим

запрос

выходного

уровня

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

списков,

полностью

расположенных

внутри секторов О,

1 и 2 с длинами списков соответственно 2, 3 и 1. Анало­

гично, список Z имеет подсписки,

полностью л е ж а щ и е

внутри секторов 1, 2 и 3

с длинами

списков 2, 3, 1. Сле­

довательно, конъюнкция

XZ может

быть расположена

144

только в секторах, содержащихся

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

начальных адресных списков X и Z. В нашем

примере

список X содержит начальный адрес списка в нулевом"

секторе. Список

Z в этом секторе не

имеет

подсписка.

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

пересечение

XZ

по

нулевом

 

сектору

пусто, поскольку

список Z в нулевом секторе отсутствует.

Аналогичные рассуждения применимы к 3-му

 

сектору.

Таким образом,

поиск по конъюнкции

списков

XZ огра­

ничится поиском

подсписков

Х\\

(или)

Z,

содержащихся

в секторах 1 и 2.

Более того, в 1-м секторе предпочтение

будет отдано списку Z (длина

его равна

двум

против

трех для списка X в 1-м секторе) . Во 2-м секторе пред­

почтение отдается списку Л', имеющему длину,

равную

единице. Общее число списков для поиска по конъюнк­

ции XZ становится равным трем

вместо

шести,

как это

было бы при поиске кратчайшего

из двух списков X, Z

при

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

организации

файла .

 

 

 

 

Если, кроме того, секторы приписаны к отдельным

дисковым

модулям, исполнительная системная

програм­

ма

поиска

установит

схему просмотра

списка

внутри

каждого индивидуального модуля,

отнеся

к а ж д ы й

поиск

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

деления секторов, например,

отвести

сектору цилиндр

диска таким образом, что

если

блок головок

установлен

иа данный цилиндр, поиск

по некоторому фиксированно­

му подсписку производится без дальнейших

передвиже­

ний блока головок.

 

 

 

 

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

может быть

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

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

для

к а ж д о г о запроса

(как это определено

выше

процеду­

рой

пересечения)

изображены

так,

 

как

показано

в табл . 7-1. Согласно таблице первый

запрос (Qi) требу­

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

0,

1,

4

и 9, второй за­

прос

( Q 2 ) — в секторах

1, 8,

9 и

15;

третий

запрос (Q3)

требует поиска в секторах 0, 2 и 4. Вначале

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

ная

программа производит

слияние

индивидуальных

списков доступа к секторам и

образует

объединенный

список, приведенный

в

табл .

7-2.

Теперь

видно,

что пер-

10—88

145

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