Моделирование: Конспект лекций для направления 654600 - ''Информатика и вычислительная техника''

Федеральное агентство по образованию ГОУ ВПО "Уральский государственный технический университет - УПИ" Кафедра "Автоматика и информационные технологии"

Ю.А.Барышников

МОДЕЛИРОВАНИЕ Конспект лекций для направления 654600 – «Информатика и вычислительная техника», специальность 2201 – «Вычислительные машины, комплексы, системы и сети»

2005

2

Используемые материалы Основные 1. Советов Б.Я., Яковлев С.А. “Моделирование систем”. Учебник для вузов. М., ВШ, 2-е издание. 1998, 3-е издание 2001. 2. Советов Б.Я., Яковлев С.А. “Моделирование систем. Практикум”. Учебное пособие. М., ВШ, 2003. Дополнительные 3. Денисов А.А. Колесников Д.Н. “Теория больших систем управления”. Учебное пособие. Л.: Энергоиздат, 1982. 4. Овчаров Л.А. “Прикладные задачи теории массового обслуживания”. М. Машиностроение, 1969. 5. Электронный справочник по GPSS/H кафедры АИТ. 6. Электронное пособие “Курсовое проектирование” кафедры АИТ. 7. Веников В.А., Веников Г.В. “Теория подобия и моделирования”. Учебник для вузов. 3е издание. М., ВШ., 1984. 8. Томашевский В., Жданова Е. “Имитационное моделирование в среде GPSS”. М., Бестселлер, 2003. 9. Боев В.Д. Моделирование систем. Инструментальные средства GPSS World: Учебное пособие. – СПБ.: БХВ – Петербург,2004. – 368с.

3

Содержание 1. Введение, основные понятия, классификация моделей и моделирования ..........................6 1.1. Понятие “модель” в дисциплине “Моделирование”.......................................................6 1.2. Понятие “моделирование”, цели моделирования............................................................6 1.3. Соотношение модели и системы.......................................................................................7 1.4. Классификация моделей и моделирования......................................................................7 1.5. Возможные последовательности разработки и использования МДСНВ....................10 2. Построение аналитических МДСНВ на основе марковских случайных процессов (МСП) изменения состояний с течением времени................................................................................11 2.1. Вероятности состояний и переходов, МСП...................................................................11 2.2. Допущение об однократности переходов z i → z j при ∆t → 0 , интенсивность

переходов, однородный МСП ................................................................................................13 2.3. Случайные факторы переходов, их интервалы действия, вероятности окончания и функции распределения этих интервалов, определение интенсивностей переходов ......15 3. Определение установившихся и стационарных вероятностей состояний с использованием усреднения по реализациям МСП.................................................................18 3.1. Установившиеся вероятности неконцевых состояний и определение установившихся вероятностей входа в концевые состояния ..............................................18 3.2. Стационарный концевой МСП, определение стационарных вероятностей состояний (СВС) ........................................................................................................................................21 4. Стационарный МСП “гибель и размножение”, типовая аналитическая модель “разомкнутая система массового обслуживания (СМО) без потерь заявок” ........................24 4.1. МСП “гибель и размножение”, стационарные вероятности состояний (СВС) ..........24 4.2. Типовая аналитическая модель “разомкнутая СМО без потерь заявок”, условие работоспособности, СВС ........................................................................................................25 4.3. Стационарные показатели работы разомкнутой СМО без потерь ..............................27 4.4. СВС и показатели работы 1-канальной СМО без потерь.............................................28 5. Типовая аналитическая модель “Разомкнутая СМО с потерями заявок” (с ограничением емкости накопителя) ...................................................................................................................30 5.1. Описание СМО с потерями, её СВС...............................................................................30 5.2. Стационарные показатели работы разомкнутой СМО с потерями .............................31 5.3. СВС и показатели работы разомкнутой 1-канальной СМО.........................................32 с потерями ................................................................................................................................32 6. Типовая аналитическая модель “замкнутая СМО” ..............................................................34 6.1. Описание типовой замкнутой СМО, её СВС.................................................................34 6.2. Стационарные показатели работы типовой замкнутой СМО. ....................................35 6.3. СВС и показатели работы типовой 1- канальной замкнутой СМО (m=1)..................37 7. Типовые линейные сети СМО, типовая аналитическая модель “разомкнутая сеть СМО” .......................................................................................................................................................38 7.1. Структура типовых линейных сетей СМО, сетевая теорема для СВС сетей .............38 7.2 Разомкнутая сеть СМО, производительности узлов, условие работоспособности ....41 7.3. СВС и показатели работы разомкнутой сети СМО ......................................................41 8. Типовая аналитическая модель “замкнутая сеть СМО”, СВС сети и ее узлов .................45 8.1. Описание замкнутой сети, ее СВС..................................................................................45 8.2. Константы усеченных сетей, их использование для вычисления сетевых констант и СВС узлов замкнутой сети СМО ...........................................................................................47

4 9. Вычисление констант замкнутых сетей ................................................................................49 9.1. Построение алгоритмов вычисления сетевых ...............................................................49 констант D M ( N) и D ← j ( N − n j ) .........................................................................................49 M −1

9.2. Константы одноканальной замкнутой сети ( m j = 1 ∀ j = 1, M ) .................................50 9.3. Константы многоканальной замкнутой сети ( max m j > 1, среди узлов S j хотя бы j=1, M

один-многоканальный) ...........................................................................................................51 10. Стационарные показатели работы типовой замкнутой сети СМО и ее узлов ................52 11. Компьютерные имитационные МДСНВ .............................................................................54 11.1. Понятие "компьютерное имитационное моделирование" (КИМ), его алгоритм....54 11.2. Концептуальная МДСНВ на основе графа состояний и операции алгоритма событийного моделирования по принципу "δz"...................................................................54 11.3. Обобщённая схема алгоритма событийного моделирования и цифровых экспериментов для программных МДСНВ на ЯОН ............................................................58 11.4. Имитация случайных величин и случайного выбора по заданному закону распределения вероятностей ..................................................................................................60 12. Концепция массового обслуживания (МО), функциональные элементы концепции (ФЭК) ............................................................................................................................................63 12.1 Концепция массового обслуживания ...........................................................................63 12.2. Основные ФЭК массового обслуживания (эти ФЭК являются в КМ моделями реальных функциональных элементов).................................................................................63 13. Основные допущения о работе КМ, имитационная GPSS - программа ..........................68 13.1. Основные допущения о работе КМ .............................................................................68 13.2. Сущность работы имитационной GPSS – программы................................................68 13.3. Формат операторов и структура GPSS - программы ..................................................69 14. Основные ФЭЯ для ФЭК, их программные модели ..........................................................70 14.1. Входы транзактов в программную модель и выходы из нее, управление длительностью прогона Тмод программы ..............................................................................70 Пример 5...................................................................................................................................71 14.2. ФЭК “Обслуживающее устройство”, ФЭЯ..................................................................71 "FACILITY" (прибор, устройство), "STORAGE" (память) .................................................71 14.3. ФЭК "Накопитель" перед запрещающими ФЭК, ФЭЯ: “QUEUE” (очередь), “STORAGE” (память), “TRANSFER BOTH”........................................................................73 ("оба" - направить при запрете по метке).............................................................................73 14.4. ФЭК “Направить заявки в точку соединения с другим потоком” (вперед или назад по КС); ФЭЯ “TRANSFER ,ME”...........................................................................................76 14.5. ФЭК "Разветвление путей заявок по условию", ФЭЯ "TRANSFER" (направить), "TEST" (проверить), "GATE" (впустить) ..............................................................................77 14.6. ФЭК "Клапан" (может быть вложен в ФЭК "Накопитель"), ФЭЯ TEST (проверить), "GATE" (впустить), "QUEUE" (очередь) ..............................................................................79 14.7. ФЭК “Табулировать”, ФЭЯ “TABULATE” (занести в таблицу) ...............................80 14.8. ФЭК “Копировать”, ФЭЯ “SPLIT” (расщепить) .........................................................81 14.9. ФЭЯ "Получение потока ТА одного семейства для программирования некоторых ФЭК" .........................................................................................................................................81 14.10. ФЭК "Присвоить значение параметру заявки", ФЭЯ "PRIORITY" (присвоить приоритет) и "ASSIGN" (присвоить) .....................................................................................83 14.11. ФЭК "Цикл" (разветвление по параметру заявки), ФЭЯ “ASSIGN” (присвоить) и “LOOP” (петля). .......................................................................................................................83

5 15. Операторы управления выводом результатов и прогонами GPSS - программы, алгоритм управления продвижением ТА по блокам................................................................84 15.1. Сохранение результатов в стандартном выводе..........................................................84 15.2. Использование блоков PRINT (напечатать) ................................................................84 15.3. Отмена стандартного вывода, вывод промежуточных отчётов картой управления START ......................................................................................................................................85 15.4. Повторение прогонов модели с изменениями операндов блоков и карт с помощью карты управления CLEAR ......................................................................................................85 15.5. Алгоритм управления моделированием (АУМ) - продвижением ТА по блокам GPSS – программы ..................................................................................................................85

6

1. Введение, основные понятия, классификация моделей и моделирования 1.1. Понятие “модель” в дисциплине “Моделирование” Научно – техническое содержание понятий часто не совпадает с общеизвестным содержанием, и “модель” в данной дисциплине не означает разновидность чего-либо. Будем использовать следующий подход к понятию “модель”. Объекты деятельности человека – это объекты реального мира, а также представления, знания о реальных объектах. Тогда объект – все то, на что направлена деятельность человека. Между объектами существуют или устанавливаются человеком различные отношения, взаимосвязи, в частности отношения подобия или соответствия, когда свойства одного объекта могут совпадать со свойствами другого объекта, и при рассмотрении этих свойств можно замещать один объект – оригинал другим объектом – моделью. Для специальности ВМКСС оригинал – это чаще всего информационная или производственная система как множество взаимосвязанных реальных элементов, объединенных общей целью функционирования. Функционирование (работа) информационно – управляющих систем – это процессы формирования, обработки и передачи данных. Цели функционирования таких систем и их разработки: полнота обработки данных, сокращение времени обработки, повышение производительности системы, снижение затрат на создание системы и её эксплуатацию. Сформулируем определение: модель – это объект, создаваемый для замещения другого объекта – системы, так чтобы вместо действий с системой можно было совершать действия с моделью. 1) 2) 3) 4) 5)

Действия с моделью, определяемые областью ее применения, – это в частности: исследование модели для изучения и анализа существующей системы, для получения показателей ее работы; разработка по модели возможных вариантов системы для их сравнения и оптимизации при проектировании новой системы; использование моделей как имитаторов реальных технических элементов при разработке АСУТП (автоматизированных систем управления технологическими процессами) и САУ (систем автоматического управления); использование моделей как тренажеров для обучения персонала; использование моделей для прогнозирования поведения системы (при постоянном совпадении результатов прогноза с реальными данными модель называют адекватной системе).

1.2. Понятие “моделирование”, цели моделирования Два содержания понятия “моделирование”: это процесс разработки и создания модели; исследование, испытание модели в различных режимах, мысленные, расчетные, компьютерные эксперименты с моделью для получения показателей работы модели в качестве оценок работы системы. В обоих случаях учитываются цели моделирования, которые различны в зависимости от применения создаваемой или используемой модели и в зависимости от требуемой степени подобия модели и системы. Главное, чтобы эти цели заранее были четко сформулированы:

1) 2)

7 1) должен быть проведен обоснованный выбор тех показателей работы модели, получение которых должна обеспечить разрабатываемая модель; 2) необходимо составить четкое описание условий проведения экспериментов с моделью для получения требуемых показателей.

1.3. Соотношение модели и системы 1) Что первично? Система, если она существует, а модель служит ее отображением, описанием. Модель, если разрабатывается новая система (но частично в модели почти всегда отображаются уже существующие компоненты новой системы). 2) Какова степень подобия, адекватности модели и системы? При изучении существующей, но незнакомой системы, стремятся создать наиболее адекватную модель в виде исчерпывающего описания системы, ее свойств. S

М

М – множество свойств модели, S – множество свойств системы, M ⊆ S При проектировании новой системы ограничиваются обычно ее главными свойствами, которыми должна обладать модель.

М

S

После создания и изучения S может оказаться, что подобие M и S частичное и требуется моделирование других важных свойств S. М2

М1

S

Тогда наряду с М1 создают М2 и т.п. Убедительная проверка адекватности модели и системы возможна только с использованием экспериментов с системой и моделью путем сравнения результатов.

1.4. Классификация моделей и моделирования 1. По признаку “форма существования модели”: 1.1. мысленные модели (чаще словесные, иногда образные); 1.2. физические модели (натурные, аналоговые, полунатурные); 1.3. содержательно – описательные (частично математические вместе с текстом, с рисунками, с видео материалами, графиками, таблицами и т.п. на различных носителях); 1.4. компьютерные (структурно – функциональные (статические), на основе диаграмм потоков данных и управления – как в 1.3., или имитационные динамические программные модели).

8 2. По концепции описания, то есть по используемой базовой теории, по основной точке зрения, по набору исходных допущений и ограничений, например: модели теории управления в концепции описания дифференциальными или разностными уравнениями, модели в концепции теории автоматов, модели в концепции теории массового обслуживания. 3. По степени подобия модели и системы (в порядке возрастания подобия): 3.1. структурные модели (состав элементов и связей); 3.2. структурно – функциональные модели (раскрываются алгоритмы работы каждого элемента и алгоритмы взаимодействия элементов через связи); 3.3. имитационные модели (по описанию алгоритма работы модели создается компьютерная программа, позволяющая имитировать множество реализаций процессов изменения состояний системы во времени; статистическая обработка этих реализаций или одной достаточно длинной дает показатели работы модели как оценки показателей системы; такие модели обеспечивают для требуемых показателей достаточное подобие; область применения практически не ограничена – зависит от полноты исходных данных); 3.4. аналитические модели для узких классов систем дают способы расчета всех требуемых показателей работы системы прямо по исходным данным без расчета процессов во времени; для этих узких классов упрощенных типовых систем получают самую высокую степень подобия модели и системы, но точная модель используется как приближенная для реальных более сложных систем; область применения ограничена. 4. По учету случайных факторов модели: 4.1. детерминированные модели; 4.2. вероятностные (стохастические) модели (иногда включают 4.1 как частный случай). 5. По признаку непрерывности или дискретности моделируемых состояний и моментов времени. Остановимся подробнее на этих признаках. Состояния различают непрерывные (НС) и дискретные (ДС). НС для каждого момента времени t 0 определяются набором минимального количества переменных числовых величин в модели (например переменная и ее (i )

производные) x (t 0 ), i = 0, n , задание которых полностью определяет состояния модели в (i )

последующие моменты времени (то есть величины x (t 0 + ∆t ) для ∆t > 0 ). Между любыми близкими НС существует бесконечное континуальное множество промежуточных НС. В целом множество НС континуально. ДС для каждого t 0 определяются наборами дискретных признаков. Признаки друг от друга отличаются или качественно (то есть дискретно, например, режим приема данных и режим их передачи) или дискретными фиксированными значениями одного качества (например, в системе передачи данных может быть занято разное целое число параллельных каналов). Каждому ДС соответствует свой набор дискретных признаков или дискретная величина. Множество ДС – конечное или бесконечное счетное. В модели могут учитываться или все возможные произвольные, в том числе случайные, моменты времени – континуальное множество (непрерывное время – НВ) или множество точечных моментов времени – счетное множество фиксированных значений t (дискретное время – ДВ). Отсюда пять типов моделей: 5.1. МНСНВ (модели теории управления на основе дифференциальных уравнений, модели непрерывных технологических процессов);

9 5.2. МНСДВ (модели теории управления на основе разностных уравнений для импульсных и цифровых систем управления с заданным постоянным шагом ∆t ); 5.3. МДСДВ (модели теории автоматов с фиксированным значением возможных моментов времени изменения состояний); 5.4. МДСНВ (модели с произвольными возможными моментами времени изменения дискретных состояний); 5.5. сложные комбинированные модели, состоящие из частей – моделей первых 4-х типов. В данном курсе лекций будут рассматриваться только МДСНВ (в общем случае вероятностные), так как эти модели в других дисциплинах специальности ВМКСС не рассматриваются. 6. По языку описания модели: 6.1. модели, разработанные с целью применения ЦВМ для расчетов и моделирования с использованием языков общего назначения (ЯОН, например, С++) или проблемно – ориентированных языков (ПОЯ, например, SIMSCRIPT); алгоритм программирования таких моделей – математическая модель системы. 6.2. модели, разработанные для компьютерного моделирования с использованием специализированного языка программирования (СЯ) например, специального языка имитационного моделирования (СЯИМ, в частности, GPSS); описание таких моделей проводится на основе понятий, порожденных СЯ, и алгоритм программирования моделей не является математической моделью в обычном виде, т.к. элементами алгоритма не являются типовые математические операции.

10

1.5. Возможные последовательности разработки и использования МДСНВ Система (реальная или проектируемая)

Содержательно – описательная модель, включая структурную модель и все исходные данные

Структурно – функциональная (в общем случае вероятностная) модель системы или Концептуальная модель на основе графа состояний или Аналитическая модель

Пакет прикладных программ на ЯОН

Концептуальная модель (КМ) массового обслуживания или

или если КМ с учетом СЯИМ

Имитационная модель, в виде математического алгоритма для ЯОН или ПОЯ

Компьютерная имитационная модель на ЯОН или ПОЯ

Компьютерная имитационная модель на СЯИМ

Оценки требуемых показателей работы системы

11

2. Построение аналитических МДСНВ на основе марковских случайных процессов (МСП) изменения состояний с течением времени 2.1. Вероятности состояний и переходов, МСП Рассматриваются модели со счётным множеством состояний Z = {z1 , z 2 , ... , z Q } , где

Q – конечно или Q → ∞ , z i – дискретные состояния модели, которым соответствуют вершины графа состояний (в соответствующей концепции). Возможные непосредственные мгновенные переходы z i → z j изображаются дугами графа состояний. Переходы из состояния в состояние определяют случайный процесс Z( t ) смены состояний во времени как множество возможных реализаций z( t ) ∈ Z( t ) , причем z( t ) = z i , i = i( t ) ∈ 1, Q, z(0) = z r , r ∈ 1, Q , где i – случайное значение, изменяющееся под действием внутренних и внешних случайных факторов, а начальное состояние z r можно считать одинаковым для всех реализаций. Рассмотрим вероятности состояний Pi ( t ) для состояния z i и вероятности переходов z i ( t ) → z j ( t + ∆t ) на интервале времени ∆t : безусловные Pij ( t , ∆t ) и условные Pi j ( t , ∆t ) . Если ∆t имеет произвольную величину, то в общем случае такие переходы не являются непосредственными, но в частности при уменьшении ∆t могут наблюдаться и непосредственные переходы z i → z j .

