А С В x

Рис. 3. Общий случай треугольного распределения вероятностей

Применимость такого распределе­ния рассмотрим на примере, связанном с динамическими характери­стиками системы управления базами данных (СУБД) в информационной системе.

Пример. Предположим, что база данных находится на ком­пьютере, не входящем в состав какой-либо вычислительной сети. Поэтому пользователь, работающий с этой базой, имеет во время работы монопольный доступ к ней. Известны структуры и частоты запросов пользователей к этой базе данных. Рассмотрим три случая физической организации базы данных (рис. 4).

Первый случай. Допустим, что администратор базы данных (сис­темный программист) осуществил физическую организацию дан­ных, которая обладает следующими свойствами:

• наиболее вероятное время ответа на запрос близко к 0 с;

• минимальное вероятное время ответа не менее 0 с;

• максимальное вероятное время ответа не превышает 15 с;

• распределение вероятностей представлено линией 1 на рис. 4.

Этот системный программист обеспечил минимальное время для наиболее вероятных запросов за счет увеличения времени для менеевероятных. Среднее время получения ответа в этом случае t = 5 с.

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

• наиболее вероятное время ответа на запрос равно 5 с;

• минимальное вероятное время ответа не менее 0 с;

• максимальное вероятное время ответа не превышает 10 с;

• распределение вероятностей показано линией 2 на рис. 4.

Рис. 3. График плотности вероятностей для треугольного распределения:

1 - максимум слева; 2 - максимум в центре; 3 - максимум справа

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

Третий случай. Администратор базы данных решил еще более уменьшить время ответа на менее вероятные запросы. Для этого он опять переделал физическую организацию данных и получил сле­дующие свойства:

• наиболее вероятное время ответа на запрос равно 7,5 с;

• минимальное вероятное время ответа не менее 0 с;

• максимальное вероятное время ответа не превышает 7,5;

• распределение вероятностей изображено линией 3 на рис. 4.

Этот системный программист обеспечил дальнейшее снижение времени ответа для менее вероятных запросов за счет увеличения времени ответа для более вероятных. Среднее время получения от­вета и в этом случае не изменилось: t=5 с.

Возникает естественный вопрос: «Какая физическая организация лучше?». Если отбросить факторы, определяющие большую или меньшую важность запросов, и вспомнить, что база данных не имеет множественного доступа из вычислительной сети, то можно утвер­ждать, что все три способа организации данных одинаковы, так как пользователи этой базы имеют одно и то же среднее время ответа.

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

,

где t_q - искомая средняя задержка в очереди;

t_s - среднее время обслуживания;

r - загрузка обслуживающего узла;

с_s - коэффициент вариации времени обслуживания.

Если известно среднеквадратичное отклонение времени обслу­живания s_s, то с_s=s_s/t_s . В трех рассмотренных случаях t_s=5 с.

Загрузка не изменяется, так как поток запросов к базе данных тот же самый. Однако разброс значений в первом случае примерно в 3 раза больше, чем в третьем. Соответственно может быть больше при­близительно в 9 раз (т.е. на порядок!), а это часть множителя в чис­лителе формулы.

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

5. Инструментальные средства моделирования

Универсальным инструментальным средством создания моделей являются языки программирования общего пользования (Pascal, C/C++ и др.). На основе этих языков в настоящее время бурное развитие получили средства визуального проектирования программ (Delphi, Visual C++), облегчающие выполнение некоторых трудоемких операций, например, создание интерфейса программы. Наряду с этим существует множество специализированных средств моделирования, позволяющих быстрее и с меньшими затратами (по сравнению с универсальными языками программирования) создавать и исследовать модели. В развитии специализированных средств можно выделить два направления:

1. Средства моделирования для анализа достаточно широкого класса систем. К ним относятся языки имитационного моделирования (GPSS, SIMSCRIPT и др.), пакеты прикладных программ, использующих для моделирования аналитические методы, такие как MathCad, MathLab, SAS и др. Основным недостатком этих средств является то, что их применение требует от исследователя специальной подготовки.

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

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

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

1. Формулирование проблемы: описание исследуемой проблемы, установление границ и ограничений моделируемой системы, определение целей исследования.

2. Разработка модели: переход от реальной системы к некоторой логической схеме (абстрагирование).

3. Подготовка данных: отбор данных, необходимых для построения модели, и представление их в соответствующей форме.

4. Трансляция модели: описание модели на языке имитационного моделирования.

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

6. Планирование: определение условий проведения машинного эксперимента с имитационной моделью.

7. Экспериментирование: многократный прогон имитационной модели на компьютере для получения требуемой информации.

