A Heterogeneous Fork-Join Queueing System in Which EachJob Occupy All Free Servers

Cover Page

Abstract


In this paper, we consider a multiserver queueing system with heterogeneous servers in whicheach job is split to be serviced into a number of tasks, one for each free server. The tasks areserviced independently, but service time depends on weight of the tasks. A job is considered tobe complete only when all the tasks associated with the job have been executed to completion.Applying a matrix-geometric approach, we obtain the exact expression for the stationarydistribution of the number of jobs in the system under exponential assumptions. Using thedistribution, we derive other important performance measures. Special attention is paid to thesojourn time in the queueing system (the time to complete a job). Finally, some numericalexamples and a section of conclusions commenting the main research contributions of thispaper are presented.The results can be used for the performance analysis of multiprocessor systems and othermodern distributed systems.


1. Введение Реальные системы, в которых имеет место параллельная обработка [1] (многопроцессорные системы, GRID-системы, распределённые базы данных), получают все большее распространение. В таких системах поступающие для обработки задачи делятся на более простые для выполнения подзадачи, которые распределяются по системе, занимая выделенные для них ресурсы. После завершения своего выполнения подзадачи освобождают выделенные им ресурсы, однако исходная задача будет считаться выполненной только после выполнения всех её подзадач. Для анализа производительности указанных выше систем используются модели теории массового обслуживания, такие как [2]: с центральным делением без синхронизирующей очереди (centralized splitting model without synchronization queue, split-merge model), с центральным делением и синхронизирующей очередью (centralized splitting model with synchronization queue), с распределённым делением и синхронизирующей очередью (distributed splitting model with synchronization queue), которые обычно относят к классу систем массового обслуживания с делением и слиянием требований (fork-join queueing systems) [3 - 8], а также такие родственные модели как, например, модель независимых приборов (independent server model) [9,10], модель командного обслуживания (team service model) [11]. Общим во всех перечисленных моделях является деление поступающих требований на части - фрагменты, которые обслуживаются параллельно на приборах системы, и последующее объединение обслуженных фрагментов в исходные требования. Требование считается обслуженным и покидает систему только после окончания обслуживания всех его фрагментов. Распределение фрагментов поступающих требований по приборам системы с делением и слиянием требований, как и число фрагментов, получаемых при делении одного требования, задаётся некоторой детерминированной или вероятностной [12, 13] стратегией. Так, в работах [3, 4, 6 - 8] требования каждый раз делятся на одинаковое число фрагментов, по одному фрагменту для каждого обслуживающего прибора системы. С другой стороны, в [12] рассматривалась модель, в которой каждое требование может быть поделено на случайное число фрагментов, которые поступают на обслуживающие приборы в соответствии с некоторым распределением вероятностей. Обзор всех основных теоретических и прикладных результатов связанных с моделями данного класса можно найти в [14, 15]. В статье рассматривается многоприборная система массового обслуживания с очередью бесконечной вместимости и пуассоновским входящим потоком. Основным отличием от известных работ является то, что деление требования в момент начала обслуживания на фрагменты происходит так, что они занимают все свободные обслуживающие приборы, то есть число фрагментов, получаемых при делении одного требования, зависит от состояния системы обслуживания, а длительность обслуживания фрагмента зависит от его величины. Фрагменты обслуживаются независимо друг от друга. Фрагмент, обслуживание которого завершено, освобождает обслуживающий его прибор. Требование будет считаться обслуженным только после того, как будет завершено обслуживание всех его фрагментов, сразу после чего фрагменты требования объединяются, а полученное исходное требование покидает систему обслуживания. Также отметим, что во многих работах [4, 7, 12, 13] рассматривается случай идентичных обслуживающих приборов, в представленной же системе обслуживания приборы имеют различные интенсивности обслуживания. Статья организована следующим образом. В разделе 2 подробно описывается изучаемая система массового обслуживания. Стационарное распределение состояний системы обслуживания, а также выражения для основных стационарных характеристик приводятся в разделах 3 и 4 соответственно. Раздел 5 содержит численные результаты анализа системы обслуживания. 2. Описание системы обслуживания Рассматривается система обслуживания, состоящая из обслуживающих приборов и очереди бесконечной вместимости с дисциплиной обслуживания FCFS. В систему обслуживания поступает пуассоновский поток требований с интенсивностью Λ. Обозначим через класс требования и положим, что для всех требований, поступающих из источника, = 1. Требование, поступающее на обслуживание, делится на фрагменты так, что они занимают все свободные в данный момент времени обслуживающие приборы: если имеется 1 6 6 свободных приборов, то поступающее требование разделяется на идентичных фрагментов с классом = . Каждый из фрагментов мгновенно занимает свободный прибор и начинает обслуживаться. То есть деление требования на > 1 фрагментов происходит в том случае, когда в момент поступления этого требования очередь системы была пуста, при этом имелось более одного свободного прибора. В других случаях требование не делится, однако для удобства будем называть и такое требование фрагментом. Длительность обслуживания любого фрагмента с классом на приборе есть экспоненциально распределённая случайная величина с параметром , здесь - интенсивность обслуживания фрагмента (требования) класса = 1. Фрагмент, обслуживание которого завершено, освобождает обслуживающий его прибор. Требование будет считаться обслуженным только после того, как будет завершено обслуживание всех его фрагментов. Сразу после этого фрагменты требования мгновенно объединяются в исходное требование, которое покидает систему обслуживания. 3. Стационарное распределение системы обслуживания Состояние системы обслуживания определим как вектор где 0 - число требований в очереди, где Очевидно, что мерный процесс есть цепь Маркова с непрерывным временем, определённая на пространстве состояний , Обозначим через интенсивность перехода цепи из состояния в состояние Справедливо число свободных приборов при нахождении системы обслуживания в состоянии ; 4. если Упорядочим состояния цепи Маркова в лексикографическом порядке. Под макросостоянием с номером , будем понимать множество состояний , определяемое как Мощности множеств равны соответственно. Заметим, что из (1) и (2) следует возможность перехода из макросостояния только в макросостояния интенсивности этих переходов не зависят от . Цепь Маркова является квазипроцессом размножения и гибели [16], а инфинитезимальный оператор цепи имеет блочнодиагональный вид: Матрицы имеют размерность соответственно. Матрицы суть квадратные матрицы порядка . Выражения (2) полностью определяют элементы матриц 0 и 10 . Отметим, что 2 = Λ I , где I - единичная матрица; 1 - диагональная матрица, 1 = -diag где diag ( ) задаёт диагональную матрицу с вектором на главной диагонали, 1 - единичный вектор-столбец. Матрицы 00 , 01 определяются выражениями (3) , (4) , (5) . Для вычисления стационарного распределения воспользуемся аппаратом матрично аналитических решений [17], а именно матрично геометрическим методом. Здесь есть вектор-строка, каждая компонента которого задаёт вероятность нахождения системы обслуживания в некотором состоянии из макросостояния в соответствии с введённым лексикографическим порядком. Будем использовать следующие обозначения: - стационарная вероятность нахождения системы в состоянии - стационарная вероятность нахождения системы в макросостоянии Для системы обслуживания стационарный режим будет существовать тогда и только тогда, когда выполнено условие где - коэффициент использования системы обслуживания. Известно [16, 17], что при выполнении условия (6) стационарное распределение имеет вид где есть решение уравнения векторы 0 и 1 находятся как решение уравнения с условием нормировки Вычисление стационарных характеристик Используя стационарное распределение , определим математическое ожидание ¯ числа требований в очереди системы обслуживания и математическое ожидание длительности пребывания требований в очереди, Одной из основных характеристик, представляющих интерес в системах данного класса, является длительность времени пребывания требования [4, 6, 7] в системе обслуживания, которая определяется как длительность интервала времени от поступления требования в систему до возвращения требования в источник. Под длительностью обслуживания требования в системе обслуживания будем понимать максимум из длительностей интервалов времени, затраченных на обслуживание приборами всех фрагментов этого требования. Обозначим через математическое ожидание длительности обслуживания требований в системе обслуживания, тогда математическое ожидание длительности времени пребывания требований в системе обслуживания = + . Рассмотрим два случая для поступающего из источника требования. 1. Требование застаёт все приборы системы обслуживания занятыми и встаёт в очередь. Тогда длительность обслуживания требования есть случайная величина с экспоненциальным распределением. 2. Требование застаёт в системе обслуживания > 0 свободных обслуживающих приборов. В этом случае длительность обслуживания требования есть максимум из независимых случайных величин с экспоненциальными распределениями. Пусть система обслуживания находится в состоянии тогда вероятность завершения обслуживания фрагмента на приборе определяется как м.о. длительности обслуживания для требования, занявшего освободившийся прибор, определяется выражением Будем рассматривать систему обслуживания при условии, что в очереди есть требования, тогда множество определяет множество состояний обслуживающих приборов. При данном предположении вероятность является вероятностью перехода из состояния в состояние обусловленного завершением обслуживания некоторого фрагмента на приборе . Случайный процесс, вложенный по моментам ухода фрагментов, является цепью Маркова с дискретным временем и множеством состояний * . Пусть состояния в * упорядочены в лексикографическом порядке, а задаёт матрицу переходов для цепи Маркова Предположим, что требование поступает в систему, когда в очереди находится > 0 требований. Рассмотрим эволюцию цепи Маркова, описывающей переходы между состояниями приборов. В этом случае задаёт вероятность нахождения приборов в состоянии при условии нахождения в очереди требований. Вектор будет являться вектором начального распределения для рассматриваемого процесса. Через завершений обслуживания поступившее в систему обслуживания требование будет первым в очереди на обслуживание, следовательно, математическое ожидание длительности обслуживания требования, заставшего требований в очереди, определяется как где есть вектор-столбец, составленный из элементов множества в соответствии с введённым лексикографическим порядком на множестве Рассмотрим теперь случай, когда поступающее в систему обслуживания требование не застаёт в очереди требований. Если все обслуживание приборы заняты, то математическое ожидание длительности обслуживания определяется аналогично предыдущему случаю. Пусть требование застаёт некоторые обслуживающие приборы свободными; обозначим через ( ) множество номеров свободных приборов для состояния Положим для некоторого тогда требование разделится на 0 фрагментов, длительность обслуживания этого требования будет максимумом из независимых экспоненциально распределённых случайных величин. Таким образом, для требований, которые застают очередь системы пустой, математическое ожидание 0 длительности обслуживания требования определяется как здесь E обозначает оператор математического ожидания, exp() - случайная величина с экспоненциальным распределением с параметром . Обсуждение нахождения распределения максимума случайных величин можно найти, например, в [16, 18]. Тогда для математического ожидания длительности обслуживания требований справедливо Матрица есть решение уравнения (8) , которое может быть переписано в привычном для уравнения Сильвестра [19, 20] виде (9) Из (7) после преобразований получаем Математическое ожидание числа требований в системе . 5. Пример На основании полученных выражений рассмотрим изменение математического ожидания длительности пребывания требований в системе обслуживания в зависимости от числа обслуживающих приборов и интенсивности входящего потока. Предполагается, что коэффициент использования меняется в следующих границах: Графики зависимости представлены на рис. 1. Отметим, что полученные с использованием выражений численные результаты были подтверждены также результатами имитационного моделирования. Рис. 1. Зависимость математического ожидания длительности пребывания требований в системе обслуживания Отметим, что когда коэффициент использования приближается к единице, рассматриваемая система ведёт себя аналогично системе с обслуживающими приборами без деления требований, тогда в случае, когда все обслуживающие приборы имеют одинаковую интенсивность обслуживания , математическое ожидание длительности времени пребывания требований в системе может быть приближённо найдено как Сравнение результатов для случая, когда = 4, = 1, приведено в табл. 1. Таблица 1 Математическое ожидание длительности пребывания требований в системе для двух различных моделей с делением требований 0,5714 0,6821 0,8324 1,1540 1,5604 2,8001 5,2955 без деления требований 1,0002 1,0132 1,0870 1,3572 1,7455 2,9694 5,4571 Видно, что во всех случаях система без деления требований на фрагменты имеет большее математическое ожидание длительности пребывания требований в системе, то есть может быть использована для нахождения верхней границы для . 6. Заключение В статье рассмотрена многоприборная система массового обслуживания с очередью бесконечной вместимости, в которой требование делится на фрагменты так, что они занимают все свободные обслуживающие приборы. С использованием матрично-геометрического метода получено стационарное распределение вероятностей состояний системы, а также точные выражения для основных стационарных характеристик системы (математическое ожидание длительности пребывания требований в системе обслуживания, математическое ожидание длительности пребывания требований в очереди и т.д.). В качестве направления дальнейших исследований могут быть рассмотрены различные дисциплины разделения требований, например, с ограничением на максимальное число фрагментов, порождаемых одним требованием.

