Протоколы Internet


Сети Петри


10.24 Сети Петри

Семенов Ю.А. (ГНЦ ИТЭФ)

Протоколы можно описывать не только с помощью модели машины конечных состояний. Альтернативой можно считать сети Петри (смотри, также книгу "Сети Петри", Котов В.Е., Москва, "Наука", ГРФМЛ, 1984 откуда взяты некоторые примеры и фрагменты данной статьи). Модель сети Петри является принципиально асинхронной и служит для отображения и анализа причинно-следственных связей в системе. Для привязки к определенным моментам времени тех или иных переходов в синхронных системах используются события. Переходы из состояния в состояния считаются "мгновенными". Если переход реально происходит через какие-то промежуточные состояния, а нам существенно учесть в модели эти обстоятельства, то вводятся соответствующие "подсобытия". Сеть Петри имеет четыре базовых элемента: позиции (places), переходы, дуги и метки (token).

Позиция (место) - это состояние, в котором находится система или определенная ее часть. Смотри рис. 10.24.1.

Рис. 10.24.1. Сеть Петри с двумя позициями и двумя переходами. Цифрами 1 и 2 обозначены переходы, а буквами А и Б - позиции.

Состояние системы формируется в результате реализации локальных операций, называемых условиями реализации событий. Условие имеет емкость:

  • Условие не выполнено - емкость равна нулю
  • Условие выполнено - емкость равна 1.
  • Условие выполнено с n-кратным запасом - емкость равна n.

Определенная комбинация условий может стимулировать определенное событие, которое вызовет в свою очередь изменение изменение условий. В сетях Петри события и условия отображаются абстрактными символами, называемыми переходами(вертикальными или горизонатальными полосками - "барьерами") и позициями (кружками). Условия-позиции и события-переходы связаны отношениями зависимости, которые отображаются с помощью ориентированных дуг. Позиции, из которых исходят дуги данного перехода, называются входными позициями. Позиции же, к которым ведут дуги данного перехода, называются выходными позициями. Выполнение условий отображается помещением соотвествтующего числа меток в соответствующую позицию. Если число меток велико (более 2-3), емкость условия может быть отображена числом.




Начало  Назад  Вперед



Книжный магазин