Моделирование процессов функционирования систем на базе Q-схем

Формализация на базе Q -схем. Рассмотрим возможности использования Q -схем для формального описания процесса функционирования некоторой системы S. Характерная ситуация в работе таких систем – появление заявок (требований) на обслуживание и завершение обслуживания в случайные моменты времени, т.е. стохастический характер процесса их функционирования. В общем случае моменты поступления заявок в систему S из внешней среды E образуют входящий поток, а моменты окончания обслуживания образуют выходящий поток обслуженных заявок.

Формализуя какую-либо реальную систему с помощью Q -схемы, необходимо построить структуру такой системы. В качестве элементов структуры Q -схем будем рассматривать элементы трех типов: И – источники; Н – накопители; К – каналы обслуживания заявок.

Пример структуры системы S, представленной в виде Q -схемы, приведен на рис. 8.4. Кроме связей, отражающих движение заявок в Q -схеме (сплошные линии), существуют различные управляющие связи. Примером таких связей являются различные блокировки обслуживающих каналов (по входу и по выходу): «клапаны» изображены в виде треугольников, а управляющие связи – пунктирными линиями. Блокировка канала по входу означает, что этот канал отключается от входящего потока заявок, а блокировка канала по выходу указывает, что заявка, уже обслуженная блокированным каналом, остается в этом канале до момента снятия блокировки (открытия «клапана»). В этом случае, если перед накопителем нет «клапана», то при его переполнении будут иметь место потери заявок. Помимо выходящего потока обслуженных заявок можно говорить о потоке потерянных заявок.

Рис. 8.4. Структура системы, представленной в виде Q -схемы

Как отмечалось выше, Q -схему можно считать заданной, если определены: потоки событий (входящие потоки заявок и потоки обслуживаний для каждого Н и К); структура системы S (число фаз L^Ф, число каналов обслуживания L^К, число накопителей L^Н каждой из L^Ф фаз обслуживания заявок и связи И, Н и К); алгоритмы функционирования системы (дисциплины ожидания заявок в Н и выбора на обслуживание К, правила ухода заявок из Н и К).

Способы построения моделирующих алгоритмов Q -схем. Моделирующий алгоритм должен адекватно отражать процесс функционирования системы S и в то же время не создавать трудностей при машинной реализации модели M_м. При этом моделирующий алгоритм должен отвечать следующим основным требованиям:

· обладать универсальностью относительно структуры, алгоритмов функционирования и параметров системы S;

· обеспечивать одновременную (в один и тот же момент системного времени) и независимую работу необходимого числа элементов системы S;

· укладываться в приемлемые затраты ресурсов ЭВМ (машинного времени и памяти) для реализации машинного эксперимента;

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

· гарантировать выполнение рекуррентного правила – событие, происходящее в момент времени t_k, может моделироваться только после того, как промоделированы все события, произошедшие в момент времени t_{k- 1}< t_k.

При этом необходимо иметь в виду, что появление одной заявки входящего потока в некоторый момент времени t_i может вызвать изменение состояния не более чем одного из элементов Q -схемы, а окончание обслуживания заявки в момент t_i в некотором канале (К) может привести в этот момент времени к последовательному изменению состояний нескольких элементов (Н и К), т.е. будет иметь место процесс распространения смены состояний в направлении, противоположном движению заявок в системе S.

При построении моделирующего алгоритма Q -схемы по «принципу D t», т.е. алгоритма с детерминированным шагом, необходимо для построения адекватной модели M_м определить минимальный интервал времени между соседними событиями D t ′ = min{ u_i } (во входящих потоках и потоках обслуживаний) и принять, что шаг моделирования равен D t ′. В моделирующих алгоритмах, построенных по «принципу d z», т.е. в алгоритмах со случайным шагом, элементы Q -схемы просматриваются при моделировании только в моменты особых состояний (в моменты появления заявок из И или изменения состояний К). При этом длительность шага
D t = var зависит как от особенностей самой системы S, так и от воздействий внешней среды E. Моделирующие алгоритмы со случайным шагом могут быть реализованы синхронным и асинхронным способами. При синхронном способе один из элементов Q -схемы (И, Н или К) выбирается в качестве ведущего и по нему “синхронизируется” весь процесс моделирования. При асинхронном способе построения моделирующего алгоритма ведущий (синхронизирующий) элемент не используется, а очередному шагу моделирования (просмотру элементов Q -схемы) может соответствовать любое особое состояние всего множества элементов И, Н и К. При этом просмотр элементов Q -схемы организован так, что при каждом особом состоянии либо циклически просматриваются все элементы, либо спорадически – только те, которые могут в этом случае изменить своё состояние (просмотр с прогнозированием).

