ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ ДВУМЯ ПАРАЛЛЕЛЬНЫМИ FIFO-ОЧЕРЕДЯМИ НА БЕСКОНЕЧНОМ ВРЕМЕНИ

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

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

• Общий отдел

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