Файл: Левковиц, Д. Структуры информационных массивов оперативных систем.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.10.2024
Просмотров: 87
Скачиваний: 0
обходимый для постоянного дерева, не намного |
больше, |
||||
чем для |
переменного дерева . В то ж е время |
однозначное |
|||
дерево проще программировать . Поэтому, если |
разработ |
||||
чик предпочитает |
декодировать |
однозначно |
(жертвуя |
||
объемом |
п а м я т и ) , |
то ему следует выбрать |
постоянное |
||
дерево. |
|
|
|
|
|
В-четвертых, рандомизатор, |
изображенный |
на рис. |
|||
6-5, предпочтительнее рандомизатора, изображенного на рис. 6-4, по фактору 3, которым оценивается гибкость декодера. Так, рандомизатор, изображенный на рис. 6-5, специально приспособлен для организации файла в виде связного списка или мультисписка, в то время как ран домизатор, изображенный на рис. 6-4, полностью уни версален.
В-пятых, можно провести еще одно сравнение между деревьями и рапдомизаторами . Если учесть дополнитель ные требования к объему З У П Д , необходимые (при организации постоянного дерева) для однозначного де кодирования, то общий объем памяти на дисках опреде
ляется значением |
параметра |
Мй (табл. |
6-4). |
Д л я рандо- |
мнзаторов общий |
требуемый |
объем памяти |
на дисках |
|
указывается в последнем столбце табл . |
6-4. |
М о ж н о от |
||
метить близкие значения этого параметра для дерева и рандомизатора, изображенного на рис. 6-4, но сущест венно разные значения для дерева и рандомизатора, изо браженного на рис. 33. С другой стороны, если выходной уровень постоянного дерева содержит изображение пол ного ключа, то отличие в требуемом объеме З У П Д меж ду деревом и рандомизатором, изображенном на рис. 6-4, также незначительное, в то время как между деревом и рандомизатором, изображенном на рис. 6-5, весьма су щественное.
Резюмируя, следует отметить, что при выборе вида
декодера справочников следует |
учитывать |
следующие |
||
количественные |
характеристики: |
скорость |
декодирова |
|
ния, |
требования |
к объемам оперативной и внешней па |
||
мяти, |
сложность |
программирования, а т а к ж е |
качествен |
|
ные факторы: возможность поиска по диапазону и слу чайность, присутствующая при организации файла ме тодом связного списка.
В табл . 6-5 представлены основные результаты по сравнению методов декодирования, полученные при ана лизе приведенных в табл . 6-4 количественных и качест венных факторов . В таблицу включены как двухуров-
127
|
|
|
|
|
|
|
|
Т а б л и ц а 6-5 |
|
Сравнение |
декодеров справочников, рассмотренных в табл. 6-4 |
||||||||
|
|
|
Требуемые объемы |
|
|
|
|||
|
|
|
оперативной памтпі |
|
|
|
|||
|
|
|
|
(ЗУПД) |
|
|
"^Возмож |
|
|
Методы декодирова |
|
|
|
|
Скорость |
Легкость |
|||
|
|
|
|
ность |
|||||
ния справочников |
|
без |
учета |
с учетом |
декодчоо- |
поиска по |
программи |
||
|
|
|
неодно-Т |
г неодно-'' |
Гвэішя |
диапазону |
рован'»! |
||
|
|
|
значности |
значности |
|
|
|
||
|
|
|
декодера |
декодера |
|
|
|
||
Двухуровневое |
|
4 |
(2*) |
НП |
(4) |
1 |
Да |
1 |
|
постоянное дере |
|
|
|
|
|
|
|
||
во (СѴ=4) |
|
|
|
|
|
|
|
|
|
Трехуровневое |
по |
2 |
(2) |
НП |
(4) |
3 |
Да |
2 |
|
стоянное |
дерево |
|
|
|
|
|
|
|
|
(С,=4) |
|
|
|
|
|
|
|
|
|
Двухуровневое |
пе |
5 |
(4) |
НП |
(3) |
1 |
Нет |
3 |
|
ременное |
дерево |
|
|
|
|
|
|
|
|
( Q = 4 ) |
|
|
|
|
|
|
|
|
|
Трехуровневое |
пе |
3 |
(4) |
НП |
(3) |
3 |
я |
1 |
|
ременное 'дерево |
|
|
|
|
|
|
|
||
(С,=4) |
|
|
|
|
|
|
|
|
|
Рандомизатор |
|
1 |
(3) |
НП |
(2) |
4 |
|
1 |
|
(рис. 6-4) |
|
|
|
|
|
|
|
|
|
Рандомизатор |
|
1 |
(1) |
НП |
(I) |
2 |
|
2 |
|
(рис. 6-5) |
|
|
|
|
|
|
|
|
|
* Упорядочивание: меньшие |
номера соответствуют более оптимальным значениям |
|||||
параметров. НП означает неприменимо. |
|
|
|
|
||
невые, так и трехуровневые деревья |
(но только |
д л я |
С/= |
|||
= 4, т а к к а к |
это наиболее |
удобное значение дл я сравне |
||||
ния с Ct=2 |
дл я р а н д о м и з а т о р а ) . |
|
|
|
||
К а ж д ы й |
параметр |
или |
фактор |
(исключая |
возмож |
|
ность поиска по диапазону) |
с н а б ж е н |
номером. Чем |
опти |
|||
мальнее параметр, тем меньше номер. Так, например, по скорости декодирования лучшими оказываются двух
уровневые |
деревья, нежели |
рандомизатор, |
изображен |
||
ный на рис. 6-4. |
|
|
|
||
Е щ е раз |
заметим, |
что читатель долже н |
осторожно |
||
подходить |
к |
категорическим |
обобщениям |
результатов |
|
проведенного |
анализа, |
так как оценки полностью осно- |
|||
128 |
|
|
|
|
|
ваны на |
данных, приведенных в табл . 6-4. Эти |
данные |
||
в свою |
очередь |
основаны |
на выбранных рабочих |
пара |
метрах. |
|
|
|
|
|
6-6. |
СКОРОСТЬ |
ДЕКОДИРОВАНИЯ |
|
Скорость декодирования определяется сравнительно про
сто. Д л я |
этого надо вычислить время перемещения го |
|
ловок (в случае З У П Д с подвижными |
головками), время |
|
задержки |
при повороте дорожки, |
время считывания |
с дорожки, время обращения к оперативной памяти и учесть количество оборотов диска, потерянных при об
работке в оперативной |
памяти. |
Последовательность |
|||
рассмотренных событий |
для |
трехуровневого |
дерева |
||
с первым уровнем, |
хранимым |
в |
оперативной |
памяти, |
|
представлена в табл . |
6-6. В этом |
примере предполагает |
|||
ся, что декодер выполнен с использованием пакета дис ков I B M 2311. Кроме того, предполагается, что к а ж д ы й набор вершин третьего уровня, связанный с данной вер шиной второго уровня, хранится на том ж е цилиндре, что и вершина второго уровня. Поэтому нет необходимо сти перемещать головки между вторым и третьим уров
нями. Это |
справедливо |
при |
хранении |
дерева |
на |
диске |
|||||
|
|
|
|
|
|
|
|
Т а б л и ц а |
6-6 |
||
Время декодирования |
для |
трехуровневого дерева |
|
|
|||||||
|
|
|
|
|
|
|
|
Номинальное значе |
|||
Компоненты |
Уровень дерева |
Время |
(симво |
ние |
(среднее) |
для |
|||||
лическое) |
пакета |
дисков |
|||||||||
|
|
|
|
|
|
|
|
I BM 2311, млсек |
|||
Обработка записей в опе |
|
1 |
|
0 |
|
|
|
0 |
|
||
ративной |
памяти |
|
|
|
|
|
|
|
|
|
|
Подвод головок |
|
|
|
Р |
|
85 |
|
||||
Задержка при |
повороте |
|
|
|
|
|
|
12,5 |
|
||
Считывание с |
дорожки |
|
|
|
R |
|
|
25 |
|
||
Обработка |
записи |
|
2 |
|
|
0 |
|
|
0 |
|
|
Потерянный |
оборот |
|
|
|
R |
|
|
25 |
|
||
Считывание |
с |
дорожки |
|
|
|
R |
|
|
25 |
|
|
Обработка |
записи |
|
3 |
|
|
0 |
|
|
0 |
|
|
Сумма |
|
|
|
|
|
P + |
3.5Я |
|
172.5 |
|
|
9-88 |
|
|
|
|
|
|
|
|
|
|
129 |
с неподвижными головками или разом, общее время обращения время установления головок. В время декодирования равно:
на барабане . Таким об к З У П Д не учитывает общем случае среднее
|
|
Т3=Р |
+ ЗЖ |
|
|
(6-11) |
||
где |
Р — среднее время установления |
головок; |
R—-вре |
|||||
мя |
оборота диска. |
|
|
|
|
|
|
|
|
Эту формулу можно обобщить дл я /г-уровневого де |
|||||||
рева при хранении первого уровня 'в |
оперативной |
па |
||||||
мяти: |
|
|
|
|
|
|
|
|
|
Tn = P + l,5R + 2(n—2)R |
= P+(2n—2,5/?) |
при |
/ г > 1 . |
||||
|
|
|
|
|
|
|
(6-12) |
|
|
Предполагается, |
что |
после |
достижения цилиндра, |
||||
содержащег о вершины второго уровня, |
головки |
не |
бу |
|||||
дут передвигаться. В других случаях эта формула |
при |
|||||||
мет |
следующий вид. |
|
|
|
|
|
|
|
Д л я /г-уровневого |
дерева, у |
которого |
первый |
уровень |
||||
хранится в оперативной памяти |
и З У П Д |
с неподвижны |
||||||
ми |
головками: |
|
|
|
|
|
|
|
|
Tn=(2n—2,5)R |
при / і > 1 . |
|
(6-12а) |
||||
Д л я /г-уровневого дерева, у которого первый уровень хранится в З У П Д и З У П Д с подвижными головками, непосредственно связанные уровни хранятся на одном цилиндре:
Тп |
= Р+ |
(2/г + 0,5)/? при и > 0 . |
(6-126) |
Д л я /г-уровневого |
дерева, для которого |
первый уро |
|
вень хранится |
в З У П Д и З У П Д с подвижными головка |
||
ми, непосредственно связанные уровни хранятся на раз
ных цилиндрах: |
|
|
|
|
|
|
|
Tn = n(P+l,5R) |
при п > 0 . |
|
(6-12в) |
||
В табл . 6-7 представлена |
последовательность |
собы |
||||
тий дл я рандомизатора, изображенного |
на рис. 6-4, ко |
|||||
торому |
соответствует |
формула (6-12) |
дл я |
п = 3 |
или |
|
(6-126) |
дл я п = 2, а в |
табл . |
6-8 — последовательность |
|||
событий |
дл я рандомизатора, |
изображенного |
на рис. 6-5. |
|||
Его можно сравнить с одноуровневым деревом по фор
муле (6-126) дл я |
м = 1 или |
с |
двухуровневым деревом |
|
(первый |
уровень |
хранится |
в |
оперативной памяти) по |
формуле |
(6-12) для /г = 2. |
|
|
|
130