диплом Анализ статических свойств сетей Петри и моделирование распределенных информационных систем (id=idd_1909_0000528)

МАГИСТРСКАЯ ДИССЕРТАЦИЯ НА ТЕМУ
ПРОЕКТИРОВАНИЕ НОВЫХ СИСТЕМ АДРЕСАЦИИ ГЛОБАЛЬНЫХ СЕТЕЙ
РЕФЕРАТ
Магистрская диссертация: 169 с., 59 рис., 23 табл., 73 источников - состоит из введения, 6 разделов, заключения и списка литературы.
Ключевые слова: ЕДИНЫЙ СЕТЕВОЙ АДРЕС Е6, ДИНАМИЧЕСКАЯ МАРШРУТИЗАЦИЯ, ДИСТАНЦИОННО-ВЕКТОРНЫЕ АЛГОРИТМЫ, МАГИСТРАЛЬНЫЕ МОСТЫ ПРОВАЙДЕРА PBB, ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ, РАСКРАШЕННЫЕ СЕТИ ПЕТРИ, ГАРАНТИРОВАННОЕ КАЧЕСТВО ОБСЛУЖИВАНИЕ, ОПЕРАЦИОННАЯ СИСТЕМА LINUX, СТЕК ПРОТОКОЛОВ
Объектом исследования являются процессы функционирования сетей с коммутацией пакетов; предметом исследования является система адресации глобальных сетей, стек сетевых протоколов, алгоритмы доставки пакета, архитектура и программное обеспечение сетевых устройств. Целью работы являются создания унифицированной системы адресации глобальных сетей с пакетной коммутацией, которая обеспечивает гарантированное качество обслуживания, повышает полезную производительность, расширяет адресное пространство. Предложена новая система адресации глобальных сетей Е6 и ее модификации; разработан соответствующий стек протоколов и спецификации использованных устройств и программного обеспечения. Единый сетевой адрес Е6 с длиной 6 октетов и иерархической структурой используется вместо IP адресов и MAC адресов; упразднены протоколы TCP и IP; для гарантированной доставки информации использованы средства Ethernet LLC2. Получены оценки повышения полезной производительности в 1,6 раз и сокращения времени доставки пакета в 4 раза; пространство сетевые адресов расширено в 16 тыс. раз относительно IP. Разработаны модели Е6 сетей с дистанционно-векторной маршрутизацией и временным отключением устройств в виде раскрашенных сетей Петри. Выполнено моделирования PBB сетей и сравнительный анализ полученных результатов относительно Е6 адресации. Найдено, что существенным недостатком технологии PBB являются непредвиденные временные перегрузки сети, обусловленные широковещательными штормами, что делает невозможным гарантированное качество обслуживания. Разработана стратегия практического внедрения Е6 сетей и организации шлюзов с TCP/IP сетями. Выполнена экспериментальная программная реализация стека протоколов Е6 в среде ядра операционной системы Linux и наблюдение передачи Е6 пакетов в сети с помощью анализаторов трафика. Результаты работы предназначены для применения в качестве новой технологии глобальных сетей. Предлагается продолжить исследование и выполнить промышленную реализацию Е6 сетей, что выведет Россию в лидеры информационнокоммуникационных технологий.

