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

В настоящее время все более востребованными становятся устройства с жесткими ограничениями на ресурсы памяти, например, различные сетевые и мобильные устройства, что вызывает особые требования к алгоритмам управления памятью. В связи с этим актуальной является задача разработки математических моделей и алгоритмов оптимального управления базовыми динамическими структурами данных, такими как стеки, очереди и приоритетные очереди.

Стеком LIFO (Last In First Out) называется линейный список, в котором все включения и исключения (и обычно всякий доступ) происходят на одном конце, который называется вершиной стека. Другой по отношению к вершине конец стека называется началом стека. Очередью FIFO (First In First Out) называется линейный список, в котором все включения происходят на одном конце (конец очереди), а все исключения (и обычно всякий доступ) происходят на другом конце (начало очереди) [25]. Под линейным списком будем понимать множество узлов, структурные свойства которого ограничиваются лишь их линейным (одномерным) относительным положением.

Понятие стека широко используется при разработке программного и аппаратного обеспечения. Стеки используются в алгоритмах синтаксического разбора [16, 34, 35], для анализа скобочной структуры текста и вычисления выражений [29], в алгоритмах машинной графики [39], в алгоритмах поиска на графах [25, 30], в алгоритмах сортировки [26, 40], в системе управления процессами [33, 38, 45], при разработке архитектуры [17, 22, 23, 27, 33, 44]. При разработке RISC процессоров для работы со скалярными аргументами и локальными переменными функций организуются перекрывающиеся окна регистров постоянного или переменного размеров [47, 51]. В этом случае получаем один стек с элементами типа «окно» в главной памяти, у которого несколько верхних элементов образуют циклический стек на регистрах. В архитектуре Intel Itanium [60] у каждой процедуры есть регистровый стек с элементами переменного размера для хранения параметров. Выходные параметры одной процедуры являются входными параметрами другой. В процессорах Intel, Motorola и др. стек наращивается в сторону уменьшающихся значений адресов памяти. Это означает, что указателю позиции вершины того или иного стека первоначально присваивается значение самого старшего адреса области памяти, предоставляемой для организации данного стека [36, 37].

При переполнении или опустошении регистровой вершины стека на практике применяют несколько программных и аппаратных методов, которые имеют преимущества по сравнению с универсальными алгоритмами замещения кэш-памяти [51, 59]:

1. Large Stack. Можно сделать стек большим и предполагать, что переполнения не будет, а если оно все же произошло, то совершить аварийное завершение работы.

2. Demand fed single element stack manager. В этой стратегии вершина стека реализована аппаратно, как циклический буфер, а продолжение стека находится в памяти. При переполнении и опустошении аппаратного стека перемещается один элемент (или несколько элементов) в память из буфера или наоборот.

3. Paging stack manager. В этом методе вершина реализована программно как часть специальной памяти. При опустошении вершины стека из памяти копируется половина буфера, а при переполнении нижняя половина буфера перемещается в память, верхняя половина перемещается в начало буфера.

4. Barometr-Pointer Algorithm. Предлагались реализации стека, когда перемещения элементов между уровнями памяти происходят не при переполнении или опустошении, а при отклонении от оптимального состояния вершины (обычно считается, что это половина быстрого буфера) в фоновом режиме, т. е. параллельно с обычным выполнением команд (аналог опережающей подкачки и откачки в страничной виртуальной памяти).

5. An associative cashe. Кэш-память для стековых машин не дает преимуществ по сравнению с рассмотренными методами, т.к. сложнее для аппаратной реализации и в тоже время не учитывает специфики стека как структуры LIFO. Но, если в стек нужно помещать структуры данных переменного размера, такие как строки и структуры, использование кэш-памяти может быть целесообразно.

Во всех этих методах вершина стека является продолжением стека, находящегося в памяти второго уровня.

Возможны также аппаратные методы реализации, когда вершина стека является копией стека, находящегося в памяти второго уровня. Тогда запоминание элементов при переполнении не нужно, а требуется лишь восстановление при опустошении [47].

В работах [31, 50] в качестве теоретической модели, описывающей управление вершиной стека в двухуровневой памяти, было предложено одномерное случайное блуждание [46]. На базе этой модели решалась задача определения оптимального количества элементов вершины стека в быстрой памяти, которое должно оставаться после перераспределения. Однако, некоторые специалисты [48] считают, что модель классического случайного блуждания недостаточно точно описывает поведение стеков, а более адекватной была бы модель, в которой вероятность следующей операции со стеком зависит от того, какая операция была предыдущей. Простейшая такая модель, описывающая поведение одного стека в двухуровневой памяти, предложена в [1, 7].

Если рассмотреть несколько стеков (процессов) и общий ресурс быстрой памяти, то можно показать, что встречное расположение стеков в виде пар стеков, растущих навстречу друг другу, лучше раздельного, если в качестве критерия оптимальности выбрано среднее время работы стеков до переполнения [42, 58]. Задача построения математической модели такого способа распределения памяти была поставлена Д. Кнутом [25]. Исследовалось поведение двух стеков, расположенных в памяти объема т и растущих навстречу друг другу. В этом случае место встречи стеков можно рассматривать как случайную величину. Известно, что на каждом шаге с вероятностью р может произойти исключение элемента из одного из стеков, с вероятностью 1 — р может произойти включение информации в один из стеков. Пусть М{т, р) математическое ожидание случайной величины max (ki, ?2), где ki и длины стеков при встрече. Задача состоит в том, чтобы установить вид функции М (т, р). В [41] предложен алгоритм вычисления М (т, р) для конечных значений т. Для решения задачи использовалась теория поглощающих цепей Маркова [24]. В [61] решалась задача исследования М (т, р) при т —* оо для 0.25 < р < 0.5. В [49, 52, 53] исследовалось асимптотическое поведение размеров стеков при переполнении и времени работы до переполнения памяти для 0 < р < 0.25. В [54] решалась задача для случая, когда вероятности включения и исключения информации зависят от размеров стеков. В [42, 55, 58] предложены марковские модели для решения задач управления несколькими стеками. В [14] исследовалась задача управления двумя параллельными стеками в двухуровневой памяти.

