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

д о в а т е л ы і ыи список, причем

к а ж д ы й новый олок

ставит­

ся в

начало списка, а когда

нужен блок ж е л а е м о г о раз­

мера,

«искатель пространства» просматривает

список

Рис. 8-6. Упорядочивание памяти.

зический

способ

обслу­

ж и в а н и я

имеет

неко­

передает системе пригодные

д л я

использования блоки

по всей памяти. Он включается,

когда устройства или

программы с более высоким

приоритетом не з а г р у ж а ю т

бодной памяти

в

течение

нескольких секунд,

оставляя

ф а й л ы полностью

в рабочем

состоянии. Н а рис. 8-6 ил­

люстрируется

этот

процесс.

В верхней

части

рисунка

и з о б р а ж е н а часть файла с

16 записями .

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

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

или ключей. Н и ж н я я часть рисунка

показывает состояние

ф а й л а после упорядочивания памя ­

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

записями 2 и 3.

Если

логические записи упакованы в физические записи

(та­

кие

как д о р о ж к и ) , то полная физическая запись

обрабо ­

тана

таким ж е образом,

а излишек

пространства

переда­

ется

следующей записи.

Запись 3

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

вверх,,

ется внезапная необходимость

в пространстве. П р о г р а м ­

ма может закончиться и оставить рабочий файл

после

окончания движения очередной записи. Д л я записи

с 20

ключами и временем декодирования и обновления

спра­

вочника

200 мсек

на один шаг

по файлу потребовалось

бы 4 сек.

Если эта

процедура

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

стоянного

списка

распределенной

имеющейся

памяти,,

в которой

к а ж д ы й

блок собирался

бы с помощью

проце­

ска очень простое (имеется

всегда Л' блоков,

относитель­

но небольшое по количеству и переменной д л и н ы ) , а

упо­

рядочивание

памяти локализовано .

Следует подчеркнуть, что упорядочивание памяти мо­

ж е т быть выполнено только на двунаправленных

муль­

тисписках

или

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

списках, потому

что,

когда

запись перемещается,

связи

к

последующим

за­

писям остаются нетронутыми, в то время как

адреса

свя­

зи к

предшествующим записям

д о л ж н ы быть

изменены.

Если

связи

однонаправленные,

адреса

предшествующих

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

не

может

быть вставлен как адрес связи в списке. Эта

трудность

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

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

с

двунаправленными

*

7"д=7"г н-1.5^?. (Добавить

R, если после

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

требуется

конт­

рольное чтение.)

** Предполагается, что длпиы списков справочника—физические,

поэтому,

если

поставлен бит уничтожения ключа или записи, не нужно

обновлять

справочник

***

Г3 —время декодирования

трехуровневого

дерева

[см. (6-12)].

(Добавить R,

тролем, ко

времени

занесения на З У П Д

д о л ж н а быть

добавлена

величина

R, которая не

включает схемного

контроля. В приложении 3

указано,

какое

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

имеет устройство схемного

контроля. Те устройства, ко-

1 76

Т а б л и ц а

8-9

Расчет

времени

обновления

для инвертированных

списков

Изменение

Изменение

Добавле­ Уничто­

Уничтоже­

неключе­

Добавление

ние

пол­

жение

вых

дан­

неключе­

п. ключей

Процедуры

ной за­

полной

ние п

ных

(без

вых

данных

(без

пере­

писи

записи

ключей

перемеще­

(с

переме­

мещения)

ния)

щением)

Декодирова­

т3

т3

т,

т,

т3

ние по спра­

вочнику

ТА

Выборка

Тл

ТА

ТА

ТА

записи

вд

ад

Обновление

пТ3

пТ3

справочника

ад

Обновление

NhTL*

nTL

n

ТL,

инвертиро­

ванного

списка

Запоминание

ТА

ТА

ТА

ТА

тА

обновленной

записи

*

Р"г + 1/2 j—J-J R.) (Добавить

R, если

требуется

контрольное

чтение.)

" Т р е б у е т с я ,

если

используется бит уничтожения. Бит уничтожения тр е б у е т с я

если производилось

упорядочивание

памяти.

Т а б л и ц а

8-10

12—88

177

торые не имеют устройств схемного контроля,

д о л ж н ы

проверяться программным чтением (на следующем по­

вороте

диска)

записанных

данных.

В к а ж д о й из этих т а б л и ц процедуры

обновления

раз ­

биты на четыре последовательных ш а г а : 1)

справочное

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

2) выборка

записи

(для

обновления);

3) обновление справочника; 4) запоминание обновленной

записи.

Предполагается, что все обновления относятся к еди­

ничной записи, которая идентифицируется по

ее

номеру.

В общем случае для того, чтобы подсчитать

время

д л я

многократного декодирования

ключей при

многократной

выборке записей, обновлений справочника и восстанов­

лений

записи, вводятся соответствующие

коэффициенты.

В т а б л и ц а х

видна

сравнительная

степень

сложности

I

к а ж д о й системы. Система

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

секторов—

наименее с л о ж н а я в предположении, что перемещение

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

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

делы сектора, что обычно наблюдается . Средней по слож-

. ности

является

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

система,

а

наиболее

j

сложной — структура

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

списка.

И з

табл . 8-11

видно, какие

соотношения

существуют

между временами обновления мультисписка и инверти­

рованного списка

д л я

всех

пяти

категорий

обновления.

Д о б а в л е н и е

полной записи

TIL=TML

+ NhTL.

(8-3)

Уничтожение

полной записи

Trz.=

TML

+ Nk(T3...).

(8-4)

Уничтожение

ключей

TIL=TML+n(T3+TL).

(8-5)

М о д и ф и к а ц и я

неключевых данных

(без

перемеще­

ния)

TIL

= TML.

(8-6)

TIL=TML+NhTL.

(8-7)