Реферат: Моделирование

МОДЕЛИРОВАНИЕ
МОДЕЛИРОВАНИЕ 1

Вопрос №1. Классификация систем массового обслуживания 1

Вопрос №2. Оценка качества последовательностей случайных величин 3

Вопрос №3,4. Имитационная модель одноканальной СМО. 7

Вопрос №5. Необходимое число реализаций процесса моделирования 16

Вопрос №6. Обработка результатов моделирования. 20

Вопрос №7. Марковские случайные процессы 22

8. Расчет вероятностей состояний однородной Марковской цепи. 24

9. Уравнения Колмогорова для вероятностных состояний. 25

10. Процесс «размножения и гибели». 26

11. Модель многоканальной СМО с отказами. 27

12. Модель одноканальной СМО с ограниченной очередью. 29

13. Модель одноканальной СМО с неограниченной очередью. 31

14. Модель многоканальной СМО с ограниченной очередью. 32

15. Модель многоканальной СМО с неограниченной очередью. 33
^ Вопрос №1. Классификация систем массового обслуживания
Первое деление (по наличию очередей):

1. СМО с отказами;

2. СМО с очередью.

В СМО с отказами заявка, поступившая в момент, когда все каналы заняты, получает отказ, покидает СМО и в дальнейшем не обслуживается.

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

СМО с очередями подразделяются на разные виды в зависимости от того, как организована очередь – ограничена или не ограничена. Ограничения могут касаться как длины очереди, так и времени ожидания, «дисциплины обслуживания».

Итак, например, рассматриваются следующие СМО:

· СМО с нетерпеливыми заявками (длина очереди и время обслуживания ограничено);

· СМО с обслуживанием с приоритетом, т.е. некоторые заявки обслуживаются вне очереди и т.д.

Кроме этого СМО делятся на открытые СМО и замкнутые СМО.

В открытой СМО характеристики потока заявок не зависят от того, в каком состоянии сама СМО (сколько каналов занято). В замкнутой СМО – зависят. Например, если один рабочий обслуживает группу станков, время от времени требующих наладки, то интенсивность потока «требований» со стороны станков зависит от того, сколько их уже исправно и ждет наладки.

^ Система массового обслуживания (СМО) представляет собой
математическую схему, предназначенную для формального
описания объектов, которые характеризуются наличием

обслуживающих приборов (обслуживающих каналов), наличием входного потока заявок на обслуживание, возможно очереди из заявок, ожидающих начала обслуживания и выходного потока обслуженных заявок или заявок, получивших отказ.

С такими системами можно столкнуться в совершенно различных сферах деятельности человека: транспорт, связь, управление, бизнес, вычислительные комплексы и пр. Все перечисленные системы можно описать, как СМО с определенными характеристиками, а построив имитационную модель этой СМО, получают показатели эффективности, по которым судят о качестве ее функционирования.

