Обзор систем параллельной обработки заявок

Данная работа является первой в серии из двух статей, посвящённых обзору систем массового обслуживания вида «fork-join» (в западной классификации) или системам с расщеплением запросов. Указанная система является естественной моделью для многих других реальных систем. В статье описаны особенности построения этой модели и родственных ей систем, основные их характеристики. Отдельное внимание уделяется методам анализа времени отклика системы. Поскольку точное выражение для среднего времени отклика известно только для случая двух приборов, в статье приведено подробное описание подхода к получению точного выражения этой характеристики. Для случая, когда число приборов больше двух, различными методами получены аппроксимации среднего времени отклика,что объясняется сложностью исследований из-за существующей зависимости между очередями под запросов в силу общих моментов поступления. В работе представлено несколько методов приближенного анализа: различные варианты эмпирической аппроксимации, т.е. методы, уточняющие полученные характеристики благодаря использованию результатов имитационного моделирования; интерполяция с помощью предельных значений загрузки системы в случаях с отличными от экспоненциального распределениями для входящего потока и времени обслуживания.

A Survey on Queuing Systems with Parallel Servingof Customers

This paper is the first in a series of two articles devoted to the review of “fork-join” (inthe western classification) queuing systems or systems with the splitting of incoming queries.This system is a natural model for many other real systems. The article describes the fork-joinqueueing model construction and main characteristics of this model. Special attention is paid tomethods of analysis of the response time of the system. Since the exact expression for the meanresponse time is known only for the case of two servers, the article gives a detailed descriptionof the approach to obtaining an accurate expression of this characteristic. For the case whenthe number of servers is more than two, approximations of the mean response time are obtainedby different methods, which is explained by the complexity of the studies due to the existingdependence between the queues of subqueries due to common arrival moments. The paperpresents several methods of approximate analysis: various variants of empirical approximation,i.e. methods that refine the obtained characteristics by using the results of simulation modeling;interpolation methods using system load limit values in cases when the incoming flow and servicetime distributions are not exponential.