Классификация возможных способов построения моделирующих алгоритмов Q -схем приведена на рис. 8.5.

Рис. 8.5. Классификация способов построения моделирующих алгоритмов Q -схем

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

Пример 8.2. Для более детального ознакомления с технологией машинной имитации остановимся на рассмотрении Q -схем достаточно общего вида, показанных на рис.8.6. В частности, разберём на данном примере, какое влияние оказывает на особенности построения схемы моделирующего алгоритма принцип, положенный в основу его машинной реализации.

На рисунке представлена трёхфазная Q -схема (L^Ф =3) с блокировкой каналов по выходу в 1-й и 2-й фазах обслуживания (пунктирные линии на рисунке). В качестве выходящих потоков такой Q -схемы могут быть рассмотрены поток потерянных заявок из Н ₁ и поток обслуженных заявок из К _3,1 (N ₁ и N ₂ на рис. 8.6.).

N ₁ N ₂

1-я фаза 2-я фаза 3-я фаза

Рис.8.6. Пример Q -схемы общего вида

Для имитационной модели рассматриваемой Q -схемы можно записать следующие переменные и уравнения: эндогенная переменная P – вероятность потери заявок; экзогенные переменные: t_m – время появления очередной заявки из И; t_k,j – время окончания обслуживания каналом K_k,j очередной заявки, k =1, 2, 3; J =1, 2; вспомогательные переменные: z_i и z_k,j – состояния Н_i и K_k,j; i =1, 2; k = 1, 2, 3; j = 1, 2; параметры: L_i – ёмкость i -го Н_i; L^k_k – число каналов в k -й фазе; L^k ₁ =2, L^k ₂ =2, L^k ₃ =1; переменные состояния: N ₁ – число потерянных заявок в Н ₁, N ₂ – число обслуженных заявок, т.е. вышедших
из 3-й фазы; уравнение модели:

P = N ₁/(N ₁+ N ₂)= N ₁/ N.

При имитации процесса функционирования Q -схемы на ЭВМ требуется организовать массив состояний. В этом массиве должны быть выделены: подмассив K для запоминания текущих значений z_k,j соответствующих каналов K_k,j и времени окончания обслуживания очередной заявки t_k,j, j =, подмассив H для записи текущего значения z_i соответствующих накопителей H_i, i =1, 2; подмассив И, в который записывается время поступления очередной заявки t_m из источника (И).

Процедура моделирования процесса обслуживания каждым элементарным каналом K_k,j сводится к следующему. Путём обращения к генератору случайных чисел с законом распределения, соответствующим обслуживанию данных K_k,j, получается длительность времени обслуживания и вычисляется время окончания обслуживания t_k,j, а затем фиксируется состояние: если канал K_k,j свободен, z_k,j = 0; если канал K_k,j занят, z_k,j = 1, в случае блокировки K_k,j записывается z_k,j = 2. При поступлении заявки в H_i к его содержимому добавляется единица, т.е. z_i = z_i + 1, а при уходе заявки из H_i на обслуживание вычитается единица, т.е. z_i = z_i – 1, i = 1, 2.

Детерминированный моделирующий алгоритм. Укрупнённая схема детерминированного моделирующего алгоритма Q -схемы, т.е. алгоритма, построенного по «принципу D t», представлена на рис. 8.7.

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