8. Анализ результатов: изучение результатов имитационного эксперимента для подготовки выводов и рекомендаций по решению проблемы.

9. Реализация и документирование: реализация рекомендаций, полученных на основе имитации, и составление документации по модели и ее использованию.

Таким образом, языки имитационного моделирования позволяют за сравнительно короткий срок составлять программные модели довольно сложных систем. К сожалению, такие модели обладают низкой способностью отвечать на вопросы типа "а что, если...", поскольку это именно те вопросы, которые наиболее полезны, так как они способствуют более глубокому пониманию проблемы и поиску лучших способов оценки возможных действий. Для ответа на подобные вопросы часто приходится непосредственно изменять программный код модели, что повышает затраты времени на анализ системы. При использовании языков имитационного моделирования возникает также другая проблема: затраты на изучение и освоение языка, тем более, что эти языки оперируют абстрактными понятиями, в то время как экспериментатор часто является специалистом в той области, которой принадлежит моделируемая система, и применяет специфическую терминологию, что может значительно осложнить освоение языка исследователем.

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

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

Принципы построения моделирующих алгоритмов

Архитектуру языка имитационного моделирования можно представить следующим образом:

1. Объекты моделирования описываются с помощью некоторых атрибутов языка;

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

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

4. Условия влияют на события, имеющие место внутри объекта моделирования и при взаимодействии с внешней средой;

5. События изменяют состояния модели системы в пространстве и времени.

Концепция и возможности объектно-ориентированной моделирующей системы

Основные функции моделирующей системы:

1) предоставление средств для формализованнго описания дискретных компонентов, дисциплин выполнения различных работ, для задания структуры графа и привязки объектов модели к координатной сетке общего информационного поля;

2) осуществление координации событий, определение путей прохождения транзактов, изменение состояний узлов и передачу управления моделям непрерывных компонентов.

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

1. Граф модели. Все процессы независимо от количества уровней структурного анализа, объединяются в виде направленного графа (многослойный иерархический).

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

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

Транзакт может выполнять следующие действия:

· Порождать группы (семейства) других транзактов;

· Поглощать другие транзакты конкретного семейства;

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

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

Основные параметры транзактов:

· Уникальный идентификатор транзакта;

· Идентификатор (номер) семейства, к которому принадлежит транзакт;

· Наборы различных ресурсов, которые транзакт может захватывать и использовать какое-то время;

· Время жизни транзакта;

· Приоритет – неотрицательное число;

· Параметры обслуживания в каком-либо обслуживающем устройстве (включая вероятностные характеристики).

Примеры транзактов:

- телекоммуникационный пакет;

- покупатель;

- заявка на товар;

- автомобиль;

- обрабатываемая деталь;

- работник и т.д.

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

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

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

6. Пространство – географическое, декартова плоскость. Узлы, транзакты и ресурсы могут быть привязаны к точкам пространства и мигрировать в нем.

Внутренняя реализация модели использует объектно-ориентированный способ представления процессов. Транзакты, узлы, события и ресурсы – основные объекты имитационной модели.

Управление модельным временем

Одной из наиболее важных задач при создании модели является реализация двух функций: 1) корректировка временной координаты состояния системы ("продвижение" времени, организация "часов"); 2) обеспечение согласованности различных блоков и событий в системе (синхронизация во времени, координация с другими блоками).

Таким образом, функционирование модели должно проте­кать в искусственном (не в реальном и не в машинном) времени, обеспечивая появление событий в требуемом логикой работы ис­следуемой системы порядке и с надлежащими временными интерва­лами между ними. При этом надо учитывать, что элементы реаль­ной системы функционируют одновременно (параллельно), а ком­поненты программной модели действуют последовательно, так как реализуются с помощью ЭВМ последовательного действия. По­скольку в различных частях объекта моделирования события могут возникать одновременно, то для сохранения адекватности причин­но-следственных временных связей необходимо в языке имитационного моделирования создать «механизм» задания времени для синхронизации действий элемен­тов модели системы.

Принципы построения моделирующих алгоритмов

Состояние системы характеризуется вектором состояний Z(t). Организуем счетчик системного времени, который в начальный момент показывает время t₀. Прибавим интервал времени Dt, тогда счетчик будет показывать t₁= t₀ +Dt. Вычислим значения Z(t₀ +Dt), затем перейдем к моменту времени t₂= t₁ +Dt и т.д. Если шаг Dt достаточно мал, то таким путем можно получать приближенные значения Z.

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

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

