Использование аппарата сетей Петри для моделирования поведения вычислительных структур
2
Федеральное агентство по образованию
Отчет по лабораторной работе № 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.Достижимость тупиковой разметки.
Построенная вычислительная структура является:
достижимой (заданная маркировка в сети принадлежит к множеству маркировок, достижимых в сети и существует последовательность запусков. В данной ВС это можно полностью проанализировать, так как все переходы срабатывают последовательно и друг за другом),
ограниченной (количество фишек в любой позиции является ограниченным, в рассматриваемой СП-модели в любой позиции имеет одну фишку),
активной (последовательность запусков существует для любого перехода, приводящая его к запуску)
обратимой и имеет достижимость тупиковой разметки.
Дерево достижимости
2
Рис.1. Дерево достижимости
Выводы
Во время выполнения работы была построена и реализована вычислительная структура с помощью иерархических сетей Петри. Проведен анализ по таким параметрам, как ограниченность, безопасность, активность, обратимость и достижимость тупиковой разметки.
Из проанализированных поведенческих свойств (параметров) вычислительной структуры можно сделать вывод, что каждое свойство для реальных ВС важно и должно соблюдаться: ограниченность - это следствие безопасности (безопасное хранение данных и безопасное поступление информации, без потери и затирания ее вновь поступившей информации), достижимость тупиковой разметки - это конечность функционирования структуры (системы, обладающие данным свойством рано или поздно перестанут функционировать, значит для реальной ВС должно быть отсутствие такого свойства, что продлит ее работу без ошибок и зависаний), активность - работоспособность и нужность данного перехода (что означает отсутствие не нужных элементов, то есть захламления системы).
