Статья опубликована в №16 (декабрь) 2014
Разделы: Математика
Размещена 10.12.2014. Последняя правка: 09.12.2014.
Просмотров - 2994

ОЦЕНКА КАЧЕСТВА РАЗЛИЧНЫХ АНАЛИТИЧЕСКИХ РЕШЕНИЙ НЕМАРКОВСКИХ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ

Гаевой Сергей Владимирович

аспирант

Волгоградский государственный технический университет (ВолгГТУ)

аспирант

Научный руководитель: Фоменков Сергей Алексеевич, доктор технических наук, профессор, Волгоградский государственный технический университет (ВолгГТУ); Научный консультант: Лукьянов Виктор Сергеевич, доктор технических наук, профессор, Волгоградский государственный технический университет (ВолгГТУ)

УДК 519.872

ВВЕДЕНИЕ

Для немарковских систем массового обслуживания (СМО) часто используются аналитические решения и приближения. В рамках курса для студентов [1] нами предлагается имитационного моделирование выполнения заданий на кластерах. Аналитическое решение этой проблемы не возможно. В данной статьей мы ставим целью определить границы применимости аналитических решений немарковских СМО. В качестве эталонного измерения используется результат имитационного расчета с помощью [2].

СРАВНЕНИЕ АНАЛИТИЧЕСКОГО И ИМИТАЦИОННОГО РЕШЕНИЙ

1 Постановка задачи

В рамках данной работы будут использованы обозначения Кендалла для типов СМО [3]. Используемыми нами законами распределения являются: G, GI – произвольный закон распределения (отдельные значения в обоих случаях независимы, но некоторые авторы используют букву „I“ для того, чтобы показать это явно), M – экспоненциальное распределение, Г — гамма-распределение, lN – логнормальное распределение.

Интенсивность входящего потока заданий обозначим λ, а интенсивность обслуживания заявок μ = 1/τ, где τ — среднее время обслуживание. Нагруженность системы определяется как ρ = λτ/n, где n – число каналов обслуживания в СМО. Коэффициенты вариации входного потока заданий и времени обслуживания обозначим cov_λ и cov_μ, соответственно.

Для Г и lN может быть задан любой коэффициент вариации. При необходимости будем сопровождать закон распределения значением коэффициента вариации в скобках справа от обозначения закона. Стоит отметить, что Г с коэффициентом вариации, равным единице, превращается в M, а любое распределение с нулевым коэффициентом вариации превращается в детерминированный случай (константу, обозначается D).

Для оценки скорости обслуживания заявок воспользуемся индексом ожидания θ = T_q/τ, где T_q — среднее время ожидания заявки в очереди. Тогда средняя длина очереди в соответствии с формулой Литтла будет равна Q = nρθ, а среднее время пребывания заявки в системе T = (θ + 1)τ.

Для модели M/M/n существует точное марковское решение [4, 5]: , где , в частности . Это решение нам потребуется в дальнейшем. Существует грубое приближение [6], которым мы не будем пользоваться: .

2 Оценка M/G/1

Данная оценка представляет собой точное аналитическое решение [6, 7]:.

Сравнение аналитического расчета с имитационным дано на рисунке 1. Здесь и далее будем обозначать аналитическую оценку звездочкой. На основе этого видно, что решения совпадают. Иными словами, конкретный вид закона распределения времени выполнения не играет роли, только первые два момента распределения.

3 Оценка GI/G/n

Данная оценка является приближенной [6, 8]:

Использование оценки GI/G/1 при детерминированном характере входного потока заданий (регулярный поток) представлено на рисунке 2. Случай Г входного потока представлен на рисунках 3 и 4. В источниках говорится, что обычно эта оценка является мажорантой искомого значения, то есть ограничивает его сверху, но в случае с Г(2.0) она дает заниженное значение. Возможно, это обусловлено «тяжелым» хвостом гамма-распределения, т. к. при lN(2.0) распределения такого не наблюдается (рис. 5).

Рисунок 1 — Сравнение аналитического и имитационного расчета M/G/1

Рисунок 2 – Использование оценки GI/G/1 при регулярном потоке заданий

Рисунок 3 – Использование оценки GI/G/1 при входном потоке Г(0.5)