zk zj

zi

t

t+∆t

zk zj

бесконечное множество всех N реализаций (N →∞, k ≠ i, k ≠ j )

zi

(∆t )1

непосредственный переход за (∆t )1

zk zj

учитывается в Ni количество реализаций, начинающихся в ∆ t с zi

zi

не учитывается в Ni и Nij.

zk zj zi

∆t t+∆t “окно” наблюдения случайного процесса

t

Рис.2.1.1

учитывается в Nij - количество переходов за ∆t по бесконечному множеству реализаций

12 Вероятность состояния N (t ) N i Pi (t ) = lim i = – как предел по вероятности (не функции!), N i – число N →∞ N N N →∞ наблюдений z i в момент t. Безусловная вероятность перехода N ij , где N ij ( t , ∆t ) – число реализаций с переходами zi → z j за ∆t , N – Pij (t , ∆t ) = N N →∞

число всех реализаций. Условная вероятность перехода N ij Pi| j (t , ∆t ) = , где N i характеризует условие: N i – число тех реализаций в окне ∆t , N i N →∞ i

которые начинаются с z i ( t ) . Допущение 1: при построении рассматриваемого класса аналитических МДСНВ считают, что эти пределы существуют, то есть: ∃Pi ( t ), Pij ( t , ∆t ), Pi| j ( t , ∆t ) . Допущение 2: всё, что происходит на интервале [ t , t + ∆t ] , не зависит от предыстории на интервале (−∞, t ) . Это так называемый главный признак МСП. Состояния z i ( t ) и z j ( t + ∆t ) наблюдаются на бесконечном множестве реализаций, а не задаются на них. Эти допущения определяют рассматриваемый далее класс МДСНВ с марковскими случайными процессами Z( t ) . Независимость от предыстории называется так же отсутствием последействия (этой предыстории на интервале [ t , t + ∆t ] ). Указанные выше определения трёх вероятностей дают их взаимосвязь: Pij ( t , ∆t ) = Pi| j ( t , ∆t )Pi ( t ) безусловная условная вероятность вероятность перехода как события (произведения событий)

Это соответствует определению условной вероятности в теории вероятностей

вероятность события – условия.

13

2.2. Допущение об однократности переходов z i → z j при ∆t → 0 , интенсивность переходов, однородный МСП

zk zj zi

t

t+∆t

∆t → 0

zk

бесконечное множество всех N реализаций (N →∞)

zj

zi

при ∆t → 0 может остаться только один переход z i → z j или ни одного

zk zj zi

t

t+∆t

∆t → 0

Рис.2.2.1

Рассмотрим: Pi| j (t , ∆t )

∆t →0

=

N ij Ni

N i →∞ ∆t →0

Очевидно, Pi| j ( t , ∆t ) → 0 при ∆t → 0 . Допущение 3. Если на одной любой реализации z( t ) на интервале ∆t → 0 возможно появление случайно m непосредственных переходов z i → z j , то условная вероятность Pi| j (m)

m =1

>> Pi| j (m)

m >1

, то есть можно принять для множества реализаций в окне

∆t → 0 : N ij

∆t →0

= nij

∆t →0

, Pi j (t , ∆t )

∆t →0

=

nij (t , ∆t ) N i (t )

N i →∞ ∆t →0

,

где n ij – количество однократных непосредственных переходов z i → z j , причем nij

∆t →0

→ 0 (рис.2.2.1).

Тогда Pi j (t , ∆t ) =

nij (t , ∆t ) N i ⋅ ∆t

⋅ ∆t

N i →∞ ∆t →0

,

(2.2.1)

14 где N i ∆t

N i →∞ ∆t →0

= nii ∆t

nii →∞ ∆t →0

+ nir ∆t

r ≠ i , n ir → 0 ∆t →0

= nii ∆t

∆t →0 nii → ∞

= Ti * (t ) – это суммарное время

наблюдения исходного z i в окне ∆t → 0 , так как nii − количество реализаций в ∆t без переходов, то есть с сохранением исходного z i . Следствие

1:

существует

предел

λij (t ) =

nij (t , ∆t ) Ti* (t )

N i →∞ ∆t →0

,

который

называется

"интенсивность переходов" - это среднее количество непосредственных переходов z i → z j , приходящееся на единицу суммарного времени Ti* ( t ) наблюдения z i в окне ∆t → 0 при z (t ) = z i . Существование λij (t ) как предела следует из допущения 1 о

существовании условной вероятности переходов Pi j (t , ∆t ) и выражения (2.2.1). Следствие 2: Pi j (t , ∆t ) = λij (t ) ⋅ ∆t

(2.2.2)

Это главное свойство рассматриваемого класса моделей с использованием МСП и интенсивностей переходов. Следствие 2 позволяет составить систему уравнений динамики вероятностей состояний – уравнения Колмогорова. Их вывод и применение не будем рассматривать, но их вид используем, переходя к более узкому классу моделей. Уравнения Колмогорова составляются по графу состояний модели, размеченному по дугам интенсивностями переходов λij . Уравнения имеют вид: Q  dPj (t ) Q = − ( t ) P ( t ) λ λ ji (t ) Pj (t ), λii = 0, j = 1, Q, где ∑ ∑  ij i dt i = 1 j = 1  Q − количество дискретных сотояний модели  (одно уравнение исключается, чтобы уравнения стали линейно независимыми ) ;  Q ∑ Pj (t ) = 1  j =1 В инженерной практике применяется в основном класс моделей, у которых существуют установившиеся вероятности, используемые для определения показателей работы: lim P j ( t ) = P j (∞) = Pj = const , j = 1, Q . В частности, это модели с

t →∞

λ ij ( t ) = λ ij = const (интенсивности переходов не зависят от времени). МСП этих моделей называются однородными и для них при использовании окна наблюдения ∆t → 0

λij =

nij (∆t ) Ti *

Ni →∞ ∆t → 0

,

Pi j (∆t ) = λij ⋅ ∆t

(2.2.3)

Установившиеся вероятности P j (∞) = P j обычно находят как предельные значения по уравнениям Колмогорова, но если нужны только Pj , то их можно определять без использования этих уравнений по известным λ ij . Далее в этом и в следующем разделе показано, как по описательно-содержательной модели системы найти λ ij и составить

15 уравнения для определения P j , значения которых позволяют рассчитать требуемые показатели работы модели.

2.3. Случайные факторы переходов, их интервалы действия, вероятности окончания и функции распределения этих интервалов, определение интенсивностей переходов Рассмотрим модель одноканального передатчика сообщений с буфером на одно сообщение. В точечные моменты времени t, разделенные случайными интервалами τ вх , сообщения поступают (входят) в модель, и если при этом передатчик свободен, сообщение занимает его (не задерживаясь в буфере) в течение случайного интервала времени передачи τ п . При занятом передатчике сообщение ожидает его освобождения в буфере. Если буфер занят при поступлении нового сообщения, оно теряется. Описательно-содержательная и структурно-функциональная модели этой системы демонстрируются рисунком 2.3.1, где показаны пути прохождения сообщений. Точечные моменты времени входа сообщений в модель

t τвх

поток сообщений через случайные интервалы τвх

1 – канальный передатчик, τ п – случайная длительность передачи

буфер для одного сообщения если буфер занят

поток переданных сообщений поток потерь

Рис.2.3.1 Концептуальная модель определяется графом состояний, показанным на рис.2.3.2, где состояние z1 означает отсутствие сообщения в модели, z 2 – наличие только одного сообщения в модели, z 3 – наличие двух сообщений (буфер занят и в этом состоянии или происходит потеря сообщений, когда интервал τ П не закончился и поступило новое сообщение, или z 3 заканчивается переходом в z 2 при окончании τ п раньше, чем τ вх ). z1

z2

z3

τвх

τвх , τп

τвх , τп

Рис.2.3.2 Окончание τ п означает переходы z 3 → z 2 или z 2 → z1 и можно назвать τ п фактором этих переходов. Аналогично, τ вх – это фактор переходов z1 → z 2 или z 2 → z 3 , или потери сообщений. На рис.2.3.2 показаны факторы, действующие в каждом

16 состоянии. На графе состояний в z 3 действие τ ВХ проявляется не в изменении состояния, а в потере сообщений. Отметим, что один фактор может действовать в одном или более состояниях. Фактор может начаться в одном состоянии и продолжаться или заканчиваться в другом. Если в z i действует фактор τ ф и окончание его действия вызывает переход z i → z j , то вероятности этих событий одинаковы. Окончание действия фактора – причина перехода, поэтому вероятность окончания фактора за ∆t во всех состояниях z i , в которых фактор действует: Pф (∆t ) = Pij (∆t ) = λ ij ∆t , то есть интенсивность переходов λ ij – это интенсивность окончаний фактора (фактор может действовать в различных z i и вызывать различные переходы z i → z j , но все λ ij одинаковы для одного фактора). Функция распределения вероятностей Fф (Θ) = P(τ ф ≤ Θ) = 1 − P(τ ф > Θ) , где τ ф ≤ Θ – это условие окончания фактора раньше момента Θ – условие наличия переходов в течение времени Θ:

τΦ

Θ t

0

τΦ

Θ

t N∆t

0

Рис.2.3.3 Соотношение τ ф > Θ – условие окончания фактора позже Θ – это условие отсутствия переходов в течение времени Θ, которое можно разделить на интервалы ∆t → 0 . Θ Пусть конечное Θ = N∆t ; ∆t = , причем события отсутствия переходов на N →∞ N ∆t →0

каждом ∆t являются независимыми с вероятностью 1 − Pф (∆t ) . Поэтому: P( τ ф > Θ) = (1 - Pф (∆t))

N N →∞ ∆t → 0

= (1 - λ ij ∆t)

N N →∞ ∆t →0

 λ ijΘ   = 1 N  

N

=e

−λijΘ

.

N →∞

Тогда рассматриваемые МСП определяются случайными факторами переходов τ ф с функцией распределения только вида Fф (Θ) = P(τ ф ≤ Θ) = 1 − e ∞

ожидание для этих факторов τ ф =

1

∫ ΘFф′ (Θ)dΘ = λ ij ,

− λijΘ

. Математическое

что дает способ определения

−∞

интенсивности переходов λij =

Отметим,

что

1

τф

, если Fф (Θ) = 1 − e − Θ τ ф , где τ Ф задано.

плотность

распределения

Fф′ (Θ) = λ ije

− λijΘ

определяет

экспоненциальное распределение интервалов действия фактора τ ф , и главным следствием

17 действия факторов переходов с таким распределения является свойство условной вероятности переходов z i → z j : Pi| j ( t , ∆t )

∆t →0

= λ ij ∆t .

(2.3.1)

Граф состояний аналитических моделей с экспоненциальными распределениями τ ф размечается по дугам значениями λ ij . Такой граф является математической моделью системы в рассматриваемом классе моделей. Для таких моделей удается получить детальные результаты аналитического моделирования, чего нельзя сказать о других видах функций распределения. Использование экспоненциального распределения дает оценки в “худшем варианте”, (то есть при других распределениях τ ф оценки в большинстве случаев хуже не будут), что используется в инженерной практике.

18

3. Определение установившихся и стационарных вероятностей состояний с использованием усреднения по реализациям МСП 3.1. Установившиеся вероятности неконцевых состояний и определение установившихся вероятностей входа в концевые состояния В графе состояний G неконцевые – это состояния z j , из которых с течением времени t модель выходит и не возвращается в эти z j при t → ∞ . “Ненаблюдаемость” при этом означает, что для неконцевых z j установившиеся вероятности P j ( t ) z1 (0) = z1

λ 21

λ13

λ12

λ14

= P j (∞ ) = 0 .

z3 λ 53 λ36 z5 λ 65 z 6

z4

λ 24

z2

t →∞

λ 26

Рис.3.1.1 Все другие состояния – концевые (одиночные или образующие группу – сильносвязный подграф), из которых после входа в них в конечный момент времени t = t кон нет выхода в каждой реализации при t > t кон (на рис.3.1.1 это состояние z 4 и группа z3 , z5 , z 6 ). В одиночные концевые z j или в концевую группу переход совершается один раз или ни одного за одну реализацию. По множеству реализаций: для любого одиночного концевого z j установившаяся при t → ∞ вероятность P j (∞) определяется суммарным числом переходов из неконцевых состояний в z j : Pj (∞) = Pj =

1 N

∑

∀i∈M нк

nij

N →∞

=

∑

∀i∈M нк

nij N

= N →∞

∑n

ij

,

∀i∈M нк

где: n ij = 0 , если в графе λ ij = 0 ; n ij – вероятность перехода (входа) в z j в установившемся режиме за время

наблюдения T → ∞ или среднее число переходов (входов) на одну реализацию; M нк – множество всех неконцевых состояний (например, P4 = P4 вх = n 24 + n 14 при λ14 ≠ 0 на рис.3.1.1). Для множества всех вершин M CC концевого сильно связного подграфа ( М СС ∈ М К , МК - множество всех концевых величин) также находим суммарную установившуюся вероятность входа, заменяя подграф обобщенным состоянием z 7 (рис.3.1.2),

эквивалентным группе z3 , z5 , z 6 на рис.3.1.1.

19

λ13

z(0) = z1

λ 21

z7

λ12 λ 24

z4

z2

Рис.3.1.2

При

P3 (∞) + P5 (∞) + P6 (∞) = P7 вх = P7 = n 13

этом

λ 26 = 0 ),

