Синхронный моделирующий алгоритм.

Рассмотрим особенности построения моделирующих алгоритмов гой же 0-схемы, структура

Продолжение рис. 8.8

которой приведена на рис.8.6, по "принципу Зг". Сначала построим синхронный моделирующий алгоритм, причем для определенности примем в качестве синхронизирующего элемента источник (И), т. е. *„= Гт. В момент т. е. на л-м шаге моделирования, на вход 1-й фазы Q-cxeмы поступает очередная заявка из И. С момента /„-1 до момента /„ в Q-cxeмe могли произойти изменения состояний Нх и К,, у, если в интервале (/*_!, /„) либо могло закончиться обслуживание в К|,* либо могли освободиться Кг, у. Эти изменения необходимо промоделировать раньше, чем поступление заявок в эту фазу в Это справедливо и для остальных фаз Q-cxe- мы: необходимо моделировать все изменения состояний к-й фазы до поступления в к-ю фазу заявок из (к— 1)-й фазы (в этом случае 0-я фаза эквивалентна И). Каналом К**. ^ имеющим

минимальное время окончания обслуживания, является тот, для которого

Укрупненная схема синхронного моделирующего алгоритма представлена на рис. 8.9. Работа большинства блоков этой схемы аналогична детально рассмотренной схеме детерминированного моделирующего алгоритма (см. рис. 8.7). Поэтому остановимся более подробно только на взаимодействии синхронизирующего элемента, т. е. источника (И) с остальной частью ()-схемы, т. е. рассмотрим работу блока 6, имитирующего запись заявки из вход-

Укрупненная схема синхронного моделирующего алгоритма 0-схемы

Рис. 8.9. Укрупненная схема синхронного моделирующего алгоритма 0-схемы

ного потока в накопитель или прием на обслуживание в один из каналов 1-й фазы (рис. 8.10).

На этой схеме вспомогательными являются операторы 6.1, 6.5 — 6.8. Проверяется наличие свободных каналов 1-й фазы (оператор 6.2). Если среди каналов 1-й фазы есть свободные, то выбирается один из них и имитируется обслуживание, т. е. определяется время окончания обслуживания в этом канале (оператор 6.3), затем фиксируется его новое состояние (оператор 6.4) и осуществляется переход к следующему шагу. Если же оба канала 1-й фазы заняты, то проверяется, есть ли свободные места в накопителе Н1 этой фазы (оператор 6.9). Если свободные места есть, то имитируется запись заявки в ^ (оператор 6.10), а в противном случае фиксируется потеря заявки (оператор 6.11).

Асинхронный моделирующий алгоритм.

Рассмотрим особенности построения асинхронного моделирующего алгоритма, который

Схема алгоритма блока 6

Рис. 8.10. Схема алгоритма блока 6

(рис. 8. 10) отличается от синхронного, отсутствием, ведущего (синхронизирующего) элемента, причем очередному шагу моделирования соответствует особое состояние, т. е. момент окончания обслуживания одной из заявок любым каналом или момент поступления заявки из источника. При использовании такого принципа построения моделирующего алгоритма целесообразно процесс изменения состояний элементов О-схемы рассматривать в направлении, противоположном направлению движения заявок в системе. Это можно сделать, циклически просматривая на каждом шаге моделирования все элементы Q-cxeмы и определяя, какие переходы заявок из одного элемента в другой могут иметь место в данный момент системного времени. Такой асинхронный циклический моделирующий алгоритм в плане просмотра состояний элементов 0-схемы тождествен детерминированному моделирующему алгоритму, который приведен на рис. 8.7. Отличие заключается лишь в том, что отсчет системного времени проводится следующим образом:

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

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

В асинхронных спорадических моделирующих алгоритмах в отличие от циклических для каждого момента системного времени /„ просматриваются только те элементы (}-схемы, которые изменяют свое состояние в этот момент времени. Для моделирования процесса распространения изменений состояний элементов ()-схемы в направлении, противоположном направлению движения заявок в системе, необходимо прослеживать цепочку разблокирований в случае освобождения каналов, т. е. рассматривать, вызовет ли освобождение К*. у разблокирование К*_1,у, освобождение ,гУ разблокирование К*_2,; и т. д. Рассмотрим случай, когда эта цепочка просматривается за один шаг моделирования.

Укрупненная схема асинхронного спорадического моделирующего алгоритма, реализующего "принцип 5г", показана на рис. 8.12. Рассмотрим подробно отсутствующий в предыдущих схемах блок 3 (рис. 8.13). Блок 3 служит для определения временного интервала до ближайшего момента изменения состояния каким-либо элементом (2-схемы (И, Н или К). Системное время

Укрупненная схема асинхронного циклического моделирующего алгоритма (2-схемы)

Рис. 8.11. Укрупненная схема асинхронного циклического моделирующего алгоритма (2-схемы)

Рис. 8.12. Укрупненная схема асинхронного спорадического моделирующего алгоритма-схемы

— это минимальное время освобождения канала К*. 1 или время до поступления новой заявки из И (операторы 3.13 и 3.14). Поиск минимального времени освобождения канала К* j реализуется с помощью операторов 3.1 —3.12. В момент осуществления ближайшего события продвижение состояний реализуется операторами 3.15 и 3.16. Таким образом, в результате работы блока 3 /*, = (), если ближайшим событием является поступление из И, и /*.у=0 и определены к и у, если ближайшим событием является освобождение к-го канала у'-й фазы Q-cxeмы.

Рассмотренные алгоритмы моделирования многофазовой многоканальной Q-cxeмыy конечно, но своей общности не охватывают всех тех разновидностей 0-схему которые применяют в практике анализа и синтеза систем. Однако эти конкретные примеры моделирования позволяют детально ознакомиться с основными принципами построения моделирующих алгоритмов таких систем, причем эти принципы инвариантны к виду и сложности моделируемой системы 5.

Возможности модификации моделирующих алгоритмов £>- схемы. В плане усложнения машинных моделей Л/м при исследовании вариантов системы 5 можно рассмотреть следующие модификации:

1. Наличие потоков заявок нескольких типов.

В этом случае необходимо иметь несколько источников (генераторов) заявок и фиксировать признак принадлежности заявки к тому или иному потоку тогда, когда накопители и каналы рассматриваемой 0,-схемы критичны

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

  • 2. Наличие приоритетов при постановке заявок в очередь в накопитель. В зависимости от класса приоритета заявок может быть рассмотрен случай, когда заявки одного класса имеют приоритет по записи в накопитель (при отсутствии свободных мест вытесняют из накопителя заявки с более низким классом приоритета, которые при этом считаются потерянными). Этот фактор может быть учтен в моделирующем алгоритме соответствующей О-схемы путем фиксации для каждого накопителя признаков заявок, которые в нем находятся (путем организации соответствующего массива признаков).
  • 3. Наличие приоритетов при выборе заявок на обслуживание каналов. По отношению к каналу могут быть рассмотрены заявки

Схема алгоритма блока 3

Рис. 8.13. Схема алгоритма блока 3

  • (рис. 8. 12) с абсолютным и относительным приоритетами. Заявки с абсолютным приоритетом при выборе из очереди в накопитель вытесняют из канала заявки с более низким классом приоритета, которые при этом снова поступают в накопитель (в начало или конец очереди) или считаются потерянными, а заявки с относительным приоритетом дожидаются окончания обслуживания каналом предыдущей заявки. Эти особенности учитываются в моделирующих алгоритмах приоритетных (2-схем, при определении времени освобождения канала и выборе претендентов на его занятие. Если наличие абсолютных приоритетов приводит к потере заявок, то необходимо организовать фиксацию потерянных заявок.
  • 4. Ограничение по времени пребывания заявок в системе. В этом случае возможно ограничение как по времени ожидания заявок в накопителях, так и по времени обслуживания заявок каналами, а также ограничение по сумме этих времен, т. е. по времени пребывания заявок в обслуживающем приборе. Причем эти ограничения могут рассматриваться как применительно к каждой фазе, так и к О-схеме в целом. При этом необходимо в качестве особых состояний Q-cxeмы рассматривать не только моменты поступления новых заявок и моменты окончания обслуживания заявок, но и моменты окончания допустимого времени пребывания (ожидания, обслуживания) заявок в £1-схеме.
  • 5. Выход элементов системы из строя и их дальнейшее восстановление. Такие события могут быть рассмотрены в О-схеме, как потоки событий с абсолютными приоритетами, приводящими к потере заявок, находящихся в обслуживании в канале или ожидающих начала обслуживания в накопителе в момент выхода соответствующего элемента из строя. В этом случае в моделирующем алгоритме Q-cxeмы должны быть предусмотрены датчики (генераторы) отказов и восстановлений, а также должны присутствовать операторы для фиксации и обработки необходимой статистики.

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

Дадим краткую сравнительную оценку сложности различных моделирующих алгоритмов (2-схем, в основу построения которых положены перечисленные принципы. Детерминированный и асинхронный циклический алгоритмы наиболее просты с точки зрения логики их построения, так как при этом используется перебор всех элементов (2-схемы на каждом шаге. Трудности возникают с машинной реализацией этих алгоритмов вследствие увеличения затрат машинного времени на моделирование, так как просматриваются все состояния элементов £1-схемы (по "принципу Л/" или по "принципу дг"). Затраты машинного времени на моделирование существенно увеличиваются при построении

Блок-диаграмма моделирующего алгоритма в символике языка

Рис. 8.14. Блок-диаграмма моделирующего алгоритма в символике языка

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

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

Асинхронный спорадический алгоритм позволяет просматривать при моделировании только те элементы 0-схемыу изменения состояний которых могли иметь место на данном интервале системного времени, что приводит к некоторому упрощению этих моделирующих алгоритмов по сравнению с синхронными алгоритмами и существенному уменьшению затрат машинного времени по сравнению с детерминированными и циклическими алгоритмами.

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

К настоящему времени накоплен значительный опыт моделирования О-схем (при их классическом рассмотрении или в различных приложениях). Рассмотренные моделирующие алгоритмы

Рис. 8.15.

Программа реализации моделирующего алгоритма на языке ОРББ

позволяют практически отразить всевозможные варианты многофазных и многоканальных 0,-схем^ а также провести исследование всего спектра их вероятностно-временных характеристик, различных выходных характеристик, интересующих исследователя или разработчика системы 5.

Рассмотрим особенности моделирования систем, формализуемых в виде Q-cxeмy с использованием языка имитационного моделирования В этом случае отпадает необходимость выбора

принципа построения моделирующего алгоритма, так как механизм системного времени и просмотра состояний уже заложен в систему имитации дискретных систем, т. е. в язык ОРББ [33, 47].

Пример 8.5. Использование языка £№5 рассмотрим при моделировании Q схемы, схема которой приведена на рис. 8.6. Блок-диаграмма моделирующего алгоритма в символике языка СР55 представлена на рве. 8.14. Условные обозначения отдельных блоков были приведены в табл. 52. Как уже отмечалось, блок-диаграмма языка <йР55 позволяет генерировать адекватные программы имитации. Пример программы на языке СР55 показан на рис. 8.15. Действия операторов блок-диаграммы (и программы для данного примера приведены в табл. 8.1. При этом приняты следующие обозначения: ЯАК/яНь КА^/С/яК*, у.

Таблица 8.1

№ карты

№ блока

Назначение оператора (карты)

1

Сообщает, что после ассемблирования необходимо начать счет по программе

2

Задает емкость накопителя 7

3

Задает емкость накопителя 2

4 — 8

Описывают функцию экспоненциального распределения с именем ЕХКЖ, номером РТ4 ] и значениями в интервале (0, 1)

9

1

Генерирует транзакты с интервалами, распределенными по экспоненциальному закону и средним значением 10 условных единиц

10

2

Проверяет, есть ли свободные места в накопителе 1

11

3

Занимает одно место в накопителе 7

12

4

Направляет транзакт в один из свободных каналов 1 и 2

13

5

Занимает канал 1, 1

14

6

Освобождает одно место в накопителе 7

15

7

Задерживает транзакт на случайный интервал времени в соответствии с экспоненциальным законом со средним значением 20

16

8

Блокирует продвижение транзактов при занятости накопителя 2

17

9

Освобождает канал 7,1

18

10

Направляет транзакты к блоку с меткой N^2

19 — 23

И — 15

Выполняют функции, аналогичные блокам 5 — 9 по отношению к каналу 7, 2

24

16

Занимает одно место в накопителе 2

25

17

Направляет транзакт в один из свободных каналов 2.7 и 2.2

26 — 30

18 — 22

Выполняет функции, аналогичные блокам 5 — 9 по отношению к каналу 2.1

Продолжение табл. 8.1.

№ карты

N?блока

Назначение оператора (карты)

31

23

Направляет транзакты к блоку с меткой KAN31

32—36

24 — 28

Выполняет функции, аналогичные блокам 59 по отношению к каналу 2,2

37

29

Занимает канал 3,1

38

30

Задерживает транзакт на случайный интервал времени в соответствии с экспоненциальным законом со средним значением 10 условных единиц

39

31

Освобождает канал 3,1

40

32

Направляет транзакты к блоку с меткой END

41

33

Подсчитывает число транзактов, получавших отказ в обслуживании

42

34

Уничтожает транзакт

43

Означает конец набора входных карт модели и устанавливает начальное значение счетчика числа завершений, равное 1000

44

Передает управление операционной системе

Из приведенных примеров моделирования системы 5*, формализуемой в виде Q-cxeмыi видно, что при использовании для реализации как универсального алгоритмического языка, так и языка имитационного моделирования возможности по оценке в процессе имитации вероятностно-временных характеристик исследуемых систем существенно расширяются по сравнению с применением аналитического подхода, когда получение оценок в явном виде ограничено результатами, полученными в теории массового обслуживания.

 
< Пред   СОДЕРЖАНИЕ     След >