Математическая модель оптимального управления настраиваемой очередью из двух последовательных циклических FIFO-очередей в общей памяти

Аннотация

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