Специфика наличия постоянного шага D t позволяет оформить «часы» системного времени в виде автономного блока 10. Этот блок служит для отсчётов системного времени, т.е. для вычисления t_n = t_{n -1}+D t. Для определения момента остановки при моделировании Q -схемы (по числу реализаций N или по длине интервала времени моделирования T) проводится проверка соответствующих условий (блок 3). Работа вспомогательных блоков – ввода исходных данных 1, установки начальных условий 2, обработки 11 и вывода результатов моделирования 12 – не отличается по своей сути от аналогичных.

Синхронный моделирующий алгоритм. Рассмотрим особенности построения моделирующих алгоритмов той же Q -схемы, структура которой приведена на рис. 8.6, по «принципу δ z». Сначала посмотрим синхронный моделирующий алгоритм, причем для определенности примем в качестве синхронизирующего элемента источник И, т.е. t_n = t_{m .}

Укрупненная схема синхронного моделирующего алгоритма представлена на рис. 8.8.

В момент t_n, т.е. на n -м шаге моделирования, на вход 1-й фазы Q -схемы поступает очередная заявка из И. С момента t_{n -1} до момента t_n в Q -схеме могли произойти изменения состояний Н ₁ и К _{1, j}, если в интервале (t_{n -1,} t_n) либо могло закончиться обслуживание в К _{1, j ,} либо могли освободиться К _{2, j .} Эти изменения необходимо промоделировать раньше, чем поступление заявок в эту фазу в t_n. Это справедливо и для остальных фаз Q -схемы: необходимо моделировать все изменения состояний k -й фазы до поступления в k -ю фазу заявок
из (k -1)-й фазы (в этом случае 0-я фаза эквивалентна И).

Каналом К^*_k,j, имеющим минимальное время окончания обслуживания, является тот, для которого

, где

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

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

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

,

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

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

В асинхронных спорадических моделирующих алгоритмах в отличие от циклических для каждого момента системного времени t_n просматриваются только те элементы Q -схемы, которые изменяют свое состояние в этот момент времени. Для моделирования процесса распространения изменений состояний элементов Q -схемы в направлении, противоположном направлению движения заявок в системе, необходимо прослеживать цепочку разблокирований в случае освобождения каналов, т.е. рассматривать, вызовет ли освобождение К_k,j разблокирование К_{k -1, j}, освобождение К_{k -1, j} разблокирование К_{k -2, j} и т.д.

Укрупненная схема асинхронного спорадического моделирующего алгоритма, реализующего «принцип d z», показана на рис. 8.10. Особенность моделирующего алгоритма проявляется в блоке 3, который служит для определения временного интервала до ближайшего момента изменения состояния каким-либо элементом Q -схемы (И, Н или К). Системное время

– это минимальное время освобождения канала К_{k , j} или время до поступления новой заявки из И. В результате работы блока 3 t_m = 0, если ближайшим событием является поступление заявки из И, и t_k,j = 0 и определены k и j, если ближайшим событием является освобождение k- го канала j- й фазы Q -схемы.

Более подробно эти моделирующие алгоритмы и их программные реализации на языке общего назначения рассмотрены в [1].

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

Дадим краткую сравнительную оценку сложности различных моделирующих алгоритмов Q -схем. Детерминированный и асинхронный циклический алгоритмы наиболее просты с точки зрения логики их построения, так как при этом используется перебор всех элементов Q -схемы на каждом шаге. Трудности возникают с машинной реализацией этих алгоритмов вследствие увеличения затрат машинного времени на моделирование, так как просматриваются все состояния элементов Q -схемы (по «принципу D t» или по «принципу d z»). Затраты машинного времени на моделирование существенно увеличиваются при построении детерминированных моделирующих алгоритмов Q -схем, элементы которых функционируют в различных масштабах времени, например, когда длительности обслуживания заявок каналами многоканальной Q -схемы значительно отличаются друг от друга.

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

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

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

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

Пример 8.3. Использование языка GPSS рассмотрим при моделировании Q- схемы, схема которой приведена на рис. 8.6. Блок-диаграмма моделирующего алгоритма в символике языка GPSS представлена на рис. 8.11. Блок-диаграмма языка GPSS позволяет генерировать адекватные программы имитации. Пример программы на языке GPSS представлен ниже. Действия операторов блок-диаграммы (и программы) GPSS для данного примера приведены в табл. 8.1. При этом приняты следующие обозначения: NAKI = H_i, KANKJ = K_k,j.