СМО разделяются на однофазные и многофазные, одноканальные и многоканальные, системы с отказами и системы с ожиданием, которые в свою очередь делятся на системы с неограниченным ожиданием заявки в очереди и системы с ограниченным ожиданием. В системах с ограниченным ожиданием на пребывание заявок в очереди накладываются те или иные ограничения. Эти ограничения могут касаться длины очереди (числа заявок, одновременно находящихся в очереди), времени пребывания заявки в очереди (после какого-то срока пребывания в очереди заявка

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

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

^ Входной поток заявок на обслуживание. Если по отношению к обслуживанию все заявки потока равноправны, то в данный момент времени важен лишь сам факт наступления события (поступления заявки). Такие потоки называются потоками однородных событий. Каждое событие потока характеризуется моментом времени tj, в который оно наступает. В случае вполне детерминированного потока однородных событий последовательность tj можно получить, перечислив их (например, сформировав одномерный массив в памяти компьютера), задав функцию tj = f(t) или, наконец, использовав рекуррентные соотношения, позволяющие получить текущее значение tj по предыдущему.

Для описания случайных потоков однородных событий
задается закон распределения, характеризующий последовательность случайных величин t1, t2 ..., tm. Обычно tj целесообразно заменять величинами £j, определяющими длину интервалов времени между моментами поступления заявок tj.#



Совокупность ξj задается совместным законом распределения. Случайный поток однородных событий называют потоком с ограниченным последействием, если ξj являются независимыми случайными величинами. В этом случае интервал ξj может быть задан своей функцией плотности fj(z).




Для стационарных потоков с ограниченным последействием справедливо следующее соотношение:





Многочисленные применения имеют стационарные ординарные потоки с ограниченным последействием (потоки Пальма). Поток однородных событий называется стационарным, если вероятность pk(to, t) появления к событий на интервале времени (to, to+t) не зависит от to, а зависит только от t и k (т.е. вероятностный режим потока не зависит от времени). Поток называется ординарным, если вероятность (p(to, t) появления двух и более заявок за промежуток времени (to, to+t) для любого t мала по сравнению с t,

означающее, что при j > 0 интервалы ξj распределены одинаково. Математическое ожидание mξ случайной величины ξj при j > 1 равно:



Величина mξ, по существу, есть средняя длина интервала между последовательными заявками.

Тогда для стационарных потоков с ограниченным последействием величина

λ=l/mξ,

определяющая среднее количество событий в единицу времени, называется плотностью или интенсивностью потока. Для

рассматриваемых потоков справедлива формула Пальма, связывающая fi(zj) и f(z):



Это соотношение позволяет получить функцию плотности f1(z1) по f(z).

Случайный поток однородных событий с ограниченным последействием называется потоком без последействия, если вероятность рk (to, t) поступления k событий за промежуток времени (to, to+t) не зависит от чередования событий до момента

to-

При моделировании СМО важную роль играет простейший (стационарный, ординарный, без последействия) поток, для которого вероятность pk (t) наступления k событий за интервал времени t выражается законом распределения Пуассона



Кроме рассмотренных потоков, практически интересны потоки Эрланга. В отдельных случаях рассматривают нестационарные входящие потоки.

^ Дисциплина ожидания. В общем случае СМО имеет n каналов (линий), параллельно обслуживающих входной поток заявок. Каждый канал может быть либо свободен, либо занят. Если в СМО имеются свободные каналы, заявка обслуживается, иначе она ожидает в очереди время т, после чего получает отказ и покидает систему.

В зависимости от значения τ различают следующие системы: с ожиданием (τ = ∞), с отказами (τ = 0) и смешанные (0 =< τ =< ∞). В ряде случаев длительность ожидания или вообще возможность встать в очередь зависят от ограничений на длину

очереди. Отсюда различают СМО без ограничений очереди и с ограничением по длине очереди.

По характеру «рассасывания» очереди различают СМО с упорядоченной и абсолютно неупорядоченной очередью. В первых - дисциплина очереди подчиняется правилу «раньше пришел - раньше поступил на обслуживание», в других - любая из заявок, стоящих в очереди, при освобождении канала с равной вероятностью может поступить на обслуживание.

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

Дисциплина обслуживания. По числу каналов СМО подразделяются на одно- и многоканальные. Последние, в свою очередь, делятся на системы с равноценными и неравноценными каналами.

Длительность обслуживания является случайной величиной с показательным законом распределения и реже - эрланговским.

По времени обслуживания различают СМО с неограниченной длительностью обслуживания и с ограничением по длительности обслуживания.

Кроме того, основанием классификации СМО является надежность каналов обслуживания. В этой связи различают системы с выходом из строя каналов. Наконец, последние подразделяются на СМО без восстановления вышедших из строя

каналов обслуживания и СМО с восстановлением каналов.
^ Вопрос №2. Оценка качества последовательностей случайных величин
Чтобы быть уверенным в результатах имитационного эксперимента, предварительно необходимо убедиться в случайности используемых последовательностей случайных величин. А качество случайных чисел, получаемых программным способом на компьютере, зависит от того, насколько удачно построен алгоритм, или подобраны коэффициенты и начальные значения параметров генераторов.

Статистическая теория предлагает целый ряд количественных критериев случайности. Однако, если последовательность удовлетворяет относительно тестов Т1? Т2, ..., Т„ , все же нет уверенности, что и тест Tn+i она выдержит столь же успешно. И все-таки чем больше тестов прошла последовательность, тем надежнее получаются результаты. Как правило, случайные числа проходят проверку с помощью следующих тестов: универсальных тестов (критерий χ2(«хи-квадрат»), критерий Колмогорова -Смирнова (КС-критерий)) и эмпирических тестов (проверка по моментам распределения, проверка равномерности, проверка серий, проверка интервалов, проверка комбинаций, проверка с помощью вычисления какой-нибудь общеизвестной константы).

^ Проверка по моментам распределения. Математическое ожидание и дисперсия равномерной случайной последовательности в интервале [0,1] равны 0,5 и 1/12 соответственно. Пусть имеется последовательность чисел ξ,i, ξ,2» ..., ξ n» полученная с использованием какого-нибудь программного генератора. Для этих чисел



Если генерируемые числа близки к равномерной случайной последовательности в интервале [0,1], то при достаточно больших

N

^ Проверка на равномерность. Интервал [0,1] разбивается на n равных подынтервалов и фиксируется, в какой из подынтервалов попадают числа ξi . Пусть m1 - количество случайных чисел, попавших в первый интервал; m2 - во второй и т.д. При этом

m1 + m2i + ... + mn = N.

Затем вычисляются частоты попадания случайных чисел в каждый из подынтервалов

pi=mi/N

Если случайная последовательностьчисел равномерная, то при больших N гистограмма (ломаная линия) должна приближаться к теоретической прямой у=1/n. Если число разбиений равно 10, то у = 0,1. На рис. 2.6 приведены результаты исследования последовательности случайных чисел (для N = 1000), полученных с использованием стандартной функции random языка Паскаль.










Рис.2,6 Результат исследования последовательности чисел на

равномерность

Проверка по критерию χ2- Применение этого метода основано на следующей процедуре:

1. Отрезок [0,1] разбивается на n подынтервалов (n принимают

равным от 10 до 20).

2. По совокупности N чисел подсчитывается количество mi,

попавших в i-й подынтервал (i = 1,2, ...,n).


3. Определяется эмпирическое значение

где p=l/n.


4. Для доверительной вероятности а и числа степеней
свободы 1 = n - 1 определяется теоретическое значение

критерия,


5. При выполнении условия χэ2< χт2 гипотеза о равномерности принимается, в противном случае - признается несостоятельной.

^ Проверка с помощью вычисления какой-нибудь общеизвестной константы. Для реализации этой проверки выбирается, например, вычисление числа п. Значение его известно и определено с большой точностью: π = 3,1416.... Нужно выбрать какую-нибудь формулу, в записи которой участвует число я. Например, площадь круга: S = πR2 и, если R = 1, то S = π. Т. е., вычислив методом имитационного моделирования площадь круга с радиусом, равным единице, и проверив на сколько эта площадь отличатся от величины 3,1416, можно судить о качестве генератора, выдающего последовательность случайных величин, равномерно распределенных в интервале [0,1].

Для вычисления S необходимо знать уравнение окружности, а оно известно: х2 + у2 = 1. Для этого нужно иметь аналитическое выражение подынтегральной . функции, которое для рассматриваемого примера записывается очень просто

y = ±√(1-x2). Так как все действия производятся в первом координатном углу, то и так как вычисляется площадь только четверти круга (рис. 2.3), то искомая величина четверти круга S’ ≈ m / N. А площадь всего круга S и, следовательно, число π ≈ 4 S’ = 4m / N. Здесь m - число точек, попавших при имитационном эксперименте под кривую

у =√1 – х2 или на саму кривую, а N - общее количество точек, брошенных в единичный квадрат.

Чем меньше отличается вычисленное значение π от точного (3,1416), тем с большей уверенностью можно считать, что статистические характеристики генератора случайных величин, который использовался при решении этой задачи, являются удовлетворительными. При этом необходимо учитывать, что точность вычисления зависит, конечно, от количества точек, брошенных в единичный квадрат, т.е. от количества реализаций процесса моделирования.
^ Вопрос №3,4. Имитационная модель одноканальной СМО.
Рис. 3.1. Системы массового обслуживания:

а, б – одноканальные;

в, г, д – двухканальные

В зависимости от характера источника заявок различают разомкнутые и замкнутые СМО. На рис. 3.1 представлены только разомкнутые СМО. В зависимости от числа мест в очереди различают СМО с отказами и без отказов. В СМО с отказами число мест в очереди конечно и вследствие вероятностного характера как входящего потока, так и процессов обслуживания существует ненулевая вероятность того, что поступившая на вход СМО заявка застанет все каналы занятыми обслуживанием и все места в очереди занятыми ожидающими обслуживания заявками, т. е. она получит отказ. В СМО без отказов заявка либо сразу назначается на обслуживание, если в момент ее поступления свободен хотя бы один канал, либо безусловно принимается в очередь.

Кратко рассмотрим методику составления сетевых моделей на примере одноканальной СМО (в совокупности с генератором заявок). Следует отметить, что процесс разработки сетевых моделей в общем случае является неформализованным. Проинтерпретируем СМО в терминах транзакций и ресурсов. Транзакции – это активные подвижные элементы системы, а ресурсы – неактивные. Транзакциями в СМО являются заявки, а ресурсом является канал обслуживания заявок. Функционирование СМО описывается как взаимодействие транзакций и ресурсов.


Рис. 3.1. Системы массового обслуживания:

а, б – одноканальные;

в, г, д – двухканальные

При переходе от системы транзакций и ресурсов к сетевой модели можно пользоваться следующими правилами. Каждый ресурс представляется позицией, причем маркировка этой позиции (простыми метками) определяет состояние ресурса. В одноканальной СМО имеется один ресурс, имеющий два состояния: "занят" и "свободен", причем начальное состояние ресурса – "свободен". Поставим этому ресурсу в соответствие позицию R сетевой модели. Маркировка М(R) = 1 будет свидетельствовать о незанятости ресурса, а М(R) = 0 – о его занятости. Маркировка M(R) >=2 является запрещенной. Переход ресурса из одного состояния в другое представляется изменением маркировки позиции R: добавление метки соответствует освобождению ресурса, а изъятие – его занятию.

В системе транзакций и ресурсов каждая транзакция представляется простой меткой или меткой с атрибутами в зависимости от того, несет она информацию или нет. Будем считать, что в нашей одноканальной СМО каждая транзакция несет информацию и, следовательно, будет представляться меткой с атрибутами.

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

0 – "готова для планирования";

1 – "планируется";

2 – "ожидание обслуживания";

3 – "заняла канал обслуживания";

4 – "обрабатывается";

5 – "обработана";

6 – "покинула канал обслуживания".

Состояния транзакции можно разделить на следующие классы:

– состояния временной активности (1, 4), связанные с процессами обработки транзакции, а также с планированием транзакции в генераторе транзакций. В этих состояниях транзакция находится во временной задержке перехода;

– состояния ожидания какого-либо ресурса (2). В этих состояниях транзакция находится в позициях, в которых нередко образуются очереди;

– состояния без ожидания (0, 3, 5, 6). В этих состояниях транзакция только "заявляет" о необходимости выполнения какого-либо события.

Каждому состоянию транзакции поставим в соответствие позицию или временную задержку перехода сетевой модели.

Переход транзакции из одного состояния в другое представляется как перемещение метки из одной позиции в другую, из позиции во временную задержку перехода, а также из временной задержки перехода в позицию.

В дальнейшем в моделируемой системе определяется множество событий, которые приводят к изменению состояния транзакций и ресурсов. В одноканальной СМО с генерацией заявок можно выделить следующие события:

1. "Приход новой заявки". При возникновении этого события транзакция переходит из состояния 1 в состояние 2. Создается копия транзакции, которая переводится в состояние 0.

2. "Планирование следующей заявки". Транзакция из состо-яния 0 переходит в состояние 1.

3. "Занятие канала обслуживания". Транзакция из состояния 2 переходит в состояние 3, а ресурс из состояния "свободен" переходит в состояние "занят".

4. "Начало обработки заявки". Транзакция из состояния 3 переводится в состояние 4.

5. "Конец обработки заявки". Транзакция из состояния 4 переводится в состояние 5.

6. "Освобождение канала обслуживания". Транзакция из состояния 5 переходит в состояние 6, а ресурс из состояния "занят" переходит в состояние "свободен".

7. "Уничтожение заявки". Транзакция покидает состояние 6 и уничтожается.

Каждому событию ставится в соответствие переход или пост-переход сетевой модели:

событие 1 – постпереход ТG;

событие 2 – переход TG;

событие 3 – переход SEIZE (мгновенный);

событие 4 – переход ADVANCE;

событие 5 – постпереход ADVANCE;

событие 6 – переход RELEASE (мгновенный);

событие 7 – переход TERMINATE (мгновенный).

На основе анализа причинно-следственных связей моделируемой системы производится соединение выделенных позиций и переходов с помощью дуг. При этом входные позиции какого-либо перехода будут определять необходимые условия возникновения соответствующего события, а выходные позиции – условия, которые возникают в результате совершения соответствующего события. Если событие приводит к модификации параметров транзакции, ее временной задержке или выбору последующего состояния в зависимости от определенных условий, то с переходом сетевой модели связывается процедура, производящая соответствующие действия. Следует отметить, что приведенный выше вариант "выделения" состояний и событий является не единственным. В результате отмеченных выше действий была получена сетевая модель,представленная на рис. 3.2,а. Следует заметить, что через переход TG имеется два потока меток: (PG, PG) и (PG, QUEUE). Графически это отображается следующим образом: позиция PG соединяется с одним из контактов перехода TG. Этот же контакт перехода соединяется с позициями PG и QUEUE.

Рис. 3.2. Сетевые модели разомкнутых одноканальных СМО:

а, б – СМО без отказов;

в, г – СМО с отказами

На рис. 3.2,б представлена сетевая модель одноканальной СМО, построенная на основе второго варианта "выделения" состояний и событий. Сеть на рис. 3.2,б эквивалентна предыдущей рассмотренной сетевой модели. Особенностью второго варианта является совмещение нескольких состояний и нескольких событий первого варианта. Целесообразно производить объединение тех событий, которые при обработке транзакции непосредственно следуют одно за другим, не разделены временным промежутком и когда условие возникновения второго события целиком зависит от первого.

Срабатывание перехода ADVANCE сетевой модели второго варианта интерпретируется как событие "занятие канала обслуживания и начало обработки заявки", что соответствует двум событиям (3 и 4) первого варианта. Срабатывание постперехода ADVANCE сетевой модели второго варианта интерпретируется как событие "Конец обработки заявки и освобождение канала обслуживания", что соответствует двум событиям (5 и 6) первого варианта.

Нахождение транзакции во временной задержке перехода ADVANCE сетевой модели второго варианта интерпретируется как состояние транзакции "Заняла канал обслуживания и обрабаты-вается", что соответствует двум состояниям (3 и 4) транзакции в первом варианте. Нахождение транзакции в позиции Р3 интер-претируется как состояние транзакции "Обработана и покинула канал обслуживания", что соответствует двум состояниям (5 и 6) транзакции в первом варианте.

^ MODEL CMO1 ( );

PLACE PG:MARK=1/1 DATA;

QUEUE,P1,P2,P3:DATA;

R:MARK=1 SIMPLE;

TRAN TG, SEIZE, ADVANCE, RELEASE, TERMINATE;

LINK PG=>TG..=>(PG;QUEUE=>SEIZE=>P1=>ADVANCE..=>

P2=>RELEASE=>P3=>TERMINATE);

RELEASE=>R=>SEIZE

^ VAR IX1,IX2:INTEGER;

PROC FOR INITIAL:

IX1:=9; IX2:=5;

END;

PROC FOR TG:

DELAY:=RANDOM(72.0,132.0,IX1);

PG.1.P[1]:=RANDOM(50.0,150.0,IX2);

END;

PROC FOR ADVANCE:

DELAY:=P1.1.P[1];

END;

END CMO1;

Pис. 3.3. Модель одноканальной СМО

Текстовое представление сетевой модели (рис. 3.2,а) на языке ЯОСМ приведено на рис. 3.3. Позиции PG, QUEUE, P1, P2, P3 относятся к типу позиций, маркируемых метками с атрибутами. Транслятор автоматически определяет тип позиции по марки-ровке, производя трассировку путей движения меток с атрибута-ми по элементам сетевой модели. Трассировка начинается из источников меток с атрибутами, в качестве которых выступают позиции, начально помеченные метками с атрибутами, а также выходные контакты "оболочки" сетевого макроопределения, отмеченные описателями TDATA и PDATA. В рассматриваемой сетевой модели имеется единственный источник меток с атрибутами – это позиция PG, начально маркированная одной меткой с одним атрибутом. В результате трассировки сетевой модели оказывается, что метки с атрибутами не заходят в позицию R, поэтому данная позиция помечается как "маркируется простыми метками". Начальная маркировка позиции R – одна простая метка.

Cледует отметить, что позиция, маркируемая метками с атрибутами, не должна маркироваться простыми метками, и наоборот. В процессе разработки сложной модели бывает трудно отследить данные требования. Для контроля соответствия действительного типа позиции по маркировке желаемому были введены два контрольных описателя – DATA и SIMPLE (см. подразд. 2.5). Позиции PG, QUEUE, P1, P2, P3 отмечены описателем DATA, а позиция R – описателем SIMPLE. Если бы в результате трассировки сетевой модели действительный тип позиций из первого множества был определен как "маркированные простыми метками" или действительный тип позиции R был определен как "маркированная метками с атрибутами", то транслятор выдал бы диагностическое сообщение о несоответствии желаемого и действительного типа.

Временная задержка в переходе TG определена как имеющая равномерный закон распределения с математическим ожиданием 102 (единиц модельного времени). Величина задержки в переходе ADVANCE определяется процедурой этого перехода путем присвоения переменной DELAY значения атрибута P[1] метки, находящейся первой в позиции P1. Значение же первого атрибута метки определяется при генерации метки процедурой перехода TG. При этом атрибуту P[1] присваивается значение случайной величины, распределенной по равномерному закону с математическим ожиданием 100. Следует отметить, что временная задержка в переходе определяется не только путем описания перехода в TRAN-предложении или путем присваивания переменной DELAY значения в соответствующей переходу процедуре, но также использованием признака временной задержки ".." совместно с именем временного перехода при описании связей в LINK-предложении. Процедура перехода вводится конструкцией PROC FOR <имя перехода>.

При описании связей используется алгебра представления графов (АПГ). Структура сетевой модели (граф) определяется с использованием операций наложения ";" и соединения "=>" графов. По определению языка ЯОСМ граф есть последовательность цепочек, соединенных операциями наложения. У каждой цепочки выделяются головные вершины (головы) и хвостовые вершины (хвосты). В простейшем случае цепочка содержит одну вершину, которая является и головой, и хвостом. При наложении нескольких цепочек получается граф, у которого множество головных вершин образуется путем объединения головных вершин соответствующих цепочек, а множество хвостовых вершин получается путем объединения хвостовых вершин соответствующих цепочек. Описание графа заключается в круглые скобки (за исключением графа верхнего уровня, описание которого следует за ключевым словом LINK).

Каждая цепочка определяется как последовательность звеньев, соединенных операцией соединения "=>". Звеном может являться вершина, граф или FOR-свертка графа, о которой речь пойдет ниже. Вершина представляет собой или позицию, или контакт перехода, или контакт нетерминала, или контакт оболочки. В любом случае у звена выделяется множество головных и хвостовых вершин. Если звеном является вершина, то она является и головой, и хвостом данного звена. Операция соединения двух звеньев заключается в том, что каждая хвостовая вершина первого звена соединяется с каждой головной вершиной второго звена, причем сгенерированным дугам назначаются атрибуты дуги, описание которых может иметься как возле первого, так и возле второго звена.

При описании связей переход представляется множеством своих контактов. При определении структуры сетевой модели на языке ЯОСМ контакт перехода Т описывается как Т.К или Т..К, где К-числовой идентификатор контакта (ЧИК) (номер контакта). Вторая конструкция описывает контакт временного перехода. При описании связей ЧИК может быть опущен. В этом случае сам транслятор производит его назначение (получается внутренний ЧИК). Внутренний ЧИК недоступен для пользователя. У перехода может быть несколько контактов с различными внутренними ЧИК. Всякий раз, когда в описании связей имя перехода встречается без ЧИК, транслятор определяет новый контакт перехода и присваивает ему новый внутренний ЧИК. В приводимом ниже примере под TG подразумевается контакт перехода с внутренним ЧИК.

Рассмотрим описание связей сетевой модели, представленной на рисунке 3.2,а. Обозначим структуру данной модели через G1. Граф G1 представляется одной цепочкой вида: PG => TG.. => Z, где звенья PG и TG.. являются вершинами – позицией и контактом перехода соответственно; звено Z представляет граф G2, Z = (G2). Граф G2 можно представить в виде наложения двух цепочек: G2 = PG; C, где цепочка PG является вершиной, а именно – позицией, а С представляет цепочку:

^ QUEUE => SEIZE => P1 => => ADVANCE.. => P2 => =>RELEASE => P3 => TERMINATE.

Граф G2 имеет две головные вершины: PG и QUEUE. Следовательно, при соединении контакта перехода TG.. с графом G2 (обозначается как TG..=>(G2)) появляются дуги и , которые, в чем можно убедиться, действительно присутствуют в сетевой модели. Соответствие цепочки С ее графическому представлению очевидно.

Описание атрибутов дуг заключается в угловые скобки. Синтаксис и семантика атрибутов, описывающих дугу, зависят от ее типа: входная или выходная, групповая или одиночная, ингибиторная или числовая.

Более полные сведения об атрибутах дуг можно получить из приложения 3 с описанием синтаксиса ЯОСМ (правила 62–68). Если описание атрибутов дуги не задано явно, то по умолчанию входной дуге перехода присваивается описатель <,1,1> (эквивалентен описателю <1,1>), а выходной – <,FIFO,1> (эквивалентен описателю ).

Первый пустой компонент первого описателя свидетельствует, что дуга числовая одиночная; второй компонент определяет разметку активизации дуги, равную 1 (т. е. число меток в позиции – источнике дуги, необходимое для разрешенности соответствующего перехода, должно быть не меньше единицы); третий компонент определяет, что при срабатывании перехода из соответствующей позиции будет удалена одна метка.

Первый пустой компонент второго описателя свидетельствует, что дуга одиночная; второй компонент указывает, что метки с атрибутами будут включаться в выходную позицию-очередь в соответствии с дисциплиной FIFO; третий компонент указывает, что в выходную позицию при срабатывании перехода будет добавлена одна метка.

При явном описании атрибутов дуги описатель может стоять справа от вершины-источника или слева от вершины-приемника. В приведенном ниже примере все фрагменты, описывающие одну и ту же дугу, эквивалентны:

^ ...QUEUE => SEIZE...

...QUEUE<,1,1> => SEIZE...

...QUEUE<1,1> => SEIZE...

...QUEUE => <,1,1>SEIZE...

...QUEUE => <1,1>SEIZE...

...QUEUE<,1,1> => <,1,1>SEIZE...

...QUEUE<1,1> => <1,1>SEIZE...

Если одной и той же дуге приписываются два описателя, то транслятор производит проверку их непротиворечивости. Если описатели противоречат друг другу, то выдается диагностическое сообщение.

При описании связей допускается многовариантность. Самым простым способом является описание структуры сетевой модели в виде списка бинарных связей. Однако рекомендуется описывать структуру в виде осмысленных фрагментов. Например, если обработка транзакции носит последовательный характер, то целесообразно представить технологический цикл ее обработки в виде цепочки элементов сетевой модели. В случае одноканальной СМО эта цепочка имеет вид:

^ QUEUE => SEIZE => P1 => ADVANCE.. => P2 => RELEASE => => P3=> TERMINATE.

В общем случае в структуре сетевой модели рекомендуется выделять графы продвижения транзакций каждого класса и отдельно их описывать. Ресурсные цепи рекомендуется также описывать отдельно. Пример описания ресурсной цепи в сетевой модели одноканальной СМО:

^ RELEASE => R => SEIZE.

Следует быть внимательным при указании путей передвижения меток с атрибутами по сетевой модели, особенно через переход. При задании потока меток через переход источник меток должен быть связан с приемником меток через один и тот же контакт перехода, иначе получается разрыв потока и из источника в приемник метки не попадают. Примеры правильного описания потоков транзакций через переход TG (в генераторе кадров):

^ PG => TG.. => (PG; QUEUE => ...)

PG => TG..1 => (PG; QUEUE => ...)

PG => TG..1; TG..1 => PG; TG..1 => QUEUE; ...

PG => TG..1 => PG; TG..1 => QUEUE => ...

Однако неправильным будет следующее описание:

^ PG => TG.. => PG; TG.. => QUEUE => ...

В данном случае позиции PG и QUEUE будут связаны с разными контактами перехода TG. Следует обратить внимание на то, что в позицию QUEUE в этом случае будут поступать простые метки. На рис. 3.2,в,г представлены сетевые модели одноканальной СМО с отказами (см. рис. 3.1,б). Предположим, что емкость оче-реди О1 равна 5. В первой предложенной сетевой модели отказы моделируются следующим образом. Позиция QUEUE объявляется ограниченной, ограниченность позиции полагается равной 5. Это означает, что в любом случае маркировка позиции QUEUE (обозначается как M(QUEUE)), не должна превосходить 5. В случае, если срабатывание какого-либо перехода (в данном случае это переход PUT) привело бы к нарушению данного условия, то этот переход блокируется и становится неразрешенным. Для уничтожения заявки используется переход REJECT. Данный переход является разрешенным всякий раз, когда в позиции Р0 находится метка. Если M(QUEUE) < 5, то при тех же условиях также будет разрешен переход PUT. Среди двух (и более) разрешенных переходов одного приоритета система может выбрать любой в соответствии с разыгранным случайным числом. Однако в данном случае согласно логике функционирования СМО должен сработать переход PUT. Чтобы выполнялось это требование, переходу REJECT присвоен приоритет на единицу меньший приоритета перехода PUT (равно как и приоритетов других переходов). Переход REJECT будет срабатывать, когда не разрешен переход PUT.

Иной вариант решения рассмотренной выше задачи описания механизма отказа предложен на рис. 3.2,г. В этом случае решение произведено с использованием проверочной дуги (QUEUE, REJECT). Данная дуга является разрешенной, если M(QUEUE)>= >= 5. Переходу REJECT присвоен приоритет выше, чем у остальных переходов. При переходе метки в позицию Р0, если M(QUEUE) < 5, переход REJECT не разрешен. В итоге срабатывает переход PUT. Если M(QUEUE) >= 5, разрешены переходы REJECT и PUT, но, поскольку приоритет перехода REJECT выше, срабатывает именно он. Следует обратить внимание на то, что при срабатывании перехода REJECT метки из позиции QUEUE не удаляются, так как атрибут дуги n2 = 0. Описание проверочной дуги может быть следующим: QUEUE<5, 0> => REJECT.

Инициализация представленных сетевых моделей сводится к начальной установке переменной IX, осуществляемой процедурой начальной установки. Процедура начальной установки вводится конструкцией PROC FOR INITIAL и выполняется перед началом имитации.


^ Вопрос 3,4.

Имитационная модель одноканальной СМО

Имитационная модель многоканальной СМО

Сущность подхода к имитации работы СМО проста— случайный процесс работы системы в интервале [О, T] рас­сматривается как детерминированный, но со случайно выбранными параметрами. Для обеспечения статистической устойчивости искомых результатов процесс моделирования повторяется заданное количество раз N1. Показатели эффективности формируются на основе статистической обработки результатов отдельных реализаций процесса моделирования.

Итак, рассматривается одноканальная СМО, в которую поступают заявки, образующие ординарный поток однородных событий с заданным законом распределения f(t) интервалов между моментами появления заявок. Заявки поступают в случайные моменты времени tj, они обслуживаются в течение времени τ*j, и обслуживание заканчивается в момент t*j. Случайная величина

длительности обслуживания t* определяется в соответствии с заданным законом распределения f(x*).

Судьба последующей заявки зависит (рис. 3, а) от момента ее появления tj относительно момента окончания обслуживания предыдущей t*j-1. Так, если бы рассматривалась СМО с отказами и очередная заявка поступила бы раньше наступления момента окончания обслуживания предыдущей, т. е. tj < t*j-i, то такая заявка получила бы отказ (рис. 3, б), если же tj>=t*j_i, то заявка была бы обслужена (см. рис. 3,а).

■

Рис. 3. Детали временной диаграммы

В связи с тем, что в рассматриваемой СМО должно учитываться ограничение времени возможного ожидания, необходимо формировать х} - случайную величину длительности ожидания j-й заявки начала обслуживания с соответствующим законом распределения f(t). Когда tj < t*j.b то j-я заявка получает

отказ (рис. 3, в), если t'jj-i , где t*j = tA+Xj - момент окончания ожидания j - й заявки начала обслуживания. Если же t'j >= t*j-1 (рис. 3, г), то обслуживание j - й заявки начинается в момент времени tHj = t*j-1. Исходные данные для моделирования: законы распределения f(t), f(x) и f(x*), величины Т и N1, а также состояние системы при t = 0, например, t*j-1=tj=0, m= n = N = 0. Принято, что заявки, для которых момент появления tj >= Т, в систему не попадают и не обслуживаются. Заявки, для которых время окончания обслуживания t*j > Т, считаются получившими отказ, а для которых t*j=