2) неособые, в которых процесс находится все остальное время. Особые состояния характерны еще и тем обстоятельством, что функции состояний Z(t) в эти моменты времени изменяются скач­ком, а между особыми состояниями изменение координат Z(t) происходит плавно и непрерывно или не происходит совсем. Таким образом, следя при моделировании системы только за ее особыми состояниями в те моменты времени, когда эти состояния имеют место, можно получить информацию, необходимую для построения функций Z(t). Очевидно, для описанного типа систем могут быть построены моделирующие алгоритмы по «принципу особых состо­яний». Обозначим скачкообразное (релейное) изменение состояния z как dz, а «принцип особых состояний» — как принцип dz.

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

Отметим, что характеристики процесса функционирования таких систем с особыми состояниями оцениваются по информации об особых состояниях, а неособые состояния при моделировании не рассматриваются. «Принцип dz » дает возможность для ряда систем существенно уменьшить затраты машинного времени на реализа­цию моделирующих алгоритмов по сравнению с «принципом Dt». Логика построения моделирующего алгоритма, реализующего «принцип dz», отличается от рассмотренной для «принципа Dt» только тем, что включает в себя процедуру определения момента времени t_d, соответствующего следующему особому состоянию си­стемы. Для исследования процесса функционирования больших систем рационально использование комбинированного принципа построения моделирующих алгоритмов, сочетающего в себе пре­имущества каждого из рассмотренных принципов.

Рассмотрим соответствующие способы управления временем в модели системы на примере, показанном на рис. 5.2, где по оси реального времени отложена последовательность событий в системе {s_i} во времени, причем события s₄ и s₅, происходят одновременно (рис. 5.2, а). Под действием событий s_i, изменяются состояния модели z_i, в момент времени t_zi, причем такое изменение происходит скачком dz.

В модели, построенной по принципу Dt (рис. 5.2, б), моменты системного времени будут последовательно прини­мать значения t^’₁ = Dt, t^’₂ =2 Dt, t^’₃ =3 Dt, t^’₄ =4 Dt, t^’₅ =5 Dt. Эти моменты систем­ного времени t^’_j(Dt) никак не связаны с моментами появления событий, ко­торые имитируются в модели системы. Системное время при этом получает постоянное приращение, выбираемое и задаваемое перед началом имитаци­онного эксперимента.

В модели, построенной по «принципу dz» (рис. 5.2, в), изменение времени наступает в момент смены состояния системы, и последовательность моментов системного времени имеет вид t^’’₁ = t_z1, t^’’₂ = t_z2, t^’’₃ = t_z3, t^’’₄ = t_z4, t^’’₅ = t_z5, т.е. моменты системного времени t^’’_k (dz) непосредственно связаны с моментами появления событий в системе s_i.

У каждого из этих методов есть свои преимущества с точки зрения адекватного отражения реальных событий в системе и за­трат машинных ресурсов на моделирование. При использовании «принципа dz» события обрабатываются последовательно и время смещается каждый раз вперед до начала следующего события. В модели, построенной по «принципу Dt», обработка событий про­исходит по группам, пакетам или множествам событий. При этом выбор Dt оказывает существенное влияние на ход процесса и резуль­таты моделирования, и если Dt задана неправильно, то результаты могут получиться недостоверными, так как все события появляются в точке, соответствующей верхней границе каждого интервала мо­делирования. При применении «принципа dz» одновременная об­работка событий в модели имеет место только тогда, когда эти события появляются одновременно и в реальной системе. Это позволяет избежать необходимости искусственного введения ран­жирования событий при их обработке в конце интервала Dt.

При моделировании по «принципу Dt» можно добиться хорошей аппроксимации: для этого Dt должно быть малым, чтобы два неодновременных события не попали в один и тот же временной интервал. Но уменьшение Dt приводит к увеличению затрат машин­ного времени на моделирование, так как значительная часть тратит­ся на корректировку «часов» и отслеживание событий, которых в большинстве интервалов может и не быть. При этом даже при сильном «сжатии» Dt два неодновременных события могут попасть в один и тот же временной интервал Dt, что создает ложное представление об их одновременности.

Для выбора принципа построения машинной модели необходимо знать: цель и назначение модели; требуемую точность результатов моделирования; затраты машин­ного времени при использовании того или иного принципа; не­обходимый объем машинной памяти для реализации модели, построенной по принципу Dt и dz; трудоемкость программирования и отладки.

Рис. 5.2. Способы управления временем в модели системы

Механизм протяжки модельного времени

