Диссертация (1155093), страница 8
Текст из файла (страница 8)
В эту систему поступает пуассоновский поток запросов с интенсивностью . При этом вмомент поступления в систему запроса, он делится на подзапросов от 1-го до-го типа и посылает подзапросы в каждую из очередей. Запрос считаетсяобслуженным в момент окончания обслуживания последнего из составляющихего подзапросов. Времена обслуживания заявок-подзапросов являются независимыми случайными величинами, распределенными по экспоненциальному закону с параметром для подзапроса -го типа, = 1,.Пусть () — число подзапросов -го типа, находящихся в системе вмомент времени , = 1,.
Обозначим () = (1 (),2 (), . . . , ()). Случайный процесс {(), ≥ 0}, описывающий поведение системы массовогообслуживания во времени, является марковским (МП) с непрерывным вре-43Диспетчерзадач...ВМ...ВМ.........ВМБуферсинхронизацииРисунок 2.2 — Схема системы массового обслуживания для облачного центраменем и дискретным множеством состояний = {(1 ,2 , . . . , ), 1 ≥ 0,2 ≥0, . .
. , ≥ 0}. Указанные состояния интерпретируются следующим образом:если () = (1 ,2 , . . . , ), то в системе находится 1 подзапросов 1-го типа, 2подзапросов 2-го типа, 3 подзапросов 3-го типа и т.д.Стационарное распределение существует и удовлетворяет следующей системе уравнений равновесия:0,0,...,0 = 1 1,0,...,0 + 2 0,1,...,0 + . . .
+ 0,0,...,1 ;( + 1 )1 ,0,...,0 = 1 1 +1,0,...,0 + 2 1 ,1,...,0 + · · · + 1 ,0,...,1 , 1 ≥ 1;(2.1)(2.2)( + 2 )0,2 ,0,...,0 = 1 1,2 ,0,...,0 + 2 0,2 +1,0,...,0 + · · · + 0,2 ,0,...,1 , 2 ≥ 1; (2.3)...( + )0,0,..., = 1 1,0,..., + 2 0,1,0,..., + . . . + 0,0,..., +1 , ≥ 1; (2.4)( + 1 + 2 )1 ,2 ,0,...,0 = 1 1 +1,2 ,0,...,0 + 2 1 ,2 +1,0,...,0 + . .
. ++ 1 ,2 ,0,...,1 , 1 ≥ 1,2 ≥ 1;( + 1 + 3 )1 ,0,3 ,0,...,0 = 1 1 +1,0,3 ,0,...,0 + 2 1 ,1,3 ,0,...,0 + . . . ++ 1 ,0,3 ,0,...,1 , 1 ≥ 1,3 ≥ 1;(2.5)(2.6)...( + 1 + 2 + 3 )1 ,2 ,3 ,0,...,0 = 1 1 +1,2 ,3 ,0,...,0 + 2 1 ,2 +1,3 ,0,...,0 + . . . ++ 1 ,2 ,3 ,0,...,1 , 1 ≥ 1,2 ≥ 1,3 ≥ 1;(2.7)44...( + 1 + 2 + · · · + )1 ,2 ,..., = 1 −1,2 −1,..., −1 + 1 1 +1,2 ,..., ++2 1 ,2 +1,..., + . . .
+ 1 ,2 ,..., +1 , 1 ≥ 1,2 ≥ 1, . . . ≥ 1;(2.8)Рассмотрим частный случай для = 2. Стационарное распределениебудет удовлетворять следующей СУР:0,0 = 1 1,0 + 2 0,1 ;(2.9)( + 1 )1 ,0 = 1 1 +1,0 + 2 1 ,1 , 1 ≥ 1;(2.10)( + 2 )0,2 = 1 1,2 + 2 0,2 +1 , 2 ≥ 1;...(2.11)( + 1 + 2 )1 ,2 = 1 −1,2 −1 + 2 1 +1,2 + 2 1 ,2 +1 , 1 ≥ 1,2 ≥ 1.(2.12)Кроме того, к этим уравнением добавляется условие нормировки:∞∞ ∑︁∑︁1 ,2 = 1.(2.13)1 =0 2 =0Далее просуммируем по всем возможным значениям 2 = 1,∞ все уравнения(2.12) с учетом уравнений (2.10) и все уравнения (2.11) с учетом уравнения (2.9),в итоге получим новую систему уравнений:0,· = 1 1,· ,( + 1 )1 ,· = 1 −1,· + 1 1 +1,· , 1 ≥ 1.(2.14)(2.15)Полученная система для маргинальных вероятностей числа подзапросов аналогична СУР для распределения вероятностей заявок в СМО вида /1 /1.Поэтому решение для полученной системы (2.14)-(2.15) имеет вид:1 ,· = 11 0,· ,0,· = 1 − 1 , 1 ≥ 1,(2.16)где здесь и далее =, = 1,.(2.17)45Проведя аналогичное суммирование, но по значениям индекса 1 = 1,∞,получим систему для маргинальных вероятностей:·,0 = 2 ·,1 ,(2.18)( + 2 )·,2 = ·,2 −1 + 2 ·,2 +1 , 2 ≥ 1,(2.19)которая в свою очередь аналогична СУР для распределения вероятностей СМОвида /2 /1, и её решение представляет собой следующее выражение:·,2 = 22 ·,0 ,·,0 = 1 − 2 , 2 ≥ 1.(2.20)Теперь исследуем СУР для произвольного числа типов подзапросов .При суммировании по возможным значениям любых ( − 2) индексов системы уравнений (2.1)-(2.8) таким образом, как это было подробно описано вышедля частного случая = 2, получим аналогичные системы уравнений длямаргинальных вероятностей.
Следовательно, маргинальное распределение вероятностей в общем случае будет иметь вид:1 ,·,·,...,· = 11 0,·,·,...,· , 1 ≥ 1;(2.21)·,2 ,·,...,· = 22 ·,0,·,...,· , 2 ≥ 1;...(2.22)·,·,...,·, = ·,·,...,0 , ≥ 1,(2.23)·,0,·,...,· = 1 − 2(2.24)где0,·,·,...,· = 1 − 1 ,...·,·,...,0 = 1 − .Заметим, что СУР (2.1)-(2.8) можно представить в более компактном виде, а именно, если множество состояний случайного процесса {(), ≥ 0},описывающего поведение системы во времени, представить в виде: = {⃗ =(1 ,..., ,..., ), 1 ≥ 0,..., ≥ 0,..., ≥ 0}, то стационарное распределениебудет удовлетворять следующей системе уравнений равновесия:(︂+∑︁=1)︂∏︁∑︁⃗ ( ) (⃗) = (⃗ − 1)( ) + (⃗ + ⃗ ), ⃗ ∈ , (2.25)=1=146где ⃗ вектор, все элементы которого равны нулю, кроме -го, который равен1, ⃗1 - единичный вектор и{︃( ) =0 если ≤ 0;1 если > 0.Также отметим, что мы не исследуем очевидное условие эргодичности рассматриваемой системы и считаем, что = max1≤≤ < 1, = / , = 1,.Теперь сформулируем утверждение о распределении маргинальных вероятностей для системы облачных вычислений с расщеплением запросов, пользуясь более компактной записью СУР (2.25) [77; 78].Утверждение 2.1.1.
Маргинальное распределение числа подзапросов в системе облачных вычислений с расщеплением имеет вид: = (1 − ) , ≥ 0.(2.26)Доказательство. Суммирование уравнений СУР (2.25) по всем индексам, кроме -го, приводит к СУР, соответствующей системе массового обслуживания / /1. Следовательно, выражения для маргинальных вероятностей макросостояний МП () представимы в виде: = (1 − ) , ≥ 0.(2.27)Заметим, что в случае для значения = 1 данный результат можно получить из выражения для производящей функции (1.6).2.2Время отклика в системе облачных вычисленийВремя отклика в системе облачных вычислений, моделируемой системоймассового обслуживания с расщеплением запросов, как уже было упомянутовыше, может определяться по-разному в зависимости от поставленной задачи.Если мы анализируем время обработки сложного пользовательского запроса,47который с целью увеличения производительности и повышения энергоэффективности был расщеплен на подзапросы, то естественно, что время отклика вэтом случае будет определятся как максимум из времен пребывания подзапросов в системе.Если же перед пользователем облачного сервиса стоит задача получитьответ на запрос как можно быстрее, то также естественно будет направитьнесколько экземпляров задачи различным поставщикам облачных услуг иждать самого раннего ответа.
Разумеется, что в этом случае время откликабудет являться минимумом из времён пребывания экземпляров одной и той жезадачи у каждого из поставщиков услуг. При этом функциональная схема исследуемой системы принципиально не изменится: просто некоторые её элементы поменяют смысловую нагрузку. В частности, под виртуальными машинамибудут подразумеваться ресурсы, имеющиеся у разных облачных сервисов.Считаем, что времена пребывания подзапросов в подсистемах являютсянезависимыми экспоненциально распределёнными случайными величинами с плотностями распределения () = − , > 0, = 1,, тогда дляминимума справедливо:(1) () = (min(1 , . . . , ) < ) = 1 − (min(1 , .
. . , ) > ) == 1 − (1 > , . . . , > ) = 1 − (1 > ) · · · · · ( > ) ==1−∏︁ ( > ) = 1 −=1∏︁∏︁(1 − ( < )) =(2.28)=1(1 − (1 − − )) = 1 − −(1 +···+ ) .=1−=1Таким образом, минимум экспоненциально распределенных независимых случайных величин имеет также экспоненциальное распределение с параметром(1 + · · · + ), т.е. (1) ∼ (1 + · · · + ).
Следовательно, математическоеожидание минимума равно:[min(1 , . . . , )] =1,1 + · · · + 48а дисперсия минимума:[min(1 , . . . , )] =1.(1 + · · · + )2Для максимума случайных величин имеем:() () = (max(1 , . . . , ) < ) = (1 < , . . . , < ) == (1 < ) · · · · · ( < ) =∏︁∏︁(1 − − ). ( < ) =(2.29)=1=1Тогда плотность распределения максимума экспоненциальных случайных величин определяется как:∏︁∑︁∑︁ () ∏︁ (1 − )== ()() () = ()1−=1=1=1=1=∑︁ −=1+∑︁( + )−( + ) +(2.30)1≤<≤∑︁( + + )−( + + ) +1≤<<≤+ . .
. + (−1)−1 (1 + 2 + . . . + )−(1 +2 +...+ ) .Следовательно, математическое ожидание имеет вид:∫︁∞[max(1 , . . . , )] =0+∑︁1≤<<≤∑︁1−() () ==1∑︁1≤<≤1+ + 11+ . . . + (−1)−1, + + 1 + 2 + ... + а дисперсию можно вычислить следующим образом:(2.31)49∑︁∑︁22[max(1 , . .
. , )] =−+2( + )2=11≤<≤∑︁22−1++...+(−1)−( + + )2(1 + 2 + . . . + )21≤<<≤(︃ ∑︁ 1∑︁∑︁11−−++ + + + + =11≤<≤1≤<<≤)︃21+ . . . + (−1)−1.1 + 2 + . . . + (2.32)Поскольку в качестве модели системы облачных вычислений с расщепленим запросов мы используем fork-join систему массового обслуживания с ветвями / /1, = 1,, то, благодаря результату для распределения маргинальных вероятностей, имеем, что время пребывания в подсистеме / /1будет иметь экспоненциальное распределение с параметром = ( − ), = 1,, следовательно, для времени отклика можем записать следующие оценки [77; 78]:1[, min ] ≈,(2.33)1 + · · · + − [, min ] ≈[,max ] ≈∑︁=1+∑︁1≤<<≤1,(1 + · · · + − )21− − ∑︁1≤<≤(2.34)1+ + − 211+ . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
