Применение аппарата сетей Петри

2. Программируемые устройства компьютерных сетей имеют несколько источников входных задач. Ввод кадра информации
из каждого КС может рассматриваться в устройстве как
начало задачи по обработке данного кадра (пакета) информации. Аналогичным образом можно выделить задачи вывода информации в КС, приема информации от устройств ввода — вывода, обработки команд оператора устройства. Таким образом, программное устрой­ство должно одновременно работать с рядом задач, эффективно распределяя при этом свои ресурсы, ограниченность которых (вычислительная мощность, емкость ОЗУ, пропускная способность КС, УВВ и магистралей) явля­ется причиной конкуренции задач за данные ресурсы.

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

Таким образом, даже в простейшем случае устройст­ва компьютерных сетей являются устройствами с несколькими парал­лельными процессами (ввод кадров из КС, вывод кад­ров в КС, ввод с УВВ, вывод на УВВ, обмен с операто­ром, обработка пакетов и т.д.).

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

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

Сказанное позволяет рассматривать компьютерные сети как системы, функционирующие в РМВ с множеством асинхронных параллельных процес­сов и конкуренцией между процессами за ограниченные внутренние ресурсы. Для описания и анализа систем с асинхронны­ми параллельными процессами предложено к настоящему времени более 25 моделей, большинство из которых разработано в рамках теории параллельного про­граммирования. Наиболее общими из данных моделей являются схемы параллельных программ Карпа — Миллера и А-программы Котова — Нариньяни. Такие же мо­дели, как параллельные операторные схемы, счетчиковые схемы, бесповторные схемы, а также различные вариан­ты потоковых схем (сети Дейвиса, схемы Родригеса, схе­мы Адамса, потоковые схемы Карпа — Миллера и др.), являются подклассами схем Карпа — Миллера.

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

Наибольшее распространение среди абстрактных мо­делей в начале 70-х годов получили билогические графы ,(UCLA-графы), представляющие собой ориентированный граф, вершины которого соответствуют операторам па­раллельной программы, а дуги — управляющим или ин­формационным связям между операторами. С каждой вершиной связаны входное и выходное управления, ко­торые могут быть двух типов — конъюнктивным или или дизъюнктивным.

На рис 2.8 показан фрагмент биологического графа, где операция * обозначает конъюнктивное, а + - дизъюнктивное управление. Вершинам и дугам графа в такой модели приписываются веса- времена выполнения операторов передачи данных. Кроме того, каждой дуге из операторов с дизъюнктивным выходным управлением могут быть приписаны вероятности перехода по этой дуге.

Рис. 2.8. Пример биологического графа

К концу 70-х годов билогические графы и аналогичные им модели были практически вытеснены сетями Петри— самым распространенным в на­стоящее время формализмом, описы­вающим структуру и взаимодействие параллельных систем и процессов. Теория сетей Петри развивается в не­скольких направлениях, среди которых — математическая теория сетей, структурная теория сетей, приложения к задачам параллельного программирования, применение сетей Петри как основы для создания моделей дискрет­ных динамических систем (в том числе и вычислитель­ных систем).

Среди достоинств аппарата сетей Петри можно ука­зать следующие:

1. Сети Петри позволяют моделировать асинхронность и недетерминизм параллельных независимых со­бытий, параллелизм конвейерного типа, конфликтные взаимодействия между процессами.

2. Как математическая модель сети Петри занимают промежуточное положение между конечными автомата­ми и машинами Тьюринга. При этом по выразительной мощности они значительно богаче автоматов и прибли­жаются к машинам Тьюринга.

3. Сети Петри включают возможности ряда других моделей, предложенных для параллельных систем (сема­форы Дийкстры, системы векторного сложения и вектор­ного замещения, вычислительные схемы, модели повтор­но используемых ресурсов и др.), позволяя описывать как типовые ситуации в данных системах (распределение ресурсов, взаимные блокировки), так и общую динамику работы сложной асинхронной системы.

4. Стремление расширить применимость аппарата се­тей Петри привело в последние годы к появлению ряда классов сетей, ориентированных на моделирование слож­ных систем с учетом таких факторов, как приоритет­ность процессов (сети с проверкой на нуль, приоритет­ные сети), временные параметры событий (сети Мерлина, временные сети), совместного отображения структуры управления и потоков данных (Е-сети).

5. В отличие от моделей параллельных программ (та­ких, как А-программы, схемы Карпа — Миллера и др.) сети Петри допускают произвольную интерпретацию эле­ментов модели как в смысле типа выполняемого фраг­мента (выражения, операторы, подпрограммы, аппарат­ные функциональные преобразования информации), так и по уровню абстракции. Таким образом, сети Петри позволяют производить иерархическую детализацию про­граммных и аппаратных подсистем модели.

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

Рассмотрим основные элементы аппарата сетей Пет­ри. Формально сеть Петри задается как

N = (В, D Ф, H), ( 2.1)

где В — конечное множество символов, называемых пози­циями, В0; D — конечное множество символов, назы­ваемых переходами, D0; BD = ; Ф : BD{0,1} — прямая функция инцидентности; Н: DB{0,1} —об­ратная функция инцидентности.

