Диссертация (1155093), страница 11

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 11)

+1,+1,() по формуле (3.32),+1() по формуле (3.32) при = 0,v. +1,1,(e) для значения = 1 вычислить+i. ,,по формуле (3.27),+для значений , меняющихся от ( − 1) доii. ,,0 c шагом (−1), по формуле (3.28),+1+iii. +1,+1,по формуле (3.29),iv. для значения = − 1++1A. +1,+1,() по формуле (3.32).3.2 Рекуррентный алгоритм вычисления преобразованияЛапласа-Стилтьеса времени отклика системы с ограничением наодновременное число активацийСлабой стороной исходной модели является чрезвычайно большая мощность пространства состояний, которая имеет квадратичную зависимость отколичества серверов.

Поэтому теперь рассмотрим упрощённую модель с уменьшенным пространством состояний благодаря наложению ограничения на максимальное количество одновременно возможных активаций, и проведём анализ её характеристик с помощью известных свойств преобразования ЛапласаСтилтьеса, алгоритм получения которого и будет предложен далее.

Также заметим, что результаты численного эксперимента в [74] позволяют сделать выводо том, что аппроксимация исходной модели упрощённой является допустимойввиду положительного с точки зрения инженерных расчетов результата, поскольку максимальная погрешность приближения составляет не более 10%.Итак, рассматривается система облачных вычислений с гистерезиснымподключением и отключением дополнительных виртуальных машин в видемноголинейной системы массового обслуживания с приборами, часть которых может быть не активна, и конечной ёмкостью системы . В систему71поступает пуассоновский поток заявок с параметром . Считаем, что приборыявляются однородными, время обслуживания распределено по экспоненциальному закону с параметром [74; 82].Активным в пустой системе, т.е.

готовым при поступлении заявки мгновенно начать ее обслуживание, является один прибор. При поступлении заявокв систему активация приборов происходит не мгновенно, при этом количествоактивных приборов определяется числом заявок в очереди, в которой установлены парные пороги, заданные значениями векторов H = (1 ,2 ,...,−1 ),1 < 2 < ... < −1 и L = (1 ,2 ,...,−1 ), 1 < 2 < ... < −1 где+1 < , = 1, − 2 и < , = 1, − 1. Заявки обслуживаются в порядке поступления, т.е. очередь имеет дисциплину FCFS.

При поступлении наприбор заявка сохраняет место в очереди. Правила работы системы следующие:1. Если в системе уже находится заявок, то при поступлении новойзаявки активируется (подключается) один ( + 1)-й дополнительныйприбор, но не мгновенно, а через случайное время, имеющее экспоненциальное распределение с параметром ;2. Если в системе есть заявок и при этом одна заявка обслужилась, то( + 1)-й прибор мгновенно отключается, либо, если он не был активен,останавливается процедура его активации.̃︀ с множеФункционирование системы описывается марковским процессом ()ством состояний:⃒⎧⎫⃒⎪⎪ = 1, = 1;⃒ 0 ≤ ≤ 1 ,⎪⎪⎪⎪⃒⎪⎪⎨⎬⃒ −1 ≤ ≤ , = 2, = − 1,̃︀⃒,(3.33) = (,,) ⃒⎪⎪3,−1,=−2,≤≤,=−1⎪⃒⎪⎪⎪⎪⃒⎪⎩⎭⃒ −1 ≤ ≤ , = , = − 2,где — необходимое количество приборов для обслуживания заявок, находящихся в системе; — количество активированных приборов; — количествозаявок в очереди.На рисунке 3.3 представлена диаграмма интенсивностей переходов упрощённой модели в случае выбора описанного выше расположения порогов, числоприборов = 4.Сформулируем утверждение [82].721,1,11,1,0...

1,1, L1  11,1, 2...1,1, H122,1, L1 ...2,1, L2  1222223,1, H1... 2, 2, H 223,1, L2 ...322... 2,1, H 22, 2, H1  12, 2, L1 ... 2, 2, L2  1 ...22,1, H1  1...... 3,1, L3  1 ...23,1, H 2  1...23,1, H 32... 3, 2, L3  1 ... 3, 2, H 2  1 ...

