Математические модели и алгоритмы оптимального управления динамическими структурами данных

• Автор: Соколов, Андрей Владимирович
• Шифр специальности: 05.13.18, 05.13.17
• Научная степень: Докторская
• Год защиты: 2006
• Место защиты: Петрозаводск
• Количество страниц: 301 с. : ил.

Оглавление
Введение

1 Динамическое распределение памяти

1.1 Базовые структуры данных

1.1.1 Линейные списки.

1.1.2 Стеки, очереди и деки.

1.1.3 Последовательное представление стека

1.1.4 Последовательное представление очереди .

1.1.5 Связанное представление линейных списков .

1.1.6 Список свободной памяти.

1.1.7 Последовательное представление нескольких

линейных списков.
1.1.8 Бинарные деревья
1.1.9 Произвольные деревья
1.1. Применение динамических структур в машинной графике.
1.1. Другие области применения стеков и очередей
1.1. Применение очередей в 1Ш1Хподобных системах .
1.2 Виртуальная память
1.2.1 Развитие способов адресации .
1.2.2 Организация обмена информацией между
уровнями памяти
1.2.3 Фрагментация памяти.
1.2.4 Методы динамического распределения нестраничной памяти.
1.3 Применение стеков в процессорах
1.3.1 Классификация стековых компьютеров
1.3.2 Методы управления памятью в стековых компьютерах.
1.3 3 Управление регистровыми окнами в ШБС
процессорах
2 Оптимальное управление стеками
2.1 Оптимальное управление одним стеком в двухуровневой памяти.
2.1.1 ЛЫнимизация среднего числа перераспределений стека
2.1.2 Минимизация среднего времени доступа с учетом потерь на перераспределения стека . .
2.2 Немарковская модель поведения стека .
2.2.1 Максимизация среднего времени .
2.2.2 Минимизация средних затрат времени с учетом перераспределения
2.3 Решение задачи Д. Кнута о двух стеках, растущих
навстречу друг другу
2.4 Оптимальное управление двумя стеками, растущими навстречу друг другу в двухуровневой памяти . .
2.4.1 Минимизация среднего числа перераспределений стеков .
2.4.2 Минимизация среднего времени доступа с учетом потерь на перераспределения стеков .
2.4.3 Оптимальное управление двумя параллельными стеками
2.5 Оптимальное расположение п стеков в памяти
2.6 Оптимальное распределение п стеков в памяти одного уровня .
2.6.1 Оптимальное начальное распределение памяти
2.6.2 Случай п
2.6.3 Оптимальное управление тремя стеками, допускающими только включения
2.6.4 Оптимальное управление четырьмя стеками,
допускающими только включения.
2.6.5 Оптимальное управление тремя стеками в
общем случае
2.6.6 Оптимальное распределение четырех и более
стеков в одноуровневой памяти
2.6.7 Оптимальное управление тремя стеками, ко
гда два стека растут навстречу друг другу, а третий растет навстречу им обоим одновременно
2.6.8 Математическая модель связанного метода
представления трех стеков.
2.6.9 Математическая модель страничного представления трех стеков
2.7 Оптимальное управление тремя стеками в двухуровневой памяти
2.8 Оптимальное управление п 4 стеками в двухуровневой памяти
3 Оптимальное управление очередями
3.1 Оптимальное управление одной очередью в двухуровневой памяти
3.1.1 Параметризованная реализация циклической
очереди в двухуровневой памяти
3.1.2 Математическая модель
3.1.3 Результаты вычислений
3.2 Оптимальное управление двумя циклическими оче
редями в случае раздельной реализации.
3.2.1 Оптимальное управление двумя циклическими очередями в случае раздельной реализации, когда разрешены только включения в очереди.
3.3 Математическая модель связанного представления двух очередей .
3.4 Математическая модель страничного представления двух очередей .
3.4.1 Выбор оптимального размера страницы
3.4.2 Матрица переходных вероятностей.
3.5 Численные результаты.
3.6 Оптимальное управление двумя очередями в случае, когда очереди двигаются друг за другом по кругу . .
3.6.1 Результаты экспериментов
3.7 Оптимальное управление к очередями в памяти одного уровня
3.8 Оптимальное управление очередями в общей памяти в случае, когда очереди принадлежат разным процессам
3.8.1 Случай раздельной последовательной циклической реализации.
3.8.2 Случай, когда очереди двигаются друг за другом по кругу.
3.9 Оптимальное управление очередями в общей памя
I ти в случае бесконечного времени блуждания
4 Оптимальные методы распределения памяти сегментами разных длин
4.1 Оценка минимального размера памяти, необходимого для динамического распределения сегментов разных длин
4.2 Оценка эффективности методов динамического распределения нестраничной памяти
4.2.1 Модель метода II.
4.2.2 Модель метода I
4.2.3 Модель метода ОРТI.
4.2.4 Модель метода динамического распределения памяти в ОС ЕС ЭВМ.
4.2.5 Анализ численных результатов
Приложение. Результаты численных экспериментов
Приложение 1. Результаты тестирования программ
Приложение 2. Анализ результатов
Литература