СОДЕРЖАНИЕ
РЕФЕРАТ 2
СПИСОК ОБОЗНАЧЕНИЙ 5
ВВЕДЕНИЕ 6
1 ТЕОРЕТИЧЕСКАЯ ЧАСТЬ. СЕТИ ПЕТРИ 8
1.1 Теоретико- множественное предстваление сетей Петри 9
1.2 Графическое предствавление сетей Петри 12
1.3 Матричное представление сетей Петри 15
1.4 Моделирование при помощи сетей Петри 15
1.4.1 Примеры 19
1.5 Структура сетей Петри 22
1.6    Графы сетей Петри 24
1.7 Маркировка сетей Петри 25
1.8  Правила выполнения сетей Петри 26
1.9 Пространство состояний сети Петри 28
1.10 Свойства сетей Петри 30
1.10.1 Безопасность 30
1.10.2 Сохранение 32
1.10.3  Активность 34
1.10.4   Достижимость и покрываемость 37
1.11 Понятие цветных (раскрашенных) сетей Петри 38
2 РАЗРАБОТКА СИСТЕМЫ АДРЕСАЦИИ Е6 40
2.1 Предварительное описание схемы адресации Е6 и ее вариантов 41
2.2 Полезная модель Е6 44
2.2.1 Формула полезной модели 44
2.2.2 Описание полезной модели 45
2.3 Стек протоколов Е6 53
2.3.1 Интерфейсы прикладного уровня 53
2.3.2 Описание стека Е6 54
2.4 Построение сети на основе схемы адресации Е6 57
2.4.1 Сетевые интерфейсы 57
2.4.2 Алгоритм работы коммутирующего маршрутизатора Е6 57
1.4.3 Схема доставки пакета в Е6 сети 58
2.4.4 Пример реализации сети на основе Схемы адресации Е6 60
2.4.5 Направления практической реализация Е6 сети 63
2.5 Особенности построения сетей на основе Схем адресации Е6-4/Е4Р 66
2.6 Дистанционно-векторный протокол динамической маршрутизации K6-RIP 67
3 ОЦЕНКА ЭФФЕКТИВНОСТИ Е6 СЕТЕЙ 71
3.1 Преимущества Е6 сетей 72
3.2 Оценка полезной нагрузки пакетов 73
3.3 Анализ алгоритмов доставки пакетов 75
3.4 Оценка времени доставки пакетов 82
3.5 Сравнительная оценки качества обслуживания Е6 и IP сетей 86
3.6 Оценка влияния очередей 88
4 МОДЕЛИРОВАНИЕ Е6 СЕТЕЙ 92
4.1 Разработка моделей Е6 сетей 92
4.1.1 Модель коммутирующего маршрутизатора КМЕ6 92
4.1.2 Компонента E6-RIP 96
4.2 Модели терминального оборудования с потоковым трафиком 99
4.3 Измерительные фрагменты для потокового трафика 101
4.4 Исследование модели Е6 на изменяющейся структуре сети 102
4.4.1 Построение моделей Е6 сетей из компонентов 102
4.4.2 Модели временного отключения устройств 105
4.4.3 Анализ результатов моделирования Е6 сетей 108
5 МОДЕЛИРОВАНИЕ PBB СЕТЕЙ 112
5.1 Обзор технологии PBB 112
5.2 Разработка компонентов моделей PBB сетей 115
5.2.1 Общая организация модели PBB сети 115
5.2.2 Модели PBB оборудования 117
5.3 Модели терминального оборудования взаимодействия клиент-сервер 125
5.4 Модель измерительной рабочей станции 128
5.5 Исследование моделей PBB сетей 131
5.5.1 Построение модели PBB сети из компонентов 131
5.5.2 Анализ результатов моделирования PBB сетей 134
6 РЕАЛИЗАЦИЯ И ВНЕДРЕНИЕ Е6 СЕТЕЙ 139
6.1 Стратегия внедрения Е6 сетей 139
6.2 Организация шлюзов Е6 и TCP/IP сетей 143
6.3 Принципы программной реализации стека Е6 146
6.4 Экспериментальная реализация стека Е6 в ядре ОС Linux 147
6.4.1 Прикладные интерфейсы 148
6.4.2 Интерфейсы канального уровня 152
6.4.3 Внутренние структуры данных и программы 154
ЗАКЛЮЧЕНИЕ 161
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ 163




СПИСОК ОБОЗНАЧЕНИЙ
Обозначение Расшифровка
CIDR Classless Inter-Domain Routing
DHCP Dynamic Host Configuration Protocol
DNS Domain Name System
DWDM Dense Wave Division Multiplexing
E6 Uniform Network Address
FTP File Transfer Protocol
IP Internet Protocol
HTTP Hypertext Transfer Protocol
MPLS Multiprotocol Label Switching
NAT Network Address Translator
PBB Provider Backbone Bridge
Qo Quality of Service
RIP Routing Information Protocol
SMTP Simple Mail Transfer Protocol
TCP Transmission Control Protocol
UDP User Datagram Protocol
URL Uniform Resource

Locator
VoIP Voice over IP
Описание
Бесклассовая маршрутизация внутри доменов
Протокол динамической конфигурации хоста
Система имен доменов Мультиплексирование с плотным распределением длин волн Единый сетевой адрес Протокол передачи файлов Протокол Интернета Протокол передачи гипертекста Многопротокольная коммутация меток Транслятор адресов сети Магистральный мост провайдера Качество обслуживания Протокол маршрутной информации Простой протокол передачи электронной почты
Протокол управления передачей данных Протокол дейтаграмм пользователя Унифицированный локатор ресурса Передача голоса через Интернет протоколВВЕДЕНИЕ
В настоящее время сложились определенные проблемы дальнейшего развития глобальных сетей, обусловленные системой адресации и алгоритмами доставки пакетов, для решения которых было предложено IPv6 для расширения адресного пространства, MPLS и PBB для ускоренной доставки пакетов, многочисленные методы инжиниринга трафика для обеспечения качества обслуживания.
Среди основных тенденций развития современных сетей следует отметить следующие:
преобладающее применение пользователем безадресного доступа и имен ресурсов (URL, DNS);
доминирование на прикладном уровне приложений стека протоколов TCP/IP в Интернет/Интранет;
развитие дополнительных технологий ускоренной доставки пакетов в магистралях (MPLS, PBB);
доминирование на канальном (физическом) уровнях технологии Ethernet и ее расширений.
Однако технология инкапсуляции IP пакетов в кадры Ethernet остается в основном такой, как это было представлено в роботах Джона Постела, Дэвида Плюмера и Чарлза Хорнига в 1980-1984 годах. Новые технологии, такие как MPLS и PBB, лишь дополняют предыдущие стандарты. Отображение адресов исторически играло положительную роль для интеграции различных канальных технологий в гетерогенных сетях, но в настоящее время в условиях доминирования на канальном уровне технологии Ethernet является в большинстве случаев избыточным. Основным препятствием на пути обеспечения гарантированного качества обслуживания является отображение адресов, воплощенное в протоколах ARP/RARP, которые могут вносить существенную задержку ко времени доставки пакета, а также широковещание и алгоритмы покрывающего дерева, используемые для доставки кадра Ethernet.
Основными проблемами развития современных сетей являются:
обеспечение гарантированного качества обслуживания;
недостаток адресов;
снижение полезной производительности;
переполнение адресных таблиц;
широковещательные штормы;
неиспользование работоспособных каналов за пределами покрывающего дерева. Настоящая работа посвящена разработке новых унифицированных систем адресации сетей, которые позволяют решить указанные проблемы и обеспечить гарантированное качество обслуживания, что обуславливает актуальность темы исследования.

