- •Ямникова о.А.
- •1.2. Процесс проектирования. Основные понятия и определения
- •1.3. Стадии процесса проектирования
- •2. Основные понятия системотехники. Сапр как объект системотехники
- •2.2. Сапр как объект системотехники
- •2.3. Структура и классификация сапр
- •3. Принципы создания сапр
- •3.1. Процесс проектирования. Основные понятия и определения
- •3.2. Этапы проектирования сапр
- •3.3. Виды обеспечения сапр. Системные среды сапр
- •3.4. Особенности систем управления проектированием и проектными данными. Понятие об открытых системах
- •4. Методики функционального и информационного моделирования сложных систем
- •4.1. Case технологии
- •4.2 Методология idef моделирования
- •Idef-модели
- •4.3. Нотации idef моделирования
- •5. Аналитические и имитационные модели
- •5.1. Разработка имитационных моделей сложных систем
- •5.1.1. Имитационное моделирование
- •5.1.2. Функции моделей
- •5.1.3. Классификация моделей
- •5.1.5. Структура имитационных моделей
- •5.1.6. Структурный синтез систем
- •5.1.7. Искусство моделирования
- •5.1.8. Требования к хорошей модели
- •5.1.9. Процесс имитации
- •5.1.10. Проверка модели
- •5.2. Языки имитационного моделирования
- •5.3. Способы представления множества проектных решений
- •6. Математическое моделирование автоматизированных систем
- •6.1. Системы массового обслуживания
- •6.1.1 Основные сведения из теории массового обслуживания
- •6.1.2. Аналитические модели смо
- •6.1.3. Имитационное моделирование смо
- •6.1.4. Событийный метод моделирования
- •6.2. Сети Петри
6.1.4. Событийный метод моделирования
В программах имитационного моделирования СМО преимущественно реализуется событийный метод организации вычислений. Сущность событийного метода заключается в отслеживании на модели последовательности событий в том же порядке, в каком они происходили бы в реальной системе. Вычисления выполняют только для тех моментов времени и тех частей (процедур) модели, к которым относятся совершаемые события.
6.2. Сети Петри
Сети Петри – аппарат для моделирования динамических дискретных систем (преимущественно асинхронных параллельных процессов). Сеть Петри определяется как четверка <Р, Т, I, О>, где Р и Т – конечные множества позиций и переходов, I и О – множества входных и выходных функций. Другими словами, сеть Петри представляет собой двудольный ориентированный граф, в котором позициям соответствуют вершины, изображаемые кружками, а переходам – вершины, изображаемые утолщенными черточками; функциям I соответствуют дуги, направленные от позиций к переходам, а функциям О – от переходов к позициям.
Как и в системах массового обслуживания, в сетях Петри вводятся объекты двух типов: динамические – изображаются метками (маркерами) внутри позиций и статические – им соответствуют вершины сети Петри.
Распределение маркеров по позициям называют маркировкой. Маркеры могут перемещаться в сети. Каждое изменение маркировки называют событием, причем каждое событие связано с определенным переходом. Считается, что события происходят мгновенно и разновременно при выполнении некоторых условий.
Каждому условию в сети Петри соответствует определенная позиция. Совершению события соответствует срабатывание (возбуждение или запуск) перехода, при котором маркеры из входных позиций этого перехода перемещаются в выходные позиции. Последовательность событий образует моделируемый процесс.
Правила срабатывания переходов (рис. 6) конкретизируют следующим образом: переход срабатывает, если для каждой из его входных позиций выполняется условие Nt > Kt, где Nt – число маркеров в t-й входной позиции, Кt - число дуг, идущих от t-й позиции к переходу; при срабатывании перехода число маркеров в t-й входной позиции уменьшается на Kt, а (t+1)-й выходной позиции увеличивается на Kt, где Kt – число дуг, связывающих переход с t-й позицией.
На рис. 6 показан пример распределения маркеров по позициям перед срабатыванием, эту маркировку записывают в виде (2,2,3,1). После срабатывания перехода маркировка становится иной: (1,0,1,4).
Можно вводить ряд дополнительных правил и условий в алгоритмы моделирования, получая ту или иную разновидность сетей Петри. Так, прежде всего полезно ввести модельное время, чтобы моделировать не только последовательность событий, но и их привязку ко времени. Это осуществляется приданием переходам веса – продолжительности (задержки) срабатывания, которую можно определять, используя задаваемый при этом алгоритм. Полученную модель называют временной сетью Петри.
Если задержки являются случайными величинами, то сеть называют стохастической. В стохастических сетях возможно введение вероятностей срабатывания возбужденных переходов. Так, на рис. 7 представлен фрагмент сети Петри, иллюстрирующий конфликтную ситуацию – маркер в позиции р может запустить либо переход t1, либо переход t2. В стохастической сети предусматривается вероятностный выбор срабатывающего перехода в таких ситуациях.
|
|
Рис. 6. Фрагмент сети Петри |
Рис. 7. Конфликтная ситуация |
Если задержки определяются как функции некоторых аргументов, которыми могут быть количества маркеров в каких-либо позициях, состояния некоторых переходов и т. п., то сеть называют функциональной.
Во многих задачах динамические объекты могут быть нескольких типов, и для каждого типа нужно вводить свои алгоритмы поведения в сети. В этом случае каждый маркер должен иметь хотя бы один параметр, обозначающий тип маркера. Такой параметр обычно называют цветом; цвет можно использовать как аргумент в функциональных сетях. Сеть Петри при этом называют цветной.
Среди других разновидностей сетей Петри следует упомянуть ингибиторные сети, характеризующиеся тем, что в них возможны запрещающие (ингибиторные) дуги. Наличие маркера во входной позиции, связанной с переходом ингибиторной дугой, означает запрещение срабатывания перехода. Введенные понятия поясним на следующих примерах.
Пример 1. Требуется описать с помощью сети Петри работу группы пользователей на единственной рабочей станции WS при заданных характеристиках потока запросов на пользование WS и характеристиках поступающих задач. Сеть Петри представлена на рис. 8.
Здесь переходы связаны со следующими событиями: – поступление запроса на использованиеWS, – занятие станции, – освобождение станции,– выход обслуженной заявки; позицияр4 используется для отображения состояния WS: если в р4 имеется метка, то WS свободна и пришедшая заявка вызывает срабатывание перехода ; пока эта заявка не будет обслужена, метки вр4 не будет, следовательно, пришедшие в позицию запросы вынуждены ожидать срабатывания переходаt3.
Рис. 8. Сеть Петри к примеру 1
Пример 2. Требуется описать с помощью сети Петри процессы возникновения и устранения неисправностей в некоторой технической системе, состоящей из М однотипных блоков; в запасе имеется один исправный блок; известны статистические данные об интенсивностях возникновения отказов и длительностях таких операций, как поиск неисправностей, замена и ремонт отказавшего блока. На рис. 9 представлена соответствующая сеть Петри. Отметим, что при числе меток в позиции, равном М, можно в ней не ставить М точек, а записать в позиции значение М.
Рис. 9. Сеть Петри к примеру 2
В нашем примере значение М в позиции соответствует числу имеющихся в системе блоков. Переходы отображают следующие события:– отказ блока,- обнаружение неисправного блока.– его замена, – окончание ремонта.
Очевидно, что при непустой позиции р2 переход срабатывает, но с задержкой, равной вычисленному случайному значению моделируемого отрезка времени между отказами. После выхода маркера изон попадает через в , если имеется метка в позициир6, это означает, что обслуживающая систему бригада специалистов свободна и может приступить к поиску возникшей неисправности. В переходе t2 метка задерживается на время, равное случайному значению длительности поиска неисправности. Далее маркер оказывается в , и если имеется запасной блок (маркер в р4), то запускается переход , из которого маркеры выйдут вр2 р5 и через отрезок времени, требуемый для замены блока. После этого в t4 имитируется восстановление неисправного блока.
Рассматриваемая модель описывает функционирование системы в условиях, когда отказы могут возникать и в рабочем, и в неисправном состояниях системы. Поэтому не исключены ситуации, при которых более чем один маркер окажется в позиции p6.
Анализ сетей Петри
Анализ сложных систем на базе сетей Петри можно выполнять посредством имитационного моделирования СМО, представленных моделями сетей Петри. При этом задают входные потоки заявок и определяют соответствующую реакцию системы. Выходные параметры СМО рассчитывают путем обработки накопленного при моделировании статистического материала.
Возможен и другой подход к использованию сетей Петри для анализа объектов, исследуемых на системном уровне. Он не связан с имитацией процессов и основан на исследовании таких свойств сетей Петри, как ограниченность, безопасность, сохраняемость, достижимость, живость.
Ограниченность (или К-ограниченностъ) имеет место, если число меток в любой позиции сети не может превысить значения К. При проектировании автоматизированных систем определение К позволяет обоснованно выбирать емкости накопителей. Возможность неограниченного роста числа меток свидетельствует об опасности неограниченного роста длин очередей.
Безопасность – частный случай ограниченности, а именно это 1-ограниченность. Если для некоторой позиции установлено, что она безопасна, то ее можно представлять одним триггером.
Сохраняемость характеризуется постоянством загрузки ресурсов, т.е. , где – число маркеров в j-и позиции, – весовой коэффициент.
Достижимость характеризуется возможностью достижения маркировки М из состояния сети, характеризуемого маркировкой Мy.
Живость сети Петри определяется возможностью срабатывания любого перехода при функционировании моделируемого объекта. Отсутствие живости либо означает избыточность аппаратуры в проектируемой системе, либо свидетельствует о возможности возникновения зацикливаний, тупиков, блокировок.
В основе исследования перечисленных свойств сетей Петри лежит анализ достижимости.
Один из методов анализа достижимости любой маркировки из состояния М0 – построение графа достижимости. Начальная вершина графа отображает М0, а остальные вершины соответствуют маркировкам. Дуга из My в М означает событие и соответствует срабатыванию перехода t. В сложных сетях граф может содержать чрезмерно большое число вершин и дуг. Однако при построении графа можно не отображать все вершины, так как многие из них являются дублями (действительно, от маркировки m£ всегда порождается один и тот же подграф вне зависимости от того, из какого состояния система пришла в МА). Тупики обнаруживаются по отсутствию разрешенных переходов из какой-либо вершины, т. е. по наличию листьев – терминальных вершин. Неограниченный рост числа маркеров в какой-либо позиции свидетельствует о нарушениях ограниченности.
Приведем примеры анализа достижимости.
Пример 3. Сеть Петри и граф достижимых разметок представлены на рис. 10.
На рисунке вершины графа изображены в виде маркировок, дуги помечены срабатывающими переходами. Живость сети очевидна, так как срабатывают все переходы, тупики отсутствуют.
Рис. 10. Сеть Петри и ее граф достижимости к примеру 3
Пример 4. Сеть Петри и граф достижимых разметок представлены на рис. 11. Сеть, моделирующая двухпроцессорную вычислительную систему с общей памятью, является живой, все разметки достижимы.
Рис. 11. Сеть Петри и ее граф достижимости к примеру 4