Реализация шаблонов потоков работ сетями Петри

Толстов Е.В. (tolstov@physicon.ru) МФТИ

Введение

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

Именно поэтому, в последнее время появилось множество продуктов, которые являются в основном либо отдельными системами управления потоками работ (workflow management systems), либо модулями, встроенными в инструментальные среды разработки информационных систем. Каждый продукт обычно базируется на своей парадигме, своей внутренней модели представления схемы процессов, а также определяет новый язык моделирования схемы потоков работ. Несмотря на усилия международной коалиции, специализирующейся на системах управления потоками работ (Workflow Management Coalition) [1] до сих пор не существует стандартов на языки моделирования, а также на сами модели. Коалиция описала лишь высокоуровневые интерфейсы, которым должна удовлетворять стандартная система управления потоками работ.

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

Спецификации потоков работ можно рассматривать в широком смысле в нескольких перспективах [2]. Структурная или процессная перспектива описывает активности и их порядок выполнения при помощи разных конструкций, которые осуществляют управление потоком

выполнения, то есть последовательное выполнение, выбор, параллелизм и синхронизация. Активности в элементарной форме представляют собой атомарные части работы, и в комбинированном состоянии моделируют порядок выполнения набора активностей. Перспектива данных относится к бизнес данным и внутренним данным процесса. Бизнес документы и другие объекты, которые передвигаются между активностями, локальные переменные потока работ влияют на пред- и постусловия выполнения активностей. Ресурсная перспектива обращается организационную структуру и ролевой модели для исполнения активностей. Операционная перспектива описывает элементарные действия, выполняемые активностью. Эти действия при выполнении вызывают функции у нижележащих приложений. Даже без формального определения, различные особенности разных языков описания схем потоков работ указывают на фундаментально разную семантику. Некоторые языки позволяют нескольким экземплярам находиться в одной активности в одно и тоже время в одном контексте потоков работ, в то время как другие не позволяют. Некоторые языки позволяют структурировать циклы только с одной входящей и одной исходящей активностью, в то время как другие могут задавать произвольные циклы. Такие различия указывают на различное понимание пригодности и различные уровни выразительной мощности.

Для применения формального подхода к определению уровня выразительной мощности языка в работе [3] было предложено следующее: выделить полезные, часто используемые конструкции управления в схемах потоков работ с точки зрения требований пользователей таких систем, то есть бизнес требований, а не производителей. Такие конструкции названы шаблонами (patterns) по аналогии с шаблонами разработки (design patterns), которые активно применяются в программировании. Как определено в [4], шаблоном называется абстракция от конкретной формы, которая часто встречается в определенных контекстах . Эрих Гамма и другие [5] впервые систематически каталогизировали 23 шаблона, которые описывают минимальные повторяющиеся взаимодействия в объектно-ориентированных средах. Шаблоны разработки, как таковые, предоставляют независимость от технологии реализации. Аналогично были введены шаблоны в процессах потоков работ. Выразительная мощность того или иного языка определяется способностью языка воспроизвести тот или иной шаблон. В этом контексте языки можно сравнивать друг с другом. Заметим, что шаблоны, определенные в [3], относятся к структурной перспективе. Далее, этими же авторами был предложен способ сравнения выразительности систем управления потоками работ при помощи шаблонов данных (workflow data patterns [6]).

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

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

Шаблоны потоков работ

Помимо работы [3], шаблонам потоков работ посвящен специализированный ресурс в Интернете (http: www.workflowpatterns.com), на котором можно посмотреть не только определения шаблонов, но и их визуальное представление. Шаблоны варьируются от очень простых, таких как последовательная маршрутизация (Шаблон 1), до сложных, требующих сложной синхронизации, как, например, шаблон дискриминатор (Шаблон 9). Традиционно шаблоны делятся на несколько групп, каждая из которых относится к определенному аспекту моделирования процесса.

Базовые шаблоны потоков управления.

Это основные конструкции, которые присутствуют в большинстве языков потоков работ для моделирования последовательной, параллельной и условной маршрутизации. Базовые шаблоны включают в себя:

Последовательность (Шаблон 1)

Параллельное расщепление (Шаблон 2)

Синхронизация (Шаблон 3)

Эксклюзивный выбор (Шаблон 4)

Простое соединение (Шаблон 5) Расширенные шаблоны ветвления и синхронизации.

