О новом подходе к оценке квантилей времени отклика системы с разделением и параллельным обслуживанием заявок

Автор(ы): Горбунова А.В., Лебедев А.В.

Выпуск: 108

Рубрика: Системный анализ

Год: 2024

Библиография: Горбунова А.В., Лебедев А.В. О новом подходе к оценке квантилей времени отклика системы с разделением и параллельным обслуживанием заявок // Управление большими системами. Выпуск 108. М.: ИПУ РАН, 2024. С.6-21. DOI: https://doi.org/10.25728/ubs.2024.108.1

Дата опубликования: 31.03.2024

Ключевые слова: система с параллельным обслуживанием заявок, fork-join система массового обслуживания, время отклика, квантили распределения, имитационное моделирование

Аннотация: Предлагается новый подход к оценке квантилей распределения времени отклика системы массового обслуживания с разделением и параллельным обслуживанием заявок, для обозначения которой в англоязычной литературе используется термин fork-join. Рассматривается классический вариант данной системы с пуассоновским входным потоком и экспоненциальными временами обслуживания на однородных приборах. Заявки при поступлении в систему мгновенно разделяются на фиксированное число подзаявок и отправляются на обслуживание в соответствующие подсистемы с накопителем неограниченной емкости и одним прибором. Заявка считается обслуженной после обслуживания всех ее компонентов. Данная система позволяет смоделировать множество реальных процессов, для которых с целью увеличения эффективности характерно разделение крупных задач на более мелкие составляющие, например, системы параллельных или распределенных вычислений. Сложность анализа систем заключается в наличии зависимости между временами пребывания подзаявок, что значительно затрудняет анализ всех показателей производительности таких систем. Основным вкладом статьи является подход к~определению квантилей распределения времени отклика, оценка которых является не менее ценной по сравнению с оценкой среднего значения времени отклика. При этом вычислению математического ожидания посвящено гораздо большее количество работ в данной области, что объясняется в том числе сложностью проведения подобного анализа даже для данной характеристики, а оценка квантилей представляется еще более трудоемкой задачей.

Author(s): Gorbunova A., Lebedev A.

Article title: On a new approach to estimating response time quantiles of a fork-join queueing system

Issue: 108

Year: 2024

Keywords: system with parallel service of tasks, fork-join queueing system, response time, distribution quantiles, simulation modeling

Abstract: The article proposes a new approach to estimating the quantiles of the response time distribution of the fork-join queueing system. We consider a classic version of this system with a Poisson input flow and exponential service times on homogeneous servers. Upon receipt of tasks into the system, they are instantly divided into a fixed number of subtasks and sent for service to the appropriate subsystem with an unlimited capacity storage device and one server. The task is considered served after all its components have been serviced. This system allows you to simulate many real processes, which, in order to increase efficiency, are characterized by dividing large tasks into smaller components, for example, parallel or distributed computing systems. The difficulty of analyzing systems lies in the presence of a dependence between the sojourn times of subtasks, which significantly complicates the analysis of all performance characteristics of such systems. The main contribution of the article is the approach to determining the quantiles of the response time distribution, the assessment of which is no less valuable than the assessment of the mean response time. At the same time, a much larger number of works in this area are devoted to calculating the mean, which is explained, among other things, by the complexity of carrying out such an analysis even for a given characteristic, and estimating quantiles seems to be an even more laborious task.