(при

или

P3 (∞) + P5 (∞) + P6 (∞) = P7 = n 13 + n 26 (при λ 26 ≠ 0 на рис.3.1.1). На графе с обобщенными состояниями G ′ остальные состояния сохраняют свои обозначения, а множество концевых вершин обозначим M к′ . Вероятности входа в концевые состояния можно найти, используя для неконцевых состояний равенства количеств входов в z j и выходов из z j в среднем за одну

реализацию: n j вх = n j вых , j ∈ M нк . Если в этих уравнениях z j не является начальным состоянием, то есть z j ≠ z(0) , то n j вх =

∑n

ij

.

∀i∈M нк

Если z j = z(0) , то n j вх = 1 +

∑n

∀i∈M нк

ij

, где 1 учитывает заданное z j (0) для каждой

−

реализации, причем n ij = 0 при λij = 0 .

∑n

При этом n jввы =

ji

∀i∈M нк UМ к ′

и здесь j ∈ М нк

В составляемых уравнениях ( n j вх = n j вых ) используются интенсивности переходов λ ij , указанные на дугах графа состояний. Для любых переходов z i → z j однородных МСП λ ij =

n ij (∆t ) Ti*

∆t →0 N i →∞

, где

N i →∞

– число наблюдений z i в нулевом окне.

Перейдем от нулевого окна к наблюдению однородного МСП на бесконечном интервале времени t ∈ [0; T ), T = K ⋅ ∆t K →∞ → ∞ ∆t →0

и

представим

λij =

Knij (∆t ) KTi

*

= ∆t → 0 K →∞

N ij Ti

N ij → ∞ Ti → ∞

=

N ij N Ti N

= N →∞

n ij Ti

–

это

результат

усреднения по реализациям ( KTi* = Ti – суммарное время наблюдения z i и N ij суммарное число переходов z i → z j в N → ∞ реализациях).

20 Смысл n ij тот же, что выше в уравнениях n j вх = n j вых . Если i, j ∈ М нк , то в каждой −

−

реализации nij и Ti - случайные величины, имеющие средние значения n ij и T i для множества реализаций ( N → ∞ ). Тогда n ij = λ ij T i ,и составляемые уравнения с неизвестными T i имеют вид: υ j + ∑ λij T i = ∑ λ ji T j , j ∈ M нк  ∀i∈M нк ∀i∈M НК UМ K ′  (3.1.1)  1, z j = z (0) υ j =   0, z j ≠ z (0) В этой системе уравнений их число равно числу неизвестных T i , после вычисления которых можно найти Pj вх = ∑ λij T i , j ∈ M к′ . (3.1.2) ∀i∈M нк

Очевидно, можно вычислять не все T i , а только необходимые для расчета Pj вх , и

∑P

∀j∈М К ′

jвв

= 1.

Пример:

λ13 = λ17

z(0) = z1

λ 21

z7

λ12 λ 24 z2

z4

1 + λ 21 T 2 = λ13 T1 + λ12 T1  λ12 T1 = λ 21 T 2 + λ 24 T 2 Суммируя эти уравнения и используя второе, получим: λ 21 + λ 24  1 = λ13 T1 + λ 24 T 2  T 1 = λ ( λ + λ ) + λ λ   13 21 24 24 12 ⇒ λ12    λ12 T 2 = λ + λ T1  T 2 =  21 24   λ13 (λ 21 + λ 24 ) + λ 24 λ12  λ13 (λ 21 + λ 24 )  P7 вх = λ13 T 1 = λ (λ + λ ) + λ λ 13 21 24 24 12   λ 24 λ12 P4 вх = P4 = λ 24 T 2 = λ13 (λ 21 + λ 24 ) + λ 24 λ12 

21

3.2. Стационарный концевой МСП, определение стационарных вероятностей состояний (СВС) На основании известной теоремы Маркова можно утверждать: в однородном МСП, соответствующем концевому сильно – связному подграфу конечного числа состояний, при t → ∞ устанавливается стационарный режим, в котором существуют вероятности Pj (∞) = lim Pj ( t ) , ∑ Pj (∞) = Pвх , где МСС – конечное множество состояний подграфа. t →∞

j∈M СС

В стационарном режиме при t → ∞ рассмотрим в нулевом окне ( ∆t → 0 ) однородный МСП: N j (t) Nj N j ∆t n jj ∆t + n ji ∆t P j (∞ ) = = = = , i≠ j N ( t ) t →∞ N N →∞ N∆t ∆t →0 N∆t ∆t →0 N →∞

N →∞

N →∞

где N j - число наблюдений z j (t ) ; N - число реализаций; n jj – наблюдаемое в окне число реализаций МСП с сохранением z j в течении всего интервала ∆t ; n ji – число реализаций с переходом z j → z i в окне ∆t , причем n jj >> n ji при ∆t → 0 , при t → ∞ .

Тогда Pj (∞) =

n jj ∆t N∆t

∆t →0 N →∞

=

T j* T*

, где T j* и T * – суммарные длительности наблюдения в

нулевом окне соответственно состояния z j и всех реализаций стационарного режима. Очевидно, стационарные вероятности P j (∞) имеют смысл относительных длительностей наблюдения состояний z j в окне ∆t → 0 . Перейдем к бесконечному окну наблюдения стационарного МСП в течение K∆t = T →∞: ∆t →0 K →∞

Pj (∞) =

KT j* KT

==

* K →∞

KT j* N KT

=

*

N

N →∞ K →∞

Tj T

, T →∞

где KT j* – суммарная длительность наблюдения z j в N → ∞ реализациях стационарного режима при T → ∞ . Значит, после усреднения по реализациям, которые при T → ∞ в стационарном режиме равнозначны, P j (∞) имеет смысл относительной суммарной длительности наблюдения состояния

z j в любой одной реализации МСП, что

используется практически для определения различных показателей работы модели: Tj , (3.2.1) P j = P j (∞ ) = T T →∞ где T j – суммарное время наблюдения z j в одной реализации стационарного режима при ее длительности T (при этом знак усреднения можно опустить). Аналогично, в стационарном режиме, если использовать полученные ранее результаты: nij (∆t ) K ⋅ nij (∆t ) / N n ij (T ) λij = = = * * ∆t →0 Ti KTi / N N →∞ T i T →∞ N i →∞

K∆t →∞

22 Если рассматривается одна реализация МСП в стационарном режиме, то n ij λ ij = (обозначения усреднений по реализациям можно опустить). Ниже Ti T →∞ i

рассматриваться только одна бесконечная реализация стационарного режима и СВС для неё. nij T f ij Тогда λij = , = Ti T T →∞ Pi где величину f ij =

n ij T

– назовем плотностью переходов z i → z j в стационарном T →∞

режиме (среднее количество переходов в единицу времени наблюдения T одной реализации). Плотности переходов определяются как f ij = λ ij Pi или f ji = λ ji Pj , причем Pi = Pi (∞), Pj = Pj (∞) . Очевидно, суммарные плотности входов в z j и выходов из z j одинаковы: f j вх = f j вых где: f j вх =

1 ∑ nij T ∀i → М СС

= T →∞

∑f

∀i∈M СС

ij

, f j вых =

∑f

∀i∈M СС

ji

,

Система уравнений для определения СВС концевого сильно-связного подграфа:  ∑ λij Pi = ∑ λ ji Pj , ∀i∈M СС ∀i∈M СС  (3.2.2) ∀j ∈ M сc , исключая одно уравнение,  Pj = Pвх , ∀j∑ ∈ M CC  где Pвх определяется, как показано в разделе 3.1. Исключать одно уравнение надо, так как сумма всех уравнений для j∈ M c даёт тождество, что говорит о линейной зависимости этих уравнений. В итоге получаем систему уравнений, число которых равно числу неизвестных вероятностей P j (∞) = P j . Если весь граф состояний сильно-связный (нет неконцевых состояний), то Pвх = 1 . Уравнения Колмогорова для стационарного МСП дают эту же систему уравнений при dPj (t ) = 0 (см. выше). dt Для неконцевых состояний выше рассматривались уравнения (3.1.1), позволяющие найти средние суммарные длительности T j этих состояний для одной реализации. Для концевых состояний z j сильно-связного подграфа, если требуется, можно найти средние длительности τ j непрерывного наблюдения z j в стационарном режиме ( j ∈ M cc ):

τj =

Tj n j вых

= T j →∞

Tj /T n j вых / T

= T →∞

Pj

∑λ

∀i∈M CC

ji

Pj

,

где n j вых – количество наблюдений z j в стационарном режиме за время T j , Тогда средняя длительность состояния z j

n jвых T

= f jвых .

23 −

τj =

1

∑λ

∀i∈М CC −

.

(3.2.3)

ji

Значит, τ j − это величина, обратная суммарной интенсивности выхода из этого состояния.

24

4. Стационарный МСП “гибель и размножение”, типовая аналитическая модель “разомкнутая система массового обслуживания (СМО) без потерь заявок” 4.1. МСП “гибель и размножение”, стационарные вероятности состояний (СВС) Результаты рассмотрения этого вопроса используются для анализа СМО. Название “гибель и размножение” введено биологами, которые изучали заселенность заданной территории особями в количестве n – переменная состояния (гибель и рождение, приход на территорию и уход с неё рассматриваются как события изменения n на n+1 или n-1). Граф состояний имеет “цепной” вид (рис.4.1.1), нумерация состояний принята z n , что оказалось удобным для СМО и сетей СМО, n = 0, Q . Обозначения интенсивностей переходов на дугах исходящих из вершины z n , приняты λ n и µ n .

λ0 z0

z1

z n −1

… µ2

µ1

λ n −1

λn −2

λ1

µ n −1

λn zn

µn

λ Q −1 zQ

… µ n +1

µQ

Рис.4.1.1

Граф на рис.4.1.1 –сильно-связный без неконцевых состояний. В стационарном режиме (при Q < ∞) начальные состояния не рассматриваются. Обозначения стационарных вероятностей: P j = P(n ) для z n , n = 0, Q . В сечении графа состояний плотности событий – переходов слева направо и обратно равны (левый и правый подграфы можно заменить обобщенными вершинами), т.е. плотности переходов f n −1,n = f n ,n −1 ⇒ λ n −1P(n − 1) = µ n P(n ) ; P (n) = P(n − 1)

n

P (n) n >0 = P (0)∏ k =1

λ n −1 = P ( n − 2) µn

 λ n − 2  λ n −1  λ λ ...λ    = ... = P(0) 0 1 n −1 ; µ1 µ 2 ...µ n n −1  µ n  1µ4 4244 3 отношения интенсивностей в сечениях графа

Q Q n  λ k −1 λ  ; P(0) ≠ 0; P(0) + ∑ P (n) = 1; P(0)1 + ∑∏ k −1  = 1 ; µk n =1  n =1 k =1 µ k 

-1

Q n  λ  P(0) = 1 + ∑∏ k −1  .    n =1 k =1 µ k 

25 Если Q < ∞ то для конечного множества состояний верно следствие теоремы Маркова о существовании P(n) . Если Q → ∞ , то: -1

-1

Q n ∞ n   λ  λ k −1    P(0) = lim 1 + ∑∏ = 1 + ∑∏ k −1  .    Q →∞   n =1 k =1 µ k   n =1 k =1 µ k  λ Вероятность P(0) существует при условии сходимости: k −1 < 1 (при k > k * < ∞ ) µk признак Даламбера.. Это условие является условием существования и P(n ) , причем P ( n ) n →∞ → 0 .

Итак, для МСП “гибель и размножение” существуют СВС: −1 Q n  λ k −1   , Q < ∞ 1 + ∑∏  n =1 k =1 µ k  P (0) =  −1 n ∞  λ k −1  λ k −1  , < 1, при k > k * 1 + ∑∏ µ µ 1 = n 1 = k k k    n

P (n) = P(0)∏ k =1

(4.1.1)

λ k −1 µk

4.2. Типовая аналитическая модель “разомкнутая СМО без потерь заявок”, условие работоспособности, СВС Модели массового обслуживания используются для широкого класса систем, задачи исследования и проектирования которых решаются в основном методами имитационного моделирования на базе концепции массового обслуживания, что подробнее рассмотрено ниже. В этой концепции рассматриваются обобщенные подвижные объемы-заявки и пути их прохождения через накопители, обслуживающие устройства, разветвления и т.п. Для некоторых типовых разновидностей СМО и сетей СМО, описываемых в частности на основе МСП типа “ гибель и размножение”, разработаны аналитические модели путем перехода к концепции графа состояний, размеченного по дугам интенсивностями переходов. Примером такой СМО является модель передатчика сообщений, рассмотренная в разделе 2.3. Более общая концептуальная схема разомкнутой многоканальной СМО без потерь заявок представлена на рис.4.2.1. τвх – случайные интервалы времени между

моментами входа заявок

накопитель неограниченной емкости, очередь FIFO текущей длины l

m – канальное обслуживающее устройство, τоб – случайные интервалы времени обслуживания заявок, u - текущее число активных каналов

τвых – случайные интервалы времени между

моментами выхода заявок

Рис.4.2.1 На вход СМО поступают заявки в точечные моменты времени через случайные интервалы τвх , распределенные экспоненциально с интенсивностью

26 1 = f вх , τ вх где f вх является плотностью потока событий появления заявок. В накопителе неограниченной емкости может существовать очередь в порядке входа заявок в СМО (дисциплина очереди FIFO означает, что заявка, входящая в очередь первой, выходит из нее также первой). Каждый из m одинаковых параллельных каналов обслуживания, если в него поступила заявка, обеспечивает случайные интервалы обслуживания τоб , распределенные экспоненциально, что определяет интенсивность событий выхода заявки 1 из одного канала µ = = µ∆t . и условную вероятность такого события P11 (∆t ) ∆t →0 τ об События входа заявок в СМО и их выхода из СМО приводят к изменениям состояния СМО, то есть текущего суммарного количества заявок n = l + u в накопителе и в обслуживающих каналах. Условные вероятности переходов n → n + 1 определяются 1 = f вх : фактором τ вх , то есть постоянной интенсивностью λ n = τ вх

Pn n +1 (∆t )

∆t →0

= λ n ∆t = f вх ∆t .

Для данной типовой модели будем считать, что события изменения состояния СМО являются однократными при ∆t → 0 , то есть выходы заявок из u параллельных обслуживающих одновременно активных каналов являются несовместными событиями. Тогда условная вероятность выхода заявки из СМО: P1 u (∆t ) = u P1 1 (∆t ) = uµ∆t ∆t →0

∆t →0

является и условной вероятностью перехода n → n − 1 : P1 u (∆t ) = Pn n −1 (∆t ) = µ n ∆t , ∆t →0

∆t →0

где: µ n = uµ – это интенсивности переходов n → n − 1 , причем

n, n = 1, m nµ , n = 1, m; u= , µn =  m, n > m. mµ , n > m Очевидно, граф состояний данной СМО является частным случаем графа, показанного на рис.4.1.1 для МСП “гибель и размножение”, при Q → ∞ . Для такого графа определено условие существования стационарного режима, являющееся одновременно условием работоспособности СМО без потерь: λ k −1 f f = вх < 1 или вх = ρ < m . (4.2.1) µ k k >m mµ µ Стационарные вероятности разомкнутой СМО без потерь определяются по формулам, полученным для МСП “гибель и размножение”: n n   f вх  1 f вх ρn = P(0) , n = 1, m; = P(0)  P(0)∏ n! k =1 kµ   µ  n! P(n) =  n m  f вх   f вх n f вх 1 ρn   P(0)∏ kµ ∏ mµ = P(0) µ  m!m n − m = P(0) m!m n − m , n > m; k =1 k = m +1    m n ∞  ρ ρn P(0) = 1 + ∑ + ∑ n −m   n =1 n! n =m +1 m!m

начав суммирование с n=0, объединим при 0!=1

   

−1

сумма членов бесконечной убывающей геометрической прогрессии (ρ/m<1)

27

Итак, при

f вх = ρ < m получаем СВС разомкнутой СМО без потерь: µ  ρn P(0) , n = 1, m; n! P(n) =  n P(0) ρ , n > m; m!m n − m 

(4.2.2)

−1

 m ρn ρ m +1    . P(0) =  ∑ + − n! m! (m ρ) n = 0  

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

P1,вых (∆t ) ∆t →0 = ∑ P1,u (∆t ) , u =1

где P1,u (∆t ) – безусловная вероятность выхода заявки из u одновременно активных каналов P1,u (∆t ) ∆t →0 = P1 u (∆t ) P(u ) , где: P1 u (∆t )

∆t →0

= uµ∆t – описанная выше условная вероятность,

P(u ) – вероятность условия (активности u каналов). m

m

Тогда P1,вых (∆t ) ∆t →0 = ∑ uµ∆tP (u ) = µ∆t ∑ uP (u ) = µ u∆t = λвых ∆t , то есть u =1 u =1 1 424 3 математическое ожидание интервалы τ вых распределены экспоненциально с интенсивностью λ вых = µu , величина которой совпадает с плотностью потоков событий выхода и входа заявок (при отсутствии потерь): f вых = f вх = µ u . Этот вывод будет использован при изучении моделей в виде сетей массового обслуживания.

4.3. Стационарные показатели работы разомкнутой СМО без потерь 1. Загрузка обслуживающих каналов: a) абсолютная – среднее число активных каналов f u = вх = ρ µ b) относительная – коэффициент загрузки обслуживающих каналов ρ f u K зок = = = вх m m µm

28 c) коэффициент простоя обслуживающих каналов m−u K пок = = 1 − K зок m 2. Средняя длина очереди (средняя абсолютная загрузка накопителя) l =

∞

∑ lP(l )

l =1 1 424 3 мат. ожидание дискретной случайной величины

=

∞

∞

∑ ( n − m) P ( n) = ∑

n = m +1

n = m +1

n−m=l n=m+l

P ( 0) ρ n P ( 0) ρ m ( n − m) = ⋅ m! m!m n − m

Условие сходимости выполняется, так как q = ρ и тогда, как известно, ∑ = m

l

ρ l  ∑ l =1  m  1 424 3 Σ - сумма членов бесконечной арифметико геометрической прогрессии ∞

ρ < 1 по условию работоспособности, m

2

ρ  1 −  .  m P(0)ρ m +1 l = (m − 1)!(m − ρ) 2 3. Среднее количество заявок в СМО n = l +u = l +ρ

(4.3.1)

4. Среднее время простоя (ожидания) заявки в очереди t ож . Используется формула Литтла. Ее упрощенный вывод: если на любом участке пути движения заявок при FIFO без потерь находится в среднем n уч заявок, то каждая проходит в среднем n уч позиций; время пребывания на одной позиции – это 1 1 τ вых = = . Среднее время прохождения участка (формула Литтла) f вых f вх

t уч =

n уч f вх

(4.3.2)

Для накопителя n уч = l , t ож =

l

f вх

.

5. Среднее время прохождения заявки через СМО n u l +u l u t= = = + = t ож + = t ож + τ об f вх f вх f вх f вых µu 6. Коэффициент использования заявок u n− l K из = = = 1 − K пз , n n где K пз – коэффициент простоя заявок.

(4.3.3)

(4.3.4)

4.4. СВС и показатели работы 1-канальной СМО без потерь Используем результаты разделов 4.2 и 4.3 при m=1.

29 Условие работоспособности:

f вх

µ

= ρ <1.

P(n) = P(0)ρ n , P(n) = 1 − ρ

СВС:

Показатели работы: f 1. u = ρ = вх ; K зок = u = ρ ; K пок = 1 − ρ = P(0),

µ

2.

l =

причем K пок = P(0) только для m = 1;

ρ2 ; 1− ρ

ρ

3. n = l + u = 4. t ож =

f вх

=

l

l

ρ

;

ρ ; µ − f вх

t ож 1 ; = f вх f вх ρ ρ µ − f вх 6. K из = 1 − ρ = P(0) − только для m = 1; . K пз = 1 − К из = ρ

5. t =

n

l

1− ρ

=

=

=

(4.4.1)

30

5. Типовая аналитическая модель “Разомкнутая СМО с потерями заявок” (с ограничением емкости накопителя) 5.1. Описание СМО с потерями, её СВС Концептуальная схема разомкнутой СМО с потерями представлена на рис.5.1.1, где некоторые обозначения те же, что на рис.4.2.1 и в разделе 4.2.

τвх распределены экспоненциально,

плотность потока 1 f вх = τвх

m – канальное ОУ, u – текущее число активных каналов, τоб распределены экспоненциально, 1 = µ – интенсивность τоб обслуживания

накопитель емкости L<∞, FIFO, l
если накопитель полон

СМО

обслуженные заявки с плотностью потока f вых

необслуженные заявки – потери с плотностью потока f п

Рис.5.1.1

Граф состояний данной СМО отличается от описанного в разделе 4.2 только ограничением для переменной состояния: n ∈ [0, L + m] , факторы переходов и интенсивности переходов n → n + 1 , n → n − 1 - прежние: nµ, n = 1, m µn =  λп = f вх , mµ, n = m + 1, L + m f Обозначая вх = ρ , можно использовать формулы для СВС P(n ) те же, что для СМО µ без потерь, но при n ∈ [0, L + m] −1

   m n  n L+ m ρ ρ   , + ∑ P(0) = ∑ n − m   n! n =m +1 m!m 1442443   n =0 ∑   где, учитывая, что n − m = l , n = m + l , и заменив пределы суммирования, получим

ρm

l

ρ ∑=   , ∑ m! 1 l =1  m  424 3 L

σ

причем  ρ mL − ρL ⋅ , ρ ≠ m (кка сумма членов конечной геометрической прогрессии);  σ = mL m − ρ L, ρ = m 

31 Тогда СВС разомкнутой СМО с потерями при ρ =

f вх : µ

−1   m ρn ρ m +1 m L − ρ L   , ρ ≠ m; P ′(0) =  ∑ + L   n =0 n! m!m m − ρ  P(0) =  −1  m mn mm   L  , ρ = m; + P ′′(0) =  ∑ n! m! n 0 =   

(5.1.1)

 ρn P(0) , n = 1, m; n! P(n) =  n P(0) ρ , n = m + 1, L + m.  m!m n − m

5.2. Стационарные показатели работы разомкнутой СМО с потерями 1. Вероятность потерь заявок Pп =

Nп N вх

, N вх →∞

где: N п = f вх TL+ m – число потерь заявок за суммарное время существования TL+ m состояния n = L + m в стационарном режиме (только в этом состоянии происходят потери); N вх = f вх T – число входных заявок за время T наблюдения стационарного режима. Тогда

РП =

f вх TL + m f вх T

= T →∞

TL + m = P ( L + m) T

Используя результаты раздела 5.1, для n = L + m получим  ρ L+m ′ P ( 0 ) , ρ ≠ m;  m!m L (5.2.1) Р П = P ( L + m) =  m m  P ′′(0) , ρ = m; m!  где ρ = m означает , что f вх = mµ − максимальной суммарной интенсивности обслуживания.

2. Пропускная способность СМО: a) абсолютная (среднее количество заявок в единицу времени)  f  f f T N f вых = f вх − f п = f вх 1 − п ; п = п = п  f вх  f вх f вх T T→∞ N вх

f вых = f вх (1 − Pп ) b) относительная (коэффициент обслуживания)

= Pп ; N вх →∞

(5.2.2)

32 K обс =

f вых = 1 − Pп f вх

3. Загрузка обслуживающих каналов: a) абсолютная u=

f вых = ρ(1 − Pп ) ; µ

b) относительная K зок =

u f вых ρ = = (1 − Pп ) . m mµ m

4. Загрузка накопителя: a) абсолютная (средняя длина очереди) l

P ( 0) ρ m L  ρ  l = ∑ lP (l ) = l  , ∑ m! 1 l =1 l =1  m  424 3 L

∑