Эти шаблоны расширяют базовые до более сложных случаев разветвления и объединения. Примером может служить синхронизирующее соединение (Шаблон 7), который действует либо как XOR-слияние либо как AND-слияние, в зависимости от контекста. Эта группа состоит из следующих шаблонов:

Множественный выбор (Шаблон 6)

Синхронизирующее соединение (Шаблон 7)

Множественное соединение (Шаблон 8)

Дискриминатор (Шаблон 9) Структурные шаблоны.

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

Произвольные циклы (Шаблон 10)

Явное завершение (Шаблон 11)

Шаблоны, включающие множественные экземпляры.

В контексте одного экземпляра процесса, иногда требуется запустить некоторые части процесса несколько раз:

Несколько экземпляров без синхронизации (Шаблон 12)

Несколько экземпляров с априорным знанием во время проектирования (Шаблон 13)

Несколько экземпляров с априорным знанием во время выполнения (Шаблон 14)

Несколько экземпляров без априорного знания во время выполнения (Шаблон 15)

Шаблоны, которые базируются на состоянии.

Типичные системы проектирования бизнес процессов обычно фокусируются только на активностях, а не на состояниях. Это сильно ограничивает выразительную силу системы, так как невозможно применять такой шаблон, как например веха (Шаблон 18):

Отложенный выбор (Шаблон 16)

Чередующаяся параллельная маршрутизация (Шаблон 17)

Веха (Шаблон 18)

Шаблоны отмены.

Возникновение события (например, подтверждение ордера), может привести к отмене активностей. В некоторых сценариях некоторые события даже могут привести к отмене всего экземпляра:

Отмена активности (Шаблон 19)

Отмена экземпляра (Шаблон 20)

Использование сетей Петри для моделирования

Рассмотрим, какой выразительностью может обладать язык моделирования потоков работ, основанный на высокоуровневых сетях Петри. В работе [7] представлены преимущества и недостатки использования этого формализма в качестве языка моделирования потоков работ. Использование сетей Петри выгодно, как минимум, по следующим причинам:

1. Формальная семантика, не смотря на графическое представление.

2. Помимо событий, сети используют понятия состояния.

3. Большое множество технологий анализа.

В той же работе, однако, показывается, что при помощи данного формализма не удается смоделировать все шаблоны. На самом деле это не совсем так (реализация шаблонов будет показана в следующем разделе). Сети Петри не поддерживают явной реализации той или иной конструкции, однако при моделировании, разработчик схемы процесса может искусственно реализовать все бизнес случаи. Также система, построенная на основе этого формализма, может расширить функциональность и обеспечить реализацию всех шаблонов. Для решения этой проблемы в работе [8] вводится язык, базирующийся на сетях Петри, но позволяющий реализовать все шаблоны (разве что за исключением одного). Этот язык назван YAWL (Yet Another Workflow Language - еще один язык моделирования потоков работ) [8], который создан специально с целью покрыть все.

С точки зрения дизайнера, язык, основанный на высокоуровневых сетях Петри, а также и YAWL является все же достаточно низкоуровневым. Поэтому их использование не всегда удобно для конечного пользователя - разработчика схем процессов. Язык описания бизнес процессов, использующийся в модуле управления потоками работ, встроенном в платформу по созданию корпоративных информационных систем Competentum[9] компании ФИЗИКОН, является более высокоуровневым, но, тем не менее, построен на основе формализма сетей Петри. Также в этом языке возможна реализация всех шаблонов (тем самым, обеспечивая высокую выразительную мощность) за счет применения именно сетей Петри. Рассмотрим, каким образом можно осуществить это моделирование на примерах наиболее сложных с точки зрения реализации шаблонов.

Реализация сложных шаблонов

Многие шаблоны реализуются сетями Петри достаточно просто, однако есть несколько сложных случаев (в работе [7] они представлены даже как невозможные). Покажем, каким образом их можно реализовать. Мы выбрали следующие шаблоны:

Множественный выбор (Шаблон 6)

Синхронизирующее соединение (Шаблон 7)

Дискриминатор (Шаблон 9)

Множественные экземпляры с априорным знанием во время выполнения (Шаблон 14)

Множественные экземпляры без априорного знания во время выполнения (Шаблон 15)

