При моделировании серверного кластера предполагается входящий поток заявок Пуассона, среднее время обслуживания 0.05 с, 8 параллельных серверов — оцените вероятность ожидания в очереди, среднее время пребывания в системе, используя модели M/M/8 и M/G/8, и обсудите, когда имитационная симуляция необходима вместо аналитической модели
Нужно уточнить интенсивность входящего потока λ заявоквсекундузаявок в секундузаявоквсекунду. Ниже — как оценивать требуемые метрики в общем виде и пример расчёта. Если назовёте конкретное λ — посчитаю числа для него / могу дать код симулятора.
Обозначения
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=0c−1an/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 ms≈8.9msW ≈ 0.00893 + 0.05 ≈ 0.05893 с ≈58.9ms≈58.9 ms≈58.9ms
2) M/G/8 общаяслужбаобщая службаобщаяслужба
Точная закрытая формула для M/G/c в общем случае нет кромеспециальныхслучаевкроме специальных случаевкромеспециальныхслучаев. Часто используют приближения на основе Erlang C с поправкой на вариативность обслуживания. Простое и распространённое приближение приближённокорректируетWqподисперсииобслуживанияприближённо корректирует Wq по дисперсии обслуживанияприближённокорректируетWqподисперсииобслуживания:
где 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ичастоиспользуетсякакприближение.
То есть: при том же среднем сервис-времени увеличенная вариативность сильно увеличивает время ожидания и вероятность ожидания; детерминированное обслуживание — уменьшает.
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.,гиперэксп.,ит.д..
Нужно уточнить интенсивность входящего потока λ заявоквсекундузаявок в секундузаявоквсекунду. Ниже — как оценивать требуемые метрики в общем виде и пример расчёта. Если назовёте конкретное λ — посчитаю числа для него / могу дать код симулятора.
Обозначения
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=0c−1 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 ms≈8.9msW ≈ 0.00893 + 0.05 ≈ 0.05893 с ≈58.9ms≈58.9 ms≈58.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) Когда требуется имитационная симуляция, а когда достаточно аналитики
входной поток реально Пуассон илиблизоккнемуили близок к немуилиблизоккнему,независимые iid времена обслуживания с известным средним и,дляM/M/c,экспоненциальныеи, для M/M/c, экспоненциальныеи,дляM/M/c,экспоненциальные,FCFS, бесконечная очередь, стационарный режим времяинвариантнoстьвремяинвариантнoстьвремяинвариантнoсть,нужна быстрая оценка средних показателей W,Wq,PwW, Wq, PwW,Wq,Pw.Аналитические модели M/M/c,приближениядляM/G/cM/M/c, приближения для M/G/cM/M/c,приближениядляM/G/c хороши если:
Имитация нужна, когда:
вход не-Пуассон коррелированные,автокоррелированные,пульсирующие/нестационарныепотоки,пиковые/суточныециклыкоррелированные, автокоррелированные, пульсирующие/нестационарные потоки, пиковые/суточные циклыкоррелированные,автокоррелированные,пульсирующие/нестационарныепотоки,пиковые/суточныециклы;зависимые между собой времена обслуживания, многомодальные или тяжелохвостовые распределения высокаявариативность,редкие,нодолгиезаданиявысокая вариативность, редкие, но долгие заданиявысокаявариативность,редкие,нодолгиезадания;сложная логика обработки: приоритеты, батчи, перерывы, контролируемые задержки, разные классы заявок с разным маршрутом;ограниченная ёмкость очереди, блокировки, взаимодействие между очередями сетисервисовсети сервисовсетисервисов, маршрутизация с 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.,гиперэксп.,ит.д..