Моделирование программно-аппаратных "реактивных" систем раскрашенными сетями Петри

Всеволод Шахов
© 2006
г. Долгопрудный

В статье рассматривается ряд вопросов, связанных с моделированием программно-аппаратных архитектур систем реального времени, имеющих множество параллельно выполняемых однотипных процессов. В качестве инструмента моделирования раскрашенными сетями Петри (Coloured Petri Net) используется программа CPNTools.

Особенности "реактивных" систем

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

"Реактивными" системами обычно являются программно-аппаратные комплексы, где аппаратная составляющая используется для согласования управляющей (программной) логики с реальной средой (механизмы, датчики и т.п.). Часто для повышения производительности таких систем или в целях получения независимости работы их подсистем применяют параллельное выполнение задач, как на программном, так и на аппаратном уровне.

Отличительными чертами этих систем является:

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

Для разработчика важнейшими задачами анализа при этом является:

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

В настоящее время у разработчиков программного обеспечения достаточно устойчиво укрепилось осознание необходимости представления архитектуры разрабатываемого проекта в виде разнообразных диаграмм, отражающих как статическую, так и динамическую составляющую системы. Фактически, в этом вопросе унифицированный язык моделирования UML (Unified Modelling Language) занял лидирующие позиции. Это связано с тем, что он предоставляет достаточный набор диаграмм для описания различных ракурсов системы. С помощью диаграмм UML можно описать и "реактивные" системы, но на довольно высоком уровне, что для анализа вышеперечисленных проблем не подходит. На диаграмме состояний, имеющихся в UML, невозможно показать, например, взаимодействие параллельных процессов и, следовательно, исследовать коллизии (в т.ч. временные). Также нет возможности наглядного представления процесса захвата разделяемых ресурсов разными процессами.

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

Раскрашенные (цветные) сети Петри (РСП)

Теория раскрашенных сетей Петри (Coloured Petri Net, CP-net) разрабатывается более 20 лет рабочей группой (CPN Group) университета г.Орхуса (University of Aarhus, Denmark) под руководством профессора Курта Йенсена (Kurt Jensen). Ими разработана основная модель, включающая использование типов данных и иерархических конструкций, определены концепции динамических свойств, развивается теория методов анализа.

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

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

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

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

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

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

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

Рис. 1. Пример раскрашенной сети Петри

На рисунке 1 представлена РСП, отражающая процесс захвата-освобождения разделяемого ресурса множеством однотипных процессов. Выделенный переход является активным для текущей итерации выполнения РСП. Состояние системы включает в себя состояния ресурса, процесса и таймера. Состояния ResourceFree(РесурсСвободен) и ResourceBusy (РесурсЗанят) имеют цвет, состоящий из пары (k,n) (НомерРесурса, НомерПроцессаЗахватившегоРесурс). Вторая переменная необходима для последующей идентификации ресурса при его освобождении. Состояния процесса Wait(Ожидание), ResourceUse (РесурсИспользуется) и ReadyFreeResource (ГотовОсвободитьРесурс) имеет цвет типа Integer, содержащий номер текущего рабочего процесса (может идентифицировать, например, физический объект). Состояние Timer2c (ТаймерНа2с) типа Boolean служит для моделирования задержки, принимая от перехода CatchResource (ЗахватРесурса) фишку с временным штампом. В соответствии с позициями (состояниями) фишки имеют свой цвет, отражая текущее состояние системы. На диаграмме компоненты цветов фишек представлены в прямоугольнике в непосредственной близости от позиций, в кружочке показано их общее число у данной позиции. Блок объявления множеств цветов и переменных выглядит следующим образом:

 colset INT = int timed;
 colset BOOL = bool timed;
 colset RES_INFO = product INT*INT;
 var n,k: INT;

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

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

Для рассматриваемого примера, при первой итерации две фишки, отражающие выполнение процесса переместятся в состояние ResourceUse, две фишки появятся в позиции Timer2c, и две фишки, представляющие ресурс - в позиции ResourceBusy, изменяя при этом элемент цвета, указывающий номер процесса, захватившего ресурс. После этого, переход CatchResource сработать не сможет, так как нет фишки в позиции ResourceFree (свободного ресурса). Не разрешен также переход ResourceWorked (РесурсВРаботе), из-за того, что фишка, имитирующая таймер несет временной штамп, равный 2000, а текущее значение глобальных часов равно 0. В случае, если установлено, что нет доступных переходов, происходит наращивание счетчика глобальных часов до тех пор, пока не "откроется" переход ResourceWorked, так как штамп фишки в позиции Timer2c окажется равен значению глобальных часов. В результате, начнется освобождение ресурсов, посредством срабатывания перехода ResourceWorked, отвечающего за условие временной задержки и перехода FreeResource, осуществляющий имитацию освобождения ресурса путем проведения операции сравнения для идентификации фишки ресурса, несущей номер процесса, который использует данный ресурс. Таким образом, позиция ResourceFree приобретает две фишки и переход CatchResource активизируется, перемещая следующую фишку процесса на позицию ResourceUse. После наращивания часов до значения 4000 (порождаемая переходом CatchResource фишка таймера будет нести штамп текущего времени, равное 2000) станут последовательно доступны переходы ResourceWorked и FreeResource. Дальнейшая работа сети прекращается, так как не остается фишек в позиции Wait.

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

