A Survey on Queuing Systems with Parallel Servingof Customers

Cover Page

Abstract


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.


1. Введение Название исследуемой системы с параллельной обработкой запросов или с расщеплением запросов не имеет утвердившегося в русском языке терминологического аналога, в англоязычной же литературе используется термин «fork-join queueing system» [1-3]. Интерес к указанной системе объясняется тем, что она является естественной моделью для многих других реальных систем. В качестве примеров можно привести сферу обслуживания, медицинские приложения, производственные системы, системы облачных вычислений и др. [4]. Если же говорить об информационных технологиях, то прежде всего стоит упомянуть распределённые вычисления, технология которых оказала значительное влияние и на концепцию облачных вычислений, а также параллельные вычисления, например обработку пакетов данных, телефонных вызовов и др. Однако, несмотря на широкий спектр задач, которые решаются с помощью систем массового обслуживания с параллельной обработкой запросов, и их популярность среди зарубежных авторов, в нашей стране данная система исследовалась значительно меньше [4-9]. Статья организована следующим образом: в разделе 2 описываются особенности построения системы с расщеплением запросов и родственных ей систем, в разделе 3 подробно описан метод точного анализа среднего времени отклика для случая расщепления на два подзапроса, в разделе 4 представлены два метода аппроксимации среднего времени отклика, в заключении кратко подведены итоги и анонсировано содержание второй части работы. 2. Системы параллельного обслуживания заявок Общая идея функционирования системы fork-join (рис. 1) заключается в следующем: на вход поступает поток заявок (запросов) в момент поступления в точке «расщепления» (англ. fork point) заявка разделяется на родственных заявок (подзапросов): каждая из которых отправляется в очередь на обслуживание к приборам или серверам с номерами 1, 2, . . . , соответственно. Предполагается, что запросы имеют одну и ту же структуру и каждый сервер предназначен для выполнения конкретных задач: подзапрос может обслуживаться только на -м сервере, Обработанные подзапросы попадают в буфер синхронизации, где дожидаются родственных им подзапросов. В момент поступления последнего родственного подзапроса одного из запросов происходит их синхронизация, т.е. объединение, после чего обработанный запрос покидает систему. Здесь и далее будем считать,что синхронизация происходит мгновенно. Рис. 1. Система массового обслуживания типа fork-join Стоит отметить, что описанную модель рассматривают и как сеть массового обслуживания (СеМО): после расщепления подзапросы одновременно поступают на вход ветвей, которые представляют собой одноканальные системы массового обслуживания (СМО) с очередями. Однако данный подход предполагает дальнейший переход к рассмотрению независимых СМО, что является упрощающим допущением в силу существующей зависимости между очередями подзапросов вследствие общих моментов поступления. Тем не менее таких сложностей не возникает для случая, когда каждая подсистема состоит из бесконечного числа приборов [6, 7]. Анализ SPM (splitting and matching queueing system) системы массового обслуживания в [10] является одной из самых ранних работ на эту тему. В ней рассматриваются авиапассажиры и их багаж, которые прибывают вместе на самолёте в аэропорт, но разделены до тех пор, пока пассажиры не получат свои вещи в зоне выдачи багажа. В этой статье анализируется система с двумя ветвями ||1, т.е. с детерминированным входящим потоком и экспоненциальным временем обслуживания на каждом из серверов. SM (split-merge queueing system) система является одним из вариантов fork-join системы массового обслуживания (рис. 2). Её отличие заключается в том, что на свободные серверы не поступит ни один подзапрос следующего запроса до того момента, пока не обслужатся все подзапросы текущего запроса [11], т.е. происходит блокировка каждого освободившегося сервера до окончания обработки всех задач запроса. Рис. 2. Система массового обслуживания типа split-merge FF (fission-fusion queueing system) система - это ещё одна разновидность forkjoin системы (рис. 3). Если допустить, что все подзапросы являются идентичными и неразличимыми: , то запрос может покинуть систему после обработки любых подзапросов, иначе говоря, подзапросы могут принадлежать разным запросам [11]. Рис. 3. Система массового обслуживания типа fission-fusion Модель независимых серверов (independent server model, ISM) представляет собой многоканальную систему массового обслуживания. Для обслуживания поступившего запроса требуется случайное число серверов, не превышающее их общее количество, причём обслуживание очередного запроса не может начаться до тех пор, пока число свободных серверов не станет по крайней мере равно числу серверов, требуемых для обслуживания. В частности, в работе [12] рассматриваемая система состоит из однородных серверов, времена обслуживания являются независимыми и имеют экспоненциальное распределение. Входящий поток является пуассоновским, а число серверов, требуемых для обработки запроса, определяется некоторой вероятностью. Запросы обслуживаются в порядке поступления (First Come First Served, FCFS) и могут покинуть систему только после освобождения всех затребованных серверов. Поскольку времена обслуживания на отдельных серверах являются независимыми, то сервер, закончивший обслуживание запроса, становится доступным для других задач. Таким образом, время обслуживания запроса является максимумом случайного числа экспоненциально распределённых случайных величин. Для модели были получены такие характеристики, как распределение времени обслуживания, распределение числа занятых серверов, а также достаточные условия для существования стационарного распределения. В случае модели группового обслуживания (team service model, TSM), так же как и в случае ISM системы, для обработки задач требуется наличие нескольких свободных серверов одновременно, но при этом серверы начинают обслуживание этих задач и освобождаются одновременно [13,14]. Также существует такой вариант fork-join системы, когда поступающие на вход в систему несколько потоков запросов делятся на подзапросы и отправляются на обслуживание на серверы в соответствии с заданной матрицей вероятностей, т.е. запросы поступают как независимых потоков, затем делятся на части, которые распределяются по серверам в соответствии с некоторой стратегией (политикой), которая и определяется матрицей [15, 16]. Первые результаты исследования fork-join системы массового обслуживания были получены для случая расщепления заявки на два подзапроса 1 , 2 с пуассоновским входящим потоком и экспоненциальным временем обслуживания на обоих серверах [17]. Однако несмотря на марковость предположений анализ fork-join систем массового обслуживания даже для случая = 2 затруднителен по следующим причинам: процессы поступления подзапросов на серверы коррелируют; модель описывается двумерной цепью Маркова с бесконечным числом состояний для каждой размерности. В силу указанных выше факторов точного решения для распределения числа подзапросов в fork-join системе не было найдено. Но при этом для случая пуассоновского входящего потока и экспоненциальных времён обслуживания можно получить явные выражения для маргинальных вероятностей [4]. Приближенное же решение для распределения числа подзапросов в случае очередей неограниченных размеров может быть получено для достаточно большой ёмкости накопителя - такой, что вероятность потери запросов в связи с этой большой ёмкостью будет пренебрежимо мала, и в данном случае будут применимы итерационные численные методы решения систем линейных уравнений большой размерности [18]. Большинство авторов в своих работах исследуют один из основных показателей качества функционирования подобных систем массового обслуживания - время отклика где - случайная величина времени пребывания подзапроса в системе до его попадания в буфер синхронизации, Стоит сразу отметить, что точное выражение для среднего времени отклика было получено только для fork-join системы с двумя ветвями в [1] с помощью результатов работы [17]. Для случая > 2 с помощью различных методов были получены аппроксимации среднего времени отклика. 3. Анализ системы с двумя ветвями M|M|1 Модель цепи Маркова с непрерывным временем для fork-join системы с двумя ветвями ||1 и накопителем неограниченной ёмкости рассматривается в [17]. Этот анализ был расширен для ветвей в [19]. Для изучения стационарного и нестационарного режимов основной краевой задачи (дифференциальное уравнение вместе с набором дополнительных ограничений) в работе [19] использовались методы исследования функций комплексной переменной, представленные, например, в [20]. В ходе последующего обсуждения более подробно остановимся на анализе статьи [17], поскольку она ведёт к точному решению задачи для fork-join системы с двумя ветвями | |1. Итак, рассмотрим fork-join систему, попадая в которую запрос расщепляется на = 2 подзапроса, входящий поток является пуассоновским с интенсивностью = 1, а интенсивности обслуживания на двух серверах удовлетворяют условию: 1 < 1 6 2 , гарантируя, что со временем система не переполнится, т.е. число подзапросов не устремится к бесконечности. Поведение системы описывается непрерывным марковским процессом - число подзапросов -го типа, соответственно Указанные состояния интерпретируются следующим образом: если 0} в некоторый момент времени , то в системе находится заявок 1-го типа, т.е. 1 , и заявок 2-го типа, т.е. - стационарная вероятность указанного состояния. Далее записывается система уравнений равновесия в терминах двойной производящей функции [17,21, 22]: Анализ производящей функции позволяет получить выражения для , которые для симметричного случаяравны между собой: Также с помощью преобразований производящей функции в граничных точках: в [17] были получены асимптотические выражения для стационарных вероятностей состояний соответственно. Это ещё раз свидетельствует о том, что данная задача требует более совершенных математических методов решения. Используя результаты анализа в [17], среднее время отклика для fork-join системы с двумя симметричными ветвями выводится в Приложении B в [1]. Интенсивность пуассоновского входящего потока имеет значение , интенсивности обслуживания на двух серверах раны , т.е. 1 = 2 = , причём < , так, что нагрузка на каждый из серверов = / меньше единицы: Вывод [ 2,max ] основан на наблюдении, что эта величина есть сумма времени пребывания в системе ||1, т.е. 1,max , и времени, проведённого подзапросом в системе после обслуживания на сервере в ожидании второго, и до ухода из неё (время синхронизации) : [ 2,max ] = [ 1,max ] + []. Согласно формуле Литтла, = 2[], где - это среднее число подзапросов, которые обслужились на приборе и ждут свою пару [22-24]. Через обозначим вероятность того, что число подзапросов во второй очереди превышает число подзапросов в первой очереди на . Благодаря симметрии = - , > 1 и, таким образом, Из уравнений, представленных в [1], можно получить: Тогда = +1 + ,0 , где ,0 - это вероятность того, что в первой очереди находится подзапросов, а во второй - ноль. Далее с учётом формулы (1) можем записать: Затем подставляем в формулу для времени синхронизации выражение для из (2) и меняем порядок суммирования: Потом вычисляем значения первой и второй производной при = 1 от выражения для производящей функции (, 0), полученном в (3) и от выражения, которое записывается исходя из определения этой функции: Теперь можем подставить полученные формулы в (4): следовательно, среднее время отклика определяется следующим выражением: 4. Аппроксимация времени отклика 4.1. Эмпирическая формула аппроксимации Один из способов аппроксимации времени отклика для fork-join системы с ветвями ||1 и одинаковыми интенсивностями обслуживания на серверах был предложен в [1]. Идея предложенного метода аппроксимации появилась из наблюдения за поведением времени отклика при проведении численных экспериментов. Верхнюю границу для среднего времени отклика можно получить, сделав допущение о независимости случайных величин времён пребывания подзапросов в системе, или, что тоже самое, рассмотреть СеМО, состоящую из независимых параллельно функционирующих систем | |1. Данное предположение подтверждается приведённым в [1] доказательством того факта, что случайные величины времён пребывания подзапросов в системе являются положительно ассоциированными. По определению [25] две случайные величины и являются положительно ассоциированными, если [ ()()] > [ ()][()], т.е. ковариация любых пар неубывающих функций и является неотрицательной, а одно из свойств положительно ассоциированных случайных величин 1 , 2 , . . . заключается в том, что [25] Нижняя граница для среднего времени отклика получается, если «пренебречь» очередями (т.е. для значений близких к нулю): в этом случае время отклика будет являться максимумом независимых одинаково распределённых случайных величин (н.о.р.с.в.) со средним 1/. Таким образом, имеем: то частичная сумма гармонического ряда. Верхняя и нижняя границы растут с одной и той же скоростью , иными словами, для больших значений границы имеют порядок (ln ). Поэтому, зная значение [ 2,max ] , можем записать: [ ,max ] ≈ () [ 2,max ] , где () - это коэффициент масштабирования, растущий со скоростью (ln ). Следовательно, аппроксимация времени отклика может быть представлена в следующем виде: = ()+() . Поскольку по определению 2 () = 1, то, подставив это значение в предыдущее выражение, получим, что () = (1 - ())/ 2 , таким образом, Посредством имитационного моделирования в [1] определяется значение () ≈ 4/11. Окончательно имеем Полученное приближение, исходя из численного анализа, проведённого авторами, имеет погрешность аппроксимации, не превышающую 5% для значений 2 6 6 32. В статье [26] исследуется аналогичная fork-join система с ветвями ||1. Полученная аппроксимация является средним арифметическим верхней и нижней оценок. В качестве верхней оценки используется видоизменённое выражение для верхней оценки из вышеупомянутой работы [1]. Нижняя оценка получается при анализе эквивалентной величины времени отклика, но для системы с непараллельной организацией очереди [27]. Итак, Далее вычисляется среднее арифметическое полученных оценок, в результате чего имеем: 4.2. Интерполяция с помощью предельных значений загрузки системы В [28] предложен другой метод аппроксимации времени отклика - комбинация методов интерполяции высокой и слабой входных нагрузок (heavy and light traffic interpolation approximations). Указанные техники в отличие от описанного выше метода не используют результаты имитационного моделирования, однако их применение может быть расширено и до анализа fork-join систем не только с экспоненциальным временем обслуживания или c пуассоновским входящим потоком. Для рассматриваемой задачи найти решение в аналитическом виде очень затруднительно, однако возможно получить асимптотические формулы для искомых характеристик. Интерполяция слабой загрузкой системы является результатом её работы в режиме слабой нагрузки, т.е. когда интенсивность входящего потока очень мала. В этом случае целесообразно обратиться к разложению в ряд Тэйлора характеристик производительности системы (в частности, функции распределения времени отклика - как функции от - в окрестности нуля), с помощью которого можно определить неизвестные величины в представлении исследуемой функции в виде полинома от порядка . Рассматриваются только полиномы нулевой и первой степени. Если же говорить об интерполяции с помощью высокой загрузки, то для fork-join системы речь идёт об анализе такого режима, в котором значение очень близко к значению . Ключевым параметром при интерполяции с помощью метода высокой нагрузки является параметр , два крайних значения которого интерпретируются как два предельных случая: если = 0, то это означает, что входящий поток является детерминированным, если = 1, то время обслуживания - детерминированное, а ветви fork-join системы являются независимыми ||1 и ||1 СМО, соответственно. Таким образом, благодаря исследованию поведения функции времени отклика в граничных значениях загрузки системы удаётся, в отличие от метода, описанного в [1], не прибегая к численным экспериментам для определения констант в интерполяционной формуле, определить их точные выражения в замкнутой форме. Для случая fork-join системы с ветвями | |1 аппроксимация времени отклика имеет вид: В случае распределения Эрланга второго порядка для входящего потока с функцией распределения и для времени обслуживания с функцией распределения Также в работе [28] для того, чтобы получить оценку среднего времени отклика в случаях с другими распределениями для входящего потока и времени обслуживания, метод интерполяции высокой нагрузки был модифицирован, и анализировались три значения ключевой константы = 0, 1/2, 1, что привело к квадратичной интерполяции, благодаря которой, в сочетании с методом низкой нагрузки, были получены формулы аппроксимации среднего времени отклика для следующих немарковских случаев: - распределение Эрланга второго порядка для входящего потока с функцией распределения и экспоненциальное время обслуживания с функцией распределения - пуассоновский входящий поток с функцией распределения 0 и распределение Эрланга второго порядка времени обслуживания с функцией распределения 0 а также для гиперэкспоненциального входящего потока и экспоненциального времени обслуживания, пуассоновского входящего потока и гиперэкспоненциального времени обслуживания, формулы для которых в силу их громоздкости приводить не будем. 5. Заключение В статье рассмотрены особенности построения систем массового обслуживания с расщеплением запросов. Представлен метод точного анализа среднего времени отклика ( = 2), а также его аппроксимации. Во второй части работы будут рассмотрены другие подходы к приближенному анализу времени отклика: матричногеометрический метод, анализ с помощью порядковых статистик для различных типов распределения времени пребывания подзапросов в системе.

