О поиске эквивалентных ресурсов в сложных системах

Размещено на http://www.allbest.ru/

О поиске эквивалентных ресурсов в сложных системах

Башкин В.А., Ломазова И.А.

A new formal method for analysis of complex resource-dependent systems is presented. Resources are modeled by multisets of tokens in a Petri net model of the system. Two resources are called similar if replacing one of them by another in any state doesn't change system's behavior. The basic properties of resource similarity are investigated. It is shown how resource similarities can be used in applications for system optimization and adaptive process management.

ВВЕДЕНИЕ

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

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

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

Системы, которые в ходе своего функционирования производят или потребляют какие-либо ресурсы, моделируются, как правило, при помощи сетей Петри [3,4]. Это весьма распространенный формализм, обладающий удобным графическим представлением и при этом достаточно выразительный с математической точки зрения. Например, в сети Петри транслируются диаграммы активности языка UML, при помощи упрощенных сетей Петри описывают схемы workflow-процессов [1]. Немаловажно и то, что сети Петри достаточно хорошо изучены математиками, для их анализа разработано множество алгоритмов.

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

В данной работе описывается новый способ поиска эквивалентностей в распределенных системах с ресурсами - на основе отношения подобия ресурсов. Ресурсы подобны, если они взаимозаменяемы при любом состоянии системы [2,6]. Это отношение также неразрешимо, однако его можно достаточно эффективно аппроксимировать.

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

ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ

Помеченной сетью Петри называется набор N=(P,T,F,l), где Р - конечное множество позиций; Т - конечное множество переходов, РТ=; F: (PT)(TP)Nat - функция инцидентности (Nat - множество неотрицательных целых чисел); l: TAct - помечающая функция, сопоставляющая каждому переходу символ из алфавита Act (конечный алфавит имен срабатываний). Разметкой (состоянием) сети N называется функция вида M: PNat, сопоставляющая каждой позиции сети некоторое натуральное число (или ноль).

Графически сеть Петри изображается как двудольный ориентированный граф. Вершины-позиции изображаются кружками и характеризуют локальные состояния сети, вершины-переходы изображаются прямоугольниками и соответствуют действиям. Дуги в графе соответствуют элементам F. Позиции могут содержать маркеры (фишки), изображаемые черными точками. При разметке M в каждую позицию p помещается M(p) фишек. Фишки, находящиеся в той или иной позиции, моделируют наличие в системе того или иного ресурса, используемого или порождаемого при срабатывании переходов. Переход может сработать только при наличии достаточного количества фишек (ресурсов) в своих входных позициях, при срабатывании он их «потребляет», но при этом «производит» фишки в своих выходных позициях. Простейший пример сети, в которой фишки изображают молекулы водорода, кислорода и воды (до и после срабатывания перехода), представлен на рисунке 1.

Рисунок 1 - Пример сети Петри

Разметки M₁ и M₂ бисимулярны (обозначается M₁M₂), если для любого срабатывания перехода при разметке M₁ возможно имитирующее срабатывание перехода с таким же именем срабатывания из Act при разметке M₂, и наоборот. Пример бисимулярных разметок приведен на рисунке 2. Здесь выполняется p₁ p₂+p₃.

Рисунок 2 - Пример бисимулярных разметок в сети Петри

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

Мы определяем ресурс как подмножество разметки. Ресурсы r и s подобны (обозначается rs), если при замене в произвольной разметке M ресурса r на ресурс s получается разметка M', такая что MM'. Примеры подобных ресурсов приведены на рисунке 3.

Рисунок 3 - Примеры подобных ресурсов

Несмотря на то, что отношение подобия ресурсов является достаточно сильным сужением фундаментального отношения бисимуляции разметок, оно все ещё неразрешимо:

Теорема 1. Не существует алгоритма, определяющего, являются ли данные два ресурса подобными, или нет.

Важнейшим конструктивным свойством подобия ресурсов является существование конечного базиса.

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

Таким образом, подобие ресурсов всегда можно эффективно задать при помощи конечного базиса. Это позволяет строить различные приближения полного отношения подобия ресурсов. В [2] приводится алгоритм приближенного вычисления подобия ресурсов, в основе которого лежит понятие бисимуляции ресурсов. Отношение бисимуляции ресурсов - это сужение отношения подобия, замкнутое относительно срабатывания переходов.

Теорема 3. Существует алгоритм, который для любой сети Петри и числа n вычисляет наибольшую бисимуляцию ресурсов, число элементов базиса которой не превышает n.

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

ПРИМЕНЕНИЕ ПОДОБИЯ РЕСУРСОВ

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

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

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

Отдельный интерес представляет изменение не начальной разметки сети, а её графовой структуры, то есть сокращение количества позиций, переходов и дуг. Информацию для такой редукции также можно получить из подобия ресурсов. Заметим, что всякому подобию ресурсов можно сопоставить «подобие» выходных дуг переходов. Другими словами, если срабатывание перехода t помещает в его выходные позиции некоторый ресурс r, у которого есть подобный ресурс s, то мы можем заменить у перехода t все выходные дуги, соответствующие r, на выходные дуги, соответствующие s.

