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

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

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

Моделирование программного средства позволяет выявить недостатки до его внедрения.

Постановка задачи и ее реализация

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

Согласно [3], классическая СП – это ориентированный граф с вершинами двух типов: позициями и переходами. СП определяется следующим набором: N=(P, T, A, W), где P={p1, p2, …, pm} – подмножество вершин, называемых позициями СП; T={t1, t2, …, tm} – подмножество так называемых переходов СП; AÍ(P´TÈT´P) – множество дуг; W: A®N [2].

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

Такое строго математико-графическое представление позволяет проводить детальный анализ задачи.

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

Функционирование СП осуществляется за счет срабатывания переходов. Условием срабатывания перехода является наличие фишек во входных местах.

В рассматриваемой СП (рис. 1) каждый компьютер, получающий доступ к веб-приложению, моделируется одной фишкой. Срабатывание перехода Ti, i=1, …, 7, отражает начало выполнения процедуры. Наличие метки в месте Pi, i=1, …, 9, показывает, что выполнено условие, предусмотренное алгоритмом программы.

Модель системы разработана в виде СП.

Позиции СП: Р1 – позиция, наличие фишки в которой свидетельствует о наличии запроса к программе таксономии от пользователя; Р2 – позиция, моделирующая выбор и загрузку файла на сервер; Р2.2 – проверка файла и выполнение сценария; Р3 – позиция, моделирующая указание пользователем максимального числа классов; Р4 – переход, моделирующий поиск количества классов, для которых достигается наилучшее разделение данных; Р5 – переход, моделирующий поиск среднего значения силуэта для класса; Р6 – позиция, наличие фишки в которой определяет результат работы программы, то есть законченный HTML-документ; Р7 – вывод результата таксономии; Р8 – графическое представление деталей, разделенных по классам.

Переходы СП: Т1 – запрос к программе выполнен; Т2 – операция загрузки файла выполнена (если условие не выполнено, происходит возврат к Р1); Т2.Р1 – если условие проверки файла не выполнено, возврат к позиции Р1; Т3 – операция указания пользователем максимального числа классов успешно завершена; Т4 – операция поиска количества классов, для которых достигается наилучшее разделение данных, успешно завершена; Т5 – операция поиска среднего значения силуэта для класса завершена.

В имитационных экспериментах отказы обслуживания компьютеров программой таксономии имитировались появлением случайного числа фишек n {0; N) маркеров в позиции Р1. При отсутствии отказа программа работает в автоматическом режиме (позиция P1), обслуживает команды на таксономию от компьютеров (P2–Р8). При появлении отказа программы на доступ дуга закрывает переход T2 и производится возврат к позиции Р1.

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

Построение графа достижимости

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

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

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

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

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

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

Литература

1.     Васильев В.В., Кузьмук В.В. Сети Петри, параллельные алгоритмы и модели мультипроцессорных систем. К.: Наукова Думка, 1990. 216 с.

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

3.     Питерсон Дж. Теория сетей Петри и моделирование систем; [пер. с англ. М.В. Горбатовой, В.Н. Торхова, В.Н. Четверикова]. М.: Мир, 1984. 264 с.

4.     Шестаков А.М. Использование удаленного доступа пакета Matlab для решения задач таксономии деталей // Вестн. Иркутского гос. технич. ун-та. 2012. № 6. С. 11–17.

References

1.     Vasilyev V.V., Kuzmuk V.V. Seti Petri, parallelnye algoritmy i modeli multiprotsessornykh sistem [Petri nets, parallel algorithms and models of multi-processor systems]. Kiev, Naukova Dumka Publ., 1990, 216 p.

2.     Kotov V.E. Seti Petri [Petri nets]. Moscow, Nauka Publ., 1984, 160 p.

3.     Piterson J.L. Petri net theory and the modeling of systems. PTR Upper Saddle River, NJ, USA, Prentice Hall Publ., 1981, 290 p. (Russ. ed.: Gorbatova M.V., Torkhov V.N., Chetveri- kov V.N. Moscow, Mir Publ., 1984, 264 p.).

4.     Shestakov A.M. Using remote control access of Matlab to solve the components taxonomy problems. Vestnik Irkutskogo gos. tekh. univ. [The bulletin of Irkutsk State Tech. Univ.]. 2012, no. 6, pp. 11–17 (in Russ.).