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

ГЛАВА

ВОСЬМАЯ

О Б Н О В Л Е Н И Е И О Б С Л У Ж И В А Н И Е

ОПЕРАТИВНОГО

ФАЙЛА

Оперативное обновление

файлов

в реальном масштабе

тобеспечения и

оборудования

не

позволит

провести

надежное сравнение стоимостей,

то способ

обновле­

ния выбирается в зависимости от временных

критериев.

Например, если

оборудование

снабжается матобеспече­

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

(т. е. классифицируется по

типу

il емкости

оперативной

п а м я т и ) , то сравнение двух

видов

обновлений

по стоимости можно считать надежным .

таются выделить

стоимость тех технических средств, ко­

торые

участвуют

в функциях

обновления. Однако те же

З У П Д

и те ж е терминальные

устройства участвуют в реа-

чества

обновлений. П а к е

т н а я система, однако, имеет не­

большое дополнительное

время СРь,~которое

затрачива­

ется

в

основном на запись файла на магнитную ленту.

Д о

тех

пор,

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

операциями

с магнитной лентой, стоимость

обновления

ления на ленте всегда предшествует

сортировка

новых

записей при их внесении в файл, а временное

выражение

стоимости этого

процесса

является

функцией

объема

новых записей.

Обозначим

значение

такой

стоимости

ницами стоимости (на

одно изменение) д л я

оператив­

ного С,- и пакетного обновлений

Сь так:

Cr =

- i r +

tfCpr;

(8-1)

П

Wb Т

^РЬ "Г <-s [Ь>

/о о\

Сь —

ді

,

{й-2)

где

Сfr и С /О — постоянные

части,

отнесенные

ко време­

ни

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

из N записей, приходящиеся на

долю технических средств

и математического

обеспече­

бавление (стирание), модификация неключевых

данных;

5) добавление

ключей.

Р а з р а б о т ч и к

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

обнов­

терно д л я

категорий пп. 4 и

5.

Процедуры обновлений

с учетом

этих двух

особенностей

д л я последовательного

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

списков

различны . В н а ч а л е будет

затем

инвертированного и, наконец, секторного. В к а ж ­

дом случае рассматриваются все пять категорий.

8-1. ОПЕРАТИВНЫЕ ОБНОВЛЕНИЯ

МУЛЬТИСПИСКОВЫХ ФАЙЛОВ

Д а л е е

предположим, что категория обновлений известна

туры, в запись

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

д а н н ы е

(рис. 8 - 1 ) . В

начале записи в фиксированной

позиции

пись находится в файле; если

ж е

этот бит

равен

едини­

це, то в процессе поиска запись

д о л ж н а

пропускаться

с переходом к следующему

адресу связи,

т а к

как эта

11—88

161

з а п и сь

логически, хотя

и не физически, удалена из

фай­

ла . К р

о м е того, имеется

бит, связанный с к а ж д о й

парой

находится

в

записи,

а в

положении

единица

означает,

что ключ

был

удален

из

записи. П а р а

ключ/адрес

связи

не может быть вычеркнута из записи,

потому

что

были

бы нарушены

связи

в списке. В качестве альтернативы

Sum

бит

\КпШч/ЯС\Уничт\ключ/ЛС

уничто­

Клшч/.Щ

тения

жения

ключа

ключа

Рис. 8-1. Параметры для обновления записи мультисписка.

си списка

к

п о с л е д у ю щ е й ^ П р е д п о л о ж и м ,

что запись,

в которой ключ д о л ж е н быть уничтожен, является

ІѴ за­

писью

списка. Тогда запись ;Ѵ—1

имеет

адрес

связи

к списку N,

а запись N имеет адрес записи

к списку N +

+ 1. Связь через запись может быть

создана

перенесе­

нием

адреса

записи N + 1 в область

адреса

связи

(для

рассматриваемого ключа) записи N—1, если

список не

лучить N—1-ю запись — это

просмотреть список сначала,

что неэффективно, когда N

велико. Легче поставить бит

записей N—1 и N+1

через запись N.

В табл . 8-1 иллюстрируется процесс добавления пол­

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

масштабе времени. Сначала (пер­

си, представленному на рис.

3-5,

и

т а к ж е ,

к а к

и

при

организации

файла,

единственной

частью,

которая

не

может

быть вставлена

в

это время,

являются

адреса

связи.

Н а

втором

этапе

ей

присваивается

адрес

ДА

в З У П Д

в соответствии

с

имеющимся

местом. В

систе­

ме, использующей подвижную

головку

З У П Д ,

новым

за­

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

адреса

в монотонной последо­

вательности

для того, чтобы

при

выборке списка

меха­

вателы-юй обработки

ключей внутри

записи.

Ключ :

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

по справочнику.

З а т е м на

четвер­

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

из

справочника

в поле адресов свя­

зи ключа

в новой

записи. Н а

пятом

этапе адрес

новой

записи Д А

становится

новым

начальным адресом

ключа

храняется независимым от

любых записей. Н а шестом

этапе длина списка ключа

в справочнике увеличивается

вторением этапов с третьего по шестой д л я всех

ключей

новой записи. Наконец, на восьмом этапе новая

запись

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

З У П Д по адресу Д А .

Н а рис. 8-2

схематически иллюстрируется этот про­

после обновления. Внизу к а ж д о й секции

показан

выход­

ной уровень

справочника

ключей. Д л я

простоты

иллю­

стрируется обновление одного

ключа,

т. е. одна итерация

цикла этапов с третьего по шестой

(см. табл . 8-1).

К а к

указано

на

седьмом

этапе,

эта

процедура д о л ж н а

повто­

ряться

д л я

к а ж д о г о

ключа

в

новой

записи. Рассмотрим

ключ X, имеющий в своем списке два адреса связи, пер­

вый из

которых указывает

на

запись

по

адресу 105

в no­

i l *

163

пятом этапе адрес новой записи, который

д о л ж е н

быть

выходной

уровень

'X/W5/2

справочника

105

ключей

ОІХ/76

[ Черед

о&новление

! 75

Выходной

X/E0L

уровень

\КлючХШ/3

справочника

ключей

m

U- п

После

105

Iпвнавления

0W76

Увеличение

76

\Ö.X/E0Ü

адресов

Рис. 8-2. Обновление ключа.

182, становится новым начальным адресом

списка в спра­

вочнике. Наконец, на шестом этапе длина списка увели­

чивается на единицу. Окончательная картина после об­

новления

показана

в

нижней

половине

д и а г р а м м ы .

Н а

рис. 8-3

представлены

процедура

и

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

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

полной записи. П о л н а я запись

уда­

ляется из ф а й л а в

реальном

м а с ш т а б е

времени

за

один

или д в а

этапа .

Н а

первом этапе

запись

выбирается

и

в бит

у д а л е н и я

записи

заносится

единица. Н а

этом

об­

новление

м о ж н о закончить,

т а к

к а к

запись

логически

у д а л е н а

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

проходят

че­

рез эту запись, остаются нетронутыми. В некоторых слу­

чаях

модифицируется

длина

списка.

Если

разработчик

р а с с м а т р и в а е т

это

число к а к

физическую

длину

списка,

т.. е. действительное

количество произвольных

выборок,

которое

требуется

д л я

просмотра

списка,

то

длина

не