Программа имитации многофазной Q-схемы

SIMULATE

1 STORAGE 10

2 STORAGE 10

EXPON FUNCTION RN1,C24

0,0/.1,.104/.2,.222/.3,.355/.4,.509/.5,.69/.6,.915/.7,.12/.75,1.38/.8,1.6

.84,1.83/.88,2.12/.9,2.3/.92,2.52/.94,2.81/.95,2.99/.96,3.2/.97,3.5/.98,3.9

.99,4.6/.995,5.3/.998,6.2/.999,7.0/.9997,8.0

GENERATE 10,FN$EXPON

GATE SNF 1,OTK

ENTER 1

TRANSFER BOTH,KAN11,KAN12

KAN11 SEIZE 1

LEAVE 1

ADVANCE 20,FN$EXPON

GATE SNF 2

RELEASE 1

TRANSFER,NAK2

KAN12 SEIZE 2

LEAVE 1

ADVANCE 20,FN$EXPON

GATE SNF 2

RELEASE 2

NAK2 ENTER 2

TRANSFER BOTH,KAN21,KAN22

KAN21 SEIZE 3

LEAVE 2

ADVANCE 20,FN$EXPON

GATE NU 5

RELEASE 3

TRANSFER,KAN31

KAN22 SEIZE 4

LEAVE 2

ADVANCE 20,FN$EXPON

GATE NU 5

RELEASE 4

KAN31 SEIZE 5

ADVANCE 20,FN$EXPON

RELEASE 5

TRANSFER,END

OTK SAVEVALVE 1+,K1

END TERMINATE 1

START 5000

END

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

Таблица 8.1

№ карты	№ блока	Назначение оператора (карты)
	—	Сообщает, что после ассемблирования необходимо начать счет по программе
	—	Задает емкость накопителя 1
	—	Задает емкость накопителя 2
4—8	—	Описывают функцию экспоненциального распределения с именем EXPON, номером RN1 и значениями в интервале (0, 1)
		Генерирует транзакты с интервалами, распределенными по экспоненциальному закону со средним значением 10 условных единиц
		Проверяет, есть ли свободные места в накопителе 1
		Занимает одно место в накопителе 1
		Направляет транзакт в один из свободных каналов 1 и 2
		Занимает канал 1,1
		Освобождает одно место в накопителе 1
		Задерживает транзакт на случайный интервал времени в соответствии с экспоненциальным законом со средним значением 20
		Блокирует продвижение транзактов при занятости накопителя 2
		Освобождает канал 1,1
		Направляет транзакты к блоку с меткой NAK2
19—23	11—15	Выполняют функции, аналогичные блокам 5 — 9 по отношению к каналу 1,2
		Занимает одно место в накопителе 2
		Направляет транзакт в один из свободных каналов 2,1 и 2,2

Окончание табл. 8.1

26—30	18—22	Выполняет функции, аналогичные блокам 5 — 9 по отношению к каналу 2,1
		Направляет транзакты к блоку с меткой KAN31
32—36	24—28	Выполняет функции, аналогичные блокам 5—9 по отношению к каналу 2,2
	29	Занимает канал 3,1
		Задерживает транзакт на случайный интервал времени в соответствии с экспоненциальным законом со средним значением 20 условных единиц
		Освобождает канал 3,1
		Направляет транзакты к блоку с меткой END
		Подсчитывает число транзактов, получивших отказ в обслуживании
		Уничтожает транзакт
	—	Означает конец набора входных карт модели и устанавливает начальное значение счетчика числа завершений, равное 1000
	—	Передает управление операционной системе

Возможности модификации моделирующих алгоритмов Q- схемы
В плане усложнения машинных моделей М_M при исследовании вариантов системы S возможны следующие модификации:

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

2. Наличие приоритетов при постановке заявок в очередь в накопитель.

3. Наличие приоритетов при выборе заявок на обслуживание каналов.

4. Ограничение по времени пребывания заявок в системе.

5. Выход элементов системы из строя и их дальнейшее восстановление.

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

Дата добавления: 2014-01-04