3, 2, H 33, 2, L2 ... 3, 2, H12 22 2222 2... 3,3, L3  1 ... 3,3, H 2  1 ... 3,3, H 33,3, L2 ... 3,3, H13 3333 33 324, 2, L3 ... 4, 2, H 22 22 34224,3, L3 ... 4,3, H 2......4, 2, L4  1...224, 2, H 3  1224,3, L4  1 2... 4, 2, R2 2 2...4,3, H 3  1 ... 4, 3, R3 333 333  ... 4, 4, H 3  1 ... 4, 4, R4, 4, L4  14, 4, L3 ... 4, 4, H 2 ...4 44 444443Рисунок 3.3 — Диаграмма интенсивностей переходов для упрощённой моделиУтверждение 3.2.1. Преобразование Лапласа-Стилтьеса ̃︀ () времени ожи̃︁ () времени пребывания заявки в систедания начала обслуживания и ПЛС ме равны:∑︁̃︀ () =̃︀,, ̃︀,,,(3.34)(,,)∈̃︀̃︁ () = ̃︀ (),+(3.35)где ̃︀,, – стационарные вероятности соответствующих состояний (,,) ∈̃︀ а ̃︀ () – ПЛС времени ожидания -й в очереди заявки, если система,,,находится в состоянии (,,), определяются следующими рекуррентными73выражениями (3.36)-(3.47):̃︀,,() = 1,̃︀,,() =̃︀ ≤ , (,,) ∈ ;−1̃︀,,−1() +̃︀,,+1(), + + + + (3.36)(3.37) < ≤ , 1 ≤ ≤ , −1 < < ;̃︀,,() =−1−1̃︀−1,−1,()+̃︀,,(),−1 +1−1 −1 + + + + (3.38) < ≤ −1 , 2 ≤ ≤ ;̃︀,,() =−1̃︀,,()+̃︀+1,,(),−1 +1 + + + + (3.39) < ≤ , 1 ≤ ≤ − 1;̃︀,,() = ̃︀ −1(), + ,,−1 < ≤ ;( − 2)−1̃︀,−2,−1()+ + ( − 2) + 2 + +̃︀,−2,+1()+ + ( − 2) + 2 + 2+̃︀,−1,(), + ( − 2) + 2 + (3.40)̃︀,−2,() =(3.41) − 2 < ≤ , 2 ≤ ≤ , −1 < < ;( − 1)−1̃︀,−1,−1()+ + ( − 1) + + +̃︀,−1,+1()+ + ( − 1) + + +̃︀,,(), + ( − 1) + + ̃︀,−1,() = − 1 < ≤ , 2 ≤ ≤ , −1 < < ;(3.42)74( − 2)−1̃︀−1,−2,()+−1 −1 + ( − 2) + 2 + +̃︀,−2,()+−1 +1 + ( − 2) + 2 + ̃︀,−2,() =−1+2̃︀ (), + ( − 2) + 2 + ,−1,−1(3.43) − 2 < ≤ −1 , 2 ≤ ≤ ;( − 1)−1̃︀−1,−1,()+−1 −1 + ( − 1) + + ̃︀,−1,()++−1 +1 + ( − 1) + + +̃︀,,(), − 1 < ≤ −1 , 2 ≤ ≤ ;−1 + ( − 1) + + ̃︀,−1,() =−1( − 2)−1̃︀,−2,()+ −1 + ( − 2) + 2 + ̃︀+1,−1,()++ +1 + ( − 2) + 2 + (3.44)̃︀,−2,() =+2̃︀,−1,(), + ( − 2) + 2 + (3.45) − 2 < ≤ , 2 ≤ ≤ − 1;( − 1)̃︀ −1()+ + ( − 1) + + ,−1, −1+̃︀+1,−1,()+ +1 + ( − 1) + + +̃︀,,(), − 1 < ≤ , 2 ≤ ≤ − 1; + ( − 1) + + ̃︀,−1,() =̃︀,,() =(3.46)( − )−1̃︀,,−1() +̃︀,+1,(), + ( − ) + + ( − ) + (3.47) < ≤ , 1 ≤ < .Доказательство.

