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

Тип работы:
Лабораторная работа
Предмет:
Программирование


Узнать стоимость

Детальная информация о работе

Выдержка из работы

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

Отчет по лабораторной работе № 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. Дерево достижимости

Выводы

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

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

ПоказатьСвернуть
Заполнить форму текущей работой