Математические модели и оптимальные методы реализации динамических структур данных

• Автор: Аксёнова, Елена Алексеевна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Петрозаводск
• Количество страниц: 124 с. : ил.

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

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

в двухуровневой памяти

1.1 Оптимальное управление одним стеком в двухуровневой памяти

1.1.1 Постановка задачи.

1.1.2 Математическая модель и матрица вероятностей переходов .

1.1.3 Решение задачи и результаты численных экспериментов

1.2 Оптимальное управление двумя параллельными стеками в двухуровневой памяти

1.2.1 Постановка задачи.

1.2.2 Математическая модель и матрица вероятностей переходов .

1.2.3 Решение задачи и результаты численных экспериментов
2 Оптимальное управление двумя ИГОочередями в памяти одного уровня
2.1 Постановка задачи
2.2 Связанное представление двух очередей
2.2.1 Математическая модель.
2.3 Страничное представление двух очередей.
2.3.1 Математическая модель и матрица вероятностей переходов .
2.3.2 Оптимальный размер страницы.
2.4 Решение задачи.
2.5 Результаты численных экспериментов.
3 Оптимальное управление очередью с двумя приоритетами в памяти одного уровня
3.1 Постановка задачи
3.2 Последовательное представление.
3.2.1 Математическая модель и матрица вероятностей переходов
3.3 Связанное представление
3.3.1 Математическая модель
3.4 Страничное представление.
3.4.1 Математическая модель и матрица вероятностей переходов
3.5 Решение задачи.
3.6 Результаты численных экспериментов.
4 Оптимальное управление тремя ИГОочередями в памяти одного уровня
4.1 Постановка задачи
4.2 Последовательное представление трех очередей
4.2.1 Математическая модель и матрица вероятностей переходов
4.3 Связанное представление трех очередей
4.3.1 Математическая модель
4.4 Страничное представление трех очередей.
4.4.1 Математическая модель и матрица вероятностей переходов
4.4.2 Оптимальный размер страницы
4.5 Решение задачи.
4.6 Результаты численных экспериментов.
5 Оптимальное управление тремя ИГОочередями на бесконечном времени
5.1 Постановка задачи
5.2 Последовательное представление трех очередей
5.2.1 Математическая модель и матрица вероятностей переходов
5.3 Связанное представление трех очередей
5.3.1 Математическая модель.
5.4 Решение задачи и результаты численных экспериментов .
Заключение
Литература


В диссертационной работе рассмотрены некоторые задачи оптимального представления нескольких FIFO-очередей в памяти одного уровня. Оптимальность понимается либо в смысле максимизации среднего времени работы до переполнения какой-либо очереди, либо в смысле минимизации доли потерянных элементов при бесконечном времени работы очередей. Первый критерий разумно применять в программных системах, когда переполнение какой-либо очереди может привести к остановке работы программы. Второй критерий уместен, например, в сетевых маршрутизаторах, когда пакеты, которые помещаются в переполненную очередь, просто теряются (’’сброс хвоста”) []. Потери пакетов приводят к нежелательному результату, поэтому число таких ситуаций необходимо свести к минимуму. Для организации РШО-очередей в памяти компьютера применяются два принципиально разных способа представления: последовательный и связанный []. Известны указатели на конец и начало очереди. В последовательном способе организации каждой очереди отводится определенная область памяти. При такой организации часто очередь зациклена, т. В связанном способе организации очередь представлена в виде связанного списка, каждый элемент которого состоит из двух единиц памяти, одна из которых используется для хранения информации, другая для хранения указателя на следующий элемент. В некоторых приложениях, например, в ряде версий операционных систем, для сетевых маршрутизаторов применяется некий промежуточный способ, когда очереди представлены в виде связанного списка буферов (страниц) одинаковой длины. В связанном представлении затраты памяти на хранение связей самые большие, в последовательном представлении таких затрат нет, но есть потери памяти за счет того, что при переполнении одной из очередей другая очередь заполнена не до конца. В страничном представлении есть затраты памяти первого и второго рода. В работах [, ] рассматривались задачи оптимального управления двумя РШО-очередями. Во многих приложениях требуется обработка записей с упорядоченными определенным образом ключами. Часто накапливается некоторый набор записей, после чего обрабатывается запись с максимальным значением ключа, затем, возможно, накопление записей продолжается, обрабатывается запись с наибольшим текущим ключом и т. Соответствующая структура данных, поддерживающая операции вставки нового элемента и удаления элемента с наибольшим приоритетом, называется очередью по приоритетам [, , ]. Существуют различные способы реализации очередей с приоритетами. Одним из часто используемых способов является представление N - приоритетной очереди в виде N Р1РО-очередей. Метод приоритетной очереди достаточно широко используется, например, как один из аппаратно-независимых методов управления перегрузками в технологии QoS. В операционной системе Cisco IOS реализация приоритетной очереди содержит четыре различные подочереди: high, medium, normal и low priority []. Целыо диссертационной работы является построение и анализ математических моделей и оптимальных методов реализации динамических структур данных, таких как стеки, очереди и приоритетные очереди. В качестве критериев оптимальности рассматриваются: минимальное среднее время, затрачиваемое на работу со стеком и на перераспределение памяти после переполнения или опустошения в случае работы с одним стеком в двухуровневой памяти, максимальное среднее время работы до перераспределения памяти после переполнения или опустошения в случае работы с двумя стеками в двухуровневой памяти, максимальное среднее время работы до переполнения выделенного объема памяти в случае работы с двумя и тремя FIFO-очередями и в случае работы с двухприоритетной очередью в памяти одного уровня, минимальная доля потерянных элементов при переполнении выделенного объема памяти в случае работы с тремя FIFO-очередями на бесконечном времени. Математические модели, описывающие процесс работы с одним стеком и двумя параллельными стеками в двухуровневой памяти. Математические модели, описывающие процесс работы с двумя и тремя FIFO-очередями в памяти одного уровня для последовательного, связанного и страничного способов представления.