где Σ – сумма членов конечной арифметико-геометрической прогрессии при ρ ≠ m , или – сумма членов арифметической прогрессии при ρ = m ; ρ обозначив q = , используем известные результаты для Σ и получим окончательное m  1 − q L (1 + L − L ⋅ q) , ρ ≠ m; q (1 − q) 2 выражение для l : ∑ =  L L + 1 , ρ = m;  2  ρ m q 1 − q L (1 + L − Lq ) ′ ⋅ P , ρ ≠ m; ( 0 )  m! (1 − q) 2  l = m  ′′ m L L + 1 ⋅ P ( 0 ) , ρ = m;  2 m! f ρ ρ = вх ; q = . m µ

b) относительная загрузка накопителя K зн =

(5.2.3)

l L

5. n = l + u – среднее число заявок в СМО l l 6. t ож = = – среднее время ожидания в очереди f вых uµ 7. Среднее время прохождения СМО обслуженными заявками n t= = t ож + τ об f вых

5.3. СВС и показатели работы разомкнутой 1-канальной СМО с потерями ( m = 1, q =

ρ = ρ) m

Используя результаты раздела 5.2, получим

33 L −1   1− ρ 2 1− ρ   = P′(0) = 1 + ρ + ρ , ρ ≠1 L+2  − 1 ρ − ρ 1   P(0) =   1 -1 P′′(0) = (1 + 1 + L) = L + 2 , ρ = m = 1  n 1− ρ ρ 1 − ρ L+2 , ρ ≠ 1 n P(n) = P(0) ⋅ ρ =  n∈[1, L +1]  1 , ρ = m =1  L + 2

(5.3.1)

(5.3.2)

При этом ρ = 1 и m = 1 определяет СМО с равновероятными состояниями ( L + 2 – это количество состояний). Далее рассмотрим СМО только при ρ ≠ 1 и m = 1 , учитывая результаты и пояснения 1 , например, раздела 5.2 (при ρ = 1 все показатели находят при P(n ) = L+2 1 PП = P( L + 1) = ). L+2 Показатели при ρ ≠ 1, m = 1 : 1− ρ 1. Pп = P(L + 1) = (5.3.3) ρ L+1 ; L+ 2 1− ρ 2. f вых = f вх (1 − Pп ) , K обс = 1 − Pп ; 3. u = ρ(1 − Pп ) ; 4.

l =

− ρ 2 1 − ρ L (1 + L − Lρ ) (учтено, что q = ρ , формула для l взята (5.2.3), и L+2 1− ρ 1− ρ

выражение для P ′(0) - из (5.3.1); L

P(l ) = если ρ = 1 , то используется l = ∑ l { l =1

n = l +u; l l 6. t ож = = ; f вых uµ

5.

7. t =

n f вых

= t ож + τ об .

1 L+2

1 L +1 L L +1 ; L = ⋅ L+2 2 2 L+2

34

6. Типовая аналитическая модель “замкнутая СМО” 6.1. Описание типовой замкнутой СМО, её СВС До сих пор источник заявок был одноканальным и для типовых СМО в графе состояний МСП “гибель и размножение” рассматривались интенсивности λ n = λ вх = f вх = const . Могут рассматриваться модели различных СМО с многоканальным источником 1 = δ , λис = uδ ис , u ис ≤ N, λис ≠ const на графе состояний, u ис − заявок (рис.6.1.1),

τ ис

текущее ограниченное число активных каналов источника.

N параллельных каналов генерации заявок через случайные интервалы τис

f вых = f ис - плотности потока заявок

m – канальная СМО без потерь, n – текущее число заявок

f ис

Рис.6.1.1 К таким моделям относится и типовая “замкнутая СМО”. Концептуальная схема этой СМО (рис.6.1.2) содержит замкнутый путь прохождения постоянного количества N заявок (нет входа заявок из внешней среды и нет ухода в нее). Внутренний источник заявок: N каналов задержки на интервалы τис , распределенные экспоненциально,

1 =δ, τис

u ис = nис – текущее число

m - канальное обслуживающее устройство,

f ис

Накопитель емкости N − m , FIFO, l – текущее число заявок

τоб

распределены

экспоненциально,

1

τ об

f вых

=µ,

u – текущее число заявок (активных каналов)

заявок (активных каналов)

Рис.6.1.2 Количество заявок n = l + u принимается за переменную состояния этой СМО, так как этим определяется и состояние источника n ис = N − n (число его активных каналов). Источник заявок дает переменную интенсивность переходов n → n + 1 : λ n = n ис δ = ( N − n )δ , что можно обосновать так же, как было показано в разделе 4.2 для µ n , причем здесь n ∈ [0, N] . В замкнутой СМО остаются такими же, как для ранее рассмотренных СМО, интенсивности переходов n → n − 1 :

35 nµ, n = 1, m . µ n = uµ =  mµ, n = m + 1, N Граф состояний данной СМО также является частным случаем графа (рис.4.1.1) для МСП типа “гибель и размножение” при Q = N . Применим полученные для этого МСП формулы для определения вероятностей состояний замкнутой СМО:

n

P (n) = P(0)∏ k =1

λ k −1 , µk −1

n N  λ  P (0) = 1 + ∑∏ k −1  ,  n =1 k =1 µ k 

kµ , k = 1, m где λ k −1 = ( N − k + 1)δ , µ k =  mµ , k = m + 1, N δ Используем обозначение ρ = (величина ρ – любая) и учтем, что в выражении µ множитель N − k + 1 ∈ [ N − n + 1, N ] , при изменении k от 1 до n.  n N! P(0)∏ (N − k + 1) δ ⋅ (N − n)! = P(0)ρ n , n = 1, m (дополнены множители  kµ (N − n)! n!(N − n)! k =1   (N - n)!до N!); P(n) =   (6.1.1)  n m n ρ (N k 1)δ (N k 1)δ (N n)! − + − + − N! P(0)∏ ∏ mµ ⋅ (N − n)! = P(0) m!mn−m (N − n)!, n = m + 1, N;  kµ k =1 k =m+1 −1

N  m ρ n N!  ρ n N! P(0) = ∑ + ∑  . n −m n! (N n)! − m! m (N n)! − n 0 n m 1 = = +  

6.2. Стационарные показатели работы типовой замкнутой СМО. −

Для этой СМО существует соотношение показателей l и u , позволяющее вычислить один из них, если известен другой: ; f вых = f вх ⇒ µ u = (N − n )δ = (N − l − u )δ ;  µ l = N − u 1 + ; (6.2.1)  δ u=

1. Загрузка каналов обслуживания:

N− l . µ 1+ δ

(6.2.2)

36 а) абсолютная:

u = m − u св ; u cв = m - n

n<m

; u св =

m

∑u

u св =1

св

P(u св ) =

0

∑ (m − n)P(n),

n = m −1

мат. ожидание где uсв - текущее число свободных каналов; тогда

u =m−

m −1

∑ (m − n )P(n )

(6.2.3)

n =0

Или из (6.2.2), если проще найти l из (6.2.5); b) относительная (коэффициент загрузки обслуживающих каналов) −

K зок

u N− l ; = = m  µ m1 +   δ

(6.2.4)

K пок = 1 − K зок (коэффициент простоя обслуживающих каналов). 2. Производительность СМО (среднее количество обслуживаний в единицу времени): f вых = uµ. 3. Загрузка накопителя а) абсолютная (средняя длина очереди) l =

N −m

∑ lP(l ) = l =1

N

∑ ( n − m) P ( n)

(6.2.5)

n = m +1

или из (6.2.1), если проще найти u из (6.2.3); b) относительная l l K зн = , K пз = (коэффициент простоя заявок), N-m N N −l u К из = = (коэффициент использования заявок). N N 4. n = l + u (среднее число заявок в СМО без учета источника). l (среднее время ожидания для заявок в накопителе). 5. t ож = f вых 6. Среднее время прохождения СМО (без учета источника) − n t= = t ож + τ об . f вых 7. Среднее время прохождения заявки по замкнутому контуру − − 1 1 − N n+ N −n l +u N −n tц = = = + = t ож + + = t ож + τ об + τ ис , f вых f вых f вых ( N − n)δ µ δ что соответствует представлению о составе времени цикла.

(6.2.6)

37

6.3. СВС и показатели работы типовой 1- канальной замкнутой СМО (m=1) СВС:  ρ n N! = P(n) P(0) ;  (N − n)!  n∈[1, N]  −1 N ρ n N!  P(0) =  ∑  .  − (N n)! n = 0    В выражении (6.1.1) для P(0) две суммы объединены в одну. Показатели: u = 1 − P(0) = K зок ; K пок = 1 − K зок = P(0) - при m = 1 ;

1. 2. f вых = [1 − P(0)] ⋅ µ ; 3. загрузка накопителя (средняя длина очереди): а) абсолютная  µ l = N − [1 − P(0)] ⋅ 1 +  ;  δ b) относительная l l K зн = , K Пз = ; N -1 N 4. n = l + u ; l ; 5. t ож = f вых n

1

= t ож + τ об ; f вых µ N N = . 7. t ц = f вых [1 − P(0)] ⋅ µ

6.

t=

= t ож +

(6.3.1)

38

7. Типовые линейные сети СМО, типовая аналитическая модель “разомкнутая сеть СМО” 7.1. Структура типовых линейных сетей СМО, сетевая теорема для СВС сетей 7.1.1. Структура линейных разомкнутых сетей СМО

Рассматривается разомкнутая сеть СМО как соединение М узлов S j , j = 1, M между собой и с внешней средой (узел S0 ) путями передачи заявок из Si в S j с заданными вероятностями rij . сеть M узлов S j (СМО)

внешняя среда S 0

внешняя среда S 0

j = 1, M N – текущее число заявок

Граф структуры разомкнутой сети может быть связным или несвязным. – это “разомкнутая СМО без потерь” с накопителем неограниченной Каждый узел S j j ≠0

емкости. Заданы: m j и µ j =

1

τ об

, j = 1, M . j

S0 – рассматривается условно как узел (в него есть входы и из него – выходы), но S0 – это не СМО (нет обслуживания), в S0 пути заявок прерываются. Вероятности передачи заявок из узла Si в узлы Sj образуют матрицу rij = R –

{}

M

матрицу вероятностей передач размерности (M+1)(M+1),

∑ rij = 1 ∀i . Если j=0

rij = 0 , то нет

пути передачи заявок из Si в Sj на графе структуры. Отметим, что r00 = 0 всегда (т.к. передача заявок внутри S0 не рассматривается, не имеет смысла). Вероятности rii

i ≠0

∈ [0;1] , то есть, возможна передача заявки с выхода Si обратно на вход Si .

Матрица R задается и определяет структуру сети, связи входов и выходов ее узлов. На рисунке показана схема суммирования потоков заявок на входе узла Sj с разветвлением суммарного потока на выходе Sj.

r0 jf 0 заявки из всех Si

r1 jf1

rMjf M

rj0 f j f j вх = f j

Sj

f j вых = f j вх = f j

r j1f j

r jM f j

заявки во все Si

39 Здесь: f j – суммарные плотности прохождения заявок через S j (СМО), при j ≠ 0 эти плотности называются абсолютными производительностями узлов при оценки показателей работы сети; f 0 – суммарная плотность поступления заявок из S0 в сеть СМО и ухода заявок из сети в S0 , обычно f 0 задается численно в исходном описании сети. Линейность сети определяется системой уравнений для входов во все S j : M ∑ rij f i = f j , f 0 − задано  i =0  j = 0, M (одно уравнение исключается). 

(7.1.1)

7.1.2. Особенности замкнутой сети СМО Нет узла S0 . Матрица R имеет размерность М × М . N = const – задается количество циркулирующих в сети заявок. Граф структуры сети - сильносвязный (каждая заявка может оказаться в любом узле сети). 5. Замкнутая сеть СМО всегда работоспособна. 1. 2. 3. 4.

7.1.3. Состояния сети СМО, сетевая теорема →

Состояние разомкнутой или замкнутой сети – это вектор n состояний узлов n j , j = 1, M :

→

n = (n1 , n 2 ,...n j ,...n M ) .

Состояния

сети

можно

пронумеровать:

→

n k = (n k1 , n k 2 ,...nkj ,...n kM ) , k = 1, Q . Множество состояний сети Z c конечное при Q < ∞

(замкнутая сеть) или бесконечное счетное при Q → ∞ (разомкнутая сеть). Граф состояний сети сильносвязный в отличие от графа структуры. В сети устанавливается при t → ∞ стационарный режим. В теории сетей граф состояний не используется. Плотности потоков заявок fj через узлы - производительности узлов могут быть →

→

рассчитаны (см. ниже). При известных f j можно сетевые состояния n ∈ Z c или n k ∈ Z c →

→

рассматривать в САУ – системе автономных узлов ( n ∈ Z а и n k ∈ Z а , Z c ⊆ Z a ), что →

→

позволяет определить вероятность Pc ( n ) состояний сети через Pa ( n ) - вероятности состояний САУ, если Sj одинаковы для сети и САУ, причем Sj - это типовые разомкнутые СМО без потерь. f1

fM

S1 m1, µ1

SM mM , µ M

f1

fM

40

Интервалы τ выхj всех узлов имеют экспоненциальные распределения (в том числе для S0 - внешней среды). Тогда вероятность изменения состояния сети при входе заявки в M

узел Pвхj (∆t ) = ∑ Pвхij (∆t ) , причем для сети предполагается однократность событий смены i =0

состояния, несовместность выходов заявок из узлов, независимость этих событий и события выбора следующего узла Sj с вероятностью rij . Поэтому Pвх ij (∆t)

∆t →0

М

Pвх j (∆t)

Тогда

= Pвых i (∆t) ∆t →0 ⋅ rij = f i ⋅ ∆t ⋅ rij

∆t →0

= (∑ f i ⋅rij ) ⋅ ∆t ,

то

Pвх j (∆t )

есть

i =o

∆t →0

= f вх j ⋅ ∆t , где

М

f вхj = ∑ f i ⋅rij = f j . i =o

Это означает, что в сети все суммарные входные потоки заявок имеют экспоненциальное распределение факторов изменения состояний сети τ вхj . Поэтому рассматриваются все узлы сети как типовые разомкнутые СМО без потерь. Множество Z a состояний САУ – всегда бесконечное счетное, а Z c может быть таким же или конечным. В общем случае все сетевые состояния наблюдаемы и в САУ. Но процессы z (t ) принципиально различны: в САУ нет переходов заявок из S i в S j . →

→

Сетевые СВС Pc ( n ) можно находить через СВС САУ Pa ( n ) , используя основной признак МСП - их независимость от предыстории: свойства наблюдаемого множества состояний системы одинаковых узлов не зависят от способа соединения узлов, если способ обеспечивает сохранение экспоненциального распределения τ вхj , j = 1, M . В стационарном режиме для любого момента времени t по множеству реализаций (их число Nc → ∞): →

N (n) Pc ( n ) = c Nc →

→

→

=

N c (n) Q

∑N

→

(nk ) 14444244443 в сети N c →∞

k =1

c

=

N a (n) Q

∑N k =1

→

a

(nk )

→

=

N a (n) / N a Q

∑N k =1

→

a

,

(nk ) / N a

a →∞ 1444444244444N4 3 в САУ где в любого времени t в стационарном режиме используются суммарные количества

→

→

N c ( n ) и N a ( n ) наблюдения сетевых состояний как в сети, так и в САУ. Отношения этих количеств для САУ к числу всех реализаций Na определяют вероятности состояний. Поэтому →

Pa ( n )

→

Pc ( n ) =

Q

→

∑ P (n k =1

a

k

- сетевая теорема.

(7.1.2)

)

Эта теорема позволяет определить вероятности состояний сети по вероятностям состояний системы автономных узлов.

41

7.2 Разомкнутая сеть СМО, производительности узлов, условие работоспособности Если в уравнениях входов (7.1.1.) f 0 задано, то имеется M + 1 уравнений и М неизвестных производительностей f j , , j = 1, M . Можно показать, что M + 1 уравнений линейно зависимы, поэтому одно уравнение исключается. Решение этой системы дает абсолютные производительности f j всех узлов – СМО разомкнутой сети. Применяются также относительные производительности α j =

fj f0

, f j = α jf 0 , причем

α0 = 1 . M ∑ rij α i = α j , α 0 = 1, rij α i f 0 = α j f 0 ⇒  i =0 ∑ i =0  j = 0, M , исключая одно уравнение.  M

(7.2.1)

Решение дает относительные производительности α j , j = 1, M . Условие работоспособности сети - это выполнение условий работоспособности всех узлов разомкнутых СМО без потерь (4.2.1): fj α jf 0 m jµ j = ρ j < m j ∀j = 1, M; < m j , f0 < ∀j = 1, M µj µj αj или f 0 < min

m jµ j αj

∀j=1, M

.

(7.2.2)

7.3. СВС и показатели работы разомкнутой сети СМО M

В разомкнутой сети - случайное количество заявок N = ∑ n j [0, ∞) , j =1

Где nj - переменные состояния узлов сети. Применим сетевую теорему для разомкнутой сети, учитывая, что состояния узлов n j ∈ [0, ∞) в сети и naj ∈ [0, ∞) в САУ, то есть множества состояний Z c и Z a эквивалентны (бесконечные счетные, количество состояний Q = ∞ ): ∞

Тогда

→

∑ Pa (nk ) = 1 , k =1

→

→

M

Pc ( n ) = Pa ( n ) = ∏ Paj (n j )

–

для

состояний

узлов

j =1

независимых событий в САУ. При одинаковых f j в сети и в САУ Paj (n j ) = Pj (n j ) .

Итак, по способу вычисления получим →

M

Pc ( n ) = ∏ Pj (n j ),

(7.3.1)

j=1

→

где n j – компоненты n . Полученный результат называется теоремой Джексона. СВС Pj (n j ) узлов сети согласно (4.2.2):

как

42

ρj =

fj µj

,

n  ρjj , n j = 1, m j ; Pj (0) ⋅ n j!  Pj (n j ) =  n ρjj  , n j = m j + 1, ∞; n j −m j Pj (0) ⋅ m m j j 

(7.3.2)

−1

m +1  m ρ nj j  ρj j Pj (0) =  ∑ +  .  n j =0 n j ! m j !(m j − ρ j ) 

Для одноканальных узлов: m j = 1, ρ j =

fj

; µj n Pj (n j ) = Pj (0)ρ j j , n j = 1, ∞;

(7.3.3)

Pj (0) = 1 − ρ j .

Рассматриваются следующие основные показатели работы разомкнутой сети и ее узлов. 1. Производительности узлов: а) абсолютные f j , j = 1, M - рассчитываются по (7.1.1) b) относительные α j =

fj

- рассчитываются по (7.2.1) f0 Коэффициент использования производительности сети M

K ИПС =

∑f j =1

j

.

M

∑µ j =1

j

mj

Коэффициент потерь производительности сети K ппс = 1 − K ИПС 2. Запас работоспособности сети согласно (7.2.2) определяется как mjµ j 1 min . A= f 0 j =1, M α j 3. Загрузка каналов обслуживания узлов и всей сети: а) абсолютная (узлов) fj = ρ j , j = 1, M ; uj =

