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

7 « Использование аппарата сетей Петри для моде лирования поведения вычислительных структур » Цель работы : Изучение методов использования иерархических сетей Петри при анализе многоуро вневых вычислительных структур (ВС) . Сети Петри : Существует три различных метода, с помощью которых может быть разработа на многоуровневая ВС. Первый метод (сверху вниз) заключается в том, что сна чала разрабатывается самый высокий уровень, затем уровень, находящийся под ним, и т.д., пока не будет достигнут уровень, который может быть интерпр етирован аппаратными средствами. Второй метод (снизу вверх) является пря мой противоположностью методу "сверху вниз". При его использовании первы м разрабатывается уровень, наиболее близкий к аппаратуре, затем уровень , примыкающий к нему сверху, и т.д. до тех пор, пока не будет достигнут самый высокий уровень. При использовании третьего метода (с промежуточного ур овня) проектирование начинается с одного из промежуточных уровней, а зат ем процесс разработки распространяется одновременно вверх и вниз. Сети Петри с успехом могут применяться при использовании любого метода. Возможны два пути практического применения СП при проектировании и ана лизе систем. Первый путь заключается в использовании СП-моделей в качест ве вспомогательного инструмента анализа. В этом случае построенная стр уктура моделируется сетью Петри и модель анализируется. Любые трудност и, встречающиеся при анализе, указывают на изъяны в проекте. Для их исправ ления необходимо модифицировать проект. Модифицированный проект затем снова моделируется и анализируется. Этот цикл повторяется до тех пор, по ка проводимый анализ не приведет к успеху. Второй путь заключается в том, что весь процесс проектирования и определения характеристик ВС провод ится в терминах сетей Петри. Вычислительные структуры, назначение которых заключается в вводе, обра ботке и выводе информации. Предлагаемые структуры состоят из процессор ных элементов (ПЭ), которые могут соединяться последовательно и параллел ьно, и каналов ввода-вывода, которые состоят из подканалов. Постановка задачи : Дана вычислительная структура, которая в ключает канал ввода-вывода, состоящий из подканалов ПКВ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.Достижимость тупиковой разметки. Построенная вычислительная структура яв ляется: достижимой (заданная маркировка в сети пр инадлежит к множеству маркировок, достижимых в сети и существует послед овательность запусков. В данной ВС это можно полностью проанализироват ь, так как все переходы срабатывают последовательно и друг за другом), ограниченной (количество фишек в любой по зиции является ограниченным, в рассматриваемой СП-модели в любой позици и имеет одну фишку), активной ( п оследовательность запусков существует для любого перехода, приводящая его к запуску ) обратимой и имеет достижимость тупиковой разметки. Дерево дост ижимости 7 Рис.1. Дерево достижимости Выводы Во время выполнения работы была построен а и реализована вычислительная структура с помощью иерархических сете й Петри. Проведен анализ по таким параметрам, как ограниченность, безопа сность , активность, обратимость и достижимость ту пиковой разметки . Из проанализированных поведенческих сво йств (параметров) вычислительной структуры можно сделать вывод, что кажд ое свойство для реальных ВС важно и должно соблюдаться: ограниченность – это след ствие безопасно сти (безопасное хране ние данных и безопасное поступление информации, без потери и затирания е е вновь поступившей информации) , достижим ость тупиковой разметки – это конечность функционирования структуры (системы, обладающие данным свойством ран о или поздно перестанут функционировать, значит для реальной ВС должно б ыть отсутствие такого свойства, что продлит ее работу без ошибок и завис аний) , активность – работоспособность и н ужность данного перехода (что означает от сутствие не нужных элементов, то есть захламления системы) .