Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

Моделирование ИС в CPN Tools

Министерство образования и науки, молодежи и

спорта Украины

Национальный аэрокосмический университет

им. М.Е.Жуковского «ХАИ»

Факультет заочного обучения

РЕФЕРАТ

на тему: Моделирование ИС в CPN Tools

по дисциплине:____________________________________

____________________________________

Выполнил: студент гр.96Т1

Лысогор В.С

Проверил:

________________

Харьков – 2013г.

Содержание Введение…………………………………………………………………….	5
1. Класс сетей Петри, реализованный в CPN Tools……………………...	5
1.1. Граф сети Петри и язык CPN ML.………..……………………..	6
1.2. Пример моделирования …………….…………..……………….	7
2. Назначение и основные функции CPN Tools………………………….	10
2.1. Назначение CPN Tools…………………………………………...	10
2.2. Основные функции CPN Tools…………………….……………	11

₃_{.Литература………………………………………..}

_Вве_д_ение

CPN Tools – это специальная моделирующая система, которая использует язык сетей Петри для описания моделей. Система была разработана в Университете Орхуса в Дании и свободно распространяется для некоммерческих организаций через сайт Уровень предоставляемого сервиса позволяет классифицировать CPN Tools как промышленную моделирующую систему. Она была использована в большом количестве реальных проектов, особенно в области телекоммуникаций. В последнее время корпорация Nokia применяет CPN Tools для управляемой моделью разработки нового поколения мобильных телефонов.

1. Класс сетей Петри, реализованный в CPN Tools

CPN Tools предлагает очень мощный класс сетей Петри для описания моделей. Согласно стандартной классификации такие сети называют иерархическими временными раскрашенными сетями Петри. Было доказано, что они эквивалентны машине Тьюринга и составляет универсальную алгоритмическую систему. Таким образом, произвольный объект может быть описан с помощью этого класса сетей.

Простейшая концепция раскрашенной сети Петри использует различные типы фишек. Тип фишки определен натуральным числом и визуально представлен как цвет: 1 – красный, 2–синий, 3–зеленый, и т.д. Концепция раскрашенной сети Петри CPN Tools более сложная. Такие сети часто

называют обобщенными раскрашенными сетями, так как тип фишки представлен абстрактным типом данных, как в языках программирования. Термин «раскрашенная» сохраняется исторически, но теперь очень трудно представить такие «цвета» визуально.

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

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

Иерархические сети обеспечивают построение сложных моделей. В таких сетях элемент может быть представлен другой сетью. В CPN Tools переход может быть замещен дополнительной сетью. Таким образом, получается вложенная конструкция: сеть внутри сети. Количество уровней иерархии не имеет принципиальных ограничений. Отметим, что, такой подход широко

распространен в языках программирования, где процедуры используются для управления сложностью.

_1.1. _Гpаф _сети _П_е_тр_и _и _язык _CPN _ML

В CPN Tools язык описания моделей представляет собой сочетание графа сети Петри и языка программирования CPN ML.

Граф сети Петри – двудольный ориентированный граф. Он состоит из вершин двух типов: позиций, представленных кругами или овалами и переходов, представленных прямоугольниками:

^{Позиция}_{Переход}

_Дуги _{соединяют} _{позиции} _и _{переход}_ы_:

^p1 _Дуга

Дуга

t1 p3

_Дуга

_p₂

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

_2`token

2`token

_p1 ₂ 2`token x

t1 p3

_p1 ₁ 1`token x

t1 x

p3 1 ^1`token

3`token

_p2 ₃ ^3`token

_p2 ₂ ^2`token

t _t

В классических сетях Петри все фишки одинаковые и элементарные. В раскрашенных сетях Петри фишки различные. Рассмотрим пример студентов, обедающих пирогами. Имеется две фишки: student (студент), pasty (пирог). Голодный студент становится сытым после того, как съедает пирог:

₇

food

5`pasty

5 ^5`pasty y

3`student

x eat

replete student

food

_hungry

5`pasty

4 ^4`pasty y

3`student

x eat