Доказательство утверждения аналогично доказательству,приведенному в разделе 3.1. Рекуррентные соотношения (3.36)-(3.47) позволяют75̃︀ с помощью которых() для всех состояний (,,) ∈ ,определить ПЛС ̃︀,,̃︁ ()вычисляются ПЛС ̃︀ () времени ожидания начала обслуживания и ПЛС времени пребывания заявки в системе с ограничением на одновременное количество активаций:∑︁̃︀ () =̃︀,, ̃︀,,();(,,)∈̃︀̃︁ () = ̃︀ (),+где ̃︀,, — стационарные вероятности для соответствующих состояний (,,),алгоритм вычисления которых приведен в [74].Теперь на основе базовых рекуррентных соотношений запишем формулыдля конкретных состояний, на основе которых впоследствии и построим самалгоритм:̃︀̃︀,,() = 1, ≤ , (,,) ∈ ;(3.48)+1̃︀,,() =+1̃︀,,() =; + +1+̃︀,,+1(), + + + + +1̃︀,,() =(3.49)−1 < ≤ − 1; (3.50)( − )+, + ( − ) + + ( − ) + ̃︀,−1,() =1 ≤ < ;( − 1)++ + ( − 1) + + + ( − 1) + + +̃︀,−1,+1(), + ( − 1) + + (3.51)(3.52)−1 ≤ ≤ − 1;( − 2)2++ + ( − 2) + 2 + + ( − 2) + 2 + +̃︀ −1(),−1 ≤ ≤ − 1; + ( − 2) + 2 + ,−2,+1−1̃︀,−2,() =(3.53)76+1̃︀,,() =+1+̃︀+1,,(), +1 + + + + +1̃︀,,() =1 ≤ ≤ − 1;+1+̃︀,,+1(), + + + + (3.54)(3.55)1 ≤ < , −1 < ≤ − 1;+2̃︀+1,+1,() =( + 1)+1̃︀,,()+ −1 + ( + 1) + +2+̃︀+1,+1,(), +1 + ( + 1) + (3.56)1 ≤ ≤ − 1;( − 1)++ + ( − 1) + + + ( − 1) + + +̃︀+1,−1,(), 2 ≤ ≤ − 1; +1 + ( − 1) + + (3.57)( − 2)2++ + ( − 2) + 2 + + ( − 2) + 2 + +̃︀+1,−1,(), 2 < ≤ − 1; +1 + ( − 2) + 2 + (3.58)̃︀,−1,() =−1̃︀,−2,() =̃︀,−1,() =( − 1)++ + ( − 1) + + + ( − 1) + + +̃︀,−1,+1(), + ( − 1) + + −1̃︀,−2,() =2 ≤ < , −1 < ≤ − 1;( − 2)2++ + ( − 2) + 2 + + ( − 2) + 2 + −1+̃︀,−2,+1(), + ( − 2) + 2 + (3.59)2 < < , −1 < ≤ − 1;(3.60)77+1+̃︀+1,,()+ +1 + + + + + + , 1 ≤ ≤ − 1;+ + + + +1̃︀+1,,() =( − 1)+ + ( − 1) + 2 + 2̃︀+1,−1,()+,++1 + ( − 1) + 2 + + ( − 1) + 2 + (3.61)̃︀+1,−1,() =(3.62)1 ≤ ≤ − 1;+̃︀,,() =+̃︀,,() = ̃︀ +−1(), + ,,−12 ≤ ≤ − ;+−1+̃︀,,−1() +̃︀,,+1(), + + + + (3.63)(3.64)2 ≤ ≤ − , −1 < ≤ − 1;+̃︀,,() =( − )+−1+̃︀,,−1() +̃︀,+1,(), + ( − ) + + ( − ) + (3.65)2 ≤ ≤ − , 1 ≤ < ;( − 1)−2+̃︀,−1,−1()+ + ( − 1) + + −1+−1++̃︀,−1,+1() +̃︀,,(), + ( − 1) + + + ( − 1) + + −1+̃︀,−1,() =2 ≤ ≤ − + 1, −1 < ≤ − 1;(3.66)78( − 2)−3+̃︀,−2,−1()+ + ( − 2) + 2 + 2−2+−2++̃︀,−2,+1() +̃︀,−1,(), + ( − 2) + 2 + + ( − 2) + 2 + −2+̃︀,−2,() =2 ≤ ≤ − + 2, −1 < ≤ − 1;(3.67)+̃︀,,() =+−1+̃︀,,()+̃︀+1,,(),−1 +1 + + + + (3.68)2 ≤ ≤ − , 1 ≤ ≤ − 1;+̃︀,,() =+−1+̃︀,,−1() +̃︀,,+1(), + + + + (3.69)2 ≤ ≤ − , 1 ≤ ≤ , −1 < ≤ − 1;+1+̃︀+1,+1,() =+( + 1)+̃︀,,()+ −1 + ( + 1) + ̃︀ +1+(), + ( + 1) + +1,+1, +12 ≤ ≤ − − 1,(3.70)1 ≤ ≤ − 1;( − 1)−2+̃︀,−1,()+ −1 + ( − 1) + + −1+̃︀+1,−1,()++ +1 + ( − 1) + + −1+̃︀,,(), 2 ≤ ≤ − + 1,+ + ( − 1) + + −1+̃︀,−1,() =(3.71)2 ≤ ≤ − 1;( − 2)−3+̃︀,−2,()+ −1 + ( − 2) + 2 + 2−2+−2++̃︀+1,−1,()+̃︀,−1,(),+1 + ( − 2) + 2 + + ( − 2) + 2 + −2+̃︀,−2,() =2 ≤ ≤ − + 2, 2 < ≤ − 1;(3.72)79( − 2)−3+̃︀,−2,−1()+ + ( − 2) + 2 + 2−2+−2++̃︀,−2,+1() +̃︀,−1,(), (3.73) + ( − 2) + 2 + + ( − 2) + 2 + −2+̃︀,−2,() =2 ≤ ≤ − + 2, 2 < ≤ , −1 < ≤ − 1;( − 1)−2+̃︀,−1,−1()+ + ( − 1) + + −1+−1++̃︀,−1,+1() +̃︀,,(), (3.74) + ( − 1) + + + ( − 1) + + −1+̃︀,−1,() =2 ≤ ≤ − + 1, 2 ≤ ≤ , −1 < ≤ − 1;+−1+̃︀,,() +̃︀+1,,()+ −1 +1 + + + + + + ++̃︀+1,+1,(), 2 ≤ ≤ − , 1 ≤ ≤ − 1; + + + (3.75)+̃︀+1,,() =( − 1)−2+̃︀,−1,()+ −1 + ( − 1) + 2 + 2−1+−1++̃︀+1,−1,()+̃︀+1,,(),+1 + ( − 1) + 2 + + ( − 1) + 2 + −1+̃︀+1,−1,() =2 ≤ ≤ − + 1, 2 ≤ ≤ .(3.76)Далее подробно опишем последовательность применения рекуррентныхформул для конкретных состояний, т.е.

выпишем непосредственно сам алгоритм:+11. вычислить ПЛС ̃︀,,() по формуле (3.49);+12. вычислить ПЛС ̃︀,,() для значений , меняющихся от ( − 1) до(−1 + 1) c шагом (−1), по формуле (3.50);3. для значений , меняющихся от ( − 1) до 1 c шагом (−1), вычислитьПЛС+1(a) ̃︀,,() по формуле (3.51),804.

Характеристики

Список файлов диссертации