Рассмотрим, как реализован механизм протяжки модельного времени в системе СИМПАС. С понятием "модельное время" связана переменная SYSTIME, значе­ние которой показывает модельное время. При моделировании модель­ное время может меняться быстрее или медленнее, чем в реальной сис­теме. Это зависит от степени детализации модели и сложности описа­ния изучаемого процесса. В любом случае модельное время изменяется при выполнении некоторых событий, а события в системе моделирова­ния возникают в результате перемещения транзактов. Причиной изме­нения модельного времени может послужить явная задержка транзакта на некоторый отрезок модельного времени в процедуре DELAYT. Алгоритм изменения модельного времени реализован процедурой PLAN. Приведем общую схему протяжки модельного времени.

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

Рассмотрим транзакт, проходящий некоторую цепочку событий. Речь идет об активном транзакте, таким может быть только один тран­закт в модели, а именно тот, который продвигается в настоящий мо­мент времени по модели. Активный транзакт может перемещаться от события к событию, вызывая выполнение связанных с событиями дей­ствий (рис. 8). Значение модельного времени SYSTIME изменяться не будет до тех пор, пока транзакт остается активным. Прекратить актив­ность транзакта может некоторое событие. Таким событием, например, может быть явная задержка транзакта процедурой DELAYT. В этом случае активный транзакт помещается в список будущих событий (FUTURE), где он занимает место среди транзактов, ожидающих своего времени продвижения. Другим событием, прекращающим активность транзакта, может быть попытка поступить в занятый прибор. В этом случае транзакт должен быть помещен в список ожидающих освобождения прибора. Некоторые другие события могут также прекращать активность транзакта. После того, как такое событие произош­ло, активным должен стать другой транзакт.

Если в системе имеются другие транзакты, способные к продвиже­нию в данный момент времени, то они находятся в списке CURRENT; если этот список не пуст, то из него извлекается первый находящийся в нем транзакт и он ста­новится активным, по­сле чего продвигается по модели. Наконец наступит такой мо­мент, что ни одного транзакта в списке CURRENT не останет­ся; тогда и просматри­вается список FUTURE. Из него вы­бирается транзакт с минимальным "буду­щим временем про­движения", модельное время устанавливается равным времени продвижения этого тран­закта, а сам транзакт перемещается в спи­сок CURRENT. Вместе с ним в список CURRENT перемещаются все транзакты с таким же временем продвижения. После этого первый транзакт из списка CURRENT становится активным, и процесс моделирования продолжа­ется. Эта схема протяжки модельного времени далеко не полна, но тем не менее она отражает принцип изменения модельного времени.

Да

Нет

Да

Нет

Рис. 11. Упрощенная схема протяжки модельного времени

Событийный и процессно-ориентированный подход к построению моделей

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

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

Событийный подход основан на формировании потока событий (рис. 5). Такой поток образует сгруппированные последовательности действий:

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

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

Как правило, условия описываются отношениями связанных с событием переменных. В результате выполнения события значения некоторых модельных переменных могут измениться; это приводит к тому, что возникают условия, необходимые для выполнения другого события. При выполнении последовательности действий, связанной с выполнением некоторого события, можно изменить условия, связанные с его последующим вызовом. Таким образом, в результате выполнения потока событий изменяется среда моделирования; это приводит к возникновению новых условий, новые условия приводят к выполнению новых событий. Моделирование развивается по такой схеме сколь угодно долго.

Рис. 5. Событийный подход

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

Для этого используются средства языка системы моделирования. Естественно, эти средства должны быть достаточно представительными для того, чтобы описывать широкий круг процессов. В частности, для процессного подхода необходимыми являются средства явного (или неявного) определения участков модели, на которых необходимо представление квазипараллельных процессов.

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

Рис. 6. Графическое представление примера процесса продвижения транзактов

Моделирование работы с материальными ресурсами.

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

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

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

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

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

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

Перемещаемый ресурс представляет собой "склад" единиц ресурса, количество которых известно. Число таких складов не регламентировано. Транзакт попадает в очередь к складу и требует выделения определенного числа единиц ресурса. Склад ресурсов может описываться в имитационной модели различными способами.

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

Существует интересная особенность при работе с перемещаемыми ресурсами: транзакт может отдать какие-либо единицы ресурса не только на тот склад, на котором он их получил, но и на другой. При таком перераспределении (или "похищении") на этих двух складах произойдет изменение мощностей: на одном она уменьшится, а на другом - увеличится. Например, в GPSS перемещаемый ресурс может быть описан ячейками памяти, значения которых изменяются оператором SAVEVALUE: при захвате ресурса транзактом значение захваченного объема ресурса присваивается соответствующему параметру транзакта, а значение ячейки соответственно уменьшается на данную величину захваченного ресурса; при возврате ресурса параметр транзакта обнуляется, а значение ячейки памяти, определяющее общий объем свободного ресурса увеличивается на величину возвращенного ресурса.