replete student

1 ^1`student s

hungry student

3 ^3`student

student

2 ^2`student

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

colset s=unit with student; colset p=unit with pasty; var x:s;

^var ^y:p;

Определены два множества цветов: множество s с элементом student и множество p с элементом pasty. Позиции «hungry student» (голодный студент) и «replete student» (сытый студент) имеют множество цветов s с фишкой student. Позиция food (пища) имеет множество цветов p с фишкой pasty. Чтобы запустить переход eat (кушать), необходимо наличие двух фишек: student и pasty. Переменные x и y используются, чтобы извлечь фишки из входных позиций и поместить новую фишку в выходную позицию.

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

В отличие от классических сетей Петри, в раскрашенных сетях у позиций,

переходов и дуг есть свои атрибуты. В вышеуказанном примере позиция имеет

имя – «hungry student», множество цветов – s, начальную маркировку –

^3`^student ^и ^{конечную} ^{маркировку} ^– ^2` ^student ^после ^тог^о^, ^как ^один^из

студентов съел пирог. Переменная x позволяет выбрать произвольного студента согласно множеству цветов переменной; переменная y позволяет выбрать произвольный пирог. Студент, который был извлечен переменной x из позиции «hungry student», будет помещен в позицию «replete student», так как выходная дуга перехода eat, подписана именем той же самой переменной x.

1.2. Пример моделирования

Рассмотрим более сложный пример для предварительного изучения CPN Tools. Пример взят из хорошо известной сказки о Золушке. Мачеха приказала Золушке отсортировать зерна; Фея послала мышей сортировать зерна, в то время как Золушка едет на балл.

₈

go home

tranport

_x ^u

1 ^1`Cinderella

Cinderella home

x x

1`pumpkin

go to ball

ball

1 ^1`Fairy

_Fairy

sack of rice

supernature

z 12`mouse magic

mice

if y=rice then 1`rice else empty

_sack _of _wheat

1000`rice++2000`wheat++3000`oat

1000`rice++

₆₀₀₀ ^2000`wheat++

3000`oat

sack with ^y mixture

sort

if y=wheat then 1`wheat else empty

if y=oat then 1`oat else empty

sack of oat

В этой раскрашенной сети Петри используются следующие описания множеств цветов и переменных:

colset	p=unit	with	pumpkin;
^colset	^c=unit	^with	^Cinderella;
^colset	^g=with	^rice	^\| ^wheat ^\| ^oat;
^colset	^m=unit	^with	^mouse;
^colset	^f=unit	^with	^Fairy;
^var ^x:	^c;
^var ^y:	^g;
^var ^z:	^f;
^var ^u:	^p;
^var ^v:	^m;

В примере есть четыре множества цветов: f с фишками под названием Fairy (Фея), c с фишками под названием Cinderella (Золушка), p с фишками под названием Pumpkin (Тыква) и g с тремя видами фишек (сортами зерен) под названием rice (рис), wheat (пшеница), oat (овес). В начальной маркировке разрешен один переход Magic (Волшебство), который подсвечен зеленым цветом. Разговаривая с Золушкой, Фея создает 12 мышей и 1 тыкву переходом Magic и исчезает. Путешествие Золушки на балл и сортировка зерен – параллельные события, и они могут происходить одновременно в любом порядке. Тыква используется для обеспечения возможности срабатывания переходов «go to ball» (ехать на балл) и «go home» (ехать домой), чтобы перенести Золушку на балл и обратно. Мыши используются для обеспечения

возможности срабатывания перехода Sort (Сортировка), чтобы выбирать зерна различных сортов.

Обсудим направления дуг и надписи на них. В переходе Magic Cinderella не изменяется, так же как Pumpkin в переходах «go to ball» и «go home», поэтому используются двунаправленные дуги. Остальные дуги – однонаправленные. Дуга, соединяющая позицию с переходом, извлекает фишку соответствующего множества цветов. Фишка извлекается в соответствии с надписью входной дуги перехода. В этом примере все надписи представлены переменными соответствующего множества цветов. Например, у входной дуги перехода sort есть надпись y; y – переменная множества цветов g; таким образом, из позиции «sack with mixture» (мешок со смесью зерен) извлекается произвольное зерно. Более сложные атрибуты входных дуг переходов будут изучены далее.

