При моделировании серверного кластера предполагается входящий поток заявок Пуассона, среднее время обслуживания 0.05 с, 8 параллельных серверов — оцените вероятность ожидания в очереди, среднее время пребывания в системе, используя модели M/M/8 и M/G/8, и обсудите, когда имитационная симуляция необходима вместо аналитической модели

10 Окт в 13:31
8 +8
0
Ответы
1

Нужно уточнить интенсивность входящего потока λ заявоквсекундузаявок в секундузаявоквсекунду. Ниже — как оценивать требуемые метрики в общем виде и пример расчёта. Если назовёте конкретное λ — посчитаю числа для него / могу дать код симулятора.

Обозначения

c = 8 числосерверовчисло серверовчислосерверовсреднее время обслуживания = 0.05 с ⇒ μ = 1/0.05 = 20 обслуживанийвсекундунасерверобслуживаний в секунду на серверобслуживанийвсекундунасерверλ — интенсивность входящего Пуассон-потока заявок/сзаявок/сзаявок/сa = λ/μ — суммарная нагрузка offeredloadoffered loadofferedloadρ = a / c = λ / cμc μcμ — загрузка одного сервера (должно быть < 1 для стационарности)C_s^2 — квадратичный коэффициент вариации времени обслуживания Var(S)/E[S]2Var(S)/E[S]^2Var(S)/E[S]2. Для экспоненциального обслуживания C_s^2 = 1; для детерминированного C_s^2 = 0; для сильно вариабельного — >1.

1) M/M/8 аналитически—формулаЭрлангаCаналитически — формула Эрланга CаналитическиформулаЭрлангаC Пусть a = λ/μ и ρ = a/c < 1. Тогда

P0 = sumn=0c−1an/n!+(ac/c!)∗(1/(1−ρ)) sum_{n=0}^{c-1} a^n/n! + (a^c / c!) * (1/(1−ρ)) sumn=0c1 an/n!+(ac/c!)(1/(1ρ))^{-1}Вероятность ожидания в очереди ErlangCErlang CErlangC: Pw = ac/c!a^c / c!ac/c! 1/(1−ρ)1/(1−ρ)1/(1ρ) P0Среднее число заявок в очереди: Lq = P0<em>ac</em>ρP0 <em> a^c </em> ρP0<em>ac</em>ρ / c!∗(1−ρ)2c! * (1−ρ)^2c!(1ρ)2Среднее время ожидания в очереди: Wq = Lq / λСреднее время в системе: W = Wq + 1/μ

Этиформулыстандартны;приρ≥1системаперегружена—средниестремятсякбесконечности.Эти формулы стандартны; при ρ≥1 система перегружена — средние стремятся к бесконечности.Этиформулыстандартны;приρ1системаперегруженасредниестремятсякбесконечности.

Пример иллюстрацияиллюстрацияиллюстрация. Пусть λ = 120 заявок/с.

μ = 20, a = 120/20 = 6, c = 8 ⇒ ρ = 6/8 = 0.75.По формулам получаем вычислениявявномвидеопущенывычисления в явном виде опущенывычислениявявномвидеопущены:
P0 ≈ 0.002142Pw ≈ 0.357 ≈35.7≈35.7% заявок ждут35.7Lq ≈ 1.071 всреднем 1.07заявкивочередив среднем ~1.07 заявки в очередивсреднем 1.07заявкивочередиWq = Lq/λ ≈ 1.071/120 ≈ 0.00893 с ≈8.9ms≈8.9 ms8.9msW ≈ 0.00893 + 0.05 ≈ 0.05893 с ≈58.9ms≈58.9 ms58.9ms

2) M/G/8 общаяслужбаобщая службаобщаяслужба Точная закрытая формула для M/G/c в общем случае нет кромеспециальныхслучаевкроме специальных случаевкромеспециальныхслучаев. Часто используют приближения на основе Erlang C с поправкой на вариативность обслуживания. Простое и распространённое приближение приближённокорректируетWqподисперсииобслуживанияприближённо корректирует Wq по дисперсии обслуживанияприближённокорректируетWqподисперсииобслуживания:

WqM/G/cM/G/cM/G/c(1+Cs2)/2(1 + C_s^2)/2(1+Cs2 )/2 * WqM/M/cM/M/cM/M/c,

