2. Сетевое представление параллельных процессов. Области применения сетей Петри

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

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

Сеть Петри формально задаётся пятёркой: где

– непустое конечное множество позиций (мест),

– непустое конечное множество переходов,

и – матрицы инцидентности, причем.

– отображение множества на ,

– отображение множества на ,

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

Сеть Петри функционирует, переходя от разметки к разметке путем реализации возможных событий. Если входные условия некоторого события выполнены, то есть во всех местах входных событий имеются точки (фишки), то событие является возможным, в противном случае невозможным. Таким образом, срабатывание перехода t изменяет разметку так, что разметка каждого его входного места р_вх уменьшается на F(p_вх,t), то есть на кратность дуги, соединяющей место p_вх и переход t, а разметка каждого его выходного места увеличивается на F(t, p_вых), то есть на кратность дуги соединяющей переход t и р_вых. Невозможное событие наступить не может. Последовательность разметок в сети отражает динамику процесса, поток событий распространяется вдоль направления дуг. В то же время, правила функционирования сети Петри не указывают, как быстро реализуется возможное событие, а также позволяют учесть реальную асинхронность и непредсказуемость времени наступления событий.

Можно указать следующие области применения сетей Петри.

1. Оценка эффективности различных систем.

2. Моделирование протоколов обмена данными в асинхронных интерфейсах.

3. Моделирование и анализ распределенных программных систем.

4. Моделирование процессов вычислений в параллельном программировании.

5. Моделирование распределенных баз данных.

6. Моделирование дискретных систем.

7. Моделирование вычислительных систем управления потоками данных.

8. Компиляторы и операционные системы.

9. Формальные языки.

10. Логические программы.