Выходные дуги переходов создают новые фишки. Новая фишка может быть создана (заново) или может совпадать с любой фишкой, извлеченной из входной позиции. Например, в переходе «go to ball» фишка Cinderella извлекается из позиции home (дом) переменной x по атрибуту входной дуги и та же самая фишка Cinderella будет помещена в позицию ball (балл) в соответствии с атрибутом x на выходной дуге. Переход Magic более сложный: Fairy исчезает после срабатывания этого перехода, потому что она извлечена входной дугой с надписью z, и переменная z не используется в атрибутах выходных дуг; Cinderella в позиции home не изменяется переходом Magic, так как используется двунаправленная дуга с надписью x, то есть, проверяется только наличие фишки в позиции home; 12 mice (мышей) и 1 pumpkin создаются, соответствующие константы подписаны на выходных дугах. Теперь рассмотрим модель после 5000 шагов моделирования:

go home

tranport

1 ^1`pumpkin p

_x ^u

home c

Cinderella

_1`pumpkin

go to ball

ball

1 ^1`Cinderella c

_x _sack _of _rice

₄₃₁ ^431`rice

supernature

Fairy f

z 12`mouse magic

mice

if y=rice then 1`rice else empty

12 ^12`mouse

^sack ^of ^wheet

⁸²² ^822`wheat

1000`rice++2000`wheat++3000`oat

569`rice++

₃₄₈₄ ^1178`wheat++

1737`oat

sack with ^y mixture

sort

if y=wheat then 1`wheat else empty

if y=oat then 1`oat else empty

sack of oat