Указанные четыре множества определяют структуру сети Петри. Такое задание удобно для формального рас­смотрения, но не обладает наглядностью, поэтому сеть Петри обычно представляют двудольным графом со мно­жеством вершин BD (рис. 2.9). Вершины-позиции изо­бражаются кружками, а вершины-переходы — черточками. Из вершины-позиции bi в вершину-переход di ведет дуга, если и только если Ф(; из вершины-пере­хода в вершину-позицию ведет дуга, если и только если H(. Для каждого перехода D можно определить множества входныx позиций перехода Ф и выходных позиций перехода Нкак:

;

,(2.2)

где i =; .

Рис. 2.9. Графовое пред­ставление сети Петри

Аналогичным образом вво­дятся определения множества входных переходов позиции bi—H(вt) и множества выход­ных переходов данной позиции Ф(bi):

;

. (2.3)

Так, например, сеть Петри на рис. 2.9 может быть фор­мально представлена как

N = (В, D Ф, H );

;

;

Наибольшее применение сети Петри нашли для моделирования систем с дискретными событиями, которые могут происходить одновременно и параллельно. При моделировании отражаются два аспекта систем: события и условия. Позиции сети соответствуют условиям, а переходы – событиям. Функции инцидентности отражают связи между условиями и событиями в системе.

Приведенное выше определение сети Петри может ис­пользоваться только для отражения статики моделируе­мой системы (взаимосвязи событий и условий), но не по­зволяет моделировать динамику функционирования. Для представления динамических свойств вводится функция разметки (маркирования) сети

М:В{0,1,2,...}.

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

Сеть Петри функционирует, переходя от разметки к разметке. Начальная разметка сети обозначается как М₀ :В{0,1,2,...}. Смена разметок происходит в результате срабатывания одного из переходов сети. Необходи­мым условием срабатывания перехода является где — разметка пози­ции bi.

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

Срабатывание перехода d_j- изменяет разметку сети M(b) = (M(b_]), M(b₂), ..., M(bi), ..., M{b_n)) на разметку М^’ (b) по следующему правилу:

,

т. е. переход d_j изымает по одной метке из каждой своей входной позиции и добавляет по одной метке в каждую из выходных позиций. Для изображения смены разметки М на М' применяют обозначение М М'.

Сеть Петри, в которой используется функция размет­ки, называют размеченной сетью Петри и задают набором

N_M = (В, D, Ф, H, М₀), (2.4)

где М₀ — начальная разметка сети.

На рис. 2.10, а приведена размеченная сеть Петри с М₀={1, 0, 0, 0, 1, 0, 1). При такой начальной разметке единственным готовым к срабатыванию переходом яв­ляется переход d₂. Срабатывание его ведет к смене раз­метки

М₀ М₁, где М₁={0,1,1,0, 1, 0, 1} (рис. 2.10,б). При разметке M₁ возможно срабатывание трех перехо­дов— d₁, d₃ и d₅. В зависимости от того, какой из пере­ходов сработал первым, получается одна из трех возможных новых маркировок (рис. 2.10, в, г, д). Функциониро­вание сети Петри продолжается до тех пор, пока существует хотя бы один возможный переход.

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

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

Рис. 2.10. Пример функционирова­ния размеченной сети Петри

Модель на основе сети Петри дает возможность ана­лиза системы на наличие желательных или нежелатель­ных свойств. Основные направления анализа для обыч­ных сетей Петри следующие.

1. Проблема достижимости. В заданной сети N_M с начальной разметкой М₀ требуется решить вопрос, до­стижима ли принципиально некоторая разметка М' из М₀. В приложении к моделированию систем эта проблема ин­терпретируется как возможность достижения определен­ного состояния системы. При анализе используется поня­тие множества всех достижимых в N_M разметок, которое обозначают R (N_M).

2. Свойство живости. Под живостью перехода сети Петри понимают принципиальную возможность его сра­батывания в некоторой N_M при начальной разметке М₀. Сеть Петри определяется как живая, если все ее пере­ходы живые. Анализ модели на свойство живости позво­ляет выявить неживые переходы, т. е. невозможные со­бытия в моделируемой системе.

3. Ограниченность сети. Позиция b_i в N_M называется к-ограниченной, если существует такое целое число к, что M(bi)k для любой разметки М в R(N_M). Если в N_M для MR(N_M),то есть N_M на­зывается к-ограниченной.

4. Безопасность сети. Сеть N_M называется безопасной,
если выполняется условие M(b)R(N_M){ .То есть безопасной является такая сеть Петри, у которой ни при каких условиях не может появиться более одной метки в каждой из позиций (k-ограниченность равна 1).

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

5. Свойство сохранения. Сеть N_M называется сохраня­ющей, если =const для M(b)R(N_M). Этим свойством N_M может обладать только в том случае, ко­гда . Другое определение свойства со­хранения использует веса позиций . В этом случае сеть N_M является сохраняющей, если= const для M(b)R(N_M). Анализ модели на сохране­ние тогда важен, когда под динамическими объектами (метками) понимаются какие-либо неизменные ресурсы системы.

Сеть Петри может рассматриваться как форма зада­ния некоторого формального языка. Для этого вводится функция индексирования переходов сети Петри , где — алфавит формального языка. Функция при­сваивает каждому переходу , где некоторый символ из . Последовательность срабатывания переходов опре­деляется как слово из множества * всех слов в алфа­вите . Множество всех возможных слов, связанных с функционированием размеченной индексированной сети Петри, определяет язык сети Петри

. (2.5)

Языки сетей Петри могут служить средством формаль­ного представления протоколов обмена информацией, что, в свою очередь, используется как для моделирования данных протоколов, так и для их реализации в микро­процессорных устройствах СПИ.