A V Gorbunova

Department of Applied Probability and Informatics Peoples’ Friendship University of Russia (RUDN University)

Author for correspondence.
Email: gorbunova_av@rudn.university
6 Miklukho-Maklaya St., Moscow, 117198, Russian Federation

Gorbunova A. V. - assistant of Department of Applied Probability and Informatics of Peoples’ Friendship University of Russia (RUDN University)

I S Zaryadov

Institute of Informatics Problems Federal Research Center “Computer Science and Control” Russian Academy of Sciences

Email: zaryadov_is@rudn.university
44-2 Vavilova St., Moscow, 119333, Russian Federation

Zaryadov I. S. - Candidate of Physical and Mathematical Sciences, assistant professor of Department of Applied Probability and Informatics of Peoples’ Friendship University of Russia (RUDN University); Senior Researcher of Institute of Informatics Problems of Federal Research Center “Computer Science and Control” Russian Academy of Sciences

K E Samouylov

Department of Applied Probability and Informatics Peoples’ Friendship University of Russia (RUDN University)

Email: samuylov_ke@rudn.university
6 Miklukho-Maklaya St., Moscow, 117198, Russian Federation

Samouylov K. E. - professor, Doctor of Engineering Science, head of Department of Applied Probability and Informatics of Peoples’ Friendship University of Russia (RUDN University)

