Моделирование программы таксономии технологий изготовления деталей машиностроительного профиля с помощью сетей Петри

УДК 004.67 Дата подачи статьи: 05.10.2013

МОДЕЛИРОВАНИЕ ПРОГРАММЫ ТАКСОНОМИИ ТЕХНОЛОГИЙ ИЗГОТОВЛЕНИЯ ДЕТАЛЕЙ МАШИНОСТРОИТЕЛЬНОГО ПРОФИЛЯ

С ПОМОЩЬЮ СЕТЕЙ ПЕТРИ

А.М. Шестаков, аспирант

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

В разработанной сети Петри отсутствуют зацикливания и тупики; программу таксономии этой модели можно применять в производстве.

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

SIMULATION OF TAXONOMY PROGRAM OF PARTS PRODUCTION TECHNOLOGY FOR MECHANICAL-ENGINEERING USING PETRI NETS Shestakov AM., Postgraduate Student

Received 05.10.2013

Аbstract. The article considers a model created using Petri nets. It allows analyzing the transmission and receipt of data from computers to the technology taxonomy program for details production on the Internet. The purpose of modeling is simulation of the program failure, deadlocks search

The developed Petri net does not have loops and dead ends. Its taxonomy program can be used in production.

Keywords: the Petri nets, mathematical model, program simulation with network, classification, components taxonomy, spanning tree, reachability graph.

Классические сети Петри (СП) были разработаны в 1962 г. Карлом Адамом Петри для описания асинхронных алгоритмов и моделирования поведения параллельных вычислительных систем.

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

высокий уровень формализации дискретно-событийных систем. Следует заметить, что в последнее время интерес к СП значительно возрос [1].

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

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

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

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

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

Согласно [3], классическая СП - это ориентированный граф с вершинами двух типов: позициями и переходами. СП определяется следующим набором: Ы=(Р, Т, А, Щ, где Р={рьр2, ,Рт} - подмножество вершин, называемых позициями СП; Т={/ь /2, .., /т} - подмножество так называемых переходов СП; Лс(РхТиТхР) - множество дуг; W: А^Ы [2].

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

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

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

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

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

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

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

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

T2.P1 // /|— М— \ 5 те гЛч

T1 \> T2 T3 T4 T5

Рис. 1. СП, моделирующая доступ к программе таксономии через сеть Интернет

Fig. 1. The Petri net modeling the taxonomy program access using the Internet

графическое представление деталей, разделенных по классам.

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

В имитационных экспериментах отказы обслуживания компьютеров программой таксономии имитировались появлением случайного числа фишек п {0; Ы) маркеров в позиции Р1. При отсутствии отказа программа работает в автоматическом режиме (позиция Р1), обслуживает команды на таксономию от компьютеров (Р2-Р8). При появлении отказа программы на доступ дуга закрывает переход Т2 и производится возврат к позиции Р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.).