Analysis of fork/join queueing networks with retrials.pdf Сети массового обслуживания (СеМО) с делением и слиянием требований (fork-join queueing networks) [1] являются математическими моделями, используемыми для анализа стохастических систем с параллельным или распределенным принципом функционирования (телекоммуникационные системы, распределенные базы данных, многопроцессорные системы). В таких реальных системах поступающие для обработки задачи делятся на более простые для выполнения подзадачи, которые распределяются по системе, занимая выделенные им ресурсы, однако исходная задача будет считаться выполненной только после выполнения всех ее подзадач. В большинстве работ рассматриваются сети массового обслуживания с делением и слиянием требований, состоящие из параллельных систем массового обслуживания (СМО). Для сети обслуживания, состоящей из двух одноприборных параллельных СМО, в [2] получено выражение для производящей функции стационарного распределения вероятностей состояний сети. Анализ же сетей обслуживания большей размерности с делением и слиянием требований проводится только приближенными методами [3-5]. Обзор основных результатов за тридцатилетний период изучения СеМО с делением и слиянием требований можно найти в [6]. Характерной особенностью моделируемых реальных систем является наличие повторных обращений от поступающих для выполнения задач спустя некоторое время, они возникают в случае отказа в выполнении, что имеет место в связи с ограниченностью ресурсов системы. Для моделирования процессов, возникающих при повторных обращениях, используют модели массового обслуживания с повторными вызовами - RQ-системы и сети массового обслуживания (retrial queues). В таких моделях требование, получившее отказ в обслуживании, поступает в источник повторных вызовов (ИПВ), из которого снова пытается получить обслуживание. Для исследования моделей обслуживания с повторными вызовами применяются матричные методы [7, 8], а также методы асимптотического анализа [9, 10]. Основные результаты можно найти в монографиях [11, 12]. В данной работе будет рассмотрена сеть массового обслуживания с делением и слиянием требований, состоящая из параллельных СМО, в которой имеют место повторные вызовы. Возникновение повторных вызовов связано с ограниченностью числа мест для ожидания в каждой системе обслуживания сети. Статья организована следующим образом. В разд. 1 описывается изучаемая сеть массового обслуживания. Стационарное распределение вероятностей состояний сети, а также выражения для основных стационарных характеристик приводятся в разд. 2 и 3 соответственно. Раздел 4 содержит численные примеры. 1. Описание сети обслуживания Рассматривается RQ-сеть массового обслуживания с делением и слиянием требований, состоящая из M параллельных одноприборных систем обслуживания, каждая с конечным числом B мест для ожидания в очереди (рис. 1). В сеть обслуживания из внешнего источника поступает пуассоновский поток требований с интенсивностью Л. Вновь поступающее требование, застающее сеть в состоянии, когда в каждой очереди имеются свободные места для ожидания, делится на M фрагментов, которые распределяются по системам сети и ожидают своего обслуживания в соответствии с дисциплиной FCFS в очередях. Длительность обслуживания фрагментов на приборе системы i имеет экспоненциальное распределение с параметром Дь Фрагмент, завершивший свое обслуживание, освобождает обслуживающий его прибор. Требование будет считаться обслуженным только после того, как будет завершено обслуживание всех его фрагментов. Сразу после этого фрагменты требования мгновенно объединяются в исходное обслуженное требование. Рис. 1. RQ-сеть обслуживания с делением и слиянием требований В том случае, когда хотя бы одна очередь заполнена полностью, поступившее требование не может быть поделено и переходит в источник повторных вызовов, где после случайной задержки вновь пытается обратиться к системам сети для получения обслуживания; если требование снова не может получить обслуживание, то оно вновь возвращается в ИПВ. Предполагается, что если в ИПВ есть требования, то длительность интервала времени между повторными вызовами имеет экспоненциальное распределение с параметром у. 2. Стационарное распределение вероятностей состояний сети Состояние рассматриваемой сети обслуживания в момент времени t определим как вектор x(t) = (r(t), n\(t), ..., пм(0), где r(t) - число требований в ИПВ, n() - число фрагментов в системе обслуживания i, i = 1, ..., M. Очевидно, что (M + 1)-мерный процесс (x(t), t>0} есть цепь Маркова с непрерывным временем, определенная на пространстве состояний X, X = {(r,П1 ,...,nM) : r > 0,0 < nt 0, q((r,«j,...,nM ),(r-1,n +1,...,им + 1)) = у; (2) 3) если существуетje{1,..., M}, такое, что nj = B + 1, q (( r, nj,..., «j-j, £ +1, «+1,..., «m ), (r +1, nj,..., «j-j, £ +1, «+1,..., «m )) = A; (3) 4) если существует j e{1,..., M}, такое, что n;- >0, q((r,«j,nj+l,...,«m ),(r,nl,...,«j -1,nj+l,...,«M )) = ^j. (4) Упорядочим состояния цепи Маркова в лексикографическом порядке, под макросостоянием с номером i будем понимать множество состояний Xi мощности (B + 2)M, определяемое как Xi = {(r,«i,...,«m) e X: r = г'}. Цепь Маркова {x(t), t > 0} является квазипроцессом размножения и гибели [7, 13], инфинитези-мальный оператор Q цепи имеет блочно-диагональный вид: Q = B00 B01 0 0 0 0 B10 A1 A2 0 0 0 0 A0 A1 A2 0 0 0 0 A0 Ai A2 0 0 0 0 Матрицы Ao, Ai, A2, B00, B01, B10 суть квадратные матрицы порядка (B + 2)M. Матрицы Ao, A2 задаются выражениями (2) и (3) соответственно, B10 = Ao, B01 = A2. Выражения (1) и (4) определяют внедиагональные элементы матриц A1, Boo; диагональные элементы матриц определяются из условий: А01 + A11 + A21 = 0, B00I + B01I = 0, где 1 обозначает единичный вектор-столбец. Для вычисления стационарного распределения п = (по, П1, ...) воспользуемся аппаратом матрично-аналитических решений [7, 13], а именно матрично-геометрическим методом. Здесь пг-, i = 0, 1, ... есть вектор-строка, каждая компонента которого задает вероятность нахождения в некотором состоянии из макросостояния Xi в соответствии с введенным лексикографическим порядком. Будем использовать следующие обозначения: п(х) = п(г, П1,..., nM) - стационарная вероятность нахождения сети обслуживания в состоянии х; п(Х) - стационарная вероятность нахождения сети в макросостоянии Xi, п(X) = 2 п(х) = п 1. xeX, Для сети обслуживания стационарный режим будет существовать тогда и только тогда, когда выполнено условие [13] аА01 > аА21, где а есть решение уравнения а( А0 + А1 + А2) = 0 с условием нормировки а1 = 1. Известно, что тогда стационарное распределение имеет следующий вид: я, = njR'-1, i = 1,2,..., где R есть решение уравнения A2 + RA1 + R2Ao = 0, векторы по и П1 находятся как решение уравнения B 00 01 (п о Я, 10 = (0 0), A1 + RA 0 , с условием нормировки по1 + ni(I-R)1=1, здесь I - единичная матрица. 3. Вычисление стационарных характеристик Используя стационарное распределение я, определим математическое ожидание (м.о.) NR числа требований в ИПВ: Nr = Z in( X) = п Z i'R'" 1 = Я! (I - R)"21. i=1 i=1 Обозначим через (ni, ..., П(в+2)М) вектор-столбец, составленный в соответствии с введенным лексикографическим порядком из всех элементов множества {(«i, ..., «М) : 0 < « < B + 1}, который отображает все возможные способы распределения фрагментов поMсистемам сети. Пусть n = («i, ..., пм), через я(п) обозначим следующую стационарную вероятность: да п(п) = Z П(r,щ,...,nM). r=0 Положим d = (я (ni), ..., я (п(в+2)М)), тогда справедливо да d =Z Щ =п0 + nj(I - R)-1. i=0 Предположим, что сеть обслуживания находится в состоянии (r, «i, ..., «М), тогда число требований, разделившихся на фрагменты, будет, очевидно, равно max{«i, ..., «м}. Математическое ожидание Ns числа таких требований Ns, = Z Z max{n,...,Пм}я(х) = d(max{«1},...,max{п 2)м}). i=0 xg xt V ^ ) ' ' Под длительностью пребывания требования в сети обслуживания будем понимать длительность интервала времени от момента разделения требования на фрагменты и распределения по системам до завершения обслуживания последнего из этих фрагментов. Тогда м.о. Ts длительности времени пребывания требований в сети обслуживания будет равно Ts = Ns/ Л. С учетом возможного пребывания в ИПВ м.о. T длительности интервала от поступления требования из источника до завершения его обслуживания будет равно t_ns + nr л . Обозначим через b вероятность того, что требование, поступающее из источника, перейдет в ИПВ, тогда интенсивность Ле потока требований из источника в ИПВ составит ЛR = ьл ( B+2)M ь = Z п(«). i=1 max{ni }= B+1 Требование, находящееся в ИПВ, осуществляет попытки занятия систем обслуживания сети, математическое ожидание Tr суммарной длительности времени пребывания требований в ИПВ, будет равно Tr=NR. Л R Для требования, находящегося в ИПВ, можно рассмотреть число повторных обращений к системам обслуживания. Обозначим через K математическое ожидание числа попыток захвата систем обслуживания. Будем исходить из следующих соображений: интенсивность входящего потока из источника в ИПВ равна Ле, требования из ИПВ обращаются к системам сети, интенсивность обращений к системам равна у(1- n(Xo)). Тогда -_у (1 - п( X 0)) K = 4. Примеры Рассмотрим изменение м.о. T длительности интервала времени от поступления требования из источника до завершения его обслуживания в зависимости от числа мест для ожидания в очереди (B = 0, 1, 2) и интенсивности Л входящего потока. Результаты численных экспериментов изображены на рис. 2, здесь M = 2, Ц1 = Ц2 = 6, у = 10. T (Л) 1,4 1,2 1 0,8 0,6 0,4 0,2 0,1 0,5 0,9 1,3 Л 2,5 1,7 2,1 Рис. 2. Графики зависимости т (Л) при 0,1 < Л < 2,5 В данном примере численно решим задачу оптимального выбора параметра у - интенсивности поступления требований из ИПВ, исходя из следующего: будем предполагать, что каждая неудачная попытка поступления из ИПВ приводит к выплате Ск; с другой стороны, Ст есть плата за нахождение одного требования в ИПВ в течение единицы времени. Тогда целевая функция Скт(у) имеет вид: Скт (Y) = ckk (y) + CTTR (Y). На рис. 3 представлен график целевой функции Скт(у) для следующих параметров сети обслуживания: Л = 1, M = 5, щ = ...= Ц5 = 2, B = 2, Ск = 1, Ст = 0,5. При интенсивности поступления из ИПВ ykt = 1,98, целевая функция достигает минимума и принимает значение Ckt(ykt) = 4,15. Y Рис. 3. График целевой функции Скт(у) при 0,8 < у < 6 Пусть теперь целевая функция определена следующим образом: CKb (Y) = CKK (y) + Cb (1 - b(Y)), т.е. каждая неудачная попытка поступления из ИПВ приводит к выплате Ск; с другой стороны, Сь есть плата за нахождение всех очередей систем в незаполненном состоянии. Y Рис. 4. График целевой функции Скь(у) при 0,8 < y < 6 Минимальное значение целевой функции достигается при интенсивности поступления из ИПВ YKb = 2,74, CKb(YKb)= 37,27. Заключение В статье рассмотрена RQ-сеть массового обслуживания с делением и слиянием требований. Получены выражения для основных стационарных характеристик сети обслуживания. Приведены примеры и рассмотрены задачи численной оптимизации. Представленная в работе сеть массового обслуживания может применяться в качестве модели многопроцессорных вычислительных систем, а также других систем с параллельным и распределенным принципами функционирования. На рис. 4 представлен график целевой функции Са(у) для следующих параметров сети обслуживания: Л = 1, M = 5, щ = ...= Ц5= 2, B = 2, Ck = 1, C = 50.

Скачать электронную версию публикации