FIFO-очереди используются в компьютерных сетях, операционных системах, графических системах, устройствах промышленной автоматики. Ряд американских фирм выпускает микросхемы, реализующие работу с несколькими FIFO-очередями (IDT Inc. [32], Cypress, AverLogic Technologies). В диссертационной работе рассмотрены некоторые задачи оптимального представления нескольких FIFO-очередей в памяти одного уровня. Оптимальность понимается либо в смысле максимизации среднего времени работы до переполнения какой-либо очереди, либо в смысле минимизации доли потерянных элементов при бесконечном времени работы очередей. Первый критерий разумно применять в программных системах, когда переполнение какой-либо очереди может привести к остановке работы программы. Второй критерий уместен, например, в сетевых маршрутизаторах, когда пакеты, которые помещаются в переполненную очередь, просто теряются («сброс хвоста») [18]. Потери пакетов приводят к нежелательному результату, поэтому число таких ситуаций необходимо свести к минимуму.

Для организации FIFO-очередей в памяти компьютера применяются два принципиально разных способа представления: последовательный и связанный [25]. Известны указатели на конец и начало очереди. В последовательном способе организации каждой очереди отводится определенная область памяти. При такой организации часто очередь зациклена, т. е. при достижении концом очереди конечной границы выделенной области памяти следующие включения элементов будут происходить с начальной границы, если есть свободная память. В связанном способе организации очередь представлена в виде связанного списка, каждый элемент которого состоит из двух единиц памяти, одна из которых используется для хранения информации, другая для хранения указателя на следующий элемент. В некоторых приложениях, например, в ряде версий операционных систем, для сетевых маршрутизаторов применяется некий промежуточный способ, когда очереди представлены в виде связанного списка буферов (страниц) одинаковой длины. В связанном представлении затраты памяти на хранение связей самые большие, в последовательном представлении таких затрат нет, но есть потери памяти за счет того, что при переполнении одной из очередей другая очередь заполнена не до конца. В страничном представлении есть затраты памяти первого и второго рода.

В работах [12, 43] рассматривались задачи оптимального управления двумя FIFO-очередями.

Во многих приложениях требуется обработка записей с упорядоченными определенным образом ключами. Часто накапливается некоторый набор записей, после чего обрабатывается запись с максимальным значением ключа, затем, возможно, накопление записей продолжается, обрабатывается запись с наибольшим текущим ключом и т. д. Соответствующая структура данных, поддерживающая операции вставки нового элемента и удаления элемента с наибольшим приоритетом, называется очередью по приоритетам [21, 28, 40].

Существуют различные способы реализации очередей с приоритетами. Одним из часто используемых способов является представление N — приоритетной очереди в виде N FIFO-очередей. Приложениями очередей по приоритетам являются системы моделирования, в рамках которых ключи могут соответствовать моментам возникновения событий, что обеспечивает возможность их обработки в хронологическом порядке, системы планирования заданий в компьютерных системах, где ключи могут соответствовать приоритетам, указывающим, какой из пользователей должен быть обслужен первым. Метод приоритетной очереди достаточно широко используется, например, как один из аппаратно-независимых методов управления перегрузками в технологии QoS. В операционной системе Cisco IOS реализация приоритетной очереди содержит четыре различные подочереди: high, medium, normal и low priority [18].

Целыо диссертационной работы является построение и анализ математических моделей и оптимальных методов реализации динамических структур данных, таких как стеки, очереди и приоритетные очереди. В качестве критериев оптимальности рассматриваются: минимальное среднее время, затрачиваемое на работу со стеком и на перераспределение памяти после переполнения или опустошения в случае работы с одним стеком в двухуровневой памяти, максимальное среднее время работы до перераспределения памяти после переполнения или опустошения в случае работы с двумя стеками в двухуровневой памяти, максимальное среднее время работы до переполнения выделенного объема памяти в случае работы с двумя и тремя FIFO-очередями и в случае работы с двухприоритетной очередью в памяти одного уровня, минимальная доля потерянных элементов при переполнении выделенного объема памяти в случае работы с тремя FIFO-очередями на бесконечном времени.

Основными результатами диссертации являются:

Заключение

.

В диссертационной работе предложены математические модели и оценки эффективности основных способов представления динамических структур данных в памяти одного и двух уровней для различных критериев оптимальности. Предполагалось, что известны вероятностные характеристики рассматриваемых структур данных.

Для практики может представлять интерес анализ последовательного представления очередей, когда память делится не оптимально в зависимости от вероятностных характеристик очередей, а просто поровну между очередями. Так логично поступать, если не известны вероятностные характеристики очередей. В дальнейших исследованиях было бы интересно сравнить эффективность такого способа организации работы со структурами данных с методами, рассмотренными в диссертационной работе.

Также для практики интересно обобщить результаты диссертации на алгоритмы работы с большим числом очередей и другими дисциплинами обслуживания, например, со справедливыми взвешенными очередями [18]. Для решения этих задач целесообразно применить метод имитационного моделирования.