Диссертация (1155093), страница 5
Текст из файла (страница 5)
1, max , и времени, проведённого21подзапросом в системе после обслуживания на сервере в ожидании второго, идо ухода из нее (время синхронизации) :[2, max ] = [1, max ] + [].(1.3)Согласно формуле Литтла, = 2[], где — это среднее числоподзапросов, которые обслужились на приборе и ждут свою пару [51–53]. Через обозначим вероятность того, что число подзапросов во второй очередипревышает число подзапросов в первой очереди на . Благодаря симметрии∑︀ = − , ≥ 1 и, таким образом, = 2 ∞=1 , следовательно,∞1 ∑︁ .[] =(1.4)=1Из уравнений, представленных в [18], можно получить: =∞∑︁,0 .(1.5)=тогда = +1 + ,0 , где ,0 — это вероятность того, что в первой очерединаходится подзапросов, а во второй — ноль. Далее с учётом формулы (1.1)можем записать: (,0) = (0,) = () =∞∑︁,0 ==0(1 − )3/2.(1 − )1/2(1.6)Затем подставляем в формулу для времени синхронизации выражение для из (1.5) и меняем порядок суммирования:∞∞∞∞∑︁1 ∑︁ ∑︁1 ∑︁1 ∑︁ ( + 1),0=,0 .[] =,0 = =1 =12=1=(1.7)=1Потом вычисляем значения первой и второй производной при = 1 от выражения для производящей функции (,0), полученном в (1.6) и от выражения,22которое записывается исходя из определения этой функции:⃒∞∑︁1 () ⃒⃒= =,0 , ⃒=1 2=1⃒∞∞∑︁∑︁322 () ⃒⃒2== ,0 −,0 .
2 ⃒=1 4(1 − )=1=1Теперь можем подставить полученные формулы в (1.7):(︂ ∞)︂(︂)︂∞∑︁1 ∑︁ 21 2 + 2(4 − )[] = ,0 +,0 =+=,2 =124(1−)28(1−)=1(1.8)следовательно, среднее время отклика определяется следующим выражением:[2, max ] = [1, max ] + [] =112 − 12 − ·=[1, max ].8−8Аппроксимация времени отклика.Эмпирическая формула аппроксимации. Один из способов аппроксимации времени отклика для fork-join системы с ветвями //1 и одинаковыми интенсивностями обслуживания на серверах был предложен в [18].
Идеяпредложенного метода аппроксимации появилась из наблюдения за поведениемвремени отклика при проведении численных экспериментов.Верхнюю границу для среднего времени отклика можно получить, сделавдопущение о независимости случайных величин времён пребывания подзапросов в системе, или, что тоже самое, рассмотреть СеМО, состоящую из независимых параллельно функционирующих систем //1.
Данное предположениеподтверждается приведённым в [18] доказательством того факта, что случайные величины времён пребывания подзапросов в системе являются положительно ассоциированными. По определению [93] две случайные величины и являются положительно ассоциированными, если [ ()()] ≥ [ ()][()],т.е. ковариация любых пар неубывающих функций и является неотрицательной, а одно из свойств положительно ассоциированных случайных величин231 , 2 ,... заключается в том, что [93] ( max > ) ≤ 1 −1≤≤∏︁ ( < ).=1Нижняя граница для среднего времени отклика получается, если «пренебречь» очередями (т.е. для значений близких к нулю): в этом случае времяотклика будет являться максимумом независимых одинаково распределённых случайных величин (н.о.р.с.в.) со средним 1/.Таким образом, имеем:1≤ [,max ] ≤ [ ],∑︀где ==1 1/ — это частичная сумма гармонического ряда.
Верхняя инижняя граница растут с одной и той же скоростью , иными словами, длябольших значений границы имеют порядок (ln ). Поэтому, зная значение[2,max ], можем записать: [, max ] ≈ ()[2, max ], где () — это коэффициент масштабирования, растущий со скоростью (ln ). Следовательно,аппроксимация времени отклика может быть представлена в следующем виде: = () + () . Поскольку по определению 2 () = 1, то, подставив этозначение в предыдущее выражение, получим, что () = (1 − ())/2 , такимобразом,1 − () , ≥ 2.
() = () +2Посредством имитационного моделирования в [18] определяется значение() ≈ 4/11. Окончательно имеем[︃[,max ] ≈(︃)︃ ]︃412 − 1+1−,21128 − ≤ 2.(1.9)Полученное приближение, исходя из численного анализа, приведённого авторами, имеет погрешность аппроксимации не превышающую 5% для значений2 ≤ ≤ 32.В статье [20] исследуется аналогичная fork-join система с ветвями//1. Полученная аппроксимация является средним арифметическим верхней и нижней оценок. В качестве верхней оценки используется видоизменённое24выражение для верхней оценки из вышеупомянутой работы [18]. Нижняя оценка получается при анализе эквивалентной величины времени отклика, но длясистемы с непараллельной организацией очереди [71].
Итак,(︃1 + ∑︁=11( − ))︃(︃≤ [,max ] ≤)︃1+=1−(︃)︃∑︁11= + .(1 − )=1Далее вычисляется среднее арифметическое полученных оценок, в результатечего имеем:[︃(︃ )︃]︃∑︁ 1∑︁11[,max ] ≈ ++ (1 − 2). (1.10)2(1 − )−( − )=1=1Интерполяция с помощью предельных значений загрузки системы.В [21] предложен другой метод аппроксимации времени отклика — комбинацияметодов интерполяции высокой и слабой входных нагрузок (heavy and lighttraffic interpolation approximations). Указанные техники в отличие от описанноговыше метода не используют результаты имитационного моделирования, однакоих применение может быть расширено и до анализа fork-join систем не толькос экспоненциальным временем обслуживания или c пуассоновским входящимпотоком.Для рассматриваемой задачи найти решение в аналитическом виде оченьзатруднительно, однако возможно получить асимптотические формулы для искомых характеристик.
Интерполяция слабой загрузкой системы является результатом её работы в режиме слабой нагрузки, т.е. когда интенсивность входящего потока очень мала. В этом случае целесообразно обратиться к разложению в ряд Тэйлора характеристик производительности системы (в частности,функции распределения времени отклика — как функции от — в окрестности нуля), с помощью которого можно определить неизвестные величины впредставлении исследуемой функции в виде полинома от порядка .
Рассматриваются только полиномы нулевой и первой степени. Если же говоритьоб интерполяции с помощью высокой загрузки, то для fork-join системы речьидёт об анализе такого режима, в котором значение очень близко к значе-25нию . Ключевым параметром при интерполяции с помощью метода высокойнагрузки является параметр , два крайних значения которого интерпретируются как два предельных случая: если = 0, то это означает, что входящийпоток является детерминированным, если = 1, то время обслуживания — детерминированное, а ветви fork-join системы являются независимыми //1и //1 СМО, соответственно.Таким образом, благодаря исследованию поведения функции времени отклика в граничных значениях загрузки системы, удаётся, в отличие от метода,описанного в [18], не прибегая к численным экспериментам для определенияконстант в интерполяционной формуле, определить их точные выражения взамкнутой форме.Для случая fork-join системы с ветвями //1 аппроксимация времени отклика имеет вид:]︃[︃(︁)︁ 1, 0 ≤ , ≥ 2,(1.11)[,max ] ≈ + − −где (︂ )︂ (︂ )︂∑︁∑︁ ( − 1)!−1 =(−1).+1=1=1В случае распределения Эрланга второго порядка для входящего потокас функцией распределения () = 1 − (1 + 2)−2 , ≥ 0 и для времениобслуживания с функцией распределения () = 1 − (1 + 2)−2 , ≥ 0:[︃[,max ] ≈ +(︃)︃ ]︃1− , 0 ≤ < , = 2,3,...,2 −(1.12)где (︂ )︂ (︂ )︂∑︁1 ∑︁ !−1 ≡, = 2,3,...(−1)+1 =1 2=0Также в работе [21] для того, чтобы получить оценку среднего времени отклика в случаях с другими распределениями для входящего потока и времениобслуживания метод интерполяции высокой нагрузки был модифицирован, ианализировались три значения ключевой константы = 0, 1/2, 1, что привело кквадратичной интерполяции, благодаря которой, в сочетании с методом низкой26нагрузки, были получены формулы аппроксимации среднего времени откликадля следующих немарковских случаев:– распределение Эрланга второго порядка для входящего потока с функцией распределения () = 1−(1+2)−2 , ≥ 0 и экспоненциальноевремя обслуживания с функцией распределения () = 1 − − , ≥ 0:[︃(︃[,max ] ≈ +)︃ ]︃251 1 − −,3612 − 0 ≤ < , = 2,3,...; (1.13)– пуассоновский входящий поток с функцией распределения () =1 − − , ≥ 0 и распределение Эрланга второго порядка времени обслуживания с функцией распределения () = 1−(1+2)−2 , ≥ 0:[︃[,max ] ≈ +(︃)︃ ]︃11 2−+ − ,6123 −0 ≤ < , = 2,3,..., (1.14)а также для гиперэкспоненциального входящего потока и экспоненциальноговремени обслуживания, пуассоновского входящего потока и гиперэкспоненциального времени обслуживания, формулы для которых в силу их громоздкостиприводить не будем.Анализ с помощью матрично-геометрического метода.
Идея использования матрично-геометрического подхода при анализе fork-join систем вбольшинстве работ сводится к рассмотрению моделей, аппроксимирующих исходную, непосредственный анализ которых позволяет сделать вывод, что изучаемый процесс, описывающий поведение системы является квазипроцессом «размножения и гибели» со всеми вытекающими из этого следствиями [51–53]. Тоже касается и fork-join системы с конечными очередями к серверам в условияхпуассоновского входящего потока и экспоненциальных времен обслуживания.Так, в [14;15] был предложен алгоритм, позволяющий свести матрицу вероятностей переходов для марковского процесса, описывающего поведение системы, кблочно-диагональному виду, что дает возможность компактно записать систе-27му уравнений равновесия (СУР) и решить её одним из известных численныхметодов и, как следствие, вычислить среднее время отклика.Матрично-геометрический подход для оценки времени отклика fork-joinсистемы используется в серии статей [22–24].
В первой работе [22] были предложены две модели, аппроксимирующие исходную fork-join систему с ветвями//1 и различными интенсивностми обслуживания на разных серверах:1. поступающий запрос принимается в систему тогда и только тогда, когда число подзапросов -го типа, находящихся в системе, меньше некоторого фиксированного положительного целого числа : < , = 2,, в противном случае он теряется;2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