Пример построения РСП для абстрактной системы

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

Рис. 2. Временная диаграмма работы одного процесса

Последовательность обработки выходных команд и входных сигналов выглядит следующим образом:

1. Включаются n каналов. Тем самым они готовы к выполнению описанной ниже процедуры.
2. Логика системы находит первый ожидающий канал и пытается захватить свободный ресурс типа A (всего таких ресурсов m).
3. Если ему это удается, то он пытается захватить ресурс типа Б (всего их k, при этом соблюдается неравенство n>m>k).
4. После того, как ресурсы задействованы, начинается выполнение временной диаграммы. Ресурс А при этом может быть захвачен, но отработка временной диаграммы начнется только после задействования ресурса Б.
5. На интервале 1,5 - 2 с система ожидает от канала ответного сигнала ОК1.
6. По истечению 2 с ресурс типа Б освобождается.
7. На временной отсечке 3 с система ожидает прихода сигнала ОК2.
8. Спустя время 5 с освобождается ресурс типа А. Считается, что канал отработал.
9. В случае отсутствия одного из ответных сигналов, система должна освободить занятые этим каналом ресурсы и начать работу со следующим каналом.

Рис. 3. РСП для моделирования абстрактного устройства

На рисунке 3 представлена РСП, построенная по описанному выше алгоритму. По мере продвижения фишек, несущих номер канала, происходит последовательный захват свободных ресурсов А и Б, при этом фишки ресурсов перемещаются в позиции ResАFree (РесурсАСвободен) и ResBFree (РесурсБСвободен). После того, как канал "вышел" на выполнение временной диаграммы фишками заполняются позиции-таймеры, обеспечивающие затем перемещение фишек процессов по временным отсечкам, путем разрешения срабатывания переходов по глобальным часам.

Зафиксирована разметка сети на временной отсечке глобальных часов, равной 5000. Первоначальная разметка предполагает наличие четырех фишек (представляющих каналы) в позиции WaitCatchA (ОжиданиеЗахватаРесурсаА), трех фишек в позиции ResAFree (РесурсАСвободен) и двух фишек в позиции ResBFree (РесурсБСвободен).

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

Рассмотренная РСП полностью моделирует временные характеристики, что делает доступным проверку динамических характеристик системы при отработке множества каналов. Но несмотря на это, не решает проблемы анализа работы при отказных ситуациях, например, в случае отсутствия сигнала ОК1 или ОК2. Искусственное создание таких ситуаций может подчиняться предопределенным сценариям (с целью проверки конкретного "узкого" места) или обладать свойством случайности (что полезно для выявления общих проблем архитектуры).

Рис. 4. Пример части РСП для имитации отказных ситуаций

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

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

В случае присутствия нескольких фишек в позиции и разрешенном переходе, через него может "проходить" любая из фишек, т.е. отсутствует приоритет их выбора. Для рассматриваемого абстрактного устройства, например, может накладываться ограничение, вследствие которого необходимо работать с каналами по возрастанию их номеров. Решением этой задачи может являться ввод в РСП специальной позиции-счетчика с фишкой, несущей номер следующей разрешенной фишки основного процесса. При этом необходимо позаботиться, чтобы фишки процесса имели в одной из компонент своего цвета уникальный идентификатор, по которому в переходе срабатывает условие разрешения. На рисунке 5 продемонстрирован механизм работы такого подхода.

Рис. 5. РСП для имитации очереди

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

Заключение

Основным свойством сетей Петри, описывающие системы, является их способность отражать динамические характеристики моделей. Для этого проектировщику необходимо иметь программный инструмент, способный интерактивно вводить данные о позициях, переходах и дугах, описывать множества цветов, отражать процесс перемещения фишек. Одним из свободно распространяемых программных продуктов, позволяющий проводить указанные выше операции (а также ряд дополнительных) является программа CPNTools (http://cpntools.org/), разработанная в университете г.Орхуса (Дания). Программный продукт постоянно развивается и сопровождается группой, которая разрабатывает теорию раскрашенных сетей Петри.

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

Литература

1. Верификация Estelle-спецификаций распределенных систем посредством раскрашенных сетей Петри.// Под ред. Непомнящего В.А., Шилова Н.В. - Новосибирск,1997.

2. Гома Х. UML.Проектирование систем реального времени, параллельных и распределенных приложений. Пер.с англ. - М.ДМК Пресс 2002 704 с.

3. Котов В.Е. Сети Петри. - М.:Наука,1984.

4. Питерсон Дж. Теория сетей Петри и моделирование систем. - М.:Мир,1984.

5. Шалыто А.А. Алгоритмизация и программирование для систем логического управления и "реактивных" систем. - Автоматика и телемеханика, 2000, №1, с.3-39.

6. Jensen K. Introduction to the practical use of coloured Petri nets -\\ URL:http://www.daimi.au.dk/~kjensen/

7. Kristensen Lars M., Christensen S., Jensen K. The practitioner's guide to Coloured Petri Nets - Springer-Verlag,1998.

8. Netjes M, etc. Analysis of resource-constrained processes with Coloured Petri Nets - Eindhoven University of Technology, Netherlands.