Публикации
Барковский Е.А., Соколов А.В.
Модель управления двумя параллельными FIFO-очередями, двигающимися друг за другом в общей памяти
// Информационно-управляющие системы, № 1 (80). 2016. C. 65-73
Ключевые слова: структуры данных, data structures, fifo-очереди, случайные блуждания, random walks, регулярные марковские цепи, regular markov chains, fifo queues
Постановка проблемы: при разработке многих аппаратных и программных приложений применяют структуру данных «FIFO-очередь». В различных сетевых устройствах и встроенных операционных системах применяется несколько FIFO-очередей, расположенных в общем пространстве памяти. Также существуют архитектуры многоядерных процессоров, где каждому ядру выделено две FIFO-очереди. Программные и аппаратные решения, применяемые для реализации описанных задач, должны увеличивать надежность (снижение доли потерянных при переполнении памяти элементов очередей) работы таких устройств. Цель: построение и анализ математической модели процесса работы с двумя FIFO-очередями, двигающимися друг за другом по кругу, в общей памяти, где на нечетном шаге происходят операции включения элементов в одну из очередей, а на четном шаге - исключения (возможно как последовательное, так и параллельное выполнение операций). Результаты: построены математическая и имитационная модели этого процесса для двух очередей и проведены численные эксперименты, основывающиеся на теоретических данных. Математическая модель представлена в виде случайного блуждания по целочисленной пирамиде с отражающими экранами. Предложен алгоритм нумерации состояний, установлен вид матрицы переходных состояний полученной регулярной цепи Маркова (доказаны соответствующие утверждения), разработаны алгоритм и программа вычисления средней доли потерянных при переполнении элементов очередей. Особенностью данного исследования является специфическое выполнение операций над очередями: включение и исключение элементов происходит в зависимости от шага (были сделаны поправки для сохранения качеств однородности и регулярности цепи) и создана возможность выполнять операции параллельно. Практическая значимость: предложенные модель, алгоритм и программный комплекс для анализа метода движения очередей «друг за другом» могут применяться при проектировании сетевых устройств, например маршрутизаторов, микросхем, реализующих работу с несколькими FIFO-очередями, и других программных и аппаратных устройств, где потери элементов являются допустимой, но нежелательной ситуацией. С помощью разработанной модели можно, при заданных вероятностных характеристиках очередей, выбрать лучший метод представления очередей, например, из двух методов - классического последовательного циклического метода или метода «Друг за другом».
Индексируется в РИНЦ
Последние изменения: 19 мая 2016