O A Osipov

Saratov State University (SSU)

Author for correspondence.
Email: oleg.alex.osipov@gmail.com
83 Astrahanskaya St., Saratov, 410012, Russian Federation

Osipov O. A. - assistant of Department of System Analysis and Automatic Control of Saratov State University (SSU)

  • R. Corrˆea, I. Dutra, M. Fiallos, F. Gomes (Eds.), Models for Parallel and Distributed Computation, Springer US, 2002. doi: 10.1007/978-1-4757-3609-0.
  • Y. Narahari, P. Sundarrajan, Performability Analysis of Fork-join Queueing Systems, Journal of the Operational Research Society 46 (10) (1995) 1237–1249. doi: 10.1057/jors.1995.171.
  • L. Flatto, S. Hahn, Two Parallel Queues Created by Arrivals with Two Demands I, SIAM Journal on Applied Mathematics 44 (5) (1984) 1041–1053. doi: 10.1137/0144074.
  • R. Nelson, A. N. Tantawi, Approximate Analysis of Fork/Join Synchronization in Parallel Queues, IEEE Transactions on Computers 37 (6) (1988) 739–743. doi: 10.1109/12.2213.
  • S.-S. Ko, R. F. Serfozo, Response Times in
  • A. 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. doi: 10.14357/19922264150304.
  • M. S. Squillante, Y. Zhang, A. Sivasubramaniam, N. Gautam, Generalized Parallel- Server Fork-Join Queues with Dynamic Task Scheduling, Annals of Operations Research 160 (1) (2008) 227–255. doi: 10.1007/s10479-008-0312-7.
  • 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.
  • L. Green, A Queueing System in Which Customers Require a Random Number of Servers, Operations Research 28 (6) (1980) 1335–1346.
  • A. Rumyantsev, E. Morozov, Stability Criterion of a Multiserver Model with Simultaneous Service, Annals of Operations Research 252 (1) (2015) 29–39. doi: 10.1007/s10479-015-1917-2.
  • K. Omahen, L. Schrage, A Queueing Analysis of a Multiprocessor System with Shared Memory, in: Proceedings of the Symposium on Computer Communication Networks and Teletraffic, 1972, pp. 77–88.
  • A. 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.
  • T. Javidi, Cooperative and Non-Cooperative Resource Sharing in Networks: A Delay Perspective, IEEE Transactions on Automatic Control 53 (9) (2008) 2134–2142. doi: 10.1109/TAC.2008.930186.
  • A. Thomasian, Analysis of Fork/Join and Related Queueing Systems, ACM Computing Surveys 47 (2) (2014) 17:1–17:71. doi: 10.1145/2628913.
  • A. V. Gorbunova, I. S. Zaryadov, K. E. Samouylov, E. S. Sopin, A Survey on Queuing Systems with Parallel Serving of Customers, RUDN Journal of Mathematics, Information Sciences and Physics 25 (2017) 350–362, in Russian. doi: 10.22363/2312-. 9735-2017-25-4-350-362.
  • Q.-M. He, Fundamentals of Matrix-Analytic Methods, Springer, New York, 2014. doi: 10.1007/978-1-4614-7330-5.
  • M. F. Neuts, Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach, The Johns Hopkins University Press, Baltimore, 1981.
  • H. A. David, H. N. Nagaraja, Order Statistics, John Wiley & Sons, Inc., 2003. doi: 10.1002/0471722162.
  • F. R. Gantmacher, The Theory of Matrices, Chelsea Publishing Company, 1959.
  • P. Lancaster, M. Tismenetsky, The Theory of Matrices, 2d edition, Academic Press, 1985, in Russian.

Views

Abstract - 322

PDF (Russian) - 44


Copyright (c) 2018 Osipov O.A.

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