ПРОГРАММИРОВАНИЕ, 2010, No 4, с. 3-15
ТЕОРЕТИЧЕСКИЕ ВОПРОСЫ ПРОГРАММИРОВАНИЯ -
УДК 681.3.06
ФОРМАЛИЗАЦИЯ СЕМАНТИКИ СИСТЕМ С НЕНАДЕЖНЫМИ АГЕНТАМИ ПРИ ПОМОЩИ СЕТЕЙ АКТИВНЫХ РЕСУРСОВ*
© 2010 г. В. А. Башкин
Ярославский государственный университет им. П.Г. Демидова 150000 Ярославль, ул. Советская, 14 E-mail: bas@uniyar.ac.ru Поступила в редакцию 21.04.2008 г.
Представлен новый способ моделирования распределенных систем - сети активных ресурсов. Данный формализм обладает той же выразительной мощностью, что и обыкновенные сети Петри, однако в его синтаксисе заложен другой принцип моделирования: вместо разделения компонентов модели (вершин графа) на агенты и ресурсы (переходы и позиции) вводится разделение способов взаимодействия (дуг графа) на производство и потребление. Направление дуги определяет активную и пассивную стороны взаимодействия; один и тот же компонент при различных срабатываниях может выступать как в роли агента, так и в роли ресурса. В сетях активных ресурсов и в их синтаксических расширениях появляется возможность для удобной формализации таких семантических свойств, как одновременная работа агентов, блокировка агента, избыточность числа агентов, возможность замены надежного узла ненадежным и др.
Рассматривается метод построения распределенных приложений на основе динамически конфигурируемых наборов исполняющих модулей. Показано, что использование сетей активных ресурсов позволяет достаточно естественным образом задавать структуру, а также формулировать свойства подобных систем.
1. ВВЕДЕНИЕ
Описание поведения отдельного агента - одна из ключевых задач при моделировании сложной мультиагентной системы. Зачастую действие, выполняемое агентом, настолько неэлементарно, что для его описания требуется отдельная модель. Однако есть ряд достаточно распространенных типов агентов, которые удобно моделировать простыми математическими структурами.
Одним из таких типов агентов является агент - преобразователь ресурсов. Подобный агент получает на вход один фиксированный набор ресурсов и производит на выходе другой фиксированный набор ресурсов.
* Работа выполнена при финансовой поддержке РФФИ (проект 09-01-00277) и ФЦП "Кадры" (проект 02.740.11.0207).
Системы с ресурсами, как правило, моделируются при помощи сетей Петри. Сеть Петри представляет собой ориентированный граф с двумя типами компонентов - позициями и переходами. Вершины-позиции моделируют состояние системы. Каждой позиции приписано целое неотрицательное число, показывающее количество доступных ресурсов данного типа (локальное состояние). Вершины-переходы моделируют действия, которые может выполнять система (срабатывания переходов). Каждый переход при срабатывании потребляет один набор ресурсов (предусловие) и производит другой (постусловие). Таким образом, понятию простого агента-преобразователя ресурсов в сетях Петри соответствует переход или набор переходов.
В данной работе представлен новый способ моделирования систем с более явным выделением понятия агента. В моделях, названных сетя-
ми активных ресурсов (АР-сетями), используется тот же способ сохранения и преобразования информации, что и в обыкновенных сетях Петри - конечное мультимножество как хранилище данных и проверка наличия в нем данного конечного подмножества как условие запуска действия. Однако здесь убрано разбиение множества вершин графа сети на позиции и переходы - все они являются равноправными узлами. Объекты, хранящиеся в вершине А, могут быть использованы при срабатываниях объектов из других вершин в качестве потребляемых или производимых ресурсов. Точно так же объекты вершины А могут сработать, производя или потребляя какие-то другие (или даже такие же) объекты. Срабатывающий объект выступает в роли агента, потребляемый или производимый - в роли ресурса. Для определения вида связи между вершинами (производство или потребление) вводится тип дуги - производящая или потребляющая. Таким образом, на два класса разбивается не множество вершин, как в обыкновенных или супер-двойственных сетях Петри, а множество дуг графа. Доказывается, что класс сетей активных ресурсов равномощен классу обыкновенных сетей Петри.
Предлагаются способы расширения синтаксиса АР-сетей, позволяющие удобно формализовать семантику систем с более сложным поведением агента.
Вводится понятие работающего агента. Работающий агент уже потребил свои входные ресурсы, но еще не произвел выходные. Работающий агент не могут потребить другие агенты в качестве ресурса. В АР-сетях с работающими агентами формализуются такие семантические свойства, как одновременная работа нескольких агентов, блокировка ресурса (агента), постоянное наличие неактивных агентов данного типа (избыточность), возможность появления неограниченного количества работающих агентов и др. Важно отметить, что при введении понятия работающего агента структура графа сети (модель системы в целом) не меняется, усложняется только семантика фишки (модель агента/ресурса).
Вводится понятие ненадежного агента. Ненадежный агент может произвести не весь свой выходной ресурс. Ненадежность рассматривается
не как свойство отдельного агента (фишки), а как свойство взаимодействия агента с конкретными видами ресурсов. В АР-сетях с ненадежными агентами формализуются такие семантические свойства, как возможность замены надежного узла ненадежным без ущерба для каких-то качеств системы, наилучшее и наихудшее поведение системы в целом (с точки зрения производства ресурсов) и др.
Доказывается, что представленные формализмы эквивалентны по выразительной мощности обыкновенным сетям Петри (предлагаются алгоритмы преобразования), то есть для них сохраняется разрешимость таких фундаментальных алгоритмических свойств, как завер-шаемость, достижимость разметки, ограниченность, безопасность и живость узла сети.
Рассматривается схема построения распределенного приложения на основе сети активных ресурсов. Приложение представляет собой набор веб-сервисов, контролируемых единой управляющей системой. Управляющая система в качестве схемы процесса использует сеть активных ресурсов, при этом узел АР-сети выступает в качестве шаблона (спецификации) сервиса, а фишки - в качестве конкретных экземпляров соответствующих данному шаблону сервисов. Веб-сервис является агентом - он может совершать действия над ресурсами (продолжительные по времени и не всегда успешные). Но при этом он же выступает и в качестве ресурса - производится и потребляется (точнее, система сама способна искать в интернете и регистрировать подходящие под шаблон сервисы, а также удалять из реестра сервисы, ставшие недоступными). Использование формализма сетей активных ресурсов позволяет достаточно естественным образом описывать структуру и формулировать свойства подобных систем.
2. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ
Через Nat обозначим множество неотрицательных целых чисел.
Пусть X - непустое множество.
Мультимножеством M над множеством X называется функция M : X — Nat. Мощность мультимножества \M\ = ^^ M(ж). Числа
тех
{M(ж) \ x £ X} называются коэффициентами
Р1 ¡1 Р2 Р1 ¡1 Р2 р; ¡1 Р2
Ч1Н© ОЧ!>=«® (-М^®
Т -^Т Т -^У V
_>£> йм») 0=Ю
(2 Р3 ¡2 Р3 ¡2 Рз
Рис. 1. Сеть Петри.
мультимножества, коэффициент М(х) определяет число экземпляров элемента х в М. Мультимножество М конечно, если конечно множество {х € X | М(х) > 0}. Множество всех конечных мультимножеств над данным множеством X обозначается как М(Х).
Операции и отношения теории множеств естественно расширяются на конечные мультимножества.
Пусть МьМ2,Мз € М(Х). Полагаем:
• Мх = М2 + Мз ^Ух € X Мх(х) = М2(ж) + +Мз(ж) - операция сложения двух мультимножеств;
• Мх = М2 - Мз ^ Ух € X Мх(х) = М2(х)е © Мз(х) - разность мультимножеств (где е - вычитание до нуля).
Сетью Петри называется набор N = (Р,Т, Е), где
• Р - конечное множество позиций;
• Т - конечное множество переходов, Р П Т =
= 0;
• Е : (Р х Т) и (Т х Р) ^ ^ - функция инцидентности (мультимножество дуг).
Разметкой (состоянием) сети N называется функция вида М : Р ^ Nat, сопоставляющая каждой позиции сети некоторое натуральное число (или ноль). Разметка может рассматриваться как мультимножество над множеством позиций сети, то есть элемент множества М(Р).
Размеченной сетью Петри называется пара (^Мо), где N = (Р,Т,Е) - сеть Петри, Мо € € М(Р) - начальная разметка (количество ресурса в наличии при запуске сети).
Графически сеть Петри изображается как двудольный ориентированный граф. Вершины-позиции изображаются кружками и характе-
ризуют локальные состояния сети, вершины-переходы изображаются прямоугольниками и соответствуют действиям. Дуги соответствуют элементам Е. Позиции могут содержать маркеры (фишки), изображаемые черными точками. При разметке М в каждую позицию р помещается М (р) фишек.
Переход £ € Т активен при разметке М, если Ур € Р М(р) > Е(р, ¿) (все входные позиции содержат достаточное количество фишек).
Активный при разметке М переход £ может сработать, порождая новую разметку М', где Ур € Р М'(р) = М(р) - Е(р,£)+ Е(г,р).
Множество всех разметок, достижимых от начальной разметки М за одно или несколько срабатываний переходов, обозначается как К^, М).
Пример срабатывания переходов в обыкновенной сети Петри приведен на рис. 1. Последовательно срабатывают переходы и ¿2.
В сети Петри модель системы явно разделена на пассивную и активную составляющие. Пассивная часть - это состояние системы, то есть мультимножество имеющихся в наличии ресурсов. Для хранения этих ресурсов (фишек) предназначен конечный набор вершин-позиций. Активная часть - конечный набор возможных преобразований состояния (множество вершин-переходов). Позиции могут быть связаны только с переходами, и наоборот. Таким образом, любая модель, основанная на сетях Петри, состоит из двух частей. Одна из них (множество позиций) меняет свое "содержимое" в ходе функционирования сети, другая (множество переходов) -жестко фиксирована и выступает только в качестве системы связей между позициями.
Такая "несмешиваемость" - одно из удобств использования сетей Петри, позволяющее детально структурировать модель системы с точки зрения разбиени
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.