µj

b) относительная (узлов)

(7.3.4)

(7.3.5)

43

fj uj = . mj mjµ j Относительная загрузка каналов обслуживания сети

εj =

M

ε=

∑u

j

j =1

.

M

∑m j =1

j

4. Коэффициент простоя сети (как вероятность отсутствия заявок в сети – по времени): M

→

K пс = P ( n ) →

n =0

= ∏ Pj (0) j =1

5. Среднее число простаивающих заявок в сети и ее узлах: m +1  Pj (0)ρ j j , m j > 1;  2 M  (m j − 1)(m j − ρ j ) l = ∑l j; l j =  2 j=1  ρj 1 − ρ , m j = 1. j  6. Среднее количество заявок в сети и ее узлах:  l j + u j, mj >1 M − M  N = ∑n j = l + u = l + ∑u j ; n j =  ρ j , mj =1 j =1 j =1  1 ρ − j для сети  7. Коэффициент простоя заявок в сети K пз =

(7.3.6)

l . N M

Коэффициент использования заявок в сети K из =

∑u

j

j =1

= 1 − K пз . N 8. Среднее время простоя заявки во всех очередях сети по формуле Литтла

t

пз

=

M M M l l lj =∑ =∑ ⋅ α j = ∑ α j t ожj ; f 0 j =1 f 0 j =1 α j f 0 j =1

M

t пз = ∑ α j t ожj

(7.3.7)

j =1

t

ожj

l j  , m j > 1; f j =  ρ j , m = 1. j µ − f j  j

9. Среднее время прохождения заявки через сеть t =

M nj N M nj =∑ =∑ αj , f 0 j=1 f 0 j=1 f 0 α j

М

t = ∑αjt j ; j=1

(7.3.8)

44 l j 1 = t ожj + t обj , m j > 1;  + f j µ j t j =  1 , m = 1. j µ j − f j 

(7.3.9)

45

8. Типовая аналитическая модель “замкнутая сеть СМО”, СВС сети и ее узлов 8.1. Описание замкнутой сети, ее СВС Отличия замкнутой сети от разомкнутой указаны в разделе 7.1.2. В описании сети задаются: N = const, все m j и µ j для М узлов, R = {rij },

M

∑ rij = 1 . Состояния

n и nk

j=1

имеют те же компоненты n j , n kj , j = 1, M , k = 1, QMN . Количество состояний определяется значениями М и N как количество всех возможных распределений N заявок по М узлам. ( N + M − 1)! N = CN , QM N + M −1 = N!(M − 1)! 5! = 10 , Q310 = 66 , Q550 = 316251 . где С – число сочетаний, например, Q33 = 3!⋅2! По сетевой теореме: M

Pc (n) =

aj

Pa (n) k =1

a

k

(n j )

j =1

=

QMN

∑ P (n

∏P QMN

∑∏ P

)

(8.1.1)

M

k =1 j =1

aj

(nkj )

Особенность замкнутой сети: N

N

P (n j ) ≠ Paj (n j ) , так как ∑ Pj (n j ) = 1 , ∑ Pаj (n j ) < 1 (при бесконечном числе состояний 1j23 123 n j =0 n j =0 14 4244 3 1 4 4244 3 САУ). в сети в САУ в сети в САУ Кроме того, плотности потоков заявок f j можно найти, когда определены Pc (n ) , причем даже зная f j , нельзя найти P j (n j ) , так как в замкнутой сети n j ≤ N =const. В отличие от разомкнутой сети сначала надо определить СВС сети Pc (n ) и только потом P j (n j ) . Формулу для СВС Pc (n ) можно получить путем преобразования (8.1.1) к виду, определяемому заданными исходными параметрами: m j , µ j , M, N, rij . Вместо

неизвестных

абсолютных

производительностей

fj

используются

относительные производительности (вероятности нахождения “меченой заявки” в узле S j ) ωj =

fj f

fj

=

M

, ∀j = 1, M ,

∑f j j=1

M

где суммарная производительность f = ∑ f j пока неизвестна, но j=1

найти ω j из уравнений входов в узлы при f i = fω i :

M

∑ ω j = 1 . Это позволяет j=1

46 M ∑ rij ω i = ω j ,  i =1 M M  rij f i = f j ⇒ ∑ rij ω i ⋅ f = ω j ⋅ f ⇒  j = 1, M, исключая одно уравнение ; (8.1.2’) ∑ i =1 i =1 M ∑ ω j = 1.  j =1 Эта система М уравнений с М неизвестными дает решение: ω j , j = 1, M . Далее ω j считаем найденными . В (8.1.1) выразим Paj (n j ) по формулам для разомкнутых СМО без потерь (см. раздел 7.3, учтя здесь, что n j ≤ N вместо ∞); ρ j =

fj µj

=

ω jf µj

; обозначим

ωj µj

= y j ; ρ j = y jf .

n n  yj jf j , n j = 0, m j ; Paj (0) n j!  Paj (n j ) =  n n yj jf j  , n j = m j + 1, N . n j −m j Paj (0) m ! m j j 

n

Это выражение можно представить как Paj (n j ) = Paj (0)f j C j (n j ) , где C j (n j ) промежуточные величины:  y jn j , n j = 0, m j ;   n j! m j ≥ 1, j = 1, M ⇒ C j (n j ) =  (8.1.2) nj  yj  m !m n j − m j , n j = m j + 1, N.  j j n

Для одноканальных узлов: m j = 1 ⇒ C j (n j ) = y j j .

(8.1.3)

Cj(nj) можно рассчитать для любой компоненты n j заданного вектора n . Аналогично для любой компоненты n kj вектора n k : Paj (nkj ) = Paj (0) f

nkj

N C j (nkj ) , k = 1, Q M . Величины

C j (n kj ) определяются формулами для C j (n j ) , где n kj - вместо n j . Тогда выражение (8.1.1) можно записать: M M  n1 + n 2 +...+ n M M P (0) f C (n ) C j (n j ) ∏ aj  ∏ j j ∏ j=1 j=1 j=1   Pc (n ) = N = QN , QM M M M  n k1 + n k2 +...+ n kM M C j (n kj ) ∑∏ C j (n kj ) ∏ Paj (0) f ∑ ∏ k =1 j=1 k =1  j=1 j 1 =  где n1+n2+…+nM = nk1+nk2+…+nkM = N, что позволило провести сокращение. В выражении

N QM

M

∑∏ C (n k =1 j=1

j

kj

) = D M (N)

(8.1.4)

каждое произведение – слагаемое соответствует распределению N заявок по М узлам, то есть вектору состояния n k . D M ( N) – константа данной замкнутой сети, зависящая от всех исходных параметров и может быть вычислена без перебора всех n k по алгоритму, который рассматривается далее.

47 M

∏ C (n ) j

Итак, Pc (n ) =

j

j=1

D M (N)

.

(8.1.5)

8.2. Константы усеченных сетей, их использование для вычисления сетевых констант и СВС узлов замкнутой сети СМО Q MN

M

В выражении, определяющем DM ( N ) = ∑∏ Ci (nki ), {nki , i = 1, M} = n k , и каждому k =1 i =1

n k соответствует свое произведение. Среди множества n k рассмотрим подмножества векторов состояния n l (со своей нумерацией l=1,2,…), у которых зафиксирована одинаковая для узла S j компонента N -1 N -1 n lj = n j , n j = 0, N, l = 1, Q M -1 , где Q M -1 - число распределений N − n j заявок по M-1

узлам. Тогда DM ( N ) = N −n

где

Q M −1 j

M

l =1

i =1 i≠ j

∑ ∏ C (n ) i

li

N −1 N QM −1 M

∑ ∑∏ Ci (nli )

=

n j = 0 l =1 i =1

nlj = n j

N −n

N

Q M −1 j

M

n j =0

l =1

i =1 i≠ j

∑ C j (n j )

∑ ∏ C (n ) , i

li

- называется константой усеченной сети (без узла S j и без n j заявок) и

обозначается DM←−j1 ( N − n j ) . N −n

←j

D M −1 ( N − n j ) =

DM ( N ) =

N

∑C

n j =0

j

QM −1 j

M

l =1

i =1 i≠ j

∑ ∏ C (n ) . i

li

(8.2.1)

j (n j ) ⋅D ← (N − n j ) , M −1

где используются все возможные значения n j , поэтому можно обозначить n вместо n j : N

j DM ( N ) = ∑ C j ( n) ⋅ D ← ( N − n) . M −1

(8.2.2)

n=0 N −1

j Далее понадобится: DM ( N − 1) = ∑ C j (n) ⋅ D ← ( N − 1 − n) . M −1

(8.2.3)

n =0

N

M Пусть S j = S M . Тогда из (8.2.2): DM ( N ) = ∑ CM (n) ⋅ D ← ( N − n) , где обозначение M −1 n=0

←M

D M −1 ( N − n) (без узла S M ) будем проще обозначать как DM −1 ( N − n) . N

DM ( N ) = ∑ C M (n) ⋅ DM −1 ( N − n) .

(8.2.4)

DM ( N − 1) = ∑ C M (n) ⋅ DM −1 ( N − 1 − n) .

(8.2.5)

n=0 N −1 n=0

Рассмотрим замкнутую сеть, в которой S M С M (n) = y Mn , C M (0) = 1 , как следует из (8.1.3). Запишем (8.2.4), отделив слагаемое для n=0:

- одноканальный узел: mM = 1 ,

48 N

N

DM ( N ) = СM (0) ⋅ DM −1 ( N ) + ∑ CM (n) ⋅ DM −1 ( N − n) = DM −1 ( N ) + yM ⋅ ∑ yMn −1 ⋅ DM −1 ( N − n) . 123 123 n =1 n =1 n yM

1

Обозначим n −1 = n ′ и заменим пределы суммирования: n = 1 ⇒ n ′ = 0 ; n = N ⇒ n′ = N − 1 CM (n′) } N −1

Тогда DM ( N ) = DM −1 ( N ) + yM ⋅ ∑ yMn′ ⋅ DM −1 ( N − 1 − n′) . n′ = 0 14444 4244444 3 D M ( N − 1) − согласно (8.2.5)

Итак, если "старший" узел S M замкнутой сети одноканальный, то DM ( N ) = DM −1 ( N ) + yM ⋅ DM ( N − 1) . Рассмотрим

СВС

узлов замкнутой сети СМО Pj (n j ) как

(8.2.6) вероятность для

несовместных событий, равную сумме вероятностей всех тех состояний n l замкнутой сети, у которых компонента n lj = n j . Количество состояний n l

- это количество nlj = n j

N -n

распределений остальных N − n j заявок по M-1 узлам, то есть Q M -1 j (см. раздел 8.2). N-n

Pj ( n j ) =

Q M -1 j

∑ l =1

N-n

=

P(n l )

Q M -1 j Μ

∑∏ l =1

nlj = n j

C i (nli ) n

lj = n j

DM ( N )

i =1

,

где использовано (8.1.5). D← j M −1

Тогда Pj (n j ) = Pj (n j ) =

C j (n j ) D M ( N)

D← j (N − n j ) . M −1

C j (n j ) D M (N)

(N − n j ) − согласно (8.2.1)

64447444 8 N-n

⋅

Q M -1 j

M

l =1

i =1 i≠ j

∑ ∏ C (n i

li

)

;

(8.2.7)

49

9. Вычисление констант замкнутых сетей 9.1. Построение алгоритмов вычисления сетевых j (N − n j ) констант D M ( N) и D ← M −1 Для расчета показателей работы замкнутой сети надо вычислять эти константы без Μ

расчета произведений

∏ C j (nkj ) и j =1

Μ

∏ C (n ) для всех n i

li

k

и n l , которых может быть очень

i =1, i ≠ j

много. Разработаны алгоритмы рекуррентных (пошаговых вычислений). Рассматриваются усеченные сети (УС) с числом узлов r ≤ M и числом заявок s ≤ N , причем рекуррентно вычисляются константы Dr (s ) через Dr −1 ( s ) и через Dr ( s − 1) . Узлы сети нумеруются: S1 УС : r = 1, j = 1

S 2 , ... S M -1 , S M

УС : r = 2, j = 1;2 номера узлов УС : r = M − 1, j = 1; M - 1 Полная сеть: r = M , j = 1; M. Задаются последовательно r = 1, 2, ... , M . Для любого r задается число заявок последовательно s = 0, 1, 2, ... , N или в любом порядке s = 0, N . По аналогии с (8.1.4) - определением D M ( N) можно записать Qrs

r

Dr ( s ) = ∑∏ C j (nkj ) ,

(9.1.1)

k =1 j =1

причем для формальной записи алгоритмов учтем: 1. s = 0 ⇒ Qr0 = 1 - одно состояние и одно слагаемое для n 1 j = 0, j = 1, r (k равно только r

1), то есть Dr (0) = ∏ C j (0) ; 123 j =1 1

(см. формулу 8.1.2)

Dr (0) = 1 ∀ r = 1, M

(9.1.2)

r2 =3 1 ⇒ j = 1, Q1s = 1, n 1j = s = 1, N , s = 0 учтено в (9.1.2) , nкj = n11 = s 2. 1 в УС только 1-й узел 1

1

Тогда D1 (s) = ∑∏ C j (n kj ), то есть k =1 j=1

D1 ( s ) = C1 ( s), s = 1, N

(9.1.3)

50

9.2. Константы одноканальной замкнутой сети ( m j = 1 ∀ j = 1, M ) Заданы также M, N, µ j , {rij } =

R .

( MxM )

Находим относительные производительности ω j из уравнений (8.1.2’), затем yj =

ωj µj

, j = 1, M .

Для вычисления константы D M ( N) , используем (8.2.6): Dr ( s ) = Dr −1 ( s) + y r ⋅ Dr ( s − 1) S >0 ; учтем (9.1.2) и (9.1.3). r >0

Алгоритм

вычисления

D M ( N)

для

одноканальной

замкнутой

сети

( m j = 1 ∀ j = 1, M ):

Dr (0) = 1 ∀ r = 1, M r = 1 : D1 ( s) = y1s , s = 1, N

(9.2.1)

r=2   M  Dr ( s) = Dr −1 ( s) + y r Dr ( s − 1), s = 1, 2, ... , N r = M  Итог: D M ( N − 1) и D M ( N ) - для расчета показателей сети.

Промежуточные значения Dr ( s ) r < M зависят от нумерации узлов сети, но итог не зависит. Для вычисления константы усеченной одноканальной замкнутой сети D ← j ( N − n j ) M −1

можно использовать тот же алгоритм при

N − n j = s , если после удаления S j

перенумеровать узлы ( S j+1 на S j , S j+ 2 на S j+1 , … , S M на S M −1 ) при сохранении всех параметров. Практика показывает, что перенумерация при ручном счете ведет к путанице да и программирование на ЭВМ усложняется. Лучше сохранить нумерацию узлов, но записать алгоритм иначе. При задании r < j удаление S j не влияет на результат. Алгоритм вычисления для одноканальной замкнутой сети констант j j D← ( N − n j ) = D← ( s), n j = 0, N , N − n j = s = 0, N : M −1 M −1