где WqM/M/cM/M/cM/M/c — рассчитанное выше значение для экспоненциального обслуживания с тем же средним 1/μ. Для Pw обычно используют Pw ≈ PwErlangCErlangCErlangC как приближение; затем Lq ≈ λ Wq, из чего можно восстановить приближённое Pw через связь Pw ≈ Lq 1−ρ1−ρ1ρэтасвязьточновернадляM/M/cичастоиспользуетсякакприближениеэта связь точно верна для M/M/c и часто используется как приближениеэтасвязьточновернадляM/M/cичастоиспользуетсякакприближение.

Примеры дляλ=120/с,Wq(M/M/c)≈0.00893с,ρ=0.75для λ = 120/с, Wq(M/M/c) ≈ 0.00893 с, ρ = 0.75дляλ=120/с,Wq(M/M/c)0.00893с,ρ=0.75:

детерминированное обслуживание Cs2=0C_s^2 = 0Cs2 =0: множитель = 0.5 ⇒ Wq ≈ 0.00446 с, W ≈ 0.05446 с; Lq ≈ 0.536; приближённо Pw ≈ 0.179.более вариабельное обслуживание, допустим C_s^2 = 2: множитель = 1.5 ⇒ Wq ≈ 0.01339 с, W ≈ 0.06339 с; Lq ≈ 1.607; приближённо Pw ≈ 0.536.

То есть: при том же среднем сервис-­времени увеличенная вариативность сильно увеличивает время ожидания и вероятность ожидания; детерминированное обслуживание — уменьшает.

3) Когда требуется имитационная симуляция, а когда достаточно аналитики
Аналитические модели M/M/c,приближениядляM/G/cM/M/c, приближения для M/G/cM/M/c,приближениядляM/G/c хороши если:

входной поток реально Пуассон илиблизоккнемуили близок к немуилиблизоккнему,независимые iid времена обслуживания с известным средним и,дляM/M/c,экспоненциальныеи, для M/M/c, экспоненциальныеи,дляM/M/c,экспоненциальные,FCFS, бесконечная очередь, стационарный режим времяинвариантнoстьвремяинвариантнoстьвремяинвариантнoсть,нужна быстрая оценка средних показателей W,Wq,PwW, Wq, PwW,Wq,Pw.

Имитация нужна, когда:

вход не-Пуассон коррелированные,автокоррелированные,пульсирующие/нестационарныепотоки,пиковые/суточныециклыкоррелированные, автокоррелированные, пульсирующие/нестационарные потоки, пиковые/суточные циклыкоррелированные,автокоррелированные,пульсирующие/нестационарныепотоки,пиковые/суточныециклы;зависимые между собой времена обслуживания, многомодальные или тяжелохвостовые распределения высокаявариативность,редкие,нодолгиезаданиявысокая вариативность, редкие, но долгие заданиявысокаявариативность,редкие,нодолгиезадания;сложная логика обработки: приоритеты, батчи, перерывы, контролируемые задержки, разные классы заявок с разным маршрутом;ограниченная ёмкость очереди, блокировки, взаимодействие между очередями сетисервисовсети сервисовсетисервисов, маршрутизация с feedback;нужно оценить конечные-выборочные распределения, высокие квантильные оценки например99.9например 99.9%-перцентили задержекнапример99.9 или редкие события;требуется проверка устойчивости/валидности приближений или подтверждение аналитических выводов на реалистичных данных;требуется учесть стартовые переходныепереходныепереходные эффекты, а не только стационарные средние.

Важные замечания по симуляции: нужна корректная настройка разогрев/отсечениеinitialtransientразогрев/отсечение initial transientразогрев/отсечениеinitialtransient, достаточное число независимых прогонов, оценка доверительных интервалов, валидация модели данных и распределений.

Если хотите — могу:

посчитать точные числа для вашего конкретного λ;дать код напримернаPython/SimPyилиRнапример на Python/SimPy или RнапримернаPython/SimPyилиR для имитационной модели кластера и показать как получить средние, квантили и доверительные интервалы;прогнать сравнение M/M/8 vs M/G/8 для заданных распределений обслуживания детermin.,гиперэксп.,ит.д.детermin., гиперэксп., и т.д.детermin.,гиперэксп.,ит.д..
10 Окт в 14:03
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Прямой эфир