Файл: Инфокоммуникаций.pdf

28
Рис. 2.1 - Графы автоматов Мили (а) и Мура (б).
При решении задач моделирования часто более удобной формой является матричное задание конечного автомата. При этом матрица соединений автомата есть квадратная матрица С=|| c ij
||, строки которой соответствуют исходным состояниям, а столбцы - состояниям перехода. Элемент c ij
=x k
/y
S
в случае автомата Мили соответствует входному сигналу x k
, вызывающему переход из состояния z i
в состояние z j
и выходному сигналу y
S
, выдаваемому при этом переходе. Для автомата Мили F1, рассмотренного выше, матрица соединений имеет вид:
1 2
1 1
1 1
1 2
2 1
2 2
1
C
x y
x y
x y
x y
x y x y
















/
/
/
/
/
/
Если переход из состояния z i
в состояние z j
происходит под действием нескольких сигналов, элемент матрицы c ij представляет собой множество пар
«вход/выход» для этого перехода, соединённых знаком дизъюнкции. Для F- автомата Мура элемент c ij равен множеству входных сигналов на переходе
(z i
z j
), а выход описывается:

y
z
z
z
k


















(
)
( )
(
)
0 1
i-ая компонента которого выходной сигнал, отмечающий состояние z i.
2.7 Непрерывно-стохастические модели (Q - схемы)
К ним относятся системы массового обслуживания ( англ. queuing system), которые называют Q- схемами [8].

29
Предмет ТМО - системы массового обслуживания (СМО) и сети массового обслуживания. Под СМО понимают динамическую систему, предназначенную для эффективного обслуживания случайного потока заявок при ограниченных ресурсах системы. Обобщённая структура СМО приведена на рис. 2.3.
Поступающие на вход СМО однородные заявки в зависимости от порождающей причины делятся на типы, интенсивность потока заявок типа i
(i=1…M) обозначено i. Совокупность заявок всех типов - входящий поток
СМО.
Обслуживание заявок выполняется m каналами.
Различают универсальные и специализированные каналы обслуживания.
Для универсального канала типа j считается известными функции распределения
Fji() длительности обслуживания заявок произвольного типа.
Для специализированных каналов функции распределения длительности обслуживания каналов заявок некоторых типов являются неопределёнными, назначение этих заявок на данный канал. В качестве процесса обслуживания могут быть представлены различные по своей физической природе процессы функционирования экономических, производственных, технических и других систем, например, потоки поставок продукции некоторому предприятию, потоки деталей и комплектующих изделий на сборочном конвейере цеха, заявки на обработку информации ЭВМ от удалённых терминалов и т.д. При этом характерным для работы таких объектов является случайное поведение заявок (требований) на обслуживание и завершение обслуживания в случайные моменты времени.
Рис. 2.3 - Схема СМО

30
Q - схемы можно исследовать аналитически и имитационными моделями.
Последнее обеспечивает большую универсальность.
В любом элементарном акте обслуживания можно выделить две основные составляющие: ожидание обслуживания заявкой и собственно обслуживание заявки. Это можно отобразить в виде некоторого i-ого прибора обслуживания Пi, состоящего из накопителя заявок, в котором может находится одновременно li=0…LiH заявок, где LiH - ёмкость i-ого накопителя, и канала обслуживания заявок, ki.
Рис. 2.4 - Схема прибора СМО
На каждый элемент прибора обслуживания П
i поступают потоки событий: в накопитель Hi поток заявок wi , на канал k i
- поток обслуживания u i
Потоком событий (ПС) называется последовательность событий, происходящих одно за другим в какие-то случайные моменты времени.
Различают потоки однородных и неоднородных событий. Однородный ПС характеризуется только моментами поступления этих событий (вызывающими моментами) и задаётся последовательностью {tn}={0t1t2…tn…}, где tn - момент поступления n- ого события - неотрицательное вещественное число.
ОПС может быть также задан в виде последовательности промежутков времени между n-ым и n-1-ым событиями {n}.
Неоднородным ПС называется последовательность {tn, fn} , где tn- вызывающие моменты; fn- набор признаков события. Например, может быть задана принадлежность к тому или иному источнику заявок, наличие приоритета, возможность обслуживания тем или иным типом канала и т.п.
Рассмотрим ОПС, для которого i{n}- случайные величины, независимые между собой. Тогда ПС называется потоком с ограниченным последействием [9].
ПС называется ординарным, если вероятность того, что на малый интервал времени t, примыкающий к моменту времени t попадает больше одного события Р1(t, t) пренебрежительно мала.