Dr← j (0) = 1 ∀ r = 1, M − 1, ∀ j = 1, M (r - количество узлов УС, и при удалении S j номер последнего узла УС при r ≥ j равен r + 1 ); r < j : Dr← j ( s) = Dr ( s), s = 1, N - взять результаты из расчета D M ( N) по (9.2.1); (9.2.2)  r{ j{ , : D1←1 ( s) = y 2s , s = 1, N ; =1 =1 один узел S удален узел S1 2   r ≥ j : r = 2   ←j ←j ←j M  Dr ( s) = Dr −1 ( s ) + y r +1 Dr ( s − 1), s = 1, 2, ... , N.  r = M - 1 Итог: D M←−1j ( N − n j ) = D M←−1j ( s), n j = N − s, s = 0, N Все результаты зависят от исходной нумерации узлов.

51

9.3. Константы многоканальной замкнутой сети ( max m j > 1, среди узлов j=1, M

S j хотя бы один-многоканальный) Дано: M , N, µ j , m j , {rij } = R , i, j = 1, M . ( MxM )

Находим: ω j , y j =

ωj µj

, j = 1, M , причем C j (n) = y nj при m j = 1 , n = 1, N а при mj>1

рассчитывается массив значений:  n 1  y j n! , n = 0, m j ,  C j (n) =  1  y nj , n = m j + 1, N. n −m  m j !m j j s

С учетом (8.2.4) Dr ( s ) = ∑ C r (n) ⋅ Dr −1 ( s − n) . n =0

Алгоритм вычисления D M ( N) для многоканальной замкнутой сети ( max m j > 1 ): j=1,M

Dr (0) = 1 ∀ r = 1, M; r = 1 : D1 ( s ) = C1 ( s ), s = 1, N − по формуле 9.1.3; r=2  s 1, N , r < M,  = D s C r (n) Dr −1 ( s − n), s =  M ( )  r ∑  N - 1, N, r = M. n =0 r = M  Итог: D M ( N − 1) и D M ( N ) .

(9.3.1)

Промежуточные результаты зависят от нумерации узлов, итог не зависит. Для константы усеченной многоканальной замкнутой сети D ← j ( N − n j ) так же, как было для M −1

одноканальной сети, запишем алгоритм вычисления без перенумерации узлов. Алгоритм вычисления для многоканальной замкнутой сети ( max m j > 1 ) j=1,M

←j

←j

констант D M −1 ( N − n j ) = D M −1 ( s), n j = 0, N , N − n j = s = 0, N :

Dr← j (0) = 1 ∀ r = 1, M − 1, ∀ j = 1, M; r < j : Dr← j ( s) = Dr ( s), s = 1, N - взять результаты из расчета D M ( N) по (9.3.1); (9.3.2)  j = 1 : D1←1 ( s) = С 2 ( s), s = 1, N ; r= 1, { 1 4 2 4 3  один узел S 2 удален S1  r ≥ j : r = 2  s   ←j M D s C r +1 (n) ⋅ Dr←−1j ( s − n), s = 1, N ; ( ) =  ∑ r  n =0 r = M - 1   Итог: D M←−1j ( N − n j ) = D M←−1j ( s), n j = N − s, s = 0, N Все результаты зависят от нумерации узлов.

52

10. Стационарные показатели работы типовой замкнутой сети СМО и ее узлов 10.1. Загрузка обслуживающих каналов сети: 1). Абсолютная загрузка каналов обслуживания в узлах (среднее число активных каналов u j равно среднему числу заявок в обслуживающих каналах узла); u j дискретная случайная величина, зависящая от n j : n j , n j = 0, m j ; uj =  m j , n j = m j + 1, N . По формуле математического ожидания

uj =

mj

∑ u j P(u j ) =

u j =1

=

mj

∑ n C (n ) ⋅

n j =1

j

j

j

mj

∑ n j Pj (n j ) +

n j =1

j D← (N − n j ) M −1

DM ( N )

+

N

∑ m P (n ) =

n j = m j +1

j

j

N

∑ m C (n ) ⋅

n j = m j +1

j

j

j

j

j D← (N − n j ) M −1

DM ( N )

,

(10.1.1)

где использовано (8.2.7), и согласно (8.1.2)  nj 1  y j n ! , n j = 1, m j ; j  C j (n j ) =  1  y nj j , n j = m j + 1, N . n j −m j  m m ! j j  Можно обе суммы в (10.1.1) объединить, если провести преобразования: n −1 yj j nj 1 n j C j (n j ) = nj yj = yj = y j C j (n j − 1) , n j =1, m j n j! (n j − 1)!

m j C j (n j )

n

n j = m j +1, N

= mj yj j

1 1 n −1 = yj yj j = y j C j (n j − 1) . n j −m j ( n j −1) − m j m j !m j m j !m j

Тогда (10.1.1) можно записать: N yj uj = C j (n j − 1) ⋅ D ← j ( N − n j ) . ∑ M −1 D M ( N) n =1 j Обозначим n j −1 = n и заменим пределы суммирования: n j = 1 ⇒ n = 0, n j = N ⇒ n = N − 1.

Тогда

uj =

yj

D

.

N −1

C j (n) ⋅ D M←−1j ( N − 1 − n) . ∑ (N ) 1 n =0 4444244443 M D ( N − 1) согласно (8.2.3) M

( N − 1) M , j = 1, M . D (N ) M 2) Относительная загрузка обслуживающих каналов:

u j = yj

D

(10.1.2)

53 для узлов сети ε j =

uj , j = 1, M ; mj M

для всей сети (сетевой показатель) ε =

∑u

j

j =1

.

M

∑m j =1

j

10.2. Коэффициент использования заявок в сети K изс =

1 N

M

∑u

j

.

j =1

M

10.3. Среднее количество простаивающих заявок в сети l = N − ∑ u j , j =1

l = 1 − K изс . N 10.4. Производительности узлов сети f j = u j µ j , j = 1, M ;

коэффициент простоя заявок в сети: K пзс =

M

коэффициент использования производительности сети K ипс =

∑f j =1

j

;

M

∑m µ j =1

j

j

коэффициент потерь производительности сети K ппс = 1 − K ипс . 10.5. Средние длины очередей в узлах сети

lj =

N-m j

∑ l j Pj (l j ) = j =1

N

∑ (n

n j = m +1

j

− m j ) ⋅ Pj (n j );

учтем (8.2.7) и заменим n j на n : N 1 ∑ (n − m j ) ⋅ C j (n) ⋅ D M←−1j ( N − n), j = 1, M ; D ( N ) n = m +1 M N 1 j l j = (n − 1) ⋅ y nj ⋅ D ← ( N − n) ; ∑ M −1 m j =1 D ( N ) n=2 M l j коэффициенты загрузки накопителей в узлах K знj = . N − mj 10.6. Среднее число заявок в узлах сети

l

j

=

n j = u j + l j , j = 1, M ; (контроль:

M

∑n

j

(10.5.1) (10.5.2) (10.5.3)

= N ).

j =1

10.7. Средние длительности простоя (ожидания) заявки в очередях узлов сети lj t ож j = , j = 1, M . fj 10.8. Средние длительности пребывания заявок в узлах сети nj t j= = t ож j + τ об j , j = 1, M . fj

54

11. Компьютерные имитационные МДСНВ 11.1. Понятие "компьютерное имитационное моделирование" (КИМ), его алгоритм Компьютерная имитационная модель системы – это компьютерная программа составленная по алгоритму математической или специально – языковой модели системы. Алгоритм разрабатывается с обязательным учетом следующих исходных положений. 1. Исходят из принятой концептуальной модели, например для МДСНВ указывалось две концепции: - концепция на основе графа состояний модели, - концепция массового обслуживания 2. Алгоритм программной имитационной модели строится с использованием так называемых принципов имитации. Для МДСНВ и МДСДВ используется принцип “ δz ” – принцип изменения состояния (в литературе неудачно называется “принцип особых состояний”), когда рассматриваются дискретные состояния z i ∈ Ζ , где целые i = 1, I , I < ∞ или i ∈ [1; ∞) – конечное или счетное множество состояний. Имитируются переходы из состояний z i в состояние z j в последовательности возрастания реального времени t, значения которого имитируются переменной текущего модельного времени T. В МДСНВ переходы z i → z j моделируются как изменение состояний (“ δz ”), то есть изменение переменных в модели в случайные точечные моменты T. Возможны любые значения времени Т, поэтому оно названо непрерывным временем. Изменения состояний – переходы z i → z j рассматриваются как случайные события, вызванные действием случайных факторов – случайных переменных в алгоритме КИМ. Такое КИМ называют событийным. Для построения и компьютерной реализации алгоритмов МНСНВ, МНСДВ и моделей комбинированных, используется принцип “ ∆t ” – принцип приращения времени, известный в вычислительной математике как основа методов численного интегрирования систем дифференциальных уравнений, когда ∆t – шаг интегрирования. Этот принцип может дать точные результаты для моделей с ДВ, но для моделей с НВ всегда получают приблизительные результаты с ошибками, которые уменьшаются с уменьшением ∆t ценой увеличения объема вычислений. 3. В алгоритме КИМ учитывают цель моделирования: имитировать в цифровых экспериментах процессы функционирования модели во времени и обрабатывать результаты, то есть получать показатели работы модели как оценки системы.

11.2. Концептуальная МДСНВ на основе графа состояний и операции алгоритма событийного моделирования по принципу "δz" Концептуальная модель (КМ) строится на основе детальной описательно-содержательной модели системы: определяются дискретные состояния z i и возможные изменения состояния – переходы z i → z j , вызываемые соответствующими случайными причинами – факторами переходов. Эти факторы описываются интервалами времени их действия τ ij ( τ ij = const или τ ij = f (ν ) , где ν – некоторая определенная переменная модели, или τ ij – случайная величина; составляется ориентированный граф состояний в качестве концептуальной схемы модели (КС), которая дополняется полным описанием работы модели.

55 КС + описание работы модели= КМ Вершины графа – это состояния z i , для которых можно указать факторы переходов τ ij = τ ф . Дуги графа – это возможные переходы z i → z j , на дугах можно указать Tij моменты текущего модельного времени переходов, определяемые величинами τ ij интервалами действия факторов. ПРИМЕР: одноканальный передатчик сообщений с буфером заданной емкости на L сообщений. Входной поток, τ вх

одноканальный передатчик, случайная длительность передачи τ п

Буфер емкости L

Поток переданных сообщений, выходящих в точечные моменты времени Tвых

Поток не переданных сообщений, выходящих в моменты времени Tвх (поток потерь) Сообщения входят в модель в точечные моменты времени , разделенные случайными интервалами τ вх . Каждый вход и выход сообщения – текущее событие. Вход сообщения в буфер (и без задержки сразу в передатчик, если он не занят передачей) или потеря сообщения происходят в случайные моменты времени Tвх , определяемые внешним фактором τ вх , окончание которого является причиной изменения состояния - перехода zi→zj. Длительность записи сообщения в буфер считается малой величиной и не моделируется отдельно (учитывается в τ вх ). Моменты Tвых сообщений определяются внутренним случайным фактором τ п . Зайдя в передатчик, сообщение находится в нем в течение τ п . При окончании τ п в момент выхода Tвых сообщение покидает передатчик, и в тот же момент в него поступает сообщение из буфера, если он не пуст. Если буфер пуст, то передатчик простаивает: τ п могут дать непрерывную передачу нескольких сообщений, но процесс передачи может прерываться (в отличие от τ вх , целиком непрерывно заполняют текущее время моделирования). Когда передатчик занят ( τ п не закончился), то поступающее сообщение ожидает в очереди буфера, если он не полон. Иначе сообщение теряется. Состояние z i в этой модели полностью определяется переменной n - количеством сообщений в модели, n называют переменной состояния. Для L = 2 : n 0 1 2 3 zi

z1

z2

z3

z4

Граф состояний как концептуальная схема модели строится по описательно– содержательной модели системы.

56 z1

Т = Твх

τ вх ⇒ Т вх Т = Твых

z2

Т = Твх

z3

τ вх ⇒ Т вх τ П ⇒ Т вых

τ вх ⇒ Т вх τ П ⇒ Т вых

Т = min(Т вх , Т вых )

Т = min(Т вх , Т вых )

Т = Твых

z4

Т = Твх

τ вх ⇒ Т вх τ П ⇒ Т вых Т = min(Т вх , Т вых ) Т = Твых

Окончание факторов переходов τ вх и τ П определяет изменения состояния в моменты модельного времени Т = Твх или Т = Твых. При найденном Т необходимо имитировать следующие значения факторов τ вх и τ вых и определять будущие (по отношению к текущему моменту Т) значения моментов времени: Т вх = Т + τ вх , если Т было определено окончанием τ вх , и Т вых = Т + τ П , если Т было определено окончанием τ П и n ≠ 0. Указанные на графе в состояниях z2, z3, z4 факторы τ вх и τ П могут начинаться в состояниях, в которых факторы указаны, или τ вх и τ П продолжаются в этих состояниях, начавшись ранее в предшествующих состояниях. В z1 всегда начинается интервал τ вх , заканчивающийся также в z1. В состоянии z4 окончание τ вх раньше, чем τ П , не вызывает изменения состояния, и при Т = Твх необходимо имитировать потерю заявки, а при окончании τ П раньше, чем τ вх , надо имитировать переход z4 → z3 при Т = Твых. Разработка алгоритма для КИМ на ЯОН по концептуальной модели на основе графа состояний – очень трудная задача в сложных случаях. Обобщение всего вышесказанного даёт приведенная ниже схема алгоритма событийного моделирования (одноканального передатчика с ограниченной ёмкостью L буфера по принципу δz) для программирования на ЯОН с одной частной целью моделирования: N определение коэффициента потерь K п = пот . При этом не фиксируются значения N вх модельного времени T (эта переменная не используется), так как в данной простой модели достаточно использовать значения Твх и Твых. Схема дана для начального состояния z (t ) t =0 = z (0) = z1 , когда n = 0.

57

8 да

1

n = n −1

τ вх , τ П .

9

да

11

Начало: ввод L, нач. зн. ГСЧ, Nпот = 0, n = 0, Nм,

n = L +1

нет

Твх < Твых

2

нет

Tвх = ϕ1 ( x )

3

х

х

12

ГСЧ да

ГСЧ

Tвых = Т вх + τп N пот = N пот + 1 4

N вх = N вх + 1

τ вх = ϕ1 ( x) Tвх = Т вх + τ вх

n = n +1

13

ГСЧ

5

τп = ϕ2 ( x )

10

нет

n=0

τп = ϕ 2 ( x ) Tвых = Т вых + τп

x

6 х

ГСЧ

7 нет

N вх = N м

да Kп =

N пот Nм

14 15

Вывод L, N м , нач.зн. ГСЧ, K п . Конец. На схеме использованы обозначения: n – переменная состояния (количество заявок в модели); N вх – текущее количество поступивших на вход заявок; N пот – количество потерянных заявок; K п – коэффициент потерь; L – ёмкость буфера; N м – заданное максимальное число входных заявок – условие окончания моделирования;

58 ГСЧ - генератор случайных чисел x; ϕ1 , ϕ 2 − функции, преобразующие равномерно распределенную случайную величину x в экспоненциально распределенные τ вх и τ Π . Начальное значение ГСЧ используется, чтобы получить псевдослучайную воспроизводимую последовательность случайных чисел x. Блоки на схеме – операции событийного моделирования: 1 – задание начальных значений для одного цифрового эксперимента – прогона модели; 2, 3, 6, 13 – имитация времени будущих событий изменения z i → z j ; 7 – контроль окончания моделирования; 8 – определение времени ближайшего события и вида наступающего состояния в переходе; 4, 9, 11, 12 – изменение состояния (фиксация и использование переменной состояния для разветвлений алгоритма); 5, 10 – счётчики; 14, 15 – получение и вывод результатов. Этот алгоритм полностью отображает работу КМ. Мысленное моделирование по алгоритму отличается большим числом деталей по сравнению с имитацией по графу состояний. Этот алгоритм легко реализуется на любом ЯОН.

11.3. Обобщённая схема алгоритма событийного моделирования и цифровых экспериментов для программных МДСНВ на ЯОН На схеме использованы обозначения: s = 1, S – множество номеров всех факторов переходов модели; M i – множество номеров факторов, действующих в z i . M ij – множество номеров факторов, начинающихся в z j при переходе z i → z j (возможно, что M ij = φ , как это видно по графу состояний передатчика при z2 → z1). Алгоритм реализует принцип "δz"

59 1 Начало. Начальные установки модели (параметры варианта)

2 Начальные установки прогона (эксперимента): T = 0, z(0) = zi , Tм , u(0), υ(0) ,…, сброс результатов предыдущего прогона, нач.знач. ГСЧ. 3 Имитация будущих времён переходов Ts = τs , s ∈ Mi ( z j становится вместо z i 4

в новом цикле)

Определение будущего времени перехода z i → z j и j: min Ts = Ts′ ; (i, s ′) ⇒ j s∈M i

(возможно z j = z i ). 5 Обновление модельного времени T = Ts′ . 6 Выбор алгоритма Aij перехода zi → z j , то есть выбор пути в сети операций для решения требуемых задач: 1) изменение, обновление переменных; 2) сбор, накопление, оперативная обработка результатов на момент времени Т; 3) определение времён будущих событий для z j ( Ts = T + τ s , ∀s ∈ M ij )

нет

7 zi - концевое одиночное состояние ?

10 Количество прогонов достаточно?

да 9

8 да

T < Tм

нет

нет

Завершение эксперимента, первичная обработка результатов.

да

11

Окончательная обработка результатов, документирование. Конец.

60 Для разработки алгоритмов A ij не существует формальных правил, кроме указанных общих требований. Добавим, что не каждый A ij требует отдельного множества операций для реализации. Эти операции могут быть общими в различных ветвях. Поэтому количество путей, реализующих все A ij меньше количества дуг графа состояний. Эквивалентные преобразования сети операций позволяют сократить их число. Например:

Aa

Ac

Ab

Ab

Aa

Ac

эквивалентно Ab

Детальная разработка сети операций для реализации всех A ij - неформальная творческая работа, что видно, если проследить работу алгоритма модели передатчика по данной выше схеме. Кстати, эта схема с добавлением фиксации T и с заменой n на i , соответствует обобщенной схеме.

11.4. Имитация случайных величин и случайного выбора по заданному закону распределения вероятностей 11.4.1. Использование программных генераторов случайных чисел (ГСЧ)

От стандартного ГСЧ для имитации обычно получают псевдослучайные последовательности чисел x ∈ [0;1] , начиная с заданного значения (начальное значение ГСЧ – “зерно”), с равномерным распределением вероятностей (“псевдослучайные”, то есть воспроизводимые, задаваемые начальным значением ГСЧ). В компьютере x вещественная дискретная случайная величина, опишем ее как непрерывную (так как в интервале [0,1] берется не менее 10 3 значений), то есть функцией распределения вероятностей: 0, x < 0 ;  F ( X ) = P( x ≤ X ) =  X , 0 ≤ X ≤ 1 ; 1, X > 1 .  F′(X) 1

F(X) 0

a

X

b

1

X

F′(X) = 1 при X ∈ [0;1] , отсюда – название “равномерное распределение”, его основное свойство: P(a ≤ x ≤ b) = b − a . P (0 ≤ x ≤ X ) = F1 ( X ) = X

61 P(X ≤ x ≤ 1) = F2 (X) = 1 − X

11.4.2. Имитация непрерывных случайных величин τ с заданной функцией распределения вероятностей F(Θ) = P(τ ≤ Θ) Применяется однозначное функциональное преобразование случайной величины x в имитируемую случайную величину τ = ϕ( x ) : Программный ГСЧ

Обращение к ГСЧ

x

τ = ϕ( x )

τ

P(τ ≤ Θ) = F(Θ)  Дано : a) P(0 ≤ x ≤ X ) = Fа (X) = X б) P( X ≤ x ≤ 1) = F (X) = 1 − X б  Требуется найти вид функции ϕ. Однозначность преобразования означает, что можно рассматривать равенства вероятностей как равенства относительных количеств попаданий в интервалы: а) P(0 ≤ x ≤ X ) = P(τ ≤ Θ), Fа ( X ) = F (Θ) = X б) P( X ≤ x ≤ 1) = P(τ ≤ Θ), Fб ( X ) = F (Θ) = 1 − X

τ = ϕ ( x) ⇒ 

Решение уравнений дает: а) Θ = ϕ а ( X ) или б) Θ = ϕ б ( X ) , где ϕ а или ϕ б - искомая функция, так как для любых x от ГСЧ и соответствующих τ можно взять равные им границы интервалов: x = X  τ = Θ Тогда τ = ϕ а ( x) или τ = ϕ б ( x) Пример 1. Задано экспоненциальное распределение F (Θ) = 1 − e −

Θ

Θ −−

τ

, τ ≥0

-

−

а) 1 − e τ = X ⇒ Θ = −τ ln(1 − X ) или τ = −τ ln(1 − x), ϕ а (x) = -τ ln(1 − x) - нелинейное преобразование −

Θ

−

б) 1 − e τ = 1 − X ⇒ τ = −τ ln x = ϕ б (x) , ϕ б ( x) = − τ ln x . Таким образом, для КИМ типовой одноканальной СМО с потерями в схеме −

−

алгоритма раздела 11.2 можно взять ϕ1 ( x) = − τ вх ⋅ ln x и ϕ 2 ( x) = − τ П ⋅ ln x Пример 2. Задано равномерное распределение общего вида: 1 P(τ ≤ 0) = F(Θ) R

R 0

A

S

B

Θ

62

τ < A; 0,  1 (Θ − A), A ≤ τ ≤ B ; F ( Θ) =  B − A τ > B. 1, Часто равномерное распределение обозначают: τ = S ± R , где A+ B B− A , R= . R ≤ S, S = 2 2

τ = A при x = 0, Принимаем:  τ = B при x = 1. 1 Тогда: а) (Θ − A) = X ⇒ Θ = A + (B − A)X = S − R + 2RX B−A τ = A + (B − A) x = S − R + 2Rx = ϕ а ( x) ; 1 (Θ − A) = 1 − X ⇒ Θ = A + ( B − A)(1 − X ) = B − ( B − A) X = S + R − 2 RX ⇒ б) B − A ⇒ τ = B − ( B − A) x = S + R − 2 Rx = ϕ б ( x). В этом примере ϕ a ( x) и ϕ б ( х) - линейные функции. 11.4.3. Имитация случайного выбора исхода Yi , i = 1, I при заданных вероятностях I