Имитация информационных ресурсов.

Информационные ресурсы - это необходимые сведения, оперативная информация (например, биржевая информация из сайтов Интернета), временно предоставляемые права на что-либо, документация и иные нематериальные ценности, без которых невозможно выполнение важной функции. Эти ресурсы подразделяются на две разновидности:

- стартовый информационный ресурс, без которого нельзя начинать выполнение функции (например, права или разрешение на ее выполнение, инструкция по сборке принципиально нового устройства);

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

Стартовый информационный ресурс дает возможность отправить заявку на выполнение какой-либо функции, т.е. поместить транзакт в очередь на обслуживание. В языках имитационного моделирования может быть реализован различными способами, например, логическими переключателями (LOGIC R, LOGIC S, GATE LS).

Оперативный информационный ресурс может описываться также разными способами - одним из них является использование операторов захвата и освобождения прибора (В GPSS - PREEMPT, RETURN).

Общие понятия сетей Петри

Сетевые модели (сети Петри) используется для анализа причинно-следственных связей в сложных системах. Аппарат теории сетей Петри позволяет описывать структуру и взаимодействие параллельных систем и процессов. Сеть Петри (N-схема) задается четырьмя элементами:

N = <B,D,I,O>,

где B - конечное множество позиций; D - конечное множество переходов; I - входная функция (прямая функция инцидентности), I:BXD®{0,1}; O - выходная функция (обратная функция инцидентности), O:DXB®{0,1}.

I отображает переход d_j в множество входных позиций , а выходная функция О отображает переход d_j в множество выходных позиций . Для каждого можно определить множество входных позиций перехода и выходных позиций перехода как

Аналогично, для каждого можно определить множество входных переходов позиции и выходных переходов позиции :

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

приход заявки

заявка ждет обслуживания

Канал обслуживания заявка обрабатывается

свободен (канал занят)

конец обслуживания

заявка ждет вывода

выход заявки

Рис. 1. Структура N-схема

Для представления динамических свойств объекта вводится функция маркировки (разметки) . Маркировка - присвоение абстрактных объектов, называемых метками (фишками), позициям:

N_M = <B,D,I,O,M>.

Функционирование сети Петри отражается путем перехода от разметки к разметке. M₀ - начальная разметка. Смена разметок - срабатывание одного из переходов сети. Необходимое условие срабатывания перехода :

,

где - разметка позиции .

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

,

т.е. переход изымает по одной метке из каждой своей входной позиции и добавляет по одной метке в каждую из выходных позиций. Для отражения временных параметров процесса функционирования моделируемой системы на базе N-схем используется расширение аппарата сетей Петри - временные сети.

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

2. Анализ сетей Петри

Само моделирование малополезно. Необходимо провести анализ моделируемой системы. Существует два подхода к анализу свойств сетей Петри - это статистическое моделирование на компьютере и аналитические методы. Большое практическое значение имеет изучение следующих свойств сетей Петри: ограниченность, сохранение, активность, достижимость и покрываемость. Необходимо отметить, что задачи нахождения этих свойств разрешимы для классических сетей Петри и неразрешимы для расширений сетей Петри (например, Е-сетей).

Рассмотрим свойство ограниченности. Позиция является к-ограниченной, если количество фишек в ней не может превышать целое число k: M(b_i)£k, для всех MÎR(N,M) (множество достижимости). 1-ограниченная позиция называется безопасной. Сеть Петри ограниченна, если все ее позиции ограничены. Изучение данного свойства может иметь важное практическое значение при проектировании технических систем, в которых должно быть ограниченно присутствие одновременное присутствие активных процессов, например моделирование транспортных потоков или систем управления трафиком в глобальных вычислительных сетях. Такие системы должны быть обеспечены механизмами автоматической разгрузки или распределения.

Важным свойством для сетей Петри является сохранение. Сеть Петри является с начальной маркировкой М называется сохраняющей по отношению к вектору взвешивания W=(w₁, w₂,..., w_n), n=|B|, w_i >0, если для всех возможных маркировок выполняется следующее условие: å w_i × M'(b_i)= å w_i × M(b_i).

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

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

Очевидными являются задачи достижимости и покрываемости. Задача достижимости: можно ли из данной маркировки М достичь маркировки М'?. Задача покрываемости: для данной маркировки М существует ли достижимая маркировка М', такая что M'>=M.

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