1 ТЕОРЕТИЧЕСКАЯ ЧАСТЬ. СЕТИ ПЕТРИ
Сети Петри — математический аппарат для моделирования динамических дискретных систем. Впервые были описаны Карлом Петри в 1962 году.
Взаимодействие событий в параллельных асинхронных дискретных системах имеет, как правило, сложную динамическую структуру. Эти взаимодействия описываются более просто, если указывать не непосредственные связи между событиями, а те ситуации, при которых данное событие может реализоваться. При этом глобальные ситуации в системе формируются с помощью локальных операций, называемых условиями реализации событий. Определённые сочетания условий разрешают реализоваться некоторому событию (предусловия события), а реализация события изменяет некоторые условия (постусловия события), то есть события взаимодействуют с условиями, а условия – с событиями. Таким образом, предполагается, что для решения задач достаточно представить системы как структуры, образованные из элементов двух типов – событий и условий. Удобный формальный механизм для этого, предложенный Петри, был развит А. Холтом, который назвал его сетью Петри.
В сетях Петри события и условия представлены абстрактными символами из двух непересекающихся алфавитов, называемых соответственно множеством переходов и множеством позиций. Имеется несколько формальных представлений сетей Петри:
-теоретико-множественное;
-графовое – бихроматический (двудольный ориентированный) граф и, соответственно, графическое;
-матричное.
Виды сетей Петри:
1)Временная сеть Петри — переходы обладают весом, определяющим продолжительность срабатывания (задержку).
2)Стохастическая сеть Петри — задержки являются случайными величинами.
3)Функциональная сеть Петри — задержки определяются как функции некоторых аргументов, например, количества меток в каких-либо позициях, состояния некоторых переходов.
4)Цветная сеть Петри — метки могут быть различных типов, обозначаемых цветами, тип метки может быть использован как аргумент в функциональных сетях.
5)Ингибиторная сеть Петри — возможны ингибиторные дуги, запрещающие срабатывания перехода, если во входной позиции, связанной с переходом ингибиторной дугой, находится метка.
6)Иерархическая сеть — содержит не мгновенные переходы, в которые вложены другие, возможно, также иерархические, сети. Срабатывание такого перехода характеризует выполнение полного жизненного цикла вложенной сети.
7)WF-сети
1.1 ТЕОРЕТИКО- МНОЖЕСТВЕННОЕ ПРЕДСТВАЛЕНИЕ СЕТЕЙ ПЕТРИ
При использовании теоретико-множественного подхода к описанию сети Петри (поскольку эта модель представляет и структуру, и функционирование системы) она формально может быть определена как двойка вида: N =. Здесь S – это структура сети, которая представляется двудольным ориентированным мультиграфом S=(V, U), где V – вершины этого графа, U – его дуги. М0 – начальное состояние сети Петри, которое также называется начальной маркировкой. В силу того, что граф S является двудольным, можно перейти к формальному описанию структуры сети Петри в виде тройки:

