Оптимальное управление двумя параллельными FIFO-очередями на бесконечном времени

Аннотация

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