Похожим способом можно заменять и входные дуги переходов. При этом, однако, необходимо дополнительно учитывать начальную разметку сети [2]. Пример комплексной редукции сети Петри приведен на рисунке 4.

Рисунок 4 - Пример редукции сети Петри. Здесь p₁p₄, p₂2p₅

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

Рассмотрим небольшой пример, показывающий один из возможных способов практического использования подобия ресурсов для адаптивного управления процессами. На рисунке 5 изображена модель некоей системы обработки запросов. Это может быть организация, система web-сервисов или вычислительное устройство. Система состоит из трех отдельных модулей (подразделений, серверов или процессоров). Каждый из них умеет обрабатывать запросы только одного определенного типа. Алгоритмы обработки различных типов запросов в целом различны, однако некоторые из операций совпадают. А именно, в каждом модуле выполняются операции «a» и «b».

Рисунок 5 - Обработка запросов. Здесь (q₂,)(p₁+p₂,), (r₁,v₁)(p₁+p₂,t₁)(q₂,u₂)

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

Для решения этой задачи предлагается использовать так называемое обобщенное подобие ресурсов [2]. Это отношение учитывает не только ресурсы, но и переходы сети. Грубо говоря, переходы подобны, если их срабатывания потребляют и производят подобные ресурсы. Обобщенные ресурсы состоят из инструментальной части (множества переходов) и материальной части (обычного ресурса). Обобщенные ресурсы подобны, если мы можем заменить материальную часть и срабатывание инструментальной части первого ресурса на материальную часть и срабатывание инструментальной части второго в любой разметке сети.

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

Подобие материальных ресурсов («обычное» подобие ресурсов) дает удобный набор правил для управления загрузкой подсистем. Например, используя правило (q₂,)(p₁+p₂,), мы можем уменьшить загруженность подсистемы 2 (ценой увеличения загруженности подсистемы 1), удаляя фишку из q₂ и помещая фишки в p₁ и p₂.

Управление загрузкой обычно производится под воздействием каких-то внешних факторов и причин. В свою очередь, обработка исключительных ситуаций чаще всего имеет дело с внутренними проблемами системы. Рассмотрим ситуацию, при которой в подсистеме 3 происходит сбой в момент выполнения задачи v₁ (или эта задача просто выполняется слишком долго, в то время как другие - возможно, более производительные - подсистемы простаивают). В такой ситуации правило подобия (r₁,v₁)(p₁+p₂,t₁)(q₂,u₂) позволяет нам перенести всю входную информацию из подсистемы 3 в другую подсистему (1 или 2), а затем (незаметно для пользователя) рестартовать задачу «a».

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

Рисунок 6 - Бизнес-процессы. Здесь p_{1 1} q₂, p_{2 1} q₁, p_{1 2} q₂

Рассмотрим пример на рисунке 6. Здесь представлены два циклических бизнес-процесса некоей абстрактной фирмы. За каждый процесс отвечает конкретное подразделение, которое имеет жесткую структуру и поэтому может функционировать только по раз и навсегда определенному алгоритму. Очевидно, что подразделения фирмы не являются взаимозаменяемыми. То есть в случае проблем в одном из процессов (на любой его стадии) мы не можем «увести» его в другое подразделение «навсегда». В этом ключевое отличие от предыдущего примера - там некоторые состояния различных модулей были полностью эквивалентными. Однако на время подразделения все-таки могут обмениваться друг с другом работой. Действительно, из рисунка видно, что на один «такт» мы можем перенести задание из состояния p₂ первого подразделения в состояние q₁ второго (и наоборот).

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

? На один такт: между p₁ и q₂, между p₂ и q₁.

? На два такта: между p₁ и q₂.

ЗАКЛЮЧЕНИЕ

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

Работа выполнена при поддержке РФФИ (проекты 06-01-00106 и 07-01-00702).

ЛИТЕРАТУРА

1. Ван дер Аалст, В. Управление потоками работ: модели, методы и системы [Текст] / В. ван дер Аалст, К. ван Хей - М.: Научный мир. 2007.

2. Башкин, В.А. Эквивалентность ресурсов в сетях Петри [Текст] / В.А. Башкин, И.А. Ломазова - М.: Научный мир, 2007. - 208 с.

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

4. Ломазова, И.А. Вложенные сети Петри: моделирование и анализ распределенных систем с объектной структурой [Текст] / И.А. Ломазова - М.: Научный мир, 2004. - 208 с.

5. Autant, C. Place bisimulations in Petri nets [Text] / C. Autant, Ph. Schnoebelen // Proc. of ICATPN'92. - Lecture Notes in Computer Science, 1992. - V.616. - P.45-61.

6. Bashkin, V.A. Petri Nets and resource bisimulation [Text] / V.A. Bashkin, I.A. Lomazova // Fundamenta Informaticae. - 2003. - V.55. №.2. - P.101-114.

7. Jancar, P. Decidability questions for bisimilarity of Petri nets and some related problems [Text] / P. Jancar // Proc. of STACS'94. - Lecture Notes in Computer Science, 1993. - V.775. - P.581-592.

Размещено на Allbest.ru