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

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

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

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

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

Постановка задачи: Дана вычислительная структура, которая включает канал ввода-вывода, состоящий из подканалов ПКВ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. Дерево достижимости Выводы Во время выполнения работы была построена и реализована вычислительная структура с помощью иерархических сетей Петри. Проведен анализ по таким параметрам, как ограниченность, безопасность, активность, обратимость и достижимость тупиковой разметки.

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