III Международная студенческая научная конференция Студенческий научный форум - 2011

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

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

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

Обзор эмуляторов сетей Петри, использующихся на кафедре

В настоящей момент в мире существует немало разнообразных эмуляторов, реализующих сети Петри. Они реализую различные варианты сетей, имеют различную функциональность, интерфейс и стоимость.  На сегодняшний день для обучения студентов кафедры МОВС,  используется эмулятор VIPeNET. Эмулятор имеет дружественный интерфейс, и достаточно прост в освоении, но имеет ряд существенных недостатков, а именно:

• Ø Не совсем корректный обсчет сети
• Ø Невысокая производительность
• Ø Неудобство в разработке даже относительно больших моделей из-за отсутствия функций копироватьвставить, а также возможности масштабирования и создания библиотеки объектов
• Ø Не совсем корректная реализация распределений
• Ø Мелкие недочеты и недоработки

Фактически, обучение происходит на недоработанном эмуляторе. Этот факт, а также факт отсутствия поддержки ОС, отличных от Windows, и стал главной причиной разработки нового кроссплатформенного интерпретатора сетей Петри - QPNet.

Описание QPNet

QPNet - это кроссплатформенная система моделирования на основе сетей Петри. Она позволяет:

• Ø Строить и исследовать дискретные модели различной степени сложности
• Ø Сохранять полученные модель в файлы .xqp, или какой-либо графический формат

Интерфейс программы представлен на рисунке 1:

Особенности QPNet:

• Кроссплатформенность. QPNet может быть собран под Linux, Mac OS и даже Windows CE
• Высокая производительность
• Возможность удобного размещения и редактирования сети, а также масштабирование
• Широкие возможности при создании моделей
• Поддержка русского и английского языка

Средства разработки QPNet:

QPNet разрабатывается c помощью библиотеки QT. Это мощное и удобное средство для разработки графических приложений в среде C++. Эта библиотека обеспечивает возможность переноса приложения на различные платформы. Немаловажно и то, что QT распространяется по лицензии GNU, то есть может использоваться бесплатно для разработки приложений с открытым исходным кодом. Именно поэтому для написания QPNet мы выбрали QT, отсюда и первая буква в названии QPNet. 

Реализация графики в QPNet

Для реализации редактора графов использовались графическая подсистема библиотеки Qt. Основу используемых в Qt средств двумерной графики составляет класс QPainter. Этот класс может использоваться для рисования простейших геометрических фигур, пиксельных карт (pixmap), изображений и текста. Также он поддерживает функции сглаживания (antialiasing), альфа-смешивания (alpha blending) и плавного перехода цветов (gradient filling). Но QPainter не разделяет изображение на объекты. Для этого используется подсистема Graphics View. В нее входят несколько классов, разделяющих вывод графики на несколько стадий. На первой стадии формируется сцена из объектов. Сцена реализована классом QGraphicsScene. На следующем этапе объекты сцены отрисовываются в графическом окне (QGraphicsView). Класс QGraphicsScene предоставляет возможности манипулировать объектами, например, выделять и изменять их положение. Объекты сцены наследуются от абстрактного класса QGraphicsItem,.у которого перегружаются несколько методов, используя которые, QGraphicsScene определяет границы объектов, а QGraphicsView отображает их.

Примеры моделей вычислительных процессов

Модель тупика двух вычислительных процессов.

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

Модель взаимодействия процессов "Управляющий-рабочий"

 

В этой модели присутствует некоторый портфель независимых задач которые надо выполнить. Задачи поручаются рабочим (процессам). Во ходе выполнения задачи рабочий может породить одну или несколько новых задач, которые так же отправляются в портфель. Для примера взяты два процесса (Рабочий 1 и Рабочий 2), которые выполняют задачи из портфеля. В модели число новых задач, порождаемых при выполнении некоторой задачи, случайно и распределено по экспоненциальному закону (с округлением) с математическим ожиданием 0,75. Следовательно, рабочие не будут создавать больше задач, чем выполняют. Время выполнения задачи так же случайно, распределено по нормальному закону с мат. ожиданием 10 и среднеквадратичным отклонением 2.

 

Модель взаимодействия процессов "Алгоритм пульсации"

 

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

Модель взаимодействия процессов "Конвейерные алгоритмы"

 

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

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

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

А также, следующие функции:

• Замедленное выполнение сети - когда за единицу времени выполняется определенное число тактов, для того что бы нагляднее проиллюстрировать работу сети
• Выполнение определенного числа тактов - для облегчения отладки сети
• Изменение размеров изображения мест и переходов
• Установка пользовательских изображений мест

Улучшение наглядности отображение сети, путём введение графических указателей направления типа ´стрелка´

Код для цитирования: Скопировать