E S Sopin

Institute of Informatics Problems Federal Research Center “Computer Science and Control” Russian Academy of Sciences

Email: sopin_es@rudn.university
44-2 Vavilova St., Moscow, 119333, Russian Federation

Sopin E. S. - Candidate of Physical and Mathematical Sciences, assistant professor of Department of Applied Probability and Informatics of Peoples’ Friendship University of Russia (RUDN University); Senior Researcher of Institute of Informatics Problems of Federal Research Center “Computer Science and Control” Russian Academy of Sciences

  • R. Nelson, A. N. Tantawi, Approximate Analysis of Fork/Join Synchronization in Parallel Queues, IEEE Transactions on Computers 37 (1988) 739–743.
  • Thomasian, Analysis of Fork/Join and Related Queueing Systems, ACM Computing Surveys (CSUR) 47 (2) (2014) 17:1–17:71.
  • Tsimashenka, W. J. Knottenbelt, Reduction of Subtask Dispersion in Fork-Join Systems, in: Computer Performance Engineering, Springer Berlin Heidelberg, 2013, pp. 325–336.
  • V. Gorbunova, I. S. Zaryadov, S. I. Matyushenko, K. E. Samouylov, S. Ya. Shorgin, The Approximation of Response Time of a Cloud Computing System, Informatics and applications 9 (2015) 32–38, in Russian.
  • S. V. Vyshenski, P. V. Grigoriev, Yu. Yu. Dubenskaya, Ideal Synchronizer for Marked Pairs in Fork-Join Network, Review of applied and industrial mathematics 15 (3) (2008) 385–399, in Russian.
  • S. P. Moiseeva, I. A. Ivanovskaya, Analysis of the Mathematical Model of Parallel Service of Mixed Type Requests, Bulletin of the Tomsk Polytechnic University. Control, Computer Science and Technology 317 (5) (2010) 32–34, in Russian.
  • S. P. Moiseeva, L. A. Zhidkova, Investigation of the Parallel Service System with Multiple Claims of the Poisson Process, Bulletin of the Tomsk Polytechnic University. Control, Computer Science and Technology 17 (4) (2011) 49–54, in Russian.
  • V. Gorbunova, I. S. Zaryadov, S. I. Matushenko, E. S. Sopin, The Estimation of Probability Characteristics of Cloud Computing Systems with Splitting of Requests, in: Proceedings of the Nineteenth International Scientific Conference Russia: Distributed computer and communication networks: control, computation, communications (DCCN-2016), Vol. 3, 2016, pp. 467–472.
  • V. Gorbunova, I. S. Zaryadov, S. I. Matushenko, E. S. Sopin, The Estimation of Probability Characteristics of Cloud Computing Systems with Splitting of Requests, in: Proceedings of the 15th International Conference named after A. F. Terpugov: Information technologies and mathematical modelling (ITMM-2016), 2016, pp. 167– 172, in Russian.
  • M. Mandelbaum, A.-B. Itzhak, Introduction to Queueing with Splitting and Matching, Israel Journal of Technology 6 (5) (1968) 376–382.
  • Duda, T. Czach´orski, Performance Evaluation of Fork and Join Synchronization Primitives, Acta Informatica 24 (5) (1987) 525–533.
  • L. Green, A Queueing System in which Customers Require a Random Number of Servers, Operations Research 28 (6) (1980) 1335–1346.
  • K. J. Omahen, L. Schrage, A Queueing Analysis of a Multiprocessor System with Shared Memory, in: Proc. of the Symposium on Computer Communication Networks and Teletraffic, 1972, pp. 77–88.
  • Thomasian, A. Avizienis, Dynamic Scheduling of Tasks Requiring Multiple Processors, in: Proceedings of the 11th IEEE Computer Society International Conference (COMPCON’75 Fall), 1975, pp. 77–80.
  • T. Javidi, Cooperative and Non-Cooperative Resource Sharing in Networks: a Delay Perspective, IEEE Transactions on Automatic Control 53 (9) (2008) 2134–2142.
  • Kumar, R. Shorey, Performance Analysis and Scheduling of Stochastic Fork-Join Jobs in a Multicomputer System, IEEE Transactions on Parallel and Distributed Systems 10 (4) (1993) 1147–1164.
  • L. Flatto, S. Hahn, Two Parallel Queues Created by Arrivals with Two Demands I, SIAM Journal on Applied Mathematics 44 (5) (1984) 1041–1053.
  • G. Bolch, S. Greiner, H. de Meer, K. S. Trivedi, Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications, John Wiley & Sons, 2006.
  • F. Baccelli, Two Parallel Queues Created by Arrivals with Two Demands: the
  • W. E. Boyce, R. C. DiPrima, Elementary Differential Equations and Boundary Value Problems, John Wiley & Sons, 2012.
  • G. P. Basharin, Introduction to Probability Theory, PFUR, Moscow, 1990, in Russian.
  • P. P. Bocharov, A. V. Pechinkin, Queueing Theory, PFUR, Moscow, 1995, in Russian.
  • G. P. Basharin, Lectures on the Mathematical Theory of Teletraffic, PFUR, Moscow, 2009, in Russian.
  • P. P. Bocharov, C. D’Apice, A. V. Pechinkin, S. Salerno, Queueing Theory, Brill Academic Publishers, 2004.
  • R. E. Barlow, F. Proschan, Statistical Theory of Reliability and Life Testing: Probability Models, John Wiley & Sons, 1981.
  • E. Varki, A. Merchant, H. Chen, The M|M|1 Fork-Join Queue with Variable Subtasks. URL http://www.cs.unh.edu/~varki/publication/2002-nov-open.pdf
  • E. Varki, Response Time Analysis of Parallel Computer and Storage Systems, IEEE Transactions on Parallel and Distributed Systems 12 (11) (2001) 1146–1161.
  • S. Varma, A. M. Makowski, Interpolation Approximations for Symmetric Fork-Join Queues, Performance Evaluation 20 (1994) 245–265.

Views

Abstract - 1129

PDF (Russian) - 655


Copyright (c) 2017 Gorbunova A.V., Zaryadov I.S., Samouylov K.E., Sopin E.S.

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.