1263 ^1263`oat g

Золушка прибыла на балл, мыши занимаются своей работой, Фея исчезла. Мыши выбрали 431 зерно риса, 822 зерна пшеницы и 1263 зерна овса. В этой маркировке есть два разрешенных перехода: sort и «go home». Рассмотрим способ сортировки зерен в этой модели. Переход sort извлекает одно зерно в переменную y, но это зерно должно быть помещено только в одну из позиций:

^«sack ^of ^rice» ⁽^мешок ^с рисо^м⁾^, ^«sack ^of ^wheat» ⁽^мешок ^с

пшеницей), «sack of oat» (мешок с овсом). Атрибуты выходных дуг содержат условия, выбирающие только зерна необходимого сорта, иначе выбирается специальная фишка Empty (пусто). Фишка Empty означает

«ничего».

Подробное рассмотрение вышеуказанного примера открывает множество отличий от оригинальной сказки. Например, в данной модели вообще не рассматривается понятие времени и предупреждение Феи о полуночи. Рекомендуется исследовать эту модель и найти все ее недостатки. После изучения CPN Tools можно построить свою собственную модель, полностью

соответствующую сказке.

Отметим, что вышеуказанный сказочный пример дает представление об организации моделей телекоммуникационных систем и сетей. Работа мышей похожа на функцию сетевого маршрутизатора. Реальный пример модели коммутируемой сети Ethernet приведен в Приложении. Но для того, чтобы понять, как он работает, необходимо изучить следующие главы данного учебного пособия.

2. Назначение и основные функции CPN Tools

2.1. Назначение CPN Tools

CPN Tools используется для построения и анализа моделей. Это – жизненно важная система для разработки сложных объектов в различных прикладных областях. Она широко применяется для менеджмента в производстве и бизнесе, управления производственными системами и роботами, а также транспортными средствами и ракетами, для планирования военных операций. Полный список реальных применений можно найти на домашней странице CPN Tools http://www.daimi.au.dk/CPNTools/. CPN Tools в настоящее время реализована в ОС Windows и на платформах Unix; она, по существу, является новым поколением ранее использованной системы Design- CPN.

Что касается области телекоммуникаций, CPN Tools применяется для спецификации и верификации протоколов, оценки пропускной способности

сетей и качества обслуживания, проектирования телекоммуникационных устройств и сетей. В последнее время корпорация Nokia применяет CPN Tools для управляемой моделью разработки мобильных телефонов нового поколения. Это направление является перспективным и эффективным для проектирования

сложных технических устройств. Раньше модели использовались только для оценки характеристик устройств или сетей в процессе их проектирования. В

управляемом моделью проектировании исходная простая модель последовательно преобразуется в заключительные спецификации системы. Процесс такого проектирования состоит в наделении модели всё большим количеством свойств и характеристик реальной системы, до тех пока она не становится технической спецификацией, необходимой для производства или инсталляции. Преимуществом этого подхода является возможность анализа системы на каждом этапе проектирования, оценки ее свойств и характеристик (соответствует ли она требованиям?). Это позволяет проектировать системы, близкие к оптимальным, так как для реальных сложных объектов формальное решение задачи оптимизации трудно реализуемо, а в большинстве случаев практически неосуществимо.

Что касается временных раскрашенных иерархических сетей Петри CPN Tools, они являются универсальной алгоритмической системой, позволяющей

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

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

процессор. Существует ряд известных примеров аппаратных процессоров сетей

Петри, например, сигнальные процессоры в контроллерах компании Klashka.

2.2. Основные функции CPN Tools

Основными функциями CPN Tools являются:

− создание (редактирование) моделей;

− анализ поведения моделей с помощью имитации динамики сети Петри;

− построение и анализ пространства состояний модели.

Для создания моделей предусмотрен специальный графический редактор раскрашенных сетей Петри. Редактор позволяет рисовать сети Петри на экране компьютера, вводить атрибуты элементов сети и дополнительные описания на языке CPN ML. Модель может состоять из нескольких страниц. Эти страницы связаны друг с другом для создания иерархической структуры.

Для достаточно простых моделей возможна генерация полного пространства состояний (графа достижимости). Это – лучший способ для верификации, например, телекоммуникационных протоколов. CPN Tools обеспечивает построение пространства состояний и автоматическую генерацию по нему отчёта, который содержит выводы о стандартных свойствах сетей Петри, таких как ограниченность и живость. Кроме того, предусмотрен специальный язык на основе языка CPN ML для описания запросов о

нестандартных свойствах пространства состояний, которые важны для пользователя. К сожалению, для сложных моделей пространство состояний может быть слишком большим, и его построение не представляется возможным.

Единственный способ для анализа сложных моделей – это имитация их поведения. CPN Tools предусматривает пошаговую имитацию для поиска и

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

модели. Такой подход применяется для оценки характеристик телекоммуникационных сетей, например, пропускной способности и качества обслуживания.

Литература

Зайцев Д.А., Шмелёва Т.Р. Моделирование коммутируемой локальной сети раскрашенными сетями Петри // Зв'язок, № 2(46), 2004, с. 56-60.

Зайцев Д.А. Измерительные фрагменты в моделях Петри телекоммуникационных сетей //

Зв'язок №2(54), 2005, с. 65-71.

Зайцев Д.А., Шмелёва Т.Р. Основы построения параметрических моделей Петри коммутируемых сетей // Моделирование и компьютерная графика: Материалы 1-й международной научно-технической конференции, 4-7 октября 2005, Донецк, ДонНТУ, 2005, с.207-215.

Зайцев Д.А., Березнюк М.В. Исследование эффективности использования адресного пространства протокола Bluetooth // Радиоэлектроника. Информатика. Управление. - 2006,

№1. - C. 57-63.

Зайцев Д.А., Сакун А.Л. Исследование эффективности технологии MPLS с помощью раскрашенных сетей Петри // Зв'язок. - 2006, №5. - C. 49-55.

Зайцев Д.А., Шмелёва Т.Р. Оценка характеристик сетей Ethernet с помощью параметрических моделей Петри // Зв'язок, № 4, 2007. - с. 62-67.

Моделирование ИС в CPN Tools 📙 Реферат → 🆔 154583