∑ Pi = 1 P ( Y ) = P i i , если i =1 исходов Например, требуется имитация случайного выбора направления движения пакета данных в сети передачи данных после узла S4 при заданных вероятностях: S1

0.2 0.3

S2

S4

0.5 S3 Имитация выбора осуществляется обращением к стандартному ГСЧ, возвращающему псевдослучайные числа x ∈ [0;1] . В этом интервале определяются числа X1 = P1, X2 = P1+P2, … XI-1 = 1-PI : X1 = P1

0

P1

X 2 = P1 + P2 P2

P3

…

XI

X I −1 = 1 − PI

… X i − X i −1 = Pi .

PI

X 1

При каждом выборе запрашивается число x и определяется номер i интервала, в который попадает x: X i −1 < x ≤ X i ⇒ i . Вероятность такого попадания P(X i −1 < x ≤ X i ) = X i − X i −1 = Pi = P(Yi ) , что означает имитацию выбора исхода Yi с заданной вероятностью Pi .

63

12. Концепция массового обслуживания (МО), функциональные элементы концепции (ФЭК) 12.1 Концепция массового обслуживания Концепция МО состоит в том, что работа системы описывается прохождением потоков подвижных объектов через функциональные элементы и взаимодействием этих объектов с элементами. Подвижные объекты - это например, сообщения, запросы, ответы, заявки, вызовы, требования, транзакции, пакеты данных, детали, партии деталей, транспортные единицы, клиенты и т.п. В концептуальной модели (КМ) реальные подвижные объекты моделируются подвижными объектами с обобщенным названием “заявки”. Состав КМ: - концептуальная схема (КС) движения заявок через функциональные элементы концепции (ФЭК), - описание взаимодействия заявок и ФЭК. КМ массового обслуживания - это одна из разновидностей математических моделей, а именно Q - схема (queueing system - модель с очередями), очереди являются главной особенностью моделей МО. Особенности подвижных элементов КМ – заявок: - виртуальность (заявки подразумеваются, но на КС изображаются только пути их движения). - заявки имеют, несут с собой при продвижении параметры (числовые величины, признаки и т.п.); этих параметров может быть несколько, и они могут изменяться при движении заявок.

12.2. Основные ФЭК массового обслуживания (эти ФЭК являются в КМ моделями реальных функциональных элементов) 12.2.1. Входы заявок в КМ и выходы из нее указываются на КС, причем для входов указываются вид распределения τ вх и средние значения, а также размерность времени: Пример 1: 5±1 с Заявки “а” КС разомкнутая Заявки “b” эксп., 2 с сеть ФЭК Заявки – потери Входы – начало путей продвижения заявок, выходы - окончания этих путей. Пример 2:

2 заявки при T = 0 5 заявок при T = 0

КС замкнутая сеть ФЭК

12.2.2. Обслуживающие устройства (ОУ):

Нет выходов

64 1 - канальное ОУ1,

m- канальное ОУ2, 7±5с

эксп., 1 мс

Указываются для случайных интервалов обслуживания τ об их вид распределения, одинаковый во всех каналах. ОУ - это модели реальных обрабатывающих или обслуживающих устройств, рабочих мест и т.п. Через ОУ возможны несколько непересекающихся путей прохождения. Количество каналов обслуживания не зависит от числа путей через ОУ. Порядок следования заявок при прохождения через 1 – канальное ОУ не изменяется по любому пути. Этот порядок при прохождении через m - канальное ОУ может изменяться. В таком ОУ одновременно находится не более, чем m заявок. 12.2.3. Накопители – модели мест ожидания заявок в очередях на продвижение. Очередность продвижения по умолчанию - FIFO (последовательность выхода заявок не изменяется). Может указываться LIFO или "по параметру заявки" (изменяется последовательность). Через накопители возможны несколько путей прохождения. Емкость накопителя или указывается, или по умолчанию не ограничена. При ограниченной емкости указывается путь для переполняющих заявок. накопитель емкости L

накопитель (Н)

12.2.4. Задержка на определенный интервал времени в продвижении заявок. Этот ФЭК может содержать неограниченное количество заявок. Последовательность их продвижения изменяется. Через ФЭК задержки проходит один путь в отличие от ОУ и накопителей. 10 ± 5 с Отличие накопителя от задержки: ожидание – следствие внешних причин, задержка не задана в накопителе. 12.2.5. Разветвления по различным указанным условиям, которые должны поясняться в описании КМ. Пример 1.

A a b

Указанное число А < 1 означает вероятность выбора заявкой направления a. По направлению b вероятность выхода 1 - А.

65 Пример 2. A

a

B

b

C

c Указанны вероятности А, B, C, причем A + B + C = 1, B + C = 1 - A < 1. Такое разветвление можно заменить двумя разветвлениями: A

a

B+C

D b E c

D + E = 1  Вероятности D ≠ B, E ≠ C. D и E надо найти, решая уравнения:  D B  E = C Пример 3. P1 = 0 a b Такое разветвление означает: заявка идет на выход а, если ее первый параметр Р1 = 0, или на выход b, если P1 ≠ 0. 12.2.6. Клапаны – ФЭК, которые могут запрещать продвижение заявок. Пример 1. закрыть путь заявок

К1

открыть Пример 2.

К2

V2=1

управляющие связи от других ФЭК

66 Указано условие прохождение заявок через клапан К2 по значению переменной V2, проверяемой на входе в клапан. Проверяться может и состояние определенного ФЭК. 12.2.7. Логический элемент управления клапанами: Пример 1.

путь заявок

управляющая связь (закрыть или открыть) ЛЭУ

Некоторые ФЭК могут быть управляющими элементами для клапанов, в которых проверяется текущее состояние этих ФЭК ("пуст", "не пуст", "полон", "не полон" и т.п.). Пример 2. Пример 3.

m – канальное ОУ1

12.2.8.

Табулировать:

Табулировать, 1

накопитель Н2

При прохождении заявки учесть в таблице 1 попадание случайной величины, указанной в описании КМ, в определенный интервал для получения гистогаммы.

12.2.9. Копировать: заявки – оригиналы Копировать, N

заявки – оригиналы заявки – копии

Указано, что каждая заявка - оригинал порождает N копий. Все заявки на выходах, порожденные одной входной заявкой, составляют одно семейство заявок. 12.2.10. Объединить (для заявок одного семейства): Объединить, N ФЭК дает на выходе одну заявку, когда накопятся N заявок (остальные N-1 заявок выводятся из модели (уничтожаются). Например, в моделях информационных коммуникаций заявки - кадры на входе этого ФЭК, объединяясь, дают на выходе заявку - сообщение. 12.2.11. Собрать (для заявок одного семейства): Собрать, N

67 ФЭК разрешает продвижение всех накопленных заявок, когда их количество становится равно N. 12.2.12. Синхронизировать (для заявок одного семейства): синхронизировать

синхронизировать Эти ФЭК обеспечивают выход заявки по одному пути, если может продвинутся заявка, имеющаяся и на другом пути. 12.2.13. Присвоить параметру заявки или переменной определенное значение: P3 = 1

X1 = 10

В заключении отметим следующее. Набор ФЭК определяется возможностями GPSS. ФЭК наряду с обозначениями дополнительно характеризуется описанием. Возможна вложенность и частичное наложение одних ФЭК с другими, что позволяет строить КМ для функционально сложных систем. Примером вложенностей являются временные задержки в обслуживающих устройствах. Приведем пример с частичным наложением ОУ1 и ОУ2 и с вложенностью общей задержки в тот и другой ФЭК. Показатели работы ОУ1 с двумя путями заявок будут отличатся от показателей ОУ2. 1 - кан. ОУ1 5 ±5 3±c3c

1 - кан. ОУ2

68

13. Основные допущения о работе КМ, имитационная GPSS программа 13.1. Основные допущения о работе КМ 13.1.1. Все возможные продвижения заявок в КМ происходят в точечные моменты времени Т и рассматриваются как события. 13.1.2. Продвижение заявки происходит через все возможные ФЭК, не запрещающие этого в момент времени Т или до выхода из модели, или до временной задержки на τ з (в частности τ з = τ об в обслуживающем устройстве, тогда T + τ з - это момент времени будущего события – выхода заявки из ОУ), или до запрета движения, когда закрыт клапан или заполнены все места следующего ФЭК (накопителя ограниченной емкости или ОУ). 13.1.3. Заявка, продвигаясь, может отменять или устанавливать указанные запреты для других заявок. 13.1.4. КМ работает по принципу “ δz ”, но алгоритм моделирования определяется не графом состояний, а заданной в КМ последовательностью продвижения заявок.

13.2. Сущность работы имитационной GPSS – программы Движение заявок в концептуальной модели имитируется продвижением подвижных объектов транзактов (ТА) в программной GPSS – модели через функциональные элементы языка (ФЭЯ). Суть программной имитации работы КМ рассмотрим на трех логических уровнях. Верхний логический уровень: каждый ФЭК имитируется соответствующим функциональным элементом языка (ФЭЯ); количество типовых ФЭЯ меньше количества ФЭК(один ФЭЯ может имитировать разные ФЭК, то есть понимание GPSS – программы опирается на КМ); виртуальный подвижный объект – заявка имитируется виртуальным же подвижным объектом программы под названием “транзакт” (ТА); ТА – это модель заявки; поток ТА – модель потока заявок; прохождение заявок через ФЭК имитируется прохождением ТА через ФЭЯ; следовательно, структура КМ имитируется структурой модельной части GPSS – программы (другая часть программы управляет работой первой и экспериментами с ней). Средний логический уровень: работа GPSS – модели состоит в том, что каждый ФЭЯ реализуется соответствующими операторами GPSS (по одному или более на один ФЭЯ), которые взаимодействуют непосредственно или с помощью других операторов с продвигающимися черезпоследовательности опреаторов транзактами. Операторы могут быть трех типов: 1) блочные операторы (блоки); только через них продвигаются ТА; через блоки ТА могут взаимодействовать с неблочными операторами; последовательная запись блоков в программе означает переходы ТА из одного блока в другой, что определяет работу ФЭЯ; 2) операторы описания (карты описания); к этим операторам обращаются блоки; 3) операторы управления моделированием (карты управления). Через операторы – карты ТА не проходят. Блоки одного ФЭЯ означают использование подпрограммы этого ФЭЯ для обработки проходящего потока ТА (накопление и формирование результатов – статистик для этого ФЭЯ, статистики входят в стандартный вывод результатов моделирования). Нижний уровень представлений о работе имитационной программы: каждый ТА – это определенная область оперативной памяти с записями служебных и пользовательских

69 параметров. GPSS обеспечивает для каждого ТА в оперативной памяти последовательное взаимодействие с блочными операторами в порядке их написания в программе и в порядке перехода по меткам, то есть каждый ТА продвигается по блокам, пока это возможно в соответствии с алгоритмом управления моделированием языка GPSS. Алгоритмом имитационной GPSS – модели является КМ системы в концепции МО. Схемой алгоритма модельной части GPSS – программы является КС системы.

13.3. Формат операторов и структура GPSS - программы GPSS/H работает в ОС DOS. В свободном формате в отдельной строке программы (можно с пропуском строк) операторы записываются в следующем виде:

с 1 или 2-й символьной позиции по 8-ю

Пробел один или более

название операции

расширение операции (если надо)

или пусто, или числовое имя (метка ), или символьное имя (метка), начиная с буквы, не более 8 буквенно – цифровых символов

операнды через запятую без пробелов

пусто или комментарий (* в начале строки означает продолжение предыдущей строки- перенос)

С помощью пробелов можно красиво, удобно для чтения оформить программу. Структура программы. Первым может быть не обязательный оператор REALLOCATE - карта управления перераспределением памяти, если это нужно (вид операторов и другие подробности для рассматриваемых операторов описаны в справочнике Help). Далее может следовать карта SIMULATE, управляющая запуском - началом прогона программы; без этой карты в листинге стандартного вывода дается транслированная программа с указанием мест и номеров синтаксических ошибок (см. Help). Следующей может быть карта RMULT, управляющая начальным значением ГСЧ; без этой карты устанавливается 100000. Далее записываются карты описания, необходимые для работы ФЭЯ, то есть блоков программы. Блочная часть программы определяет входы ТА в программу и их последовательное прохождение по блокам в строгом соответствии с КС; каждому входному потоку ТА соответствует свой сегмент программы, но не исключается и переход ТА в чужой сегмент (по метке). В конце программы записываются карты управления окончанием моделирования (обязательна карта START - хотя бы одна), повторением прогонов и изменениями в программе при проведении экспериментов; при этом используются и блоки. Последней в программе может быть не обязательная карта END - конец программы.

70

14. Основные ФЭЯ для ФЭК, их программные модели 14.1. Входы транзактов в программную модель и выходы из нее, управление длительностью прогона Тмод программы 14.1.1. ФЭК «Вход заявок в КМ, ФЭЯ "Вход ТА в программу" – блок GENERATE(генерировать) Подробно блок описан в справочнике Help. Общее правило для всех операторов GPSS: указываются только задаваемые операнды, а пропущенные до них отмечаются запятыми(пробелы в поле операндов недопустимы).

Пример 1. 10 заявок при Т = 0

КС

Концептуальная схема системы

GENERATE

,,,10

10 ТА к следующему блоку при Т = 0

Пример 2.

A ± B сек. поток заявок

GENERATE A,B КС поток ТА с равномерным распределением интервалов τ вх = A ± B к следующему блоку

Пример 3. А = 0,5 с., B = 0,1 с. ⇒

GENERATE 0.5,0.1

При изменении модельной единицы времени (м.е.в.) на 0,01 с: GENERATE 50,10 Программирование стандартных распределений нормального). Пример 4. GENERATE RVEXPO (1,.5) Поток ТА

ГСЧ №1

GENERATE RVNORM(7,2,1) Поток ТА ГСЧ №7

Мат. ожидание τ вх = 2

τ вх

(экспоненциального

τ вх = 0,5 м.е.в.

и

71 Пример 5. σ=1 среднее квадратичное отклонение 14.1.2. ФЭК «Выход заявок из КМ», ФЭЯ "Выход ТА из программы" - блок TERMINATE (завершить) КС

поток ТА

TERMINATE A Если операнд А отсутствует, этот блок не влияет на завершение прогона программы. Если операнд А ≠ 0 указан, то он управляет окончанием прогона одним из способов: 1) каждый ТА “вычитает” А из стандартного числового атрибута (СЧА) - текущего значения счетчика завершений ( TG1 − A ), до обнуления; начальное значение В счетчика при Т = 0 задается картой START B; часто A = 1 , B ≥ 10 4 (для моделирования стационарного режима). Возможно несколько TERMINATE и TERMINATE A. 2) задание Tмод в сегменте таймера в “немодельной” части GPSS - программы; тогда все TERMINATE - без операнда, кроме этого сегмента: GENERATE C TERMINATE A START B Часто задается С = Тмод, А = 1, В = 1 для окончания прогона при Т = Тмод. Возможно: T С = мод , А = 1, В = 1000 и т.п. 1000

14.2. ФЭК “Обслуживающее устройство”, ФЭЯ "FACILITY" (прибор, устройство), "STORAGE" (память) 14.2.1. ФЭК "Одноканальное обслуживающее устройство", ФЭЯ "FACILITY"

Такой ФЭЯ - это три обязательных блока: SEIZE, ADVANCE, RELEASE (возможно их повторение в программе). Пример 1: 1

1 – канальное ОУ1, 2 С ± D сек.

Вложенная задержка на τоб с равномерным распределением

3

72 Точками отмечены действия, программируемые блоками 1, 2, 3. Эти номера здесь указаны и в программной модели (в КС обычно такие номера не указываются, а в программе после трансляции проставляются автоматически как порядковае номера операторов-блоков). поток ТА

1 2 3

имя, числовое или символьное

SEIZE ОУ1 ADVANCE С,D RELEASE ОУ1

1 - блок "занять устройство"

2 - блок задержки; если (без D) С = RVEXPO, то этим задается экспоненциальное (см. раздел 4.1.1) распределение τоб; если С - число (без D), то задержка постоянна. 3 - блок "освободить устройство"ТА. Метка может быть В этот ФЭЯ не может зайти ТА, пока не вышел предыдущий у SEIZE. По метке могут в ФЭЯ входить ТА из других потоков. Разрешается выход ТА, только вошедшего через SEIZE. Когда ФЭЯ занят обслуживаемым ТА, блок SEIZE является запрещающим для следующих ТА, которые образуют очередь в предыдущем блоке. Пример 2: 1 – канальное ОУ2, 1 12

2

5±3с

3

2±1с

11 10

Два потока с двумя различными вложенными задержками (но не два канала обслуживания)

поток ТА

1 МЕ1 SEIZE 2 2 ADVANCE 5,3 3 RELEASE 2

часть программы 2 – ой вход в ОУ2 10 МЕ2 SEIZE 2 11 ADVANCE 2,1 12 RELEASE 2

блоки с одним операндом - числовым или символьным именем устройства

73 Ме1 - 3-ий вход в ОУ2; МЕ2 - 4-й вход. В стандартном выводе даются сведения с обозначением FACILITY. Результаты приводятся для суммарного потока, если не один входной поток. Расшифровка стандартного вывода дана в справочнике Help. 14.2.2. ФЭК "m – канальное ОУ", ФЭЯ "STORAGE" Этот ФЭЯ называется "моделью многоканального ОУ", даже если m = 1.

