Использование аппарата сетей Петри для моделирования поведения вычислительных структур
Методы разработки вычислительной структуры. Изучение методов использования иерархических сетей Петри, пути их практического применения при проектировании и анализе систем. Анализ полученной модели на активность, обратимость, конечность функционирования.
Рубрика | Программирование, компьютеры и кибернетика |
Вид | лабораторная работа |
Язык | русский |
Дата добавления | 03.12.2009 |
Размер файла | 36,8 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
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. Дерево достижимости
Выводы
Во время выполнения работы была построена и реализована вычислительная структура с помощью иерархических сетей Петри. Проведен анализ по таким параметрам, как ограниченность, безопасность, активность, обратимость и достижимость тупиковой разметки.
Из проанализированных поведенческих свойств (параметров) вычислительной структуры можно сделать вывод, что каждое свойство для реальных ВС важно и должно соблюдаться: ограниченность - это следствие безопасности (безопасное хранение данных и безопасное поступление информации, без потери и затирания ее вновь поступившей информации), достижимость тупиковой разметки - это конечность функционирования структуры (системы, обладающие данным свойством рано или поздно перестанут функционировать, значит для реальной ВС должно быть отсутствие такого свойства, что продлит ее работу без ошибок и зависаний), активность - работоспособность и нужность данного перехода (что означает отсутствие не нужных элементов, то есть захламления системы).
Подобные документы
Понятие сетей Петри, их применение и возможности. Сетевое планирование, математические модели с использованием сетей Петри. Применение сетевых моделей для описания параллельных процессов. Моделирование процесса обучения с помощью вложенных сетей Петри.
курсовая работа [1,0 M], добавлен 17.11.2009Исследование методов моделирования, отличных от сетей Петри. Моделирование при помощи инструментария IDEF. Пример простейшей байесовской сети доверия. Анализ младшего разряда множителя. Сложение на сумматорах. Заполнение и анализ редактора сетей Петри.
курсовая работа [2,6 M], добавлен 28.10.2013Методы моделирования, отличные от инструментария "сети Петри". Пример моделирования стандартом IDEF0 процесса получения запроса браузером. Раскрашенные (цветные) сети Петри. Моделирование процессов игры стандартными средствами сетей Петри, ее программа.
курсовая работа [1,6 M], добавлен 11.12.2012Разработка и реализация графического редактора сетей Петри. Описание программы, которая позволяет создавать новые сети путем добавления позиций и переходов, соединяя их определенным образом. Основы построения систем автоматизационного проектирования.
курсовая работа [2,6 M], добавлен 21.06.2011Анализ инцидентов информационной безопасности. Структура и классификация систем обнаружения вторжений. Разработка и описание сетей Петри, моделирующих СОВ. Расчет времени реакции на атакующее воздействие. Верификация динамической модели обнаружения атак.
дипломная работа [885,3 K], добавлен 17.07.2016Основные принципы организации сетей абонентского доступа на базе PLC-технологии. Угрозы локальным сетям, политика безопасности при использовании технологии PLC. Анализ функционирования PLC здания инженерно-внедренческого центра ООО "НПП "Интепс Ком".
дипломная работа [3,0 M], добавлен 25.11.2012Анализ существующих решений системы поддержки принятия решений для корпоративной сети. Многоагентная система. Разработка концептуальной модели. Структура базы знаний. Разработка модели многоагентной системы на базе сетей Петри. Методика тестирования.
дипломная работа [5,1 M], добавлен 19.01.2017Построение математической модели программы, одноленточного автомата над алфавитом, допускающего различные множества слов. Алфавит терминальных символов, множество состояний и переходов. Определение начального и конечного состояний. Понятие сети Петри.
контрольная работа [294,8 K], добавлен 17.09.2013Стандартные схемы программ в линейной и графовой формах. Инварианты и ограничения циклов. Анализ сетей Петри на основе дерева достижимости. Доказательство полной правильности программы. Суммы элементов диагоналей, параллельных главной диагонали матрицы.
курсовая работа [280,4 K], добавлен 30.05.2012Понятие сетей и связи их компонентов. Характеристики и структура сетей. Основные модели, описывающие поведение сетей. Проектирование и реализация взвешенных сетей: требования к интерфейсу, выбор среды разработки, структура приложения. Анализ результатов.
курсовая работа [1,1 M], добавлен 29.06.2012