Чередующаяся параллельная маршрутизация (Шаблон 17)

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

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

сание шаблона (его определение), и путь реализации сетями Петри (с краткими комментариями).

Шаблон 6. Множественный выбор (Условная маршрутизация, ИЛИ-выбор)

Описание: Точка в процессе потоков работ, в которой на основе решения или данных процесса, выбирается несколько веток.

Реализация: Для имплементации данного шаблона, обратимся к рис. 1а. После выполнения активности A будет выбрана либо активность С, либо активность B либо и та, и другая, порождая при этом параллельные потоки. Это решение будет принято в зависимости от условий, которые сосредоточены в этих активностях. Если условие не срабатывает, тогда нам необходимо избавиться от меток, иначе мы не придем к конечному состоянию (получим тупик). Для избавления от этих меток можно поступить разными способами. В работе [10] было предложено ввести булевские метки. То есть, если условие выполняется, то продвигается метка, со значением True (истина). В противном случае продвигается метка со значением False (ложь). Также, в данном шаблоне можно на каждое условие добавить анти-условие, которое ведет в конечную позицию сети. Но как будет показано далее, для реализации шаблона 7 необходимо применить либо механизм булевских меток, либо поступить как показано на рис 1б. В случае анти-условия, мы строим параллельную ветвь, которая содержит активности (переходы), срабатывающие автоматически, когда они становятся активными (мы их пометили белыми прямоугольниками). То есть, метка будет продвигаться до тех пор, пока не встретиться конструкция синхронизации.

Рис. 1. Множественный выбор: а) общая схема, б) реализация сетями Петри Шаблон 7. Синхронизирующее соединение

Описание: Точка в процессе потоков работ, в которой несколько путей сходятся в один единственный поток. Если задействован более чем один путь, применяется синхронизация активных потоков. Если задействован только один поток, альтернативные ветви сходятся без синхронизации. Данный шаблон предполагает, что ветвь, которая уже была активирована, не может быть активирована вновь, пока соединение все еще ожидает завершения других ветвей.

Реализация: В работе [7] показано, что данный шаблон нереализуем высокоуровневыми сетями Петри. Это аргументируется тем, что в сетях Петри каждая конструкция слияния является AND-объединением (переход) либо XOR-объединением (позиция). Тем не менее, можно реализовать шаблон несколькими способами. Прежде всего, возможно передать информацию от вершины разветвителя к вершине объединения. Это можно сделать, продвигая метку по невыбранной ветви к синхронизатору. Во-вторых, можно использовать булевские метки. В-третьих, возможно построить новый вид правил срабатывания переходов, например такое:

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

Рис. 2. Синхронизирующее соединение Шаблон 9. Дискриминатор

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

Реализация: Данный шаблон является одним из самых сложных в реализации. Он явно реализован в очень ограниченном количестве продуктов. Языки композиции web служб вообще не поддерживают данный шаблон. На самом деле, он является очень важным. Например, одна система запрашивает определенную информацию на поисковых серверах. Интересует лишь результат с сервера, который вернет ответ первым. Остальные должны быть проигнорированы. Более того, этот шаблон позволяет реализовать конструкцию вида n из m (рис. 3). То есть из входящих n ветвей требуется ожидать первые m (при этом n>m). В работе [7] говорится, что шаблон не реализуем сетями Петри. В действительности, это не совсем так. Для этого придется ввести дополнительную позицию p1, в которую будет помещаться метка после разветвления. Она поможет сработать активности E только один раз. Заполнение меткой этой активности необходимо осуществить в AND-разветвлении, для того чтобы дискриминатор корректно выполнился при повторном использовании. Также, необходимо добавить автоматическую активность F, которая будет очищать позицию p2 от меток (перемещать их в конечную позицию, для избегания тупиков). При этом необходимо выставить приоритет у перехода E больший чем у перехода F. Очевидно, что таким образом использовать дискриминатор становится достаточно неудобно, конструкция становится весьма громоздкой. Однако, если применять более высокоуровневый язык, который будет скрывать такую сложную реализацию от разработчика процессов, то шаблон будет легким в использовании.

а) 6)

Рис. 3. Дискриминатор: а) Пример использования дискриминатора для реализации случая 2 из 3; б) Дискриминатор в нотации сетей Петри Шаблон 14. Множественные экземпляры с априорным знанием во время выполнения

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

