МОДЕЛЬ УПРАВЛЕНИЯ ДВУМЯ ПАРАЛЛЕЛЬНЫМИ FIFO-ОЧЕРЕДЯМИ, ДВИГАЮЩИМИСЯ ДРУГ ЗА ДРУГОМ В ОБЩЕЙ ПАМЯТИ

Постановка проблемы: при разработке многих аппаратных и программных приложений применяют структуру данных «FIFO-очередь». В различных сетевых устройствах и встроенных операционных системах применяется несколько FIFO-очередей, расположенных в общем пространстве памяти. Также существуют архитектуры многоядерных процессоров, где каждому ядру выделено две FIFO-очереди. Программные и аппаратные решения, применяемые для реализации описанных задач, должны увеличивать надежность (снижение доли потерянных при переполнении памяти элементов очередей) работы таких устройств. Цель: построение и анализ математической модели процесса работы с двумя FIFO-очередями, двигающимися друг за другом по кругу, в общей памяти, где на нечетном шаге происходят операции включения элементов в одну из очередей, а на четном шаге — исключения (возможно как последовательное, так и параллельное выполнение операций). Результаты: построены математическая и имитационная модели этого процесса для двух очередей и проведены численные эксперименты, основывающиеся на теоретических данных. Математическая модель представлена в виде случайного блуждания по целочисленной пирамиде с отражающими экранами. Предложен алгоритм нумерации состояний, установлен вид матрицы переходных состояний полученной регулярной цепи Маркова (доказаны соответствующие утверждения), разработаны алгоритм и программа вычисления средней доли потерянных при переполнении элементов очередей. Особенностью данного исследования является специфическое выполнение операций над очередями: включение и исключение элементов происходит в зависимости от шага (были сделаны поправки для сохранения качеств однородности и регулярности цепи) и создана возможность выполнять операции параллельно. Практическая значимость: предложенные модель, алгоритм и программный комплекс для анализа метода движения очередей -друг за другом» могут применяться при проектировании сетевых устройств, например маршрутизаторов, микросхем, реализующих работу с несколькими FIFO-очередями, и других программных и аппаратных устройств, где потери элементов являются допустимой, но нежелательной ситуацией. С помощью разработанной модели можно, при заданных вероятностных характеристиках очередей, выбрать лучший метод представления очередей, например, из двух методов — классического последовательного циклического метода или метода «Друг за другом».

• Соколов А.В.
• Барковский Е.А.

• Общий отдел

• Технические науки. Промышленность
• Физико-математические науки