Диссертация (1155093), страница 6
Текст из файла (страница 6)
отказ в обслуживании на -ом сервере происходит тогда и только тогда,когда нарушается условие: − ̸= , для некоторого и для фиксированных положительных целых чисел , , ∀,, ̸= , причём сервер блокируется до тех пор, пока подзапрос не закончит обслуживатьсяна сервере ;где вектор ⃗ = (1 ,..., ,..., ) отражает состояние системы, — число подзапров в системе, = 1,.В результате анализа обеих систем с помощью матрично-геометрическогометода удаётся определить стационарное распределение числа подзапросов всистемах (⃗).
Далее полученное распределение используется при алгоритмическом решении задачи нахождения функции распределения времени оклика:,max () =∑︁(⃗),(),⃗ > 0.⃗Таким образом, задача сводится к поиску условного распределения времениотклика ,() при условии, что система находится в состоянии ⃗. Для⃗первой модифицированной модели искомое условное распределение может бытьвыражено с помощью распределения Эрланга, а во втором случае условноераспределение получается при анализе процесса поглощения для подзапросов.Кроме того, авторы доказали, что решения, полученные при анализе этих двухсистем, являются верхней и нижней границами для функции распределениявремени отклика, соответственно.В следующей статье авторов [23] изучается fork-join система с пуассоновским входящим потоком, но при этом время обслуживания на однородных сер-28верах имеет распределение Кокса.
Отметим, что для стационарных вероятностей состояний в СМО / /1 известно точное решение [94]. Как и в предыдущей работе рассматриваются две аналогичные, аппроксимирующие исходнуюсистему модели:1. модель, в которой все очереди кроме очереди к первому серверу имеютконечную ёмкость;2. модель, в которой вводится ограничение на то, что разница между каждой парой длин очередей к серверам не должна превышать заданныйпорог.Матрично-геометрический анализ указанных систем, предложенный в [95]благодаря тому, что матрицы вероятностей перехода сводятся к блочнотреугольному виду, позволяет получить стационарные вероятности, которые,используются для вывода распределения времени отклика, а, соответственно,и моментов этого распределения.
Полученные выражения являются верхнимии нижними границами для моментов времени отклика.Следующая работа [24] продолжает начатые исследования. Авторы предлагают алгоритмический метод для вычисления верхних и нижних оценок производительности системы, основанный опять же на построении двух ограничивающих исходную систему моделей, стационарное распределение для которыхнаходится с помощью матрично-геометрического метода. Указанный подход,по мнению авторов, может быть расширен для анализа систем с отличными отпуассоновского входящим потоком и отличным от экспоненциального временемобслуживания на разнородных серверах.
Представлены доказательства того,что оценки являются верхними и нижними, также приведены оценки погрешности предложенных аппроксимаций.Отметим, что матрично-геометрический метод (МГМ) использовался ипри анализе систем родственных fork-join. Так, МГМ был применён для анализа модели независимых серверов (ISM), в [96] с помощью МГМ анализируетсяsplit-merge система с двумя ветвями с наложением ограничения на ёмкость накопителя одной из очередей. Были получены выражения для математическогоожидания, дисперсии и функции распределения времени отклика.
Также былразработан метод аппроксимации для систем с более чем с двумя ветвями. Вработах [97; 98] также исследуется fork-join система, но уже с распределениемфазового типа для входящего потока и с потерями. В статье [99] рассматрива-29ется ещё одна вариация классической fork-join системы, для анализа которойиспользуется МГМ: обслуживание каждого подзапроса происходит в несколькоэтапов, включая фазу ожидания и фазу объединения родственных подзапросов; существует динамическая политика планирования нагрузки системы дляподдержания эффективного использования сервера.Анализ с помощью порядковых статистик.
Поскольку время отклика fork-join системы классически определяется как максимум, а в некоторыхслучаях и как минимум из случайных величин времён пребывания подзапросов в системе [84], то естественно, что одним из альтернативных способовоценки среднего времени отклика является использование теории порядковыхстатистик [33–35]. По определению [33–35], если 1 ,..., — конечная выборка,определённая на некотором вероятностном пространстве (Ω, , ), и для ∈ Ω : = (), = 1,...,, и далее, если перенумеровать последовательность { }=1в порядке неубывания таким образом, что (1) ≤ (2) ≤ ...
≤ (−1) ≤ () , тотакая последовательность будет называться вариационным рядом, а его члены — порядковыми статистиками. Случайная величина же () : () () = ()называется −ой порядковой статистикой исходной выборки. Из определенияясно, что(1) = min(1 ,..., ), () = max(1 ,..., ).(1.15)Таким образом, время отклика ,max = () или ,min = (1) в терминахтеории порядковых статистик, где , = 1, — положительные случайныевеличины времён пребывания подзапросов в системе до попадания в буфер синхронизации. Следовательно, математическое ожидание времени отклика можно вычислить, зная распределения экстремальных значений (1) и () , причемфункция распределения второй случайной величины фактически является совместной функцией распределения случайных величин 1 ,..., :() () = (max(1 ,..., ) < ) = (1 < ,..., < ),(1) () = (min(1 ,..., ) ≤ ) = 1 − (1 > ,..., > ).Обозначим через () — функцию распределения, а через () — плотностьраспределения случайной величины , = 1,. Если сделать допущение отом, что 1 ,..., — независимые, что в нашем случае, как уже говорилось выше,30является упрощающим предположением, то [54]:() () = (1 < ,..., < ) =∏︁ (),=1∏︁(1) () = 1 − (1 > ,..., > ) = 1 − [1 − ()],=1а -ый момент случайной величины времени отклика можно определить, вычислив интеграл:[,max] ≈ [()]=∫︁∞ () (),0[,min] ≈ [(1)]=∫︁∞ (1) (),0где∑︁ () ∏︁() () = (),()=1=1(1) () =∑︁ ()=1∏︁1 − ()=11 − ().Далее, если предположить, что серверы являются однородными, т.е.
случайные величины 1 ,..., не только независимы, но и одинаково распределены,а, следовательно, их функции и плотности распределения равны между собой: () = (), () = (), = 1,, то (1 < ,..., < ) = (),1 − (1 > ,..., > ) = 1 − (1 − ()) ,и, соответственно,[()]=∫︁∞ () −1 (),(1.16) ()(1 − ())−1 .(1.17)0[(1)]=∫︁∞031Также заметим, что математическое ожидание максимума н.о.р.с.в. можнопредставить в виде [100]:∫︁∞[() ] =0∫︁∞ () = [1 − ()].(1.18)0Для того чтобы проанализировать время отклика, необходимо вычислить указанные интегралы. В зависимости от типа распределения для оценки интегралов могут быть применены численные методы, однако для таких распределений,как экспоненциальное, гиперэкспоненциальное и распределение Эрланга 2-гопорядка, распределение Кокса, результат может быть получен в символьномвиде [100–102]. Вычислительные затраты увеличиваются с ростом ветвей () иувеличением порядка для распределений Эрланга или Кокса.
Для уменьшениявычислительных затрат при вычислении максимума может быть использованхарактеристический максимум [103].Экспоненциальное распределение. Допустим, что времена пребыванияподзапросов в подсистемах являются независимыми экспоненциально распределёнными случайными величинами с плотностями распределения () = − , > 0, = 1,Для того, чтобы определить моменты высшего порядка максимума независимых экспоненциальных случайных величин, эффективнее с вычислительной точки зрения может быть дифференцирование соответствующее числораз преобразования Лапласа-Стилтьеса (ПЛС) совместной функции распределения максимума () () по и в последующем приравнивание к нулю. Вчастности, для случая = 2 функция распределения, плотность распределения и ПЛС [75; 76] равны:(2) () = 1 ()2 () = 1 − −1 − −2 + −(1 +2 ) ,(2) () =2 ()= 1 ()2 () + 2 ()1 () == 1 −1 + 2 −2 − (1 + 2 )−(1 +2 ) ,32∫︁∞(2) () =2 ()− =21 + 21+−.
+ 1 + 2 + 1 + 20Тогда математическое ожидаемое максимума равно [75; 76; 100; 102]:(2)⃒2 () ⃒⃒=−⃒ ⃒==0111+−.1 2 1 + 2(1.19)Общее выражение для ПЛС максимума экспоненциально распределённых случайных величин может быть записано в следующем виде [31]:() () =∑︁(−1)−1=1( ) ∑︁∑︁∑︀=1 =1 +=1 (+−1)∑︀=1 (+−1),(1.20)где ( + − 1) обозначает сложение по модулю . Кроме того, ПЛС максимума независимых экспоненциально распределённых случайных величинс параметрами = (1 ,..., ) и плотностью распределения () (,) с ПЛС() (,) можно представить с помощью рекуррентной формулы [28]:(︀+∑︁)︀ () (,) =∑︁ (−1) (/ ,), 1 ≤ ≤ ,(1.21)=1=1где «/» означает исключение , т.е.
/ = (1 ,...,−1 , +1 ,..., ) и 0 (0,) =1. Тогда момент -ого порядка максимума независимых экспоненциальнораспределённых случайных величин равен: (,) = ∑︀=1 ∑︀ (, − 1) +=1 −1 (/ ,),∑︀=1 (1.22) ≥ 1, 0 (0,) = 0 для всех ≥ 1 и (,0) = 1 для всех ≥ 0.Распределение Эрланга.
Формула для аппроксимации среднего времениотклика fork-join системы с распределением Эрланга −го порядка ( ), которое представляет собой сумму независимых случайных величин, распределённых по одному и тому же экспоненциальному закону с параметром длявремени пребывания в -ой ветви системы, = 1, с функцией и плотностью33распределения: () = 1 − − −1∑︁( )=0!, ( ) −1 − () =,( − 1)!(1.23)где ≥ 0; = 1,2,...; ≥ 0, а математическое ожидание равно / , представлена в [25]:)︃]︃(︃∫︁∞ [︃ −1∏︁∑︁( )[, max ] ≈1−1 − − .!=00(1.24)=1Для случая = 2:)︂1 −1 ∑︁2 −1 (︂2∑︁∑︁+1 2[2, max ] ≈−. =0 =0(1 + 2 )++1(1.25)=1Распределение экстремальных значений.
Ещё один метод вычислениямаксимума н.о.р.с.в. — это его аппроксимация распределением экстремальныхзначений [26]. Распределение экстремальных значений представляет собой предельное распределение наибольшего () (или, соответственно, наименьшего(1) ) из значений н.о.р. непрерывных с.в. при устремлении к бесконечностиих количества → ∞, т.е., говоря иными словами, это предельное распределение наибольшего или, соответственно, наименьшего выборочного значенияпри условии бесконечного роста объёма выборки [26], хотя, конечно, нельзясказать, что распределение экстремального значения — это распределение ()при → ∞, поскольку фактически оно будет вырожденным, поэтому, чтобыполучить невырожденное предельное распределение, рассматривают линейноепреобразование () с коэффициентами, которые зависят от объёма выборки,что в действительности аналогично нормировке, но по большому счёту не исчерпывается только комбинациями линейных преобразований [26].Существует три типа семейств экстремальных распределений [26]:1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