Реализация: Этот шаблон достаточно сложно реализовать. Трудность заключается в невозможности определить количество экземпляров данной активности в момент разработки - это число становится известным лишь в момент выполнения. Рассмотрим рис. 4а. Активность, которая должна быть выполнена несколько, раз обозначена переходом A. Переход B является конструкцией типа AND-разветвление. После его выполнения одна фишка попадает в позицию p3 другая вновь в p1. В позиции p3 будет происходить накопление меток. Ни переход D, ни переход E не сработают, пока пуста позиция p4. В позиции p1 происходит проверка условия - счетчик выполнений перехода A совпал ли с заданным количеством. Как только это условие становится выполнимым, срабатывает переход C. Тем самым становится активным переходы D и E, но у перехода E меньший приоритет (он будет срабатывать только, когда не будет возможности сработать переходу D). После каждого срабатывания перехода D количество меток в позиции p3 будет уменьшаться на одну, пока их количество не уменьшится до одной. После чего сработает переход E, который является следующей выполняемой активностью после активности A.

Шаблон 15. Множественные экземпляры без априорного знания во время выполнения

Описание: Для одного экземпляра процесса некоторая активность выполняется несколько раз. Количество экземпляров данной активности для данного экземпляра процесса неизвестно во время выполнения. После очередного выполнения активности может приниматься решение о запуске очередного потока управления, который активирует эту активность вновь. Реализация: Реализация очень схожа с реализацией шаблона 14 (рис. 4б), за исключением того, что счетчик количества экземпляров не ведется, а решение принимается пользователем или системой после каждого выполнения активности A. Если принято решение продолжить выполнение той же активности, то срабатывает переход C (AND-расщепление) и еще один экземпляр активности A будет активирован. После того, как будет принято решение о том, что активность A больше не должна выполняться, срабатывает механизм, как и в шаблоне

а=<3

Рис. 4. Множественные экземпляры: а) априорным знанием во время выполнения, б) без априорного знания

Шаблон 17. Чередующаяся параллельная маршрутизация (неупорядоченное выполнение)

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

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

Рис. 5. Неупорядоченное выполнение при помощи взаимного исключения

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

Литература

1. Workflow Management Coalition. http: www.wfmc.org

2. W.M.P. van der Aalst and K.M. van Hee. Workflow Management: Models, Methods, and Systems. MIT press, Cambridge, MA 2002.

3. W.M.P. van der Aalst, A.H.M. ter Hofstede, B. Kiepuszewski, and A.P. Barros. Workflow Patterns. BETA Working Paper Series, WP 47, Eindhoven University of Technology, Eindhoven, 2000.

4. D. Riehle and H. Zullighoven. Understanding and Using Patterns in Software Development. Theory and Practice of Object Systems, 2(1):3-13, 1996.

5. E. Gamma, R. Helm, R. Johnson, and J. Vlissides. Design Patterns: Elements of Reusable Object-Oriented Software. Professional Computing Series. Addison Wesley, Reading, MA,

USA, 1995.

6. Nick Russell, Arthur H.M. ter Hofstede1, David Edmond, W.M.P. van der Aalst. Workflow Data patterns. QUT Technical report, FIT-TR-2004-01, Queensland University of Technology, Brisbane, 2004.

7. W.M.P. van der Aalst and A.H.M. ter Hofstede. Workflow Patterns: On the Expressive Power of (Petri-net-based) Workflow Languages. In K. Jensen, editor, Proceedings of the Fourth Workshop on the Practical Use of Coloured Petri Nets and CPN Tools (CPN 2002), volume 560 of DAIMI, pages 1-20, Aarhus, Denmark, August 2002. University of Aarhus.

8. W.M.P. van der Aalst and A.H.M. ter Hofstede. YAWL: Yet Another Workflow Language. QUT Technical report, FIT-TR-2002-06, Queensland University of Technology, Brisbane,

2002.

9. Competentum Enterprise Platform. http: www.competentum.ru

10. P. Langner, C. Schneider, and J.Wehler. Petri Net Based Certification of Event driven Process Chains. In J. Desel and M. Silva, editors, Application and Theory of Petri Nets 1998, volume 1420 of Lecture Notes in Computer Science, pages 286-305. Springer-Verlag, Berlin, 1998.