S=
где Р – конечное множество позиций, Р ={pi},i = 1,n ; Т – конечное множество переходов, Т = {tj}, j = 1, m ; ТUР = V, Т?Р= O , то есть Т и Р – это два типа вершин биграфа S; Y – конечное множество дуг, заданное отношениями между вершинами графа S : Y Є (Р * T)U(T * Р).
Поскольку двудольный мультиграф S является ориентированным, то любой переход tj, j = 1,m соединяется с позициями рi Є Р через входные и выходные дуги, которые задаются через функцию предшествования В:(P * T) ({0,1, 2,...} и через функцию следования Е:(Т * Р) ( {0,1,2..}, являющиеся отображениями из множества переходов в комплекты позиций (синонимом термина комплект является понятие мультимножества). Эти функции определяют комплекты позиций {рi} Є P , 354 связанных с переходом tj Є Т через множество дуг {(pi,tj)l}, где 1?|{(pi,tj)l:i,j = const}|?W, и комплекты позиций {рk}? P , связанных с переходом tj Є Т через множество_дуг {(tj,pk)l}, где 1?|{(ti,pk)l: j,k = const}|?W. Здесь W – мультичисло графа S; P – пространство комплектов, заданное на множестве функциями Е и В;
{(pi,tj)v} – v-я дуга, выходящая из позиции pi и входящая в переход tj, {(ti,pk)v – v-я дуга, выходящая из перехода tj и входящая в позицию pk .
Таким образом, теперь структура S сети Петри N может быть представлена как четверка: S(P,T,B,E). Представим множество позиций Р как объединение двух пересекающихся множеств: P=IUO; I?O?O. Здесь мы через I и О обозначим следующие множества:



где I(tj) = {pi:B(pi ,tj) ?1, i = 1,n }, j = 1,m ; O(tj) = {pk:E(tj ,pk) ? 1 k = 1,n }, j = 1,m ;

(pi ,tj) – дуга с весом w ? W, выходящая из вершины pi и входящая в вершину tj
(tj ,pk) – дуга с весом w ? W, выходящая из вершины tj и входящая в вершину pk то есть I(tj) и O(tj) – комплекты соответственно входных и выходных позиций пере- хода tj.
Элементы множества T обычно представляют собой те возможности (возможные ситуации, условия), при которых могут быть реализованы интересующие нас процессы (действия).
Начальная маркировка М0 (как и текущая маркировка М, которая соответствует некоторому состоянию сети в текущий момент модельного времени) определяется одномерной матрицей (вектором), число компонентов которого равно числу позиций сети п, п =|Р |, а значение i-го компонента, 1 ? i ? п, есть натуральное число m(pi), которое определяет количество маркеров (меток) в позиции рi то есть

М0 = (m0(p1), m0(p2), … , m0(pn));
М = (m(p1), m(p2), … , m(pn)),
где m(p1) m(pi)?Z; Z – множество неотрицательных целых чисел. Маркировку М можно представлять и как множество или комплект с той лишь только разницей, что отсутствие некоторого элемента в множестве будем обозначать специальным элементом – нулём. В этом случае запись вида Mi = Mi-1 – I(t) означает разность множеств и такое изменение маркировки, при котором на соответствующих местах вектора Мi будут уменьшенные значения.
Передвижение маркеров по сети осуществляется посредством срабатывания её переходов. Срабатывание возбужденного перехода, являющееся локальным актом, в целом ведёт к изменению маркировки сети, то есть к изменению её состояния. Таким образом, если в сети задано начальное маркирование М0, при котором хотя бы один переход возбуждён, то в ней начинается движение маркеров, отображающее смену состояний сети. Переход tj может сработать, если
pi Є I(tj): m(pi) ?# (рi , I(tj)) – w.
Переход, для которого выполняется это условие, называется возбуждённым. Здесь запись вида #(рi, I(tj)) означает число появлений позиций рi во входном комплекте перехода tj оно, естественно, равно весу w, если вместо мультиграфа рассматривать взвешенный граф. При срабатывании перехода tj маркировка М0 изменяется на маркировку M1 следующим образом: M1 = М0 – I(tj) + О(tj). Иначе говоря,
p i Є P: т1(рi) – т0(рi) - #(рi, I(tj)) + #(рi, О(tj)).
Из последнего выражения видно, что количество маркеров, которое переход tj изымает из своих входных позиций, может не равняться количеству маркеров, которое этот переход помещает в свои выходные позиции, так как совсем не обязательно, чтобы число входных дуг перехода равнялось числу его выходных дуг.
1.2 ГРАФИЧЕСКОЕ ПРЕДСТВАВЛЕНИЕ СЕТЕЙ ПЕТРИ
Графически сеть Петри представляется в виде двудольного ориентированного графа с двумя типами вершин – позициями и переходами (рис. 1.1). Позиция обозначается кругом, переход – чертой или прямоугольником. Как правило, чертой обозначают простой, мгновенный переход, прямоугольником – длительный. В позициях могут находиться фишки – некая сущность, наличие которой говорит о том, что условие, соответствующее текущей позиции, выполняется. К примеру, наличие фишки может говорить о наличии входных данных для некоторой процедуры. Наличие нескольких фишек говорит о том, что условие выполнено с многократным запасом. В примере с процедурой это может быть наличие нескольких элементов в очереди ее входных данных. Количество фишек в каждой позиции является целым неотрицательным числом. Наличие фишек в позиции на графе обозначается числом либо жирными точками в соответствующем количестве. Совокупность всех фишек, размещенных в позициях сети Петри, называется разметкой сети.
Дуги сети Петри могут быть направлены лишь от позиций к переходам либо от переходов к позициям. Дуги могут быть кратными, т.е. иметь вес – также целое неотрицательное число. Наличие кратной дуги между позицией и переходом эквивалентно наличию между ними соответствующего количества простых дуг в том же направлении. Дуги, направленные от позиций к переходам, называются входными, направленные от переходов к позициям – выходными. Аналогичными терминами обозначаются и соответствующие позиции по отношению к некоторому переходу.


Рисунок 1.1 - Пример графического представления сети Петри

Таким образом, сеть Петри полностью описывается следующими параметрами:
- множество позиций;
- множество переходов;
- множество входных дуг (дуг от позиций к переходам);
- множество выходных дуг (дуг от переходов к позициям);
- множество фишек, размещенных в позициях изначально (начальная разметка).
Функционирование сети Петри осуществляется в виде последовательности срабатывания переходов. В каждый момент времени в сети есть некоторое количество разрешенных переходов, т.е. таких, которые могут сработать. Переход считается разрешенным, если во всех его входных позициях количество фишек не меньше, чем кратность соответствующих входных дуг. Из всего множества разрешенных переходов сработать может любой. Какой именно сработает, определяется вне сети, также как и момент его срабатывания во времени. Выбор может быть осуществлен на основе ожидания аппаратного события, события завершения длительного процесса, выбора пользователем и т.п. При срабатывании простого перехода из каждой его входной позиции изымается количество фишек, равное кратности соответствующей входной дуги, после чего к каждой выходной позиции добавляются фишки в соответствии с кратностью выходных дуг. После каждого срабатывания перехода множество разрешенных переходов в общем случае меняется, поскольку меняется текущая разметка сети. Считается, что сеть Петри «жива», если в ней есть разрешенные переходы. Если после срабатывания очередного перехода разрешенных переходов в сети не остается, она завершает выполнение.
В случае, когда позиция является входной для двух или более разрешенных переходов, срабатывание любого из них и соответствующее уменьшение количества фишек в ней может запретить другие переходы. Такой ситуацией моделируются конфликты, когда для выполнения нескольких операций требуется использование общего ресурса. Пример такой ситуации виден на рис. 1.1. В самом начале работы сети разрешенным является один переход – t1. После его первого срабатывания разрешенными являются все три перехода сети. Если же теперь сработает, к примеру, переход t2, он запретит переход t3, и наоборот, срабатывание t3 запретит переход t2, поскольку переходы t2 и t3 имеют общую входную позицию p3.
Срабатывание простого перехода считается мгновенным. Поскольку вероятность одновременного происхождения двух мгновенных событий равна нулю, два простых перехода не могут сработать одновременно. Отсюда вытекает довольно парадоксальное свойство сетей Петри: притом, что они моделируют асинхронное выполнение параллельных процессов, сама по себе работа сети Петри происходит строго последовательно. Именно невозможностью одновременного срабатывания каких-либо переходов определяется асинхронная природа сетей Петри.
1.3 МАТРИЧНОЕ ПРЕДСТАВЛЕНИЕ СЕТЕЙ ПЕТРИ
Сети Петри могут быть использованы с точки зрения анализа системы на возможность возникновения в ней тупиковых ситуаций. Этот анализ проводится посредством исследования пространства возможных состояний сети Петри. При этом под последним понимается множество возможных маркировок сети. Анализ сетей посредством матричных методов имеет множество проблем, поэтому в основном используется подход, основанный на построении редуцированного до дерева графа возможных маркировок. В таком дереве вершины графа – это состояния (маркировки) сети, а ветви дерева, помеченные соответствующими переходами сети, – это возможные изменения состояний сети, то есть срабатывания её переходов. Если взять любую вершину в таком дереве (за исключением корневой), то путь к этой вершине от корня дерева (путь из начальной маркировки к заданной) будет представлять собой последовательность срабатывания переходов.
Говорят, что переход tj для разметки М является живым, если для всех разметок М' достижимым из разметок М существует последовательность срабатывания переходов, которая приводит к маркировке М' при которой переход tj может сработать. Сеть Петри называется живой, если все её переходы живы; живучая разметка – это разметка, при которой каждый из её переходов сможет запускаться бесконечное число раз. Когда достигнута такая разметка, при которой ни один из переходов не может быть запущен, говорят, что сеть Петри завершилась (достигнута желаемая конечная маркировка) или же зависла (то есть имеет место тупиковая ситуация).
1.4 МОДЕЛИРОВАНИЕ ПРИ ПОМОЩИ СЕТЕЙ ПЕТРИ
Сети Петри были разработаны и используются в основном для моделирования. С их помощью могут быть промоделированы многие системы в особенности системы с независимыми компонентами., например аппаратное и программное обеспечение ЭВМ, физические системы, социальные и др. Сети Петри применяются для моделирования возникновения различных событий в системе. В частности сети Петри могут моделировать поток информации и другие ресурсы системы.
Простое представление системы сетью Петри основано на двух основополагающих понятиях: событиях и условиях. События – это действия, имеющие место в системе. Возникновением событий управляет состояние системы. Состояние системы может быть описано множеством условий. Условие – предикат или логическое описание состояния системы. Условие может принимать, либо значение «истина», либо значение «ложь».
Так как события являются действиями, то они могут происходить. Для того чтобы событие произошло, необходимо выполнение соответствующих условий. Эти условия называются предусловиями события. Возникновение события может вызвать нарушение предусловий и может привести к выполнению других условий, постусловий.
В сети Петри условия моделируются позициями, события переходами. При этом входы перехода являются предусловиями соответствующего события; входы – постусловиями. Возникновение события равносильно запуску соответствующего перехода. Выполнение условие представляется фишкой в позиции, соответствующей этому условию. Запуск перехода удаляет разрешающие фишки, представляющие выполнение предусловий и образует новые фишки, которые представляют выполнение постусловий.
Одной из особенностей является свойственный сетям и их моделям параллелизм, или одновременность. В модели сети Петри два разрешенных невзаимодействующих события могут происходить независимо друг от друга. Синхронизировать события, пока это не требуется моделируемой системе, нет нужды. Но когда синхронизация необходима, моделировать её легко. Таким образом, сети Петри представляются идеальными ля моделирования систем с распределенным управлением, в которых несколько процессов выполняются одновременно.
Другая важная особенность сетей Петри – это их асинхронная природа. В сети Петри отсутствует измерение времени или течение времени. Это отражает философский подход к понятию времени, с логической точки зрения, - это определение частичного упорядочения событий. В реальной жизни различные события укладываются в различные интервалы времени, и это отражено в модели сети Петри независимостью от времени управления последовательностью событий. Структура сети Петри такова, что содержит в себе всю необходимую информацию для определения возможных последовательностей событий.
Выполнение сети Петри рассматривается как последовательность дискретных событий. Порядок выполнения событий является одним из возможных, допускаемых основной структурой. Это приводит к явной недетерминированности в выполнении сети Петри. Если в какой-то момент времени разрешено более одного перехода, то любой из нескольких возможных переходов может стать «следующим» запускаемым. Выбор запускаемого перехода осуществляется недетерминированным образом, т. е. случайно. Но все же выбор для запуска одного из разрешенных переходов детерминирован, но не на модели, просто потому что модель не дает полной информации о системе.
При анализе динамического поведения сет Петри, когда определяется последовательность запусков переходов, возникают некоторые трудности. Для простоты обычно вводят следующее ограничение. Запуск перехода ( и соответствующего события) рассматривается как мгновенное событие, занимающее нулевое время, и возникновение двух событий одновременно невозможно. Моделируемое таким образом событие называется примитивным; примитивные события мгновенны и неодновременные.( Иногда это обосновывается тем, что время – это непрерывная действительная переменная. Следовательно, если мы присвоим каждому событию время возникновения, то вероятность того, что любые две произвольно выбранные непрерывные действительные переменные совпадают, равна нулю, и следовательно, события неодновременные.)
Непримитивными называются такие события, длительность которых отлична от нуля. Они не являются неодновременными и, следовательно, могут пересекаться во времени. Непримитивное событие может быть представлено в виде двух примитивных событий: «начало непримитивного события», «конец непримитивного события» и условия «непрмитивное событие происходит».
Петри и другие предложили представлять непримитивные события в сети Петри в виде прямоугольника, а примитивные планками. Это упростит некоторые сети Петри. Но прямоугольник может иметь значение при моделировании сложных систем на нескольких иерархических уровнях, так как он позволяет выделить в отдельный элемент сети целые подсети. Это в некотором смысле подобно понятиям подпрограммы или макроса в языках программирования.
Недетерминированность и неодновременность запусков переходов в моделировании параллельной системы показываются двумя способами. Один из них представлен на рис. 1.2. В этой ситуации два разрешенных перехода в любом случае не влияют друг на друга, и в число возможных последовательностей событий входит последовательность, в которой первым срабатывает один переход, и последовательность, в которой первым будет запущен другой переход. Это называется одновременностью.


Рисунок 1.2 - Одновременность
Другая ситуация, в которой одновременное выполнение затруднено и которая характеризуется невозможностью одновременного возникновения событий, показана на рис. 1.3. Здесь два разрешенных перехода находятся в конфликте. Может быть запущен только один переход, так как при запуске он удаляет фишку из общего входа и запрещает другой переход.


Рисунок 1.3 - Конфликт
1.4.1 ПРИМЕРЫ
Сетями Петри легко моделируется создание и выполнение параллельных ветвей различных вычислительных процессов. К примеру, на рис. 1.4 изображена одна из довольно популярных на сегодняшний день конструкций fork/join. Переход fork моделирует «разветвление» – создание из одной ветви выполнения двух параллельных ветвей. Это, как правило, реализуется путем создания одной дополнительной ветви вдобавок к существующей. Переход join, в свою очередь, осуществляет «слияние» двух ветвей по завершению их работы – уничтожение созданной параллельной ветви за ненадобностью.


Рисунок 1.4 - Конструкция fork/join
Используемые сегодня объекты синхронизации также легко моделируются сетями Петри. К примеру, на рис. 1.5 изображен фрагмент сети Петри, моделирующий барьерную синхронизацию трех процессов.



Рисунок 1.5 - Фрагмент сети Петри, моделирующий барьерную синхронизацию трех процессов
В начале работы сети разрешенными являются три длительных перехода, характеризующих выполнение некоторых подзадач. Три независимых процесса выполняют эти подзадачи, и лишь после их полного завершения становится разрешенным переход-барьер wait(all). После его срабатывания все три процесса снова продолжают свою работу.
Похожим образом может быть смоделировано ожидание завершения любой из подзадач, первой завершившей свое выполнение. К примеру, на рис. 1.6 показан такой фрагмент сети. При завершении выполнения любого длительного перехода становится разрешенным переход wait(any). После его срабатывания дальнейшая работа продолжается, в то время как остальные подзадачи завершают свое выполнение. Дополнительная входная позиция перехода wait(any) защищает его от срабатывания при завершении остальных подзадач в случае, если в текущий момент ожидание не выполняется. В процессе дальнейшей работы сети фишка в эту позицию возвращается, и тем самым разрешается ожидание и обработка результатов выполнения остальных подзадач.


Рисунок 1.6 - Фрагмент сети, моделирующий ожидание завершения любой из подзадач
Другой пример синхронизации параллельных процессов – критическая секция. Фрагмент сети на рис. 1.7 обеспечивает взаимоисключающий доступ к некоторому общему ресурсу для двух процессов.




Рисунок 1.7 - Фрагмент сети обеспечивает взаимоисключающий доступ к некоторому общему ресурсу для двух процессов
Первый же процесс, захвативший доступ к критической секции, лишит фишки соответствующую позицию res, тем самым запретив доступ к критической секции второму процессу до момента ее освобождения. В случае, когда в позиции res изначально более одной фишки, такой фрагмент сети моделирует использование семафора – объекта синхронизации, позволяющего одновременный доступ к ресурсу нескольких процессов в количестве не более заданного.
Важная особенность сетей Петри заключается в атомарности срабатывания перехода и, как следствие, возможности атомарного захвата одновременно нескольких ресурсов, что исключает взаимоблокировки процессов (dead lock).
1.5 СТРУКТУРА СЕТЕЙ ПЕТРИ
  Определение 1.1.1. Сеть Петри С является четверкой, С = (P,T,I,O). P = {p1, p2, … , pn} – конечное множество позиций, n ? 0. T = {t1, t2, … , tn} – конечное множество переходов, m ? 0.Множество позиций и множество переходов не пересекаются P 
T = ?. I отображает переход ti в множество позиций, I(ti) – I: T?P? - является входной функцией – отображением из переходов в комплекты позиций. O отображает переход tj в множество позиций O(tj), O: T ? P? - выходная функция – отображение из переходов в комплект позиций.
Комплект – обобщение множества, включающее многократно повторяющиеся элементы. Использование комплектов для представления входных и выходных функций позволяет позиции быть кратным входом либо кратным выходом перехода.
Кратность  входной позиции pi для перехода tj есть число появлений позиции во входной во входном комплекте перехода - #(pi,I(tj)). Аналогично кратность выходной позиции pi есть число появлений позиции в выходном комплекте перехода - #(pi,O(tj)). Если входная и выходная функции являются множествами (а не комплектами), то кратность каждой позиции есть либо 0, либо 1.
Входные и выходные функции используются для отображения позиций в комплекты переходов, а также их можно использовать для отображения переходов в комплекты позиций. Переход tjявляется входом позиции pi, если pi есть выход tj. Переход tj есть выход позиции pi, если pi есть вход tj.
Определение 1.1.2. Определим расширенную входную функцию I выходную функцию O 
I: P ? T?, O: P ? T?
таким образом, что #(tj , I(pi)) = #(pi , O(tj)), #(tj , O(pi)) = #(pi , I(tj)).
Пример 1. Для сети Петри, представленной на рисунке 1.8
С = (P, T, I, O),               I(t1) = {p1},                  O(t1) ={p2, p3, p5},
P = {p1, p2, p3, p4, p5},     I(t2) = {p2, p3, p5,};      O(t2) ={p5},
T = {t1, t2, t3, t4},              I(t3) = {p3},                  O(t3) ={p4},
                   I(t4) = {p4},               O(t4) ={p2, p3},
Рисунок 1.8- Структура сети Петри представлена в виде четверки, состоящей из множества позиций (P), множества переходов (T), входной функции I: P ? T? и выходной функции O: P ? T?.
 
 
 

 

расширенными входной и выходной функциями являются:
I(p1) = {     },      O(p1) = {t1},
I(p2) = {t1, t4},     O(p2) = {t2},
I(p3) = {t1, t4},     O(p3) = {t2, t3},
I(p4) = {t3},         O(p4) = {t4},
I(p5) = {t1, t2},     O(p5) = {t2}.
 
1.6    ГРАФЫ СЕТЕЙ ПЕТРИ
  Определение 1.2. Граф G сети Петри есть двудольный ориентированный мультиграф, G=(V, A), где V ={u1, u2, …, us} – множество вершин, а A = {a1, a2, …,  ar} – комплект направленных дуг, ai = (vj ,vk), где vj ,vk ? V. Множество V может быть разбито на два непересекающихся подмножества P и T, таких, что V = P 
T, P 
T = ?, и для любой направленной дуги ai ? A, если ai = (vj ,vk), тогда либо vj ? P и vk ? T, либо vj ? T P а vk ? P.
            В соответствии с этим граф сети Петри обладает двумя типами узлов: позиции и переходы.
Ориентированные дуги (стрелки) соединяют позиции и переходы, при этом некоторые дуги направлены от позиций к переходам, а другие – от переходов к позициям. Дуга, направленная от позиции рi к переходу tj, определяет позицию, которая является входом перехода. Кратные входы в переход указываются кратными дугами из входных позиций в переход. Выходная позицияопределяется дугой от перехода к позиции. Кратные выходы также представлены кратными дугами. При большом числе дуг – показывается одна дуга и указывается только их количество.
  Структура сети Петри определяется ее позициями, переходами, входной и выходной функциями.
События выражают действия, реализация которых управляет состояниями системы. Состояния задаются в виде сложных условий, формируемых в виде функций с переменными в виде простых условий.
Базовые понятия «Условие» и «Событие» могут быть связаны отношением типа «Выполняется после». Построение полной структуры таких отношений моделируемой проблемной ситуации составляет цель и задачу формирования структуры модели.
 1.7 МАРКИРОВКА СЕТЕЙ ПЕТРИ
  Наличие тех или иных условий в позициях определяется метками в этих позициях.
Определение 1.3.1. Маркировка ? сети Петри С = (P,T,I,O) есть функция, отображающая множество позиций P в множество неотрицательных целых чисел N:
?: P ?N.
Маркировка ? может быть также определена как n – вектор ? = (?1,?2,… , ?n), где n = ?P? и каждое ?i ? N, i=1, … , n. Вектор ? определяет для каждой позиции pi  СП количество меток (фишек) в этой позиции. Состояние СП задается ее маркировкой ?.
На графе сети Петри фишки изображаются маленькой точкой в кружке, который представляет позицию сети Петри.
Пример 2. На рис. 1.9 показана маркированная сеть Петри. Маркировка ? этой сети может быть представлена как n – вектор в виде: ? = (1, 2, 0, 0, 1)


Рисунок 1.9 –Маркированная сеть Петри
 
 Определение 1.3.2. Маркированная сеть Петри M =(C, ?) есть совокупность структуры сети Петри C = (P, T, I, O) и маркировки ? и может быть записана в виде M = (P, T, I, O, ?)
Так как количество фишек, которое может быть определено для каждой позиции, неограниченно, то в целом для сети Петри существует бесконечно много маркировок. Множество всех маркировок сети Петри, обладающей n позициями, есть множество всех n – векторов, Nn
 1.8  ПРАВИЛА ВЫПОЛНЕНИЯ СЕТЕЙ ПЕТРИ
  Выполнением сети Петри управляют количество и распределение фишек в сети. Фишки находятся в позициях и управляют выполнением переходов сети. Сеть Петри выполняется посредством запусков переходов. Переход запускается удалением фишек из его входных позиций и образованием новых фишек, помещаемых в его выходные позиции.
Переход может запускаться только в том случае, когда он разрешен. Переход называется разрешенным, если каждая из его входных позиций имеет число фишек по крайней мере равное числу дуг из позиции в переход. Кратные фишки необходимы для кратных входных дуг. Фишки во входной позиции, которые разрешают переход, называются его разрешающими фишками.
Определение 1.4. Переход tj ?T в маркированной сети Петри C = (P, T, I, O) с маркировкой ? разрешен, если для всех pi ?P
?( pi) ? #( pi, I(tj)).
Дополнительные фишки в позициях pi не влияют на запуск перехода (хотя они могут разрешать дополнительные запуски этого перехода).
Запуск перехода заменяет маркировку ? СП на новую маркировку ?./.
Переход tj в маркированной СП с маркировкой ? может быть запущен всякий раз, когда он разрешен. В результате запуска разрешенного перехода tj образуется новая маркировка ?./, определяемая следующим соотношением:
?./( pi) = ?( pi) - #(pi,I(tj)) + #(pi,O(tj)).  


Рисунок 1.9 - Сеть Петри с маркировкой
Пример 3. На рис. 1.9 показана маркированная сеть Петри, иллюстрирующая правила запуска переходов.
При такой маркировке разрешены только переходы: t1, t3 и t4. Переход t2 не разрешен, так как ни позиция р2, ни позиция р3, являющиеся входами перехода t2, не содержат ни одной фишки. Так как переходы t1, t3 и t4 разрешены, любой из них может быть запущен. Если запущен переход t4, то происходит удаление фишек из каждого входа и помещение фишки в каждый выход. При этом одна фишка удаляется из р5, одна фишка помещается в р3, а количество фишек в р4 увеличивается с двух до трех. Новая маркировка будет такой ?= (1, 0, 1, 3, 0). 
  1.9 ПРОСТРАНСТВО СОСТОЯНИЙ СЕТИ ПЕТРИ
Состояние сети Петри определяется ее маркировкой. Запуск перехода изменяет состояние СП посредством изменения маркировки сети. Изменение в состоянии, вызванное запуском перехода, определяется функцией изменения ?, которую мы назовем функцией следующего состояния. Когда эта функция применяется к маркировке ? (состоянию) и переходу tj, она образует новую маркировку (состояние), которая получается при запуске перехода tj в маркировке ?. Так как tj может быть запущен только в том случае, когда он разрешен, то функция ?(?, tj) не определена, если tj не разрешен в маркировке ?. Если же tj разрешен, то ?(?, tj) = ?/, где ?/ есть маркировка, полученная в результате удаления фишек из входов tj и добавления фишек в выходы tj.
Определение 1.5.1. Функция следующего состояния ? : Nn? T ? Nn для сети Петри C = (P, T, I, O) с маркировкой ? и переходом tj ? Т определена тогда и только тогда, когда ?(pi) ? #( pi,I(tj)) для всех pi ? Р. если ?(?, tj) определена, то ?(?, tj) = ?/ где ?/(pi) = ?(pi) - #( pi, I(tj)) + #( pi, О(tj)) для всех pi ? Р.
Пусть дана сеть Петри C = (P, T, I, O) с начальной маркировкой ?0. Эта сеть может быть выполнена последовательными запусками переходов. Запуск разрешенного перехода tj в начальной маркировке образует новую маркировку ?1 = ?(?0, tj). В этой новой маркировке можно запустить любой другой разрешенный переход, например tk, образующий новую маркировку ?2 = ?(?1, tk). Этот процесс будет продолжаться до тех пор, пока в маркировке будет существовать хотя бы один разрешенный переход. Если же получена маркировка, в которой ни один переход не разрешен, то никакой переход не может быть запущен, функция следующего состояния не определена для всех переходов, и выполнения сети должно быть закончено.
При выполнении СП получаются две последовательности: последовательность маркировок (?0, ?1, ?2, … ) и последовательность переходов, кото

Заказать эту работу прямо сейчас

Посмотреть другие готовые работы по предмету ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА

© 2002-2024 Москва 'Мастерская дипломов'. Все права защищены.