Файл: Левковиц, Д. Структуры информационных массивов оперативных систем.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.10.2024
Просмотров: 92
Скачиваний: 0
где INT является целым числом, a R— дробным остат ком. Затем обозначим:
|
|
|
I N T _ M = I N T ; |
|
|
|
|
|
|||
|
I N T + [X] |
= |
I N T + 1 , |
если |
|
ЯфО, |
|
||||
|
INT, |
|
если |
R = |
0. |
|
|||||
|
|
|
|
|
|||||||
|
Если объем доступного на д о р о ж к е пространства |
ра |
|||||||||
вен |
Ci—Сг, то для |
постоянного |
дерева |
|
|
|
|||||
|
/га = |
I N T . |
Г |
с - * ~ |
с ' |
С I |
1 |
|
(6-1) |
||
|
|
|
|
С, + |
С 0 |
+ |
|
|
|
||
а для переменного |
дерева |
|
|
|
|
|
|
|
|
||
|
/л = |
I N T . |
Ct |
— Cr — |
NdCn |
|
(6-2) |
||||
|
С , + |
C a |
+ |
C t |
|
|
|||||
|
|
|
|
|
|
|
|||||
|
Так как на нижнем уровне любого дерева должны |
||||||||||
иметься все ключи словаря Nu, исключая остаток, |
ча |
||||||||||
стично заполняющий одну д о р о ж к у |
на |
следующем, |
бо |
||||||||
лее |
высоком уровне [например, |
ВАВВ |
на |
д о р о ж к е |
Too |
||||||
(рис. 6-1)], то количество дорожек, требуемых для со хранения низшего уровня я-уровневого дерева, равно:
|
tftn |
= I N T _ [ ^ - ] . • |
|
(6-3) |
|
К а ж д а я д о р о ж к а |
следующего |
(более |
высокого) |
||
п—1-го уровня |
дерева |
соответствует |
m д о р о ж к а м уров |
||
ня п или количеству фрагментов ключей, |
равному |
тг. |
|||
Следовательно, |
для хранения словаря |
из Nu |
ключей |
тре |
|
буется WT+[Nh/m2] дорожек на уровне п—1. Все пред шествующие уровни, включая первый, должн ы также равняться INT+, а для хранения каждого последующего (более высокого) уровня требуется \/т дорожек, исполь зуемых д л я хранения предыдущего уровня. Поэтому при
водимые ниже формулы дают возможность |
рассчитать |
|
количество дорожек, требуемое д л я |
хранения каждого |
|
уровня дерева в З У П Д : |
|
|
tftn=INT_ |
|
|
|
il— |
(6-4) |
i = l. |
1; |
|
|
|
(6-5) |
Md = CiNi. |
|
(6-6) |
118
Если высший уровень дерева хранится в оператив ной памяти, то
Mc = Nu_(Ci + Ca);
Md = C t i |
N t i . |
: |
о |
I
f |
( 6 _ 7 ) |
I
В случае двухуровневого дерева, когда первый уро вень хранится в оперативной памяти, можно снизить требуемый объем оперативной памяти, используя дл я
хранения ключей |
З У П Д |
(т. е. можно хранить ключи |
|||||
в выходном уровне д е р е в а ) . В этом |
случае |
формула (7) |
|||||
читается следующим |
образом: |
|
|
|
|||
|
|
Ntt(C, |
+ |
Ca)-\ |
|
||
|
A f l a |
|
|
N |
1 |
> |
(6-7а) |
|
= I N T + |
|
|
|
|||
Р а с с м а т р и в а я |
значения |
Nu |
в |
формуле (6-4) для |
|||
т > 1 0 и Nh в диапазоне |
до |
100 000, |
можно |
увидеть, что |
|||
Nti^^Nin |
при |
і = І , |
|
п—1. |
|
||
Следовательно, можно считать, что количество доро жек, требуемое дл я хранения дерева с л ю б ы м числом уровней, составляет:
|
Nt~Nln |
= mT_ |
|
|
|
(6-8) |
На |
рис. 6-6 иллюстрируется |
применение |
формулы |
|||
(6-4) |
к трехуровневому дереву при m = 4 и Nk = 22. |
К а ж |
||||
дая горизонтальная |
п р я м а я обозначает |
дорожку . |
Вер |
|||
тикальные штрихи на этих прямых р а з д е л я ю т |
логиче |
|||||
ские записи (тройки |
фрагментов |
ключей), |
а косые |
штри- |
||
Уровень1
ИровеНьг
Уровень 3 ^
•4 3 2 /
20 1818 17 |
1В 15 П13 |
12 11 10 3 |
8 7 S 5 |
Рис. 6-6. Пример трехуровневого дерева. |
119 |
|
хи обозначают резервное пространство дорожки . Из при
веденных формул • на |
рис. 6-6 |
ясно, |
что Nt3 |
есть целая |
часть отношения 22/4, |
р а в н а я |
5; Ntz |
равно |
отношению |
22/42 =22/16, которое равно 2 (берется целая часть плюс единица), a Nu — отношению 22/4 3 = 22/64, равному еди нице (берется целая часть плюс единица) . Следуя про цедуре создания дерева, показанного на рис. 6-1, необ ходимо полностью заполнить пять д о р о ж е к по четыре ключа е а д о р о ж к у (для ключей от 1-го д о 20-по). Объем памяти, требуемый для хранения второго уровня, равен
одной |
полной д о р о ж к е |
(рис. 6-6). Д л я того чтобы мож |
||||
но |
было о б р а щ а т ь с я к |
пятой |
д о р о ж к е |
третьего |
уровня, |
|
т. |
е. к |
дорожке, с о д е р ж а щ е й |
ключи |
от 17-го до |
20-го, |
|
необходимо хранение одной записи на второй дорожке второго уровня. Остальные дв а ключа, 21-й и 22-й, по мещаются в две из оставшихся трех записей второй до р о ж к и второго уровня. Резервное пространство этой до рожки равно, таким образом, н а ч а л ь н о м у резервному пространству плюс одна неиспользованная запись. Дл я того чтобы обеспечить две дорожки второго уровня, тре
буется только одна |
д о р о ж к а |
|
первого уровня. |
Следова |
||||||||||||
тельно, словарь с 22 ключами требует |
одну д о р о ж к у для |
|||||||||||||||
хранения |
первого |
уровня |
дерева, |
две — дл я |
второго и |
|||||||||||
пять — д л я |
третьего |
уровня |
|
(на |
к а ж д о й |
д о р о ж к е |
хра |
|||||||||
нится по четыре |
к л ю ч а ) . |
|
|
|
|
|
|
|
|
|
|
|
|
|||
Если хранить |
первой уровень |
в оперативной |
памяти, |
|||||||||||||
то требуется только две логические записи |
типа |
фраг |
||||||||||||||
мент ключа/двойной |
адрес |
[т. е. |
|
|
Mc—2(Cf+Ca)]. |
|
||||||||||
Рассмотрим наиболее |
распространенные |
случаи. |
||||||||||||||
1. Трехуровневое |
дерево: |
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
iWft = 20000; |
|
|
|
|
|
|
||||||
|
|
|
|
m = |
100; |
|
|
|
|
|
|
|
||||
|
|
yVt3 |
= |
I N T . ? ^ |
= |
200; |
|
|
|
|
||||||
|
|
Л ^ = |
Ш Т + |
2 |
0 |
ÎOO2 |
' «- ' |
|
|
|
|
|||||
|
|
|
|
|
|
0 |
0 |
0 |
|
|
|
|
|
|
||
|
|
д. |
|
|
|
20 000 |
, |
|
|
|
|
|
||||
|
|
|
|
Wt = 203. |
|
|
|
|
|
|
||||||
З а м е т и м , что так как m значительно |
больше |
10, то |
||||||||||||||
приближение Ni^Nt3=200 |
|
является |
весьма |
точным. |
||||||||||||
120
2. |
Двухуровневое |
дерево: |
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
Wh = 20 ООО; |
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
m |
=100; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Nu = |
\ЫТ_ |
20 ООО |
= |
200; |
|
|
|
|
|||||
|
|
|
|
|
|
|
100 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
л , |
т |
м ^ |
20 000 |
- = |
0 |
2. |
|
|
|
|
|
||
|
|
|
|
tft1 = |
|
I N T + |
- r o 5 ï |
|
|
|
|
|
|
||||
|
|
6-5-2. |
Формулы дл я р а н д о м и з а т о р а |
|
|
|
|||||||||||
Требуемый дл я декодера с рандомизацией объем |
|
памя |
|||||||||||||||
ти зависит от вида данного рандомизатора, |
однако дл я |
||||||||||||||||
обобщенных рандомизаторов, показанных |
на |
рис. 6-4 и |
|||||||||||||||
6-5, применимы следующие |
формулы . |
|
|
|
|
|
|||||||||||
Д л я рис. 6-4: |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
Md= - ^ 5 - + Nk |
[ c f c + C , + 1 + |
|
|
|
||||||||||
|
+ ( ^ r ) c |
« + c « ] = |
|
( c " + c < + 2 C « + |
! > - |
|
(6-9) |
||||||||||
|
|
|
|
||||||||||||||
Для рис. |
6-5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
Md |
= N*Ca |
|
|
|
|
|
a— 1 |
{Ca + |
Cf) |
|
|
|||||
|
|
|
|
Cffl |
|
|
l |
- f d |
+ |
Ca + |
2 |
|
|
(6-10) |
|||
|
|
|
|
|
|
|
|
|
|||||||||
При расчете по формуле (6-9) |
дл я хранения |
уровня |
|||||||||||||||
косвенной |
адресации |
требуется |
Nul о, |
областей, |
к а ж д а я |
||||||||||||
из которых |
содержит |
адрес |
записи, |
хранимой в |
З У П Д . |
||||||||||||
При |
словаре ключей |
объемом 20 000 |
слов и |
выделении |
|||||||||||||
(при |
рандомизации) |
из к а ж д о г о |
ключа 10 бит создает |
||||||||||||||
ся 1024 |
кода, причем |
среднее |
количество |
избыточных |
|||||||||||||
декодирований |
(т. е. |
средняя |
длина |
цепи |
а) |
|
равно: |
||||||||||
20000/1024 ~20 . Таким |
образом, |
объем памяти (в сим |
|||||||||||||||
волах), требуемый дл я хранения |
уровня косвенной |
адре |
|||||||||||||||
сации, равен NkCJu. |
Д л я к а ж д о г о |
|
из Nu |
ключей, |
полу |
||||||||||||
чаемых с помощью декодера, требуется следующее коли
чество символов: |
дл я |
полного |
ключа — 6\; |
дл я |
длины |
|
списка — Са; |
дл я |
цепного адреса — Са (если |
есть |
цепь), |
||
и для адреса |
ссылки |
на выход |
декодера — Са. |
|
||
М о ж н о сэкономить |
один параметр, д о б а в л я я в выход |
|||||
ную запись |
символ, |
у к а з ы в а ю щ и й существование цеп- |
||||
121