Использование аппарата сетей Петри для моделирования поведения вычислительных структур

Федеральное агентство по образованию

Отчет по лабораторной работе № 2

по курсу «Моделирование систем»

Тема:

«Использование аппарата сетей Петри для моделирования поведения вычислительных структур»

Екатеринбург

2008г

Цель работы:

Изучение методов использования иерархических сетей Петри при анализе многоуровневых вычислительных структур (ВС).

Сети Петри:

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

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

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

Постановка задачи:

Дана вычислительная структура, которая включает канал ввода-вывода, состоящий из подканалов ПКВ1, ПКВ2, ПКВ3, и параллельный процессор, состоящий из трех процессорных элементов ПЭ1, ПЭ2, ПЭ3. Ввод данных выполняют подканалы ПКВ1 и ПКВ2, вывод - подканал ПКВ2. Подканал ПКВ3 управляет передачей данных в процессорные элементы, которые после обработки информации передают ее на вывод.

Разработать СП-модель в соответствии с ее словесным описанием.

Провести анализ полученной СП-модели при помощи графа достижимости.

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

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

СП-модель в соответствии с ее словесным описанием:

Информационное поле - условие, которое является началом передачи потока данных;

ПКВ1 – событие, в котором происходит получение информации в ПКВ1 – подканал, выполняющий ввод данных - и дальнейшая последовательная передача в следующий подканал ВС;

Получение инф-ции от ПКВ1 – условие последовательного получения и передачи информации от ПКВ 1 к ПКВ 2;

ПКВ2 – событие, в котором происходит получение информации в ПКВ2 – подканал, выполняющий ввод-вывод данных - и дальнейшая последовательная передача в следующий подканал ВС;

Поступление инф-ции на вывод от ПКВ2 – условие, в котором выполняется поступление и передача информации на вывод данных ВС

Получение инф-ции от ПКВ2 - условие последовательного получения и передачи информации от ПКВ 2 к ПКВ 3;

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

Передача инф-ции в ПЭ1 – условие, которое выполняет передачу инф-ции от ПКВ3 в ПЭ1;

Передача инф-ции в ПЭ2 – условие, которое выполняет передачу инф-ции от ПКВ3 в ПЭ2;

Передача инф-ции в ПЭ3 – условие, которое выполняет передачу инф-ции от ПКВ3 в ПЭ3;

ПЭ1 – событие получения информации ПЭ1;

ПЭ2 – событие получения информации ПЭ2;

ПЭ3 – событие получения информации ПЭ3;

Получение инф-ции от ПЭ1 – условие, в котором выполняется получение инофрмации от ПЭ1;

Получение инф-ции от ПЭ2 – условие, в котором выполняется получение инофрмации от ПЭ2;

Получение инф-ции от ПЭ3 – условие, в котором выполняется получение инофрмации от ПЭ3;

Вывод информации - событие вывода информации в информационное поле.

Анализ СП-модели

Анализ СП-модели выполняется с помощью Analysis Module Manager, State Spaсes Analysis Module – по трем параметрам Bounded (проверка ограниченности), Safe (проверка на безопасность), Deadlock (отсутствие безвыходного положения или тупика).

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

1.Достижимость. Маркировка Mn достижима из маркировки M0, если существует последовательность запусков, приводящих от M0 к Mn.

Множество всех маркировок, достижимых в сети (N, M0) от M0, обозначаются как R(N, M0), или R(M0). Таким образом, проблема достижимости в сетях Петри заключается в том, чтобы при заданной маркировки Mn в сети (N, M0) установить принадлежность M0 к множеству R(M0).

2.Ограниченность. Сеть Петри называется К-ограниченной, или просто ограниченной, если для любой маркировки, достижимой от маркировки M0, количество фишек в любой позиции не превышает некоторого числа К, то есть М(р)<=К для любого р и любой маркировки М, принадлежащей R(M0).

Сеть Петри (N, M0) называется безопасной, если она l-ограниченна.

3.Активность. Сеть Петри активна (или маркировка М0 сети Петри активна), если независимо от достигнутой М0 маркировки, для любого перехода существует последовательность дальнейших запусков, приводящая к его запуску.

4.Обратимость и базовое состояние. Сеть Петри обратима, если для любой маркировки М из R(M0) маркировка M0 достижима от М. Маркировка М называется базовым состоянием, если она достижима от любой маркировки М из R(M0).

5.Достижимость тупиковой разметки.

Построенная вычислительная структура является:

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

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

активной (последовательность запусков существует для любого перехода, приводящая его к запуску)

обратимой и имеет достижимость тупиковой разметки.

Дерево достижимости

Рис.1. Дерево достижимости

Выводы

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

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