Материал: Имитационное и статистическое моделирование — копия

5) Запасы D1, ..., Dn по пропускным способностям

Запас Di определяется в виде Di = Вi – Λi (i = 1, ..., n). Запас Di показывает, насколько может быть увеличена интенсивность прихода заявок по i-му входу в сеть (при заданных остальных интенсивностях) без нарушения условия стационарности.

Если в виде СеМО моделируется некоторая реальная система, то перечисленные системные характеристики сети могут дать ценную информацию о свойствах этой реальной системы. Например, если СеМО изображает инфор- мационно-вычислительную сеть, то среднее время пребывания E характеризует среднее время ответа системы на запросы, а запасы Di выражают готовность моделируемой сети продолжать устойчивое функционирование при увеличении нагрузки (интенсивности запросов) по тому или иному входу.

Среднее время E пребывания заявок в СеМО рассчитывается по формуле Литтла

где N = N1 + … + Nn – среднее число заявок в СеМО, Λ = Λ1 + … + Λn – суммарная интенсивность поступления заявок в сеть по всем входам.

Расчёт системных характеристик СеМО выполняется после определения её локальных характеристик. Так, в формуле (3.18) используются локальные пока-

затели Ni.

Для рассмотренного в предыдущей работе примера СеМО (см. рис. 3.8) среднее время прохождения заявки через сеть составляет

Входовые средние времена F1, ..., Fn определяются с помощью уравнений, которые можно составлять, опираясь на конфигурацию СеМО и учитывая свойство суммы и свойство смеси случайных величин.

Свойство суммы с. в. состоит в том, что м. о. суммы случайных величин всегда равно сумме м. о. этих с. в.

Смесью с. в. x1, …, xk называется с. в. z, которая c вероятностью p1 принимает значение с. в. x1, c вероятностью p2 – значение с. в. x2, …(и т. д.)… и c вероятностью pk – значение с. в. xk. Здесь p1 + … + pk = 1, и случайный выбор из случайных величин xi статистически независим от их значений. Смесь z имеет м. о.

Теперь рассмотрим СеМО на рис. 3.8 и проследим, как формируется с. в. «входовое время пребывания в сети» для заявок первого потока.

Из рис. 3.8 видно, что это время состоит из двух слагаемых. Первое слагаемое есть время пребывания в СМО 1, составляющее в среднем U1. Второе слагаемое, формируемое в момент выхода заявки из СМО 1, есть смесь трёх с. в.: с вероятностью p10 оно равно нулю (когда заявка покидает сеть), с вероятностью p12 равно входовому времени F2 (когда заявка с выхода СМО 1 «входит в сеть» через СМО 2) и с вероятностью p13 – входовому времени F3. Отсюда с учётом свойства смеси вытекает, что в среднем второе слагаемое составляет величину p10 × 0 + p12F2 + p13 F3 = p12F2 + p13F3. В целом среднее входовое время

116

пребывания F1 (по свойству суммы) равно сумме средних значений первого и второго своих слагаемых:

Из этой системы с известными Uj (они вычислены при расчёте локальных характеристик СеМО) нетрудно найти решение: F1 = 5,507, F2 = 5,593,

F3 = 6,202 (с).

По аналогии с (3.22) можно составлять уравнения относительно Fi для любой экспоненциальной СеМО.

Примечание 1 . Если речь идёт о СеМО других типов, то при составлении уравнений для входовых времён необходимо убедиться, что выбор очередного слагаемого (т. е. выбор продолжения маршрута заявки) является случайным событием, независимым от выбираемых слагаемых. В нашей СеМО и в вариантах заданий к лабораторной работе это условие выполняется по определению. Но оно не выполняется, например, когда заявка выбирает переход к СМО с минимальной очередью.

Абсолютную пропускную способность по i-му входу Аi можно найти сле-

дующим образом.

В уравнениях баланса (см., например, (3.16)) нужно все имеющиеся там входные интенсивности Λk сохранить в буквенном виде, как переменные. Решая систему уравнений относительно входных интенсивностей СМО λj (j = 1, …, n),

k

Получаемые таким образом числовые коэффициенты αk j имеют смысл среднего числа прохождений через j-ю СМО той заявки, которая входит в сеть из k-го входного потока. Коэффициент αkj – это коэффициент передачи интенсивности (от k-й входной точки СеМО к входной точке j-й СМО). С учётом (3.23) условия стационарности ρj ≤ 1 (j = 1, …, n) можно записать следующим образом:

В системе линейных неравенств (3.24), которой должны удовлетворять переменные Λk, известны (и неотрицательны) все входящие в неё числовые коэффициенты. Эта система вместе с естественными ограничениями Λk ≥ 0 (k = 1, …, n) задаёт в евклидовом пространстве Rn выпуклый многогранник – область стационарности, точки которой (Λ1, …, Λi, …, Λn) соответствуют допустимой для СеМО стационарной нагрузке.

117

После получения системы (3.24) из неё легко определяется абсолютная пропускная способность сети Ai по любому выбранному i-му входу. Для этого достаточно в этой системе неравенств заменить все Λk, кроме Λi, нулями и найти максимально возможное значение Λi = Ai, при котором система неравенств не нарушается. Из (3.24) можно видеть, что при этом получается следующее решение:

Содержательный смысл выражения (3.25) достаточно прост. Числитель дроби – это интенсивность обслуживания заявок в j-й СМО, когда она работает без простоя. Разделив эту интенсивность на передаточный коэффициент αi j , мы определяем соответствующую интенсивность рассматриваемого входного потока СеМО. Поскольку ни одна СМО не должна получить нагрузку, которая была бы больше предельно допустимой, мы выбираем минимум.

Например, для СеМО, изображённой на рис. 3.8, в которой только первый входной поток имеет ненулевую интенсивность Λ1 = 1, мы ранее нашли, что λ1 = 10, λ2 = 5, λ3 = 4 (с–1). Поскольку все λj здесь просто пропорциональны Λ1, то можно сразу определить передаточные коэффициенты: α11 = 10, α12 = 5, α13 = 4. Поэтому данная сеть стационарна, пока Λ1 ≤ A1, где A1 = min{1/(10·0,07); 1/(5·0,06); 2/(4·0,35)} = min{10/7; 10/3; 10/7} = 10/7(с–1).

Относительная пропускная способность по i-му входу СеМО может быть найдена по такому же алгоритму, как и абсолютная, с тем лишь отличием, что в условиях стационарности (3.24) все интенсивности Λk для k ≠ i сохраняются равными численно заданным в исходной модели. Относительная пропускная способность Bk определяется как наибольшее значение интенсивности Λk, удовлетворяющее одновременно всем неравенствам системы (3.24) при фиксированных Λj для (j ≠ k).

Для рассматриваемой нами в качестве примера СеМО (см. рис. 3.8) относительная пропускная способность B1 совпадает с A1, поскольку все входные

потоки в СеМО, кроме первого, нулевые. Следовательно, для этой СеМО

B1 = 10/7 (с– 1 ).

Запасы по пропускным способностям вычисляются в соответствии с их оп-

ределениями. Для используемого примера СеМО (рис. 3.8) запас по её пропуск-

ной способности для первого входного потока составляет D1 = В1 – Λ1 = = 10/7 – 1 = 3/7 (с–1).

3. В данной лабораторной работе необходимо рассчитать аналитически и/или определить путём имитационного моделирования системные характеристики E, Fi, Ai, Bi и Di для вашего конкретного варианта СеМО (см. табл. 3.3).

Путём имитационного моделирования требуется также построить гистограммы распределения вероятностей: а) для времени t прохождения заявок через сеть; б) для числа ń заявок, застигаемых в сети вновь приходящей заявкой.

Для определения показателей E и Fi при имитационном моделировании в GPSS-программу рекомендуется ввести соответствующие пары блоков QUEUE

118

(при входе заявки в сеть) и DEPART (при выходе из сети). Одна из этих очередей будет иметь содержимое, равное числу всех заявок в сети, поэтому её можно одновременно использовать и для получения гистограммы распределения с. в. ń.

Построение гистограмм осуществляется с помощью соответствующих таблиц TABLE и блоков сбора статистики TABULATE. Например, в программу, листинг которой представлен на рис. 3.11, с целью сбора статистики о случайных величинах t и ń были добавлены следующие операторы, выделенные ниже жирным шрифтом:

Здесь в строке E_time описываются параметры таблицы (гистограммы) для сбора статистики о времени прохождения через сеть. Сбор статистики (регистрация времени M1) осуществляется блоком с меткой Exit_. Следующий за ним блок регистрирует выход транзакта из очереди general. Каждый транзакт входит в неё в момент появления из первого блока GENERATE, но перед входом табулирует число ń имеющихся в сети других транзактов (не считая себя).

На рис. 3.16 приведены гистограммы распределения с. в. t (слева) и ń (справа) для примера СеМО (см. рис. 3.8), полученные моделированием 50 тыс. единиц модельного времени.

Рис. 3.16. Гистограммы времени пребывания в сети и числа застигнутых заявок

На рис. 3.17 приведено сравнение расчётных результатов и результатов моделирования. Точное расчётное среднее время E пребывания заявки в сети,

119

найденное по формуле (3.18), составило 5,507с. Оценка этого показателя, выданная после прогона модели (длившегося 50 тыс. единиц модельного времени) как среднее время прохождения очереди general, получилась равной 5,494 с. Среднее время, выданное таблицей E_time, составило 5,493 с. Все эти значения получились достаточно близкими.

Рис. 3.17. Пример оформления таблицы с результатами моделирования СеМО

Расчётное среднее число заявок N = 5,507 близко к среднему содержимому 5,511 очереди general. Оба эти числа более заметно отличаются от среднего значения с. в. ń, выданного таблицей N_general. Эта разница объясняется тем, что здесь сравниваются разные показатели. Число заявок ń, застигаемое в сети каждой приходящей заявкой, – это случайный процесс, определённый на множестве дискретных моментов времени, и его свойства зависят от расположения этих моментов на оси времени. А среднее число заявок в сети N, определяемое очередью general, таблицей E_time или по формуле Литтла, – это среднее значение процесса n, рассматриваемого на непрерывном времени, который имеет иные свойства, нежели процесс ń. Сравните с примером аналогичного различия статистик в лабораторной работе 1 в примечании 1.

Варианты заданий

Необходимо рассчитать аналитически системные характеристики E, Fi, Ai, Bi и Di для вашего варианта СеМО (см. табл. 3.3). При этом входовые характеристики Ai, Bi и Di достаточно рассчитать только для одного входного потока, номер которого i – это наименьший из номеров СМО в вашем варианте.

Путём имитационного моделирования нужно проверить рассчитанные значения E и Fi, а также построить гистограммы распределения вероятностей: а) для времени t прохождения заявок через сеть; б) для числа ń заявок, застигаемых в сети вновь приходящей заявкой.

120