Пособие ТСиСА

If (variable>250) P5+1

t7

P2

If (certificate=physics)

P2+1 else empty (P2) If (certificate=informatics) P2+1 else empty (P2)

Рис. 63. Пример цветной сети Петри, описывающей процесс подачи документов на специальность

(к дугам добавлены функциональные выражения)

5.3. Функциональная сеть Петри

Функциональные сети Петри отличаются дополнительной информацией, которую можно ассоциировать с позициями, переходами и/или дугами. Вместо натуральных чисел, задающих кратность дуг в обыкновенных сетях Петри, в сетях Петри высокого уровня дугам могут быть приписаны выражения, содержащие переменные. Например, для сетей Петри, рассмотренных рис. 62–63, число маркеров можно задать переменными (или выражениями), которым присвоить соответствующие значения (рис. 64). Различные режимы срабатывания переходов задаются различными значениями переменных в данных выражениях, при этом переменной в качестве значения приписывается маркер некоторого типа, а значением выражения является мультимножество маркеров.

Для задания условий срабатывания перехода в сетях Петри высокого уровня переходу также может быть приписано логическое выражение, называемое охраной перехода. Например, что переход t1 может сработать только при x, отличным от y [12].

140

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

Рис. 64. Пример функциональной сети Петри, описывающей процесс подачи документов на специальность (цветная сеть Петри расширена до-

полнительной информацией, содержащейся на позициях, переходах и дугах)

5.4. Временная сеть Пети

Необходимость учета времени для исследования систем предопределило появление и использование временных сетей Петри. Временные сети Петри первыми в 1970-х годах упомянули в литературе Merlin P.M., Farber D.J., поэтому временные сети Петри иногда назы-

вают сетями Merlin-Farber [13].

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

141

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

Рассмотрим основные модификации временных сетей Петри, их свойства и правила построения. Возможны три варианта временных сетей Петри.

1). Каждому переходу временной сети Петри приписывается вес

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

2). Каждой позиции временной сети Петри приписывается вес – время выполнения (задержка маркеров в позиции). Все маркеры, которые переходят в позицию, оказываются недоступными (заблокированными) для срабатывания перехода в течение заданного времени выполнения.

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

Таким образом, временные сети Петри позволяют моделировать динамику изменения состояний системы в привязке их ко времени.

Временной сетью Петри называют вектор S = (P, T, I, O, D, K),

где:

P {p1 , p2 , , pn } , n > 0 конечное множество позиций.

T {t1 ,t2 , ,tm } , m > 0; конечное множество переходов.

D={α, β} интервал срабатывания перехода, где α – нижний, а β

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

142

K={α, β} интервал задержки маркеров в позиции, где α – нижний, а β – верхний.

Временные сети Петри могут быть представленными:

– жестко временными – временное дополнительное условие представлено задержкой при срабатывании перехода, который должен сработать в только указанный интервал времени (рис. 65) [14].

[5, 20]

t2

P3

Рис. 65. Пример жестковременной сети Петри

– мягко временными – срабатывание перехода осуществляется за определенное время, но срабатывание перехода является необязательным условием. Мягко временные сети Петри более предпочтительны для анализа программных продуктов (рис. 66) [14].

5.5. Вложенные сети Петри

Простые сети Петри являются удобным средством для моделирования и анализа различных параллельных и распределенных сис-

143

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

t4

2

Рис. 66. Пример мягко временной сети Петри

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

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

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

144

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

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

Содержательный смысл позиций и переходов для рассматриваемой вложенной сети Петри (первый уровень вложенности):

Р1 – студент университета; Р2 – учебный план направления или специальности; Р3 – аудиторная и самостоятельная учебная работа студента по дисциплине, (посещение семинаров, практических занятий, лабораторных работ и индивидуальных консультаций с преподавателем); Р4 сдача зачетов и курсовых работ; Р5 – сдача экзаменационной сессии; Р6 – принятие решения о переводе студента на следующий курс; t1 – проверка необходимости перезачета ранее изученных дисциплин; t2 –окончание учебных занятий в семестре; t3 – проверка допуск к экзаменационной сессии (студент не допущен);

творительные результаты сдачи); t6 – проверка результатов сдачи экзаменационной сессии (удовлетворительные результаты); t7 – решение о переводе студента на следующий курс.

145

146

Содержательный смысл позиций и переходов для рассматриваемой вложенной сети Петри (второй уровень вложенности):

Р31 – посещение первой лекции; Р32 – посещение второй лекции; Р33 – посещение первого практического занятия; Р34 – посещение второго практического занятия; Р35 – посещение первой лабораторной работы; Р36 – посещение второй лабораторной работы; Р37 – посещение первой консультации с преподавателем; Р38 – посещение второй консультации с преподавателем; t31– освоение материала первой лекции; t32 – освоение материала первого практического занятия; t33 – освоение материала первой лабораторной работы; t34 – получение замечаний и рекомендаций.

Содержательный смысл позиций и переходов для рассматриваемой вложенной сети Петри (третий уровень вложенности):

Р311 – методические указания к первому заданию практического занятия; Р312 – индивидуальное задание на первое задание практического занятия; Р333 – выполнение первого задания практического занятия; Р314 – методические указания ко второму заданию практического занятия; Р315 – индивидуальное задание на второе практическое занятие; Р336 –выполнение второго задания практического занятия; t331–проверка теоретической готовности к выполнению первого задания; t332 – обсуждения результатов выполнения первого задания (удовлетворительны результат); t333 – обсуждения результатов выполнения первого задания (неудовлетворительны результат).

5.6. Стохастическая сеть Петри

Стохастические сети Петри были введены около 30-ти лет назад и представляют модель количественного анализа динамических систем с дискретными событиями. Как и в обычной сети Петри, в стохастической сети Петри при срабатывании переходов происходит процесс перераспределения маркеров по позициям, но данное распределение связано с вероятностью срабатывания переходов. Вероятность может принимать численные значения от 0 до 1. Если предположить, что в системе (в зависимости от случая) может произойти или не произойти некоторое событие A, то вероятность события A может быть определена следующим образом: P (A)=m/n, где n – общее число взаимно исключающих друг друга исходов; m – число исходов, которые приводят к наступлению события A. Несколько собы-

147

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

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

Рис. 68. Фрагменты стохастических сетей Петри

5.7.Задачи для самостоятельного решения

1.Расширить сети Петри, в пунктах 1-22 третьей главы путем: задания времени срабатывания переходов и задержек для маркеров

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

148

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

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

Контрольные вопросы

1.Какой тип сетей Пери можно дополнить вероятностью срабатывания переходов?

2.Какие события для стохастических сетей Петри классифицируются как несовместимые и достоверные?

3.Какие основное подходы применяют при проектировании вложенных сетей Петри?

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

5.Какими особенностями характеризуются раскрашенные сети Петри?

6.Перечислите основные модификации временных сетей Петри, их свойства и правила построения?

7.В чем заключается основное отличие вложенных сетей Петри от других типов?

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

9.Почему концепции базовых сетей Петри недостаточно для описания сложных систем?

10.Можно ли одновременно использовать несколько типов модификаций сети Петри для одной сети?

11.Какие основные причины использования раскрашенных, вложенных, временных, стохастических и функциональных сетей Петри.

12.В каких случаях моделирование оправдано и необходимо?

149