Рисунок 4 – Использование оценки GI/G/1 при входном потоке Г(2.0)

Рисунок 5 – Использование оценки GI/G/1 при входном потоке lN(2.0)

Рисунок 6 – Использование оценки GI/G/2 (фрагменты)

Далее мы рассмотрим набор СМО с двумя каналами: рассмотрим вариант M/G/2 (рис. 6). Мы видим случаи и слишком оптимистичной оценки (для Г(2)/D/2), так и случай пессимистичной (у lN(2)/lN(2)/2), при этом остальные оценки из рисунка 6 очень точны.

Очевидно, что все оценки типа GI/G/n приближаются к истинному результату при высокой нагруженности [6-8].

4 Оценка GI/M/1

Согласно этой оценке [9], , где σ — корень уравнения σ = F(μ - μσ) из интервала (0;1), F(p) — изображение по Лапласу от плотности вероятности GI . Для Г уравнение принимает вид .

 

Рисунок 7 – Использование оценки GI/M/1

 

Для D необходимо найти предел при cov_λ->0 (используем второй замечательный предел) : .

Структура уравнения делает удобным использование метода итераций. При старте из точки σ = 1/2 все варианты привели нас к требуемому корню.

Данная оценка так же, как и M/G/1, является точной, что видно из рисунка 7.

ЗАКЛЮЧЕНИЕ

Таким образом, был проведен анализ существующих оценок производительности немарковских СМО.

Очевидно, «общее» решение GI/G/n может быть использовано лишь при высокой загруженности. В иных случаях она обычно дает слишком пессимистичный результат, но может давать и слишком оптимистичный.

Оценки M/G/1и GI/M/1точны. Первая оценка требует простейшего входного потока и одноканальности СМО. На практике простейший поток встречается далеко не всегда, но довольно часто. Вторая оценка предполагает оперированием преобразованием Лапласа от плотности вероятности распределения GI. Для логнормального распределения, например, это уже является сложным.

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

1. Имитационное моделирование грид-систем : монография / Лукьянов В.С., Андреев А.Е., Жариков Д.Н., Островский А.А., Гаевой С.В.; ВолгГТУ. - Волгоград, 2012. - 215 с.
2. Свид. о гос. регистрации программы для ЭВМ № 2013614201 от 25 апреля 2013 г. РФ, МПК (нет). Имитационная модель для оценки влияния параметров надёжности и иных характеристик на производительность кластерной системы (SrvModel) / Гаевой С.В., Лукьянов В.С.; ВолгГТУ. - 2013.
3. Kendall's notation [Электронный ресурс] // Wikipedia. – [2014]. – Режим доступа : http://en.wikipedia.org/wiki/Kendall%27s_notation
4. M/M/c queue [Электронный ресурс] // Википедия. – [2014]. – Режим доступа : http://en.wikipedia.org/wiki/M/M/c_queue
5. The Erlang-C Formula [Электронный ресурс] // Mitan Ltd.. – [2014]. – http://www.mitan.co.uk/erlang/elgcmath.htm
6. Non-Parametric Models of a Service System; GI/GI/1, GI/GI/n: Exact & Approximate Analysis [Электронный ресурс] // The William Davidson Faculty of Industrial Engineering and Management. – [2014]. – Режим доступа : http://ie.technion.ac.il/serveng/Lectures/Lecture_GGQ's_FULL_Marked.pdf
7. Pollaczek–Khinchine formula [Электронный ресурс] // Википедия. – [2014]. – Режим доступа : http://en.wikipedia.org/wiki/Pollaczek%E2%80%93Khinchine_formula
8. Kingman's formula [Электронный ресурс] // Википедия. – [2014]. – Режим доступа : http://en.wikipedia.org/wiki/Kingman%27s_formula
9. 5 G/M/1 queue [Электронный ресурс] // Technische Universiteit Eindhoven. – [2014]. – Режим доступа : http://www.win.tue.nl/~iadan/blockq/h5.pdf

Рецензии:

12.12.2014, 0:33 Назарова Ольга Петровна
Рецензия: Исследование вызывает большой интерес. Грамотно изложен материал. Рекомендуется к печати.

Комментарии пользователей:

Оставить комментарий