m { – канальное ОУ3,

(A) 1

число

С±D

2

(В) 3

поток заявок

A – число занимаемых одной заявкой мест, B – число освобождаемых мест, А = 1 и (или) В = 1 не указывается . ФЭЯ STORAGE (память) – это пара блоков ENTER, LEAVE и карта описания емкости памяти – числа каналов обслуживания. Карта записывается обычно перед блочной частью программы, например: 3

STORAGE m имя памяти

числовое (или символьное) имя памяти

1 2 3

ENTER 3,A (войти) ADVANCE C,D задержка, вложенная в ОУ LEAVE 3,B (выйти)

Если все m мест заняты, то блок ENTER становиться запрещающим и возникает очередь в предыдущем блоке. Возможны параллельные потоки и повтор блоков ФЭЯ, как в пункте 14.2.1 (без повтора карты). Возможно занятие мест ТА одного потока, а освобождение транзактом другого потока; вход в любой блок ФЭЯ может быть по метке; при m = 1 одноканальное устройство ОУ3, программируемое памятью, может работать иначе, чем ОУ1 (выше): можно занять ФЭЯ одним ТА и освободить другим, не зашедшим через блок ENTER. При этом стандартный вывод с обозначением STORAGE отличается от вывода FACILITY.

14.3. ФЭК "Накопитель" перед запрещающими ФЭК, ФЭЯ: “QUEUE” (очередь), “STORAGE” (память), “TRANSFER BOTH” ("оба" - направить при запрете по метке) Запрещать вход заявок могут такие ФЭК: обслуживающие устройства, накопители ограниченной емкости, клапаны, разветвления при запрете всех выходов, "синхронизировать". Блоки соответствующих ФЭЯ могут запрещать вход ТА.

74 14.3.1. ФЭК "Накопитель неограниченной емкости", ФЭЯ "QUEUE"

накопитель Н1, емкость ∞

поток заявок

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

Если нужны показатели очереди, то используется регистратор – ФЭЯ “QUEUE” – это пара блоков QUEUE и DEPART (поставить в очередь, удалить из очереди). Пример:

1

2

H1, 3 емкость ∞

m – канальное ОУ1, 4 A±B

5

Обычно на КС указывают соединение Н1 и ОУ1 без частичного наложения. Номера точек - это номера блоков ФЭЯ в программе, соответствующие представлению "в уме" выйти из Н1 можно, если разрешен вход в ОУ1:

1

H1, 2 емкость ∞

3

m – канальное ОУ1, 4 С±D

5

Такое наложение в КС обычно не изображается. 1

STORAGE m

1 2 3 4 5

QUEUE 1,A ENTER 1 DEPART 1,B ADVANCE C,D LEAVE 1

карта описания

Для ФЭЯ разного типа можно использовать одинаковые имена (здесь числовое имя 1).

Здесь А, В - количества занимаемых и освобождаемых мест(по умолчанию - без А и В - одно место) в очереди с именем 1 (возможно символьное имя), причем в данном примере А = В (для более сложных КС может быть А ≠ В). В стандартном выводе в разделе с названием “QUEUE” есть среднее время прохождения для ТА с ожиданием (без учета нулевых входов) – обозначено как TIME $STORAGE , и есть тоже самое для всего потока ТА (без $ в обозначении UNIT результата). ФЭЯ регистратор "очередь" используется и для определения среднего времени прохождения потока заявок через ряд вложенных ФЭК, вложенных для этого в накопитель.

75

накопитель Н2 1 емкости ∞

ФЭК 1

(A)

1

ФЭК3

ФЭК2

2

ФЭК4

(B)

QUEUE 2,A

вложенная часть программы

2 DEPART 2,B В данном случае средние длительности прохождения одинаковы для ожидавших ТА и для полного потока ТА, если всегда tож≠0. 14.3.2. ФЭК "Накопитель ограниченной емкости", ФЭЯ "STORAGE" (память) и TRANSFER BOTH (направить при запрете по метке) Пример. ФЭК разветвления по запрету 12

13

накопитель Н3 емкости L

15

m – канальное ОУ2, 14 16 С±D

17

число

a) потери заявок  б) в другие ФЭК если Н3 полон Переполнение Н3 и образование перед ним очереди не имеет смысла. Поэтому накопитель ограниченной емкости программируется всегда вместе с ФЭЯ - блоком TRANSFER BOTH. 2 3

STORAGE m  карта задания емкости памятей STORAGE L 

76 12 13 ME1 14 15 16 17

TRANSFER BOTH,ME1,ME2 ENTER 3 ENTER 2 LEAVE 3 ADVANCE C,D LEAVE 2

Если блок с ME1 следует сразу за TRANSFER, то ME1 в блоках 12 и 13 можно опустить, сохраняя запятые (без пробела между ними)

Любые символьные имена, кроме имен стандартных числовых атрибутов (СЧА) Блок 12 - вид условного перехода: если нельзя зайти в следующий блок (или по метке ME1), то ТА идет по МЕ2 если имеется запрет по МЕ1 и МЕ2, то ТА остается в предыдущем блоке (попытки продвижения ТА будут повторятся). Программирование перехода ТА по метке МЕ2 может направить его: а) в счетчик потерь - отдельный блок j, для которого в стандартном выводе указывается количество ТА (это количество можно использовать в программе как СЧА Nj или N$МЕ2) j МЕ2 TERMINATE; этот блок записывается как самостоятельный сегмент - строка в программе. б) в блок другого ФЭЯ, например, многоканального ОУ20

МЕ2 ENTER ОУ20 в) в блок прекращения прогона программы при переполнении Н3 обнуление счетчика завершений

МЕ2 TERMINATE TG1

14.4. ФЭК “Направить заявки в точку соединения с другим потоком” (вперед или назад по КС); ФЭЯ “TRANSFER ,ME” Такой ФЭЯ дает безусловный переход ТА по метке МЕ. Пример.

1-й поток

Н1

ОУ2

ОУ3 2-й поток

Н2

QUEUE 1 SEIZE 2 DEPART 1 ADVANCE 3,2 RELEASE 2 TRANSFER ,ME

ME

RELEASE 3 QUEUE 2

77

Для второго потока здесь запрограммированы только выход из ОУ3 и вход в Н2. После блока TRANSFER ,А следующим может быть блок GENERATE… или другой блок с обязательной меткой В.

14.5. ФЭК "Разветвление путей заявок по условию", ФЭЯ "TRANSFER" (направить), "TEST" (проверить), "GATE" (впустить) 14.5.1. ФЭК "Разветвление по заданной вероятности r", ФЭЯ "TRANSFER r,ME1,ME2". r<1

а

(1-r)

б

r - вероятность движения заявки по пути а, 1 - r - вероятность для пути б (можно не указывать). Вход ФЭЯ - блока

TRANSFER .05,ME1,ME2 можно опустить, если это метка следующего блока.

Точка в записи - признак модификации блока; дан пример для r = 0,05.

Выходы ФЭЯ - блока с вероятностями r по метке МЕ2 и 1 - r по МЕ1.

14.5.2. ФЭК "Разветвление по условию для величин или выражений", ФЭЯ "TEST" (сравнение СЧА, чисел или выражений) Пример 1. заданное условие выполняется

иначе

Вход ФЭЯ - блока TEST

A,B,ME

если условие выполняется Выходы ФЭЯ - блока

А,В - числа, СЧА, выражения как арифметические, так и логические. Модификатор блока (проверяемое условие): Е (равно), NE (не равно), G (больше), GE (больше или равно), L (меньше), LE (меньше или равно) иначе

78

Если по тому и (или) другому выходу действует запрет, то ТА остается в блоке TEST в соответствующей очереди после разветвления, и для этого ТА проверка условия не повторяется, так как СЧА может быть параметром ТА. В блоке TEST может быть две очереди. Пример 2 каждая n-я заявка Ответвление каждой n-ой заявки (в том числе каждой четной или нечетной) программируется с использованием целочисленной арифметической переменной с картой описания, например: 1 VARIABLE 1 N$ME 23 @ n или Nj

Здесь деление по модулю на n дает результат V1 - остаток от деления.

Предыдущий блок; МЕ

для разделения четных и нечетных ТА надо С = 0 или С = 1 при n = 2; для любого n задание С < n определяет, начиная с какого ТА, начать ответвление каждого n-ого ТА.

вход в ФЭЯ - блок TEST E V1,C,ME1

кроме каждого n-ого ТА

каждый n-ый ТА

14.5.3. ФЭК "Разветвление по контролю состояния проверяемых ФЭК", ФЭЯ "GATE" (впустить) для контроля состояния проверяемых ФЭЯ если существует данное состояние проверяемого ФЭК иначе проверяемое состояние заданного ФЭЯ - стандартный логический атрибут проверяемое состояние имеется

GATE

A, ME

Выход ТА к следующему блоку

A – числовое или символьное имя проверяемого ФЭЯ иначе по метке

79

Виды проверяемого состояния заданного ФЭЯ U

– одноканальное ОУ занято?

NU

– одноканальное ОУ незанято?

SF

– память полна?

SNF SE SNE LR

:

– память неполна? – память пуста? – память не пуста? – логический ключ сброшен?

– логический ключ установлен? LS Логический ключ - это виртуальный ФЭЯ с двумя состояниями R и S, которые изменяются блоком LOGIC; этот блок представляет собой ФЭЯ "Логический переключатель", которым программируется ФЭК "Логический блок управления клапанами" (ЛБУ). Логические ключи при запуске программы сброшены.

LOGIC

A имя логического ключа (числовое или символьное)

- действия блока (его модификации): R – сбросить ключ А, S – установить ключ А, I – инвертировать ключ А. Если по обоим выходам блока GATE имеется запрет продвижения, то ТА остаётся в предыдущем блоке (попытки продвижения ТА будут повторятся).

14.6. ФЭК "Клапан" (может быть вложен в ФЭК "Накопитель"), ФЭЯ TEST (проверить), "GATE" (впустить), "QUEUE" (очередь) 14.6.1. Использование блока TEST Н1, емк. ∞ Пример с регистрируемой очередью в накопителе неограниченной емкости

K1 если выполняется заданное условие

80 Блок TEST здесь работает в режиме клапана; А, B - это СЧА, или числа, или арифметические, или логические выражения. Модификации блока см. в разделе 14.5.2.

QUEUE 1 А,В TEST DEPART 1

14.6.2. Использование блока GATE управляющая связь от проверяемых ФЭК Н2

QUEUE 2 GATE А DEPART 2

K2 если имеется проверяемое состояние заданного ФЭК

Здесь блок GATE работает в режиме клапана; А - имя проверяемого ФЭЯ; модификации блока см. в разделе 14.5.3.

14.7. ФЭК “Табулировать”, ФЭЯ “TABULATE” (занести в таблицу) табулировать

TABULATE А

А - числовое или символьное имя таблицы.

Для таблицы нужна карта описания, которая позволяет получить гистограмму – количество и проценты попаданий случайной величины (СЧА) в заданные интервалы. шаг нижний интервал

ВГНИ

СЧА интервалы гистограммы (их число 15 ÷ 20)

верхний интервал

Карта описания: A

TABLE СЧА,ВГНИ,шаг,КИ

СЧА определяется целями моделирования; ВГНИ - верхняя граница нижнего интервала; шаг гистограммы подбирается так, чтобы существенная часть гистограммы занимала 15 - 20 шагов;

81 КИ - количество всех интервалов, включая нижний и верхний (на два более числа шагов). Частный случай: таблица А для времени ожидания или времени прохождения очереди В (при этом изменяется карта описания и блок TABULATE не нужен). Карта описания: A

QTABLE В,ВГНИ,ШАГ,КИ

Имя таблицы

имя очереди

QUEUE B

В блочной части программы

DEPART B

В стандартном выводе таблица обозначена TABLE A.

14.8. ФЭК “Копировать”, ФЭЯ “SPLIT” (расщепить)

заявки – оригиналы заявкиоригиналы

копировать, N

SPLIT N,МЕ

ТА - оригиналы (родители)

ТА - копии (потомки)

заявки - копии

14.9. ФЭЯ "Получение потока ТА одного семейства для программирования некоторых ФЭК" ME

GENERATE ,,,1 ADVANCE A,B SPLIT 1,ME1 TRANSFER ,ME

В программу входит один ТА при Т = 0, от которого образуется поток ТА копий

14.9.1. ФЭК "Объединить", ФЭЯ “ASSEMBLE” (соединить ТА одного семейства) и "QUEUE" (очередь) поток ТА одного семейства

82

ФЭК "Объединить" обычно вложен в ФЭК "Накопитель", здесь H1; он указывается на КС как место простоя заявок. Н1 программируется только тогда, когда нужна регистрация заявок. заявки одного Н1, емк. ∞ заявки – соединения или нескольких Объединить, N семейств

QUEUE 1 ASSEMBLE N DEPART 1

Из N накопленных ТА одного семейства один идет дальше, остальные удаляются из модели. Заявки - соединения могут образовать поток ТА различных семейств. Этот поток на выходе будет разреженным по отношению к входному потоку. 14.9.2. ФЭК “Собирать”, ФЭЯ “GATHER”(собирать ТА одного семейства) и "QUEUE" (очередь)

Н2, емк. ∞

N заявок могут выйти одновременно

QUEUE 2 GATHER N DEPART 2

Собирать, N

Н2 программируется только тогда, когда нужна регистрация простоя ТА. 14.9.3. ФЭК “Синхронизировать”, ФЭЯ “MATCH” (синхронизировать ТА одного семейства)

Н3 синхронизировать

Н4 синхронизировать

МЕ1

QUEUE 3 MATCH МЕ2 DEPART 3

МЕ2

QUEUE 4 MATCH МЕ1 DEPART 4

Н3 и Н4 программируются только тогда, когда нужна регистрация простоя ТА.

83

14.10. ФЭК "Присвоить значение параметру заявки", ФЭЯ "PRIORITY" (присвоить приоритет) и "ASSIGN" (присвоить) По умолчанию при T = 0 все параметры нулевые (их обнуление излишне). P1 = V2

Карта описания: 2

VARIABLE …

PRIORITY 10

Присвоить приоритет 10

ASSIGN 1,V2

В GPSS можно использовать 128 уровней приоритета.

14.11. ФЭК "Цикл" (разветвление по параметру заявки), ФЭЯ “ASSIGN” (присвоить) и “LOOP” (петля). Pj = n

ФЭК1

ФЭК2

пройти n раз

ME

ASSIGN j,n ENTER 1

RELEASE 2 LOOP j,ME

84

15. Операторы управления выводом результатов и прогонами GPSS - программы, алгоритм управления продвижением ТА по блокам 15.1. Сохранение результатов в стандартном выводе Используются СЧА с обозначением Xj (j - номер) - сохраняемые величины, для которых, если они не равны нулю, приводятся их значения в стандартном выводе. Например, надо сохранить значение вещественной переменной V2 с картой описания 2 FVARIABLE …. . Для этого в сегменте таймера выполняется присваивание X1 = V2 блоком SAVEVALUE (сохранить величину) при прохождении через него транзакта, который вызывает завершение прогона при Т = Тмод . Пример. Сегмент таймера: GENERATE Тмод SAVEVALUE 1,V2,XL TERMINATE 1 START 1 END

номер сохраняемой величины X1 (ячейки) - здесь X1 сохраняется в формате чисел с плавающей точкой (возможно ХН - полусловная величина, ХВ байтовая величина, XF - в формате "слова", который действует и по умолчанию, когда нет третьего операнда)

В одном сегменте возможно несколько блоков SAVEVALUE для регистрации нескольких СЧА. Если в качестве СЧА используется арифметическое выражение, то все действия проводятся с целыми частями чисел, поэтому надо преобразовать выражение для получения верного результата или описать выражение картой j FVARIABLE … , чтобы сохранzть Vj.

15.2. Использование блоков PRINT (напечатать) Подробное описание - в книге "Моделирование на GPSS" Т. Шрайбера.

PRINT A,B,C

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

85

15.3. Отмена стандартного вывода, вывод промежуточных отчётов картой управления START START 100,,25

START 100, NP начальное значение счетчика завершений отмена вывода отчета

вывод 4 отчётов через каждые 25 завершений

15.4. Повторение прогонов модели с изменениями операндов блоков и карт с помощью карты управления CLEAR управление окончанием первого прогона изменения и управление окончанием второго прогона

эти метки даются в исходной программе блокам и картам для внесения изменений

START 10 ME1 GENERATE 1000 ME2 RMULT 200000 CLEAR START 100 и т.д.

без такого управления ГСЧ не возвращается в начальное состояние обнулить все статистики начать прогон снова Карта END - только в конце всей программы

15.5. Алгоритм управления моделированием (АУМ) - продвижением ТА по блокам GPSS – программы Реализуется “принцип δz ”(изменения состояния) в точечные моменты времени. Каждое изменение – это событие продвижения всех ТА программы, насколько это возможно, во все следующие блоки. Времена будущих событий Ts определяются только блоками GENERATE и ADVANCE: Ts = T + τs , где τs - это или τвхода или τобслуживания . В АУМ используется упорядоченный по Ts список всех ТА, для которых известно будущее время возможного продвижения – это список будущих событий (СБС), в его начале стоит ТА с min Ts , и этот ТА будет продвигаться первым после имитации текущего события в момент времени Т. Текущее событие имитируется с помощью списка текущих событий (СТС); в нем находятся все ТА, вошедшие в программу, кроме находящихся в СБС. СТС упорядочен по правилу FIFO с приоритетом: в начале СТС стоят ТА с высшим приоритетом, а в группе ТА одного приоритета ближе к началу списка стоит тот ТА, который раньше занесён в список. АУМ пытается продвигать ТА по блокам программы по одному, начиная с первого в СТС. Положение ТА в СТС может изменяться. Для продвижения ТА используется его основные записи: z1 – номер ТА в распределения оперативной памяти; z 2 – номер блока, в котором находится ТА до начала движения; z3 – номер следующего блока, в который должен пройти ТА по программе (в том числе по метке); z 4 – время будущего продвижения ТА (учитывается только в СБС); z5 – уровень приоритета ТА (при входе в программу – 0) – учитывается только в СТС.

86 Когда продвижение ТА состоялось, записи z2 и z3изменяются обязательно, а z 4 и z5 могут измениться или нет. Ниже дана схема алгоритма продвижения ТА по блокам программы. начало 1

6

При наличии карты SIMULATE ввод первых ТА через все GENERATE с заполнением z 4 ( z 2 – пусто, z1 – номер блока GENERATE), занести эти ТА в СБС в порядке увеличения z4

Продвинуть начальный ТА через все возможные блоки до 1) запрета*) движения или 2) до ADVANCE**) или 3) до TERMINATE(с удалением из СТС). Если начальный ТА нельзя продвинуть, то продвигается следующий ТА

2 Взять начальный ТА в СБС и присвоить T = z 4 (модельное время)

7 3

Перенести начальный ТА из СБС в СТС на последнее место в группе его приоритета

нет

да

У следующего ТА в СБС z 4 = T ? нет

8 нет

Есть ли в СТС следующий ТА?

4 да

да

Нужен ли повтор просмотра СТС? ***)

да

5

TG1>0?

9

Продвинуть ТА через все возможные блоки до 1), 2), 3) – см. выше 6 6

нет конец TG1 - текущее значение счетчика завершений. *) После GENERATE не должен стоять запрещающий блок – между ними можно написать ADVANCE без операндов (следующий ТА входит в GENERATE из стека и заносится в СБС с z 4 – будущим временем только после выхода ТА предшественника из этого GENERATE. **) Задержка времени продвижения означает определение будущего времени движения Ts = T + τs и ТА переходит из СТС в СБС. ***) Повторный просмотр осуществляется автоматически после прохождения ТА блоков: SEIZE, RELEASE, ENTER, LEAVE, LOGIC, PRIORITY или этот повтор может задать программист блоком BUFFER (без операндов); при повторном

87 просмотре может стать другим начальный ТА в СТС, если у прежнего ТА изменится приоритет, или прежний перейдет в СБС и т.п.