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

символ и положим, что требуется

только а—1

цепных

адресов (если

длина

цепи равна

а ) . Если

в

формуле

(6-9) раскрыть

скобки

и привести

подобные

члены, то а

му так

получилось.

Из

формулы (6-10) видно, что

для хранения уровня

косвенной адресации снова требуется N^CJa

символов.

Однако

хранение полного ключа

не требуется

(так как

звездочки (сигнального символа

ц е п и ) — е д и н и ц е , для

а—1

цепных адресов — Са (если

длина цепи равна а) и

для

фрагмента ключа — С/. При

раскрытии скобок и

результат, полученный по формуле (6-10),

меньше

ре­

зультата,

полученного

по формуле (6-9),

на

Nn[Ck—

— С / ( 1 — 1/а)+С„ — 1 ]

символов.

Если

разместить уровень косвенной

адресации в

опе­

ративной

памяти, то

формулы

примут

следующий

вид:

д л я рис.

6-4

(6-9а)

М , = = Л ^ [ С , ; + С г + С а ( 2 - 1 / а ) + 1 ] ;

для рис.

6-5

(6-10а)

Ма

= N* [С, +

(Сj + Cd)

(1 - i/o.) +

2].

Необходимо, однако, заметить, что

обе

эти

формулы

значно,

в то время

как формулы

д л я

деревьев (6-6) и

(6-7) не

учитывают

этого предположения . Следователь­

но, если

удалить из

формул (6-9)

и

(6-10) часть, свя­

дения прямого сравнения

с формулами

(6-6)

и (6-7)], то

они примут

следующий

вид:

д л я рис.

6-4

Md = Nk[Cj

+

Ci+Ca(l

+ l/a)].

(6-96)

Д о б а в к а ,

связанная

с

неоднозначностью,

равна:

Ск - Сj +

1 + ( I -

4-)

Са] ;

(6-9в)

для рис. 6-5

M

^ /

V ^ + ^

+ l ) .

(6-106)

Добавка, связанная

с неоднозначностью,

равна:

(6-10в)

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

нице (выделением из ключа logzNk

бит), чтобы создать

столько областей

д л я

уровня

косвенной

адресации,

тем

лучше

рандомизатор . Обычно хороший рандомиза-

тор

имеет

а около 1,1. Д л я ускорения декодирования

мен

о б

р а щ е н и я ) . Так

как Md

не

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

памяти

нет (если косвенный уровень не хранится в опе­

ративной п а м я т и ) . Поэтому

при

ограниченной памяти а

надо

увеличивать.

6-5-3. Сравнение

требований

к объему памяти

ство символов

равно 8,

что более

типично для

длины

фрагмента. Значения этих параметров у к а з а н ы

в столб­

це для Cf. Д л я

к а ж д о г о

значения

С/ создается

дерево

с т р е м я

различными значениями Nu

(ключей

в системе);

как указано в третьем столбце таблицы,

эти значения Nh

равны

соответственно

1 ООО, 10 ООО и 30

ООО.

П а р а м е т р а м и

длины

ключа

для

рандомизатора,

изо­

браженного на рис. 6-4,

являются

С,-

и

Ch

[формулы

(6-9в)

и

(6-9с)],

а для

рандомизатора,

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

на

рис.

6-5, — Cf.

Д л я

С,-

выбрано

значение

2, так

как

при

этом

выделяется

16

бит

или

2 1 8

ячеек

косвенной

адресации, что соответствует заданному

количеству

клю-

чей Nk-

Д л я

средней длины

ключа Cf t выбрано значение

12 (этот

п а р а м е т р

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

домизатора) . В четвертом

столбце

(для т)

приведено

количество

ключей

дерева,

которое

можно

разместить

формул (6-1) и (6-2). В

нижней части таблицы приво­

дятся типичные значения

постоянных

параметров . Объем

дорожки

берется

равным 3000,

что

является

близким

к объему

д о р о ж к и

диска

I B M ,

1301,

равному

2800 сим­

волов. Н а

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

10%

простран­

ства, соответствующего

300 символам .

Д л я

указания

символа

(32

бит) . Д л я

заголовка

Сл. в дереве

ключевых

слов

переменной

длины

достаточно

двух

символов,

а среднее количество однозначно закодированных

фраг­

ментов различной

длины

в дереве ключевых слов пе­

ременной

длины

полагается

равным

4.

Д л и н а

цепи

а,

используемой в

методе

рандомизации,

равна 1,1, что

сов­

местимо со значениями Cf

и Nk.

Требования

к

объему

оперативной

памяти д л я двух- и трехуровневого

дерева

даются (в символах) соответственно в столбцах

5

и 6

табл. 6-4. Требования к объему памяти

д л я двух- и

трех­

уровневого

дерева

даются

(в тысячах

символов)

соот­

ветственно

в

столбцах

7 и 8. П р е д п о л а г а е т с я т а к ж е ,

что

как

уровень

косвенной

адресации,

т а к

и выходной

уро­

приводить

сведения

д л я

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

объему

З У П Д

только в

случае

двухуровневого дерева .

Т а к

как

в формулу

(6-7),

по

которой

рассчитываются

деревья,

не включено предположение о неоднозначности

д л я

по­

стоянного дерева [в отличие от формул

(8-9)

и

(6-10)

для

рандомизаторов],

то

данные

д л я

дисков

были

раз ­

биты

на

две

части. Одна — д л я

декодера

без

предполо­

ж е н и я

о

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

(табл .

6-4 и

6-5), другая указывает добавку, связанную с

неодно­

значностью

(столбец

9). Д л я

постоянного

дерева

можно

либо ввести избыточность, проверяя записи файла

по

полному

ключу

(что

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

поисков

в ф а й л е ) ,

либо

хранить

полный

ключ

из

12

символов

в дополнение к фрагменту. В

случае.переменного

дерева

*

Здесь

считается,

что

символ

соответствует

одному

байту.

{Прим.

пер.)

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

затем

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

результаты.

Из проведенного анализа можно сделать несколько

выводов. Во-первых

(как

и предполагалось), поскольку

m значительно больше 10, то требуемые объемы

памяти

на дисках для двух-

и трехуровневых деревьев

почти

обращение

к З У П Д ,

но

больший

объем

оперативной

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

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

го дерева

требуется

два

обращения

к З У П Д , но мень­