3. Методы приближённой оценки характеристик вычислительных систем

Оценка при большой нагрузке. Аналитические зависимости, позволяющие определить параметры распределений выходных характеристик, имеются только для ограниченного круга систем. У более широкого круга систем могут быть вычислены средние значения в стационарном установившемся режиме. Однако оста­ется ряд систем и режимов, для которых отсутствуют точные фор­мулы даже по определению средних значений. К таким системам относятся, в первую очередь, системы с произвольными распреде­лениями периодов поступления и длительностей обслуживания заявок. Это системы G/G/1 и G/G/m. При отсутствии точных зависи­мостей приходится довольствоваться приближенными оценками.

Одним из методов приближений является оценка характери­стик при близких к единице значениях коэффициента загрузки, как наиболее важных с практических позиций. В частности, для системы G/G/1 время ожидания заявки в очереди распределено по экспоненциальному закону и среднее время ожидания можно опре­делить по следующей формуле:

(33)

где — дисперсия периодов поступления и длительностей обслуживания заявок соответственно.

Используя зависимость (10) и формулы Литтла, можно вы­числить средние значения других характеристик.

Определение границ. При значениях 0 ρ < 1 для оценки характеристик используется несколько различных подходов опре­деления верхней и нижней границ, в пределах которых находится истинное значение той или иной характеристики. Например, для системы G/G/1 приводятся следующие формулы расчета гра­ниц среднего времени ожидания заявки в очереди:

(24)

где v , — коэффициенты вариации периодов поступления и длительностей обслуживания заявок соответственно.

Средняя длина очереди , и среднее число заявок в си­стеме .

Дискретное и непрерывное приближения. Другие методы оценки ориентированы не на поиск приближенного решения исходной задачи, а на точное решение упрощенно сформулированной за­дачи. Уравнения, описывающие работу системы G/G/1, предна­меренно преобразуются к такому виду, при котором полученная система уравнений может быть решена.

В теории массового обслуживания показано, что если исходные величины являются дискретными, можно определить точное рас­пределение времени ожидания. На этом основывается метод дис­кретного приближения, при котором промежутки времени между моментами поступления заявок и длительности обслуживания аппроксимируются дискретными распределениями.

Для исследования нестационарных систем и режимов перегруз­ки оказывается полезным метод непрерывного приближения. Процессы поступления и ухода заявок — это ступенчатые вероят­ностные процессы (рис. 7). Но когда длины очередей значительно больше единицы, а времена ожидания существенно больше среднего времени обслуживания, становится разумной замена этих ступенчатых процессов сглаженными непрерывными функциями времени, поскольку величины отдельных ступенек малы по срав­нению со средними значениями (рис. 6).

Когда Х (f) становится значительно больше единицы, на ос­новании закона больших чисел можно ожидать лишь небольшого относительного отклонения этой величины от ее среднего значения

Рис. 6. Временная диаграмма процессов поступления и ухода заявок с непрерывной аппроксима­цией зависимостей количества зая­вок от времени М [х(t)]= На этом основывается приближение первого порядка, которое за­ключается в замене вероят­ностного процесса его сред­ним значением, зависящим от времени, т. е. детерминированным процессом . Это отно­сится и к процессу ухода заявок . Тогда число заявок в сис­теме тоже представляет собой детерминированную непрерывную функцию времени:

(35)

Функции и определяются из зависимостей:

(36)

(37)

—число поступивших и покинувших систему заявок к нулевому моменту времени.

Диффузионная аппроксимация. Непрерывное приближение яв­ляется довольно грубым, поскольку не учитывает случайный характер процессов поступления и ухода заявок. По методу диф­фузионной аппроксимации непрерывное приближение усовершен­ствуется путем учета флуктуаций относительно среднего значения. С этой целью случайный процесс (42) заменяется марковским процессом диффузионного типа х (/) с непрерывным временем и непрерывным множеством состояний. Диффузионный процесс определяется коэффициентом сноса

и коэффициентом диффузии

Эти коэффициенты выражаются через параметры исходной модели. Для системы G/G/1 считается, что при больших t рас­пределение Х (t) является приближенно нормальным с математи­ческим ожиданием и дисперсией и распределение Y (f) тоже приближенно нормальное с математическим ожиданием и дисперсией . Тогда коэффициент сноса

(38)

и коэффициент диффузии

(39)

В связи с тем, что процесс п (t) не может принимать отрица­тельных значений, для аппроксимирующего процесса х (t) зада­ется граничное условие, удерживающее его траекторию на неотри­цательной полуоси. Например, при достижении х (t) =0 совер­шается скачок в целочисленные точки положительной полуоси, выполняемый с заданным распределением вероятностей после экспоненциальной задержки в нуле.

Применение диффузионной аппроксимации дает возможность получения оценок различных характеристик СМО. В частности, для системы G/G/1 средняя длина очереди в стационарном режиме определяется по формуле

(40)

при постоянных коэффициентах сноса и диффузии, соответствую­щих случаю независимых от длины очереди вероятностных харак­теристик поступления и обслуживания заявок.

Контрольные вопросы

1. Одноканальная СМО для описания ВС.

2. Как определяется коэффицент загрузки ВС?

3. Как определяется число заявок в СМО?

4. Как определяется длина очереди в СМО?

5. Как определяется время реакции в СМО?

6. Формулы Литтла.

7. Многоканальная СМО для описания ВС.

8. Основные характеристки многоканальной СМО.

9. Для каких систем используются методы приближенной оценки характеристик?

Литература

Лекция 11. НЕСТАЦИОНАРНЫЕ РЕЖИМЫ ФУНКЦИОНИРОВАНИЯ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ (2 часа)

План