Отметим, что максимальную длину таких динамических объектов можно предсказать достаточно редко например, в статье получена такая оценка в случае применения очереди для алгоритмов заполнения областей в машинной графике, а если бы это даже удалось, то размещение многих объектов по максимуму было бы невозможно, тем более, что некоторые из них нужны лишь на небольшую долю общего времени выполнения программы и, следовательно, все они одновременно
почти никогда не будут заполнены на максимальную глубину. Здесь мы рассмотрим последовательную реализацию стека, когда элементы стека хранятся в последовательных элементах памяти, размер которых зависит от типа переменных, хранящихся в стеке. Мы представим параметризованную версию алгоритма с использованием шаблонов языка , предполагается, что версия транслятора поддерживает их реализацию, в которой тип элементов стека передается в класс как параметр. В данном примере с помощью параметризованного класса будут созданы стеки, хранящие элементы типа i, и Для операций включения и исключения элементов в стек сохранены традиционные названия и рор. Для хранения элементов используется массив х это член класса указатель на тип элемента стека , для указания на вершину стека переменная . Член класса п это размер выделяемого для стека массива. Переменная i это размер стека, который передается конструктору класса как параметр. Создаем стек с элементами типа i Создаем стек с элементами типа Создаем стек с элементами типа Используем стеки i, и , записывая и удаляя из каждого по одному элементу. В этой реализации возможны две ситуации переполнения стека, когда не хватает памяти для выполнения операции при вызове конструктора, или при выполнении функции . Эти ситуации в разных системах обрабатываются поразному. В главе 2 мы будем рассматривать задачи, в рамках которых сделана попытка обрабатывать такие ситуации некоторым оптимальным образом. Пусть в памяти размера п мы работаем с последовательной циклической очередью , . Здесь мы приведем параметризованную реализацию с использованием шаблонов языка и обозначений . Член класса это указатель на конец очереди, указатель на место, непосредственно перед началом очереди рис. Член класса п это размер выделяемого для очереди массива. Он на 1 больше размера очереди i, который передается как параметр конструктору класса , так как в циклической реализации , один элемент массива обычно оставляют свободным, чтобы отличить пустую очередь от переполненной. Можно вместо этого хранить длину очереди, но это эквивалентно потере одной ячейки. Метод класса помещает элемент в конец очереди, а рор исключает элемент из начала очереди. Если догнал Я, то произошло опустошение очереди, а если К догнал рис. В функции i приведены примеры использования данного класса для нескольких типов данных элементов очереди. Невозможно создать очередь. Создаем очередь с элементами типа Используем очереди i, и , записывая и удаляя из каждой по одному элементу. Обычно ситуация опустошения означает условие окончания какоголибо процесса, а в ситуации переполнения происходит аварийное завершение по переполнению или другое действие. В главе 3 мы будем рассматривать задачи, где ситуация переполнения очереди обрабатывается неким оптимальным образом. Связанное представление списков подразумевает хранение элементов в произвольных ячейках памяти и связь между элементами с помощью адресов , . Операции работы со стеками и очередями в связанном представлении мы не будем здесь отдельно приводить, так как они достаточно полно описаны в литературе 1, . Отметим только, что в примере алгоритма заполнения областей в машинной графике будет использована связанная реализация очереди, а реализация связанного стека будет описана в следующем пункте на примере списка VI. Нужно сказать, что при связанном представлении стеков и очередей проблема переполнения не исчезает, а в некотором смысле даже усугубляется, так как связанное представление требует дополнительной памяти на связи, однако переполнение теперь возникает только когда свободной памяти больше нет вообще. В последовательном представлении потерь на связи нет, но есть потери памяти за счет того, что при переполнении одного из стеков, другие заполнены не до конца. Заметим, что в литературе, например,, с.