31
Если для любого интервала t событие P0(t, t) + P1(t, t) + Р1(t, t)=1,
P1(t, t) - вероятность попадания на интервал t ровно одного события. Как сумма вероятностей событий, образующих полную группу и несовместных, то для ординарного потока событий P0(t, t) + P1(t, t)  1, Р1(t, t)=(t), где
(t)- величина, порядок малости который выше, чем t, т.е. lim((t))=0 при
t0.
Стационарным ПС называется поток, для которого вероятность появления того или иного числа событий на интервале времени  зависит от длины этого участка и не зависит от того, где на оси времени 0 - t взят этот участок. Для ОПС справедливо 0*P0(t, t) + 1*P1(t, t)= P1(t, t) - среднее число событий на интервале t. Среднее число событий, наступающих на участке t в единицу времени составляет P1(t, t)/t. Рассмотрим предел этого выражения при t0 lim P1(t, t)/t=(t)*(1/един.вр.).
Если этот предел существует, то он называется интенсивностью
(плотностью) ОПС. Для стандартного ПС (t)==const.
Применительно к элементарному каналу обслуживания ki можно считать что поток заявок w i
W, т.е. интервалы времени между моментами появления заявок на входе k i
образуют подмножество неуправляемых переменных, а поток обслуживания u i
U, т.е. интервалы времени между началом и окончанием обслуживания заявки образуют подмножество управляемых переменных [8].
Заявки, обслуженные каналом k i
и заявки, покинувшие прибор П
i по различным причинам не обслуженными, образуют выходной поток y i
Y.
Процесс функционирования прибора обслуживания
Пi можно представить как процесс изменения состояний его элементов во времени Zi(t).
Переход в новое состояние для Пi означает изменение кол-ва заявок, которые в нём находятся (в канале ki и накопителе Hi). Т.о. вектор состояний для Пi имеет вид :
i
i
H
i
K
Z
z z

 (
,
)
, где
i
H
z
- состояния накопителя, (
i
H
z
=0 - накопитель пуст,
i
H
z
=1- в накопителе одна заявка…,
i
H
z
=
i
H
L
- накопитель занят полностью;
i
K
z
- состояние канала k i
(
i
K
z
=0 - канал свободен,
i
K
z
=1 канал занят).
Q-схемы реальных объектов образуются композицией многих элементарных приборов обслуживания Пi. Если ki различных приборов обслуживания соединены параллельно, то имеет место многоканальное обслуживание (многоканальная Q-схема), а если приборы П
i
и их параллельные

32 композиции соединены последовательно, то имеет место многофазное обслуживание (многофазная Q-схема).
Для задания Q-схемы необходимо оператор сопряжения R, отражающий взаимосвязь элементов структуры.
Связи в Q-схеме изображают в виде стрелок (линий потока, отражающих направление движения заявок). Различают разомкнутые и замкнутые Q-схемы.
В разомкнутой выходной поток не может снова поступить на какой-либо элемент, т.е. обратная связь отсутствует.
Собственными (внутренними) параметрами Q-схемы будут являться количество фаз LФ, количество каналов в каждой фазе, L
kj
, j=1… LФ, количество накопителей каждой фазы L
kj
, k=1… LФ, ёмкость i-ого накопителя
L
i
H. Следует отметить, что в теории массового обслуживания в зависимости от
ёмкости накопителя применяют следующую терминологию [9]:
- системы с потерями (L
i
H=0, накопитель отсутствует);
- системы с ожиданием (L
i
H);
- системы с ограниченной ёмкостью накопителя Н
i
(смешанные).
Обозначим всю совокупность собственных параметров Q-схемы как подмножество Н.
Для задания Q-схемы также необходимо описать алгоритмы её функционирования, которые определяют правила поведения заявок в различных неоднозначных ситуациях.
В зависимости от места возникновения таких ситуаций различают алгоритмы (дисциплины) ожидания заявок в накопителе Нi и обслуживания заявок каналом k i
. Неоднородность потока заявок учитывается с помощью введения класса приоритетов.
В зависимости от динамики приоритетов Q-схемы различают статические и динамические. Статические приоритеты назначаются заранее и не зависят от состояний Q-схемы, т.е. они являются фиксированными в пределах решения конкретной задачи моделирования. Динамические приоритеты возникают при моделировании. Исходя из правил выбора заявок из накопитель Нi на обслуживание каналом k i
можно выделить относительные и абсолютные приоритеты.
Относительный приоритет означает, что заявка с более высоким приоритетом, поступившая в накопитель Н, ожидает окончания обслуживания представляющей заявки каналом k i
и только после этого занимает канал.
Абсолютный приоритет означает, что заявка с более высоким приоритетом, поступившая в накопитель, прерывает обслуживание каналом k i

33 заявки с более низким приоритетом и сами занимает канал (при этом вытесненная из k i
заявка может либо покинуть систему, либо может быть снова записана на какое-то место в Н
i
).
Необходимо также знать набор правил, по которым заявки покидают Н
i и k
i
: для Н
i
– либо правила переполнения, либо правила ухода, связанные с истечением времени ожидания заявки в Н
i
; для k i
– правила выбора маршрутов или направлений ухода. Кроме того, для заявок необходимо задать правила, по которым они остаются в канале k i
, т.е. правила блокировок канала.
При этом различают блокировки k i по выходу и по входу. Такие блокировки отражают наличие управляющих связей в Q-схеме, регулирующих поток заявок в зависимости от состояний Q-схемы. Набор возможных алгоритмов поведения заявок в Q-схеме можно представить в виде некоторого оператора алгоритмов поведения заявок А.
Вопросы для самопроверки по разделу 2:
1.

34 3 Имитационное моделирование систем
3.1 Измеряемые характеристики моделируемых систем
При имитационном моделировании можно измерять значения любых характеристик, интересующих исследователя. Обычно по результатам вычислений определяются характеристики всей системы, каждого потока и устройства [10].
Для всей системы производится подсчёт поступивших в систему заявок, полностью обслуженных и покинувших систему заявок без обслуживания по тем или иным причинам. Соотношения этих величин характеризует производительность системы при определённой рабочей нагрузке.
По каждому потоку заявок могут вычисляться времена реакций и ожидания, количества обслуженных и потерянных заявок. По каждому устройству определяется время загрузки при обслуживании одной заявки м число обслуженным устройством заявок, время простоя устройства в результате отказов и количество отказов, возникших в процессе моделирования, дины очередей и занимаемые ёмкости памяти.
При статистическом моделировании большая часть характеристик - это случайные величины. По каждой такой характеристике y определяется N значений, по которым строится гистограмма относительных частот, вычисляется математическое ожидание, дисперсия и моменты более высокого порядка, определяются средние по времени и максимальные значения.
Коэффициенты загрузки устройств вычисляются по формуле:

k
=Vk*Nok/Tm.
V
k
- среднее время обслуживания одной заявки к-ым устройством;
N
ok
- количество обслуженных заявок устройством за время моделирования Tm.
Определение условий удовлетворения стохастических ограничений при имитационном моделировании производится путём простого подсчёта количества измерений, вышедших и не вышедших за допустимые пределы.
Рассмотрим машинную модель M
m
, системы S как совокупность блоков
{m i
}, i=1,2…n. Каждый блок модели можно охарактеризовать конечным набором возможных состояний {Z0}, в которых он может находиться. Пусть в течение рассматриваемого интервала времени (0,Т) блок i изменяет состояние в моменты времени tijТ , где j - номер момента времени. Момент времени можно разделить на три группы:
- случайные, связанные с внутренними свойствами блока;

35
- случайные, связанные с изменением состоянием других блоков, имитирующая воздействие среды Е;
- детерминированные моменты, связанные с заданным расписанием функционирования блока.
Моментами смены состояний модели Мм в целом t(k) Т будем считать все моменты изменения блоков {mi}, рис. 8.1. см. ниже.
Рис. 3.1 - Смена состояний модели для случаев 3-х блоков
При этом моменты ti(j) и tk являются моментами системного времени, т.е. времени, в котором функционирует система S. При машинной реализации модели Мм её блки представляются соответствующими программными модулями.
При моделировании Q-схем следует адекватно учитывать как связи, отражающие движения заявок (сплошные линии) так и управляющие связи
(пунктирные линии).
Рассмотрим фрагмент Q-схемы (рис. 3.2.):
Рис. 3.2 - Фрагмент Q-схемы
Примерами управляющих связей являются различные блокировки обслуживающих каналов (по входу и по выходу): «клапаны» изображены в виде треугольников, а управляющие связи пунктирными линиями. Блокировка канала по входу означает, что этот канал отключается от входящего потока заявок, а блокировка канала по выходу указывает, что заявка обслуженная

36 блокированным каналом, остаётся в этом канале до момента снятия блокировки. В этом случае, если перед накопителем нет «клапана», то при его переполнении будут иметь место потери заявок.
Моделирующий алгоритм должен отвечать следующим требованиям [10]:
- обладать универсальностью относительно структуры, алгоритмов функционирования и параметров системы S;
- обеспечивать одновременную и независимую работу системы S;
- укладываться в приемлемые затраты ресурсов ЭВМ. (памяти, времени расчёта для реализации машинного эксперимента);
- проводить разбиение на достаточно автономные логические части
(блоки);
- гарантировать выполнение рекуррентного правила расчётов;
При этом необходимо иметь виду, что появление одной заявки входящего потока в некоторый момент времени ti может вызвать изменение состояния не более чем одного из элементов Q-схемы, а окончание обслуживания заявки в момент ti в некотором канале К может привести в этот момент времени к последовательному изменению состояний нескольких элементов (Н,К), т.е. будет иметь место процесс распространения смены состояний в направлении противоположном движению заявки в системе S. Поэтому просмотр элементов
Q-схемы должен быть противоположным движению заявок.
Все виды моделирующих алгоритмов Q-схемы можно классифицировать следующим образом (рис. 3.3):
Рис.3.3 - Виды моделирующих алгоритмов Q-схемы
Алгоритмы моделирующие Q-схему по принципу «t» являются детерминированными (по шагу), а по принципу особых состояний –