Применение сетей петри в разработке многопоточного программного обеспечения с ограниченными разделяемыми ресурсами на примере центров дистанционного управления
На правах рукописи
Коротиков Сергей Викторович
ПРИМЕНЕНИЕ СЕТЕЙ ПЕТРИ В РАЗРАБОТКЕ МНОГОПОТОЧНОГО ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ С ОГРАНИЧЕННЫМИ РАЗДЕЛЯЕМЫМИ РЕСУРСАМИ НА ПРИМЕРЕ ЦЕНТРОВ ДИСТАНЦИОННОГО УПРАВЛЕНИЯ И КОНТРОЛЯ
Специальность 05.13.11 – Математическое и программное обеспечение
вычислительных машин, комплексов и компьютерных сетей
АВТОРЕФЕРАТ
диссертации на соискание ученой степени
кандидата технических наук
Новосибирск – 2008
Работа выполнена в Государственном образовательном учреждении высшего профессионального образования «Новосибирский государственный технический университет».
Научный руководитель: | доктор технических наук, профессор, Воевода Александр Александрович |
Официальные оппоненты: | доктор технических наук, профессор, Хабаров Валерий Иванович кандидат технических наук, доцент, Долозов Николай Лаврентьевич |
Ведущая организация: | Томский политехнический университет |
Защита состоится « 19 » июня 2008 г. в 14 часов на заседании диссертационного совета Д 212.173.06 при Новосибирском государственном техническом университете по адресу: 630092, г. Новосибирск, пр. Карла Маркса, 20
С диссертацией можно ознакомиться в библиотеке Новосибирского государственного технического университета.
Автореферат разослан 16 мая 2008 г.
Ученый секретарь
диссертационного совета Чубич В.М.
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы исследований. Основная задача разработчика многопоточного (multithread) программного обеспечения (ПО) с ограниченными разделяемыми ресурсами – обеспечить надежность (стабильность, устойчивость к ошибкам и восстанавливаемость) функционирования ПО. Примером данного класса ПО является центр дистанционного управления и контроля (ЦДУК), предназначенный для непрерывного дистанционного контроля и управления интеллектуальным оборудованием. При разработке ПО ЦДУК (в современной индустрии ПО) используется объектно-ориентированный подход к анализу и проектированию (ООАП) с применением языка UML (Unified Modeling Language). Некорректное представление сложных алгоритмов и механизмов синхронизации на UML-диаграммах приводит к взаимным блокировкам потоков и другим проблемам при функционировании ПО. Подобные ошибки могут обнаруживаться только при очень специфичных условиях эксплуатации ЦДУК, например центра дистанционного управления и контроля таксофонов (ЦДУКТ) и диспетчерского центра блоков релейной защиты (ДЦ БРЗ). Их трудно, а иногда невозможно воспроизвести в условиях тестовой среды.
В языке UML и CASE (Computer Aided Software Engineering) средствах на его основе, например «Rational Rose», нет собственных средств обоснования правильности и согласованности наборов диаграмм, поэтому наибольшее внимание уделяется методам и инструментам для преобразования UML-диаграмм в сети Петри и их анализа. При этом различные расширения сетей Петри предлагаются для проверки отдельных видов диаграмм. В решениях для совокупности диаграмм проекта не учитывается применение программных элементов синхронизации и другая специфика разработки объектно-ориентированного многопоточного приложения (в частности ЦДУК). Отсутствует описание технологий применения профессиональных, свободно распространяемых пакетов моделирования раскрашенных иерархических сетей Петри, например «CPN Tools» (Coloured Petri Net), предложений по автоматизации процесса и преодоления ограничений пространства состояний модели. Всё это делает весьма затруднительным применение указанных подходов в инженерии ПО. В известных автору работах не предлагаются шаблоны (типичные образцы проектирования) моделей и кода для проектирования многопоточных системных служб управления и контроля. Отсутствуют предложения по анализу требований к многопоточному ПО с помощью совокупности диаграммы процессов и диаграмм деятельности, детализирующих алгоритмы потоков с учётом используемых при реализации кода элементов синхронизации и аттестации (validation) данного набора диаграмм с использованием раскрашенных иерархических сетей Петри.
Предмет исследования: модели и методы разработки программных средств сбора и обработки данных в вычислительных машинах; методы повышения надежности функционирования программ; теория и практика технологических аспектов программирования, изготовления многопоточных программ, а также программных инструментальных технологических комплексов поддержки разработки программных средств.
Цель работы: разработка методик применения сетей Петри при аттестации наборов UML-диаграмм в процессе разработки многопоточного ПО с ограниченными разделяемыми ресурсами и их применение в разработке программного обеспечения ЦДУК для обеспечения надежности его функционирования.
Основные задачи исследования:
- исследовать и определить набор UML-диаграмм и свойств сети Петри, необходимых и достаточных для обеспечения надежности функционирования создаваемого многопоточного ПО с ограниченными разделяемыми ресурсами;
- разработать методику для этапа анализа многопоточного ПО с ограниченными разделяемыми ресурсами, основанную на создании и аттестации набора UML-диаграмм данного этапа с помощью раскрашенных иерархических сетей Петри и использовании средств автоматизации разработки программ;
- разработать методику для этапа проектирования многопоточного ПО с ограниченными разделяемыми ресурсами, основанную на создании и аттестации набора UML-диаграмм проекта с помощью раскрашенных иерархических сетей Петри и использовании средств автоматизации разработки программ;
- разработать набор шаблонов моделей и программных решений для повышения производительности моделирования и анализа при создании программ и преодоления ограничений компьютерного пакета моделирования;
- разработать ПО ЦДУКТ и ДЦ БРЗ с применением предложенных методик, шаблонов и программных решений.
Методы исследования. Результаты исследования получены на базе аппарата сетей Петри и ООАП. При разработке ПО ЦДУКТ применялись отраслевые и международные стандарты, «Концепция Единой Таксофонной Карты России». При проектировании и реализации ПО ЦДУКТ и ДЦ БРЗ использовались CASE-технологии, инструментальные среды и пакеты моделирования.
Научной новизной обладают представленные на защиту результаты, полученные для класса объектно-ориентированного многопоточного ПО с ограниченными разделяемыми ресурсами:
- определены необходимые и достаточные, в отличие от известных подходов, наборы UML-диаграмм и свойства сети Петри, что позволяет при разработке данного класса ПО в процессе моделирования и анализа применять для обеспечения надежности его функционирования раскрашенные иерархические сети Петри, которые в известных подходах либо не используются, либо при их эпизодическом использовании не учитываются особенности исследуемого класса ПО;
- впервые разработаны методики для этапов анализа и проектирования данного класса ПО, основанные на создании и аттестации наборов UML-диаграмм с помощью раскрашенных иерархических сетей Петри и использовании средств автоматизации разработки программ, применение которых обеспечивает устранение ошибок и несогласованности набора UML-диаграмм, отражающего требования к разрабатываемому ПО, и гарантирует надежность функционирования спроектированных классов;
- впервые разработаны наборы шаблонов UML-диаграмм (типичных образцов проектирования) и страниц раскрашенных иерархических сетей Петри модели многопоточной системной службы управления и контроля, применение которых на этапах анализа и проектирования позволяет значительно сократить время разработки ПО;
- разработаны шаблоны и программные решения для повышения производительности моделирования в компьютерном пакете моделирования раскрашенных иерархических сетей Петри «CPN Tools», отличающиеся простотой использования и модификации под модель любой сложности. Эти шаблоны и решения позволяют при помощи управления сложностью пространства состояний модели преодолевать ограничения на его размер;
- разработано и успешно внедрено в эксплуатацию ПО ЦДУКТ и ДЦ БРЗ.
Практическая ценность и внедрение результатов исследования.
В результате применения на фазах анализа и проектирования предлагаемых методик программист получает автоматически сгенерированный проект и готовые к реализации в функциях классов алгоритмы, правильность которых обеспечена с помощью анализа полного пространства состояний модели на надежность функционирования и соответствие требованиям. Предложенные методики, шаблоны и программные решения позволяют ускорить и облегчить процесс изготовления программ данного класса, органично вписываются в принятые в индустрии ПО подходы и методы разработки и готовы к реальному применению.
Результаты диссертационной работы были использованы при проектировании и реализации ПО ЦДУКТ, принятого в эксплуатацию СП «Сибирьтелеком» - НГТС в 2003 г.; при проектировании и реализации ПО ДЦ БРЗ, которое поставляется с 2007 г. в комплекте с БРЗ, выпускаемыми ФГУП ПО «Север»; в процессе обучения студентов АВТФ НГТУ.
Апробация работы. Основные результаты работы были представлены на Международном научно-техническом симпозиуме KORUS (Ульсан, 2000; Томск, 2001; Новосибирск, 2002), Международной научно-технической конференции “Информационные системы и технологии” (Новосибирск, 2000), Международной научно-технической конференции “Актуальные проблемы электронного приборостроения” (Новосибирск, 2000), Ежегодной международной сибирской школе-семинаре по электронным приборам и материалам EDM’2003 (Эрлагол, 2003), Международной научно-практической конференции «Электронные средства и системы управления» (Томск, 2004), IV Сибирском конгрессе по прикладной и индустриальной математике “ИНПРИМ-2000” (Новосибирск, 2000). Материалы диссертации обсуждались в 2003 г. в университете г. Айхштет (Германия) на «The 4th Advanced Course on Petri Nets», летней школе «IFAC Summer School on Control, Computing and Communication», проходившей в 2005 г. в Чешском техническом университете (г. Прага), объединенном научном семинаре отдела МОВВС ИВМ и МГ СО РАН, кафедры параллельных вычислительных технологий НГТУ и кафедры параллельных вычислений НГУ, объединенном научном семинаре АВТФ и ФПМИ НГТУ.
Публикации. Основные положения и результаты диссертационной работы опубликованы в 29 работах, в том числе: 5 – в изданиях, рекомендуемых ВАК РФ; 14 – в сборниках научных трудов; 7 – в материалах международных симпозиумов и конференций; 3 – в материалах российских конференций. В конце автореферата приведен список основных публикаций.
Личный вклад. Все разработки и научные результаты, выносимые на защиту и изложенные в тексте диссертации, получены либо самим автором лично, либо при его непосредственном участии.
Структура и объем работы. Диссертация состоит из введения, пяти разделов, заключения, списка использованной литературы, включающего 117 наименований и приложений. Общий объем работы составляет 216 страниц, в том числе основное содержание изложено на 171 странице и включает 75 рисунков, 9 таблиц и приложения размещены на 44 страницах.
ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении обоснована актуальность темы диссертации, сформулированы цель и задачи исследования, определены научная новизна и практическая ценность работы, дана общая характеристика полученных результатов, аннотируются основные положения работы.
Первый раздел посвящен методологическим и технологическим особенностям разработки многопоточного ПО с ограниченными разделяемыми ресурсами и обеспечения надежности его функционирования.
Определены: назначение, структура, состав и задачи разработки данного класса систем. Проведен анализ процессов, подходов и моделей разработки систем, методов обеспечения их правильности и возможностей применения сетей Петри на технологическом цикле разработки ПО. В разработке исследуемого класса ПО предлагается использовать ООАП с применением языка UML и CASE средства «Rational Rose», а для аттестации наборов UML-диаграмм на фазах анализа и проектирования использовать сети Петри. Это необходимо для обеспечения надежности ПО, так как в UML и CASE средствах на его основе, нет собственных средств аттестации наборов диаграмм. Актуальность проблемы аттестации UML-диаграмм подтверждается рядом публикаций.
В качестве формального метода выбран аппарат сетей Петри, поскольку он позволяют наилучшим образом решить задачи, связанные с представлением, моделированием и анализом причинно-следственных связей в сложной системе параллельно действующих процессов.
Определение. Сетью Петри называется набор N = {Р, Т, F, W, Mo), где: (Р, Т, F) — конечная сеть; P — непустое множество элементов сети, называемых местами; T — непустое множество элементов сети, называемых переходами; — отношение инцидентност и;
— функция кратности дуг;
— функция начальной раз метки сети Петри.
Различные расширения сетей Петри используются для проверки отдельных видов диаграмм в ряде работ. Предложения по использованию ординарных сетей Петри для анализа диаграмм взаимодействия и деятельности предназначены для моделирования потоков работ на отдельных диаграммах в терминах бизнес процессов. Подходы с применением обобщенных стохастических сетей Петри для моделирования диаграмм последовательности, состояний, деятельности являются не связанными работами, направленными на анализ производительности систем, критичных к времени выполнения, и систем реального времени. Указанные подходы не ориентированы на обеспечение надежности функционирования ПО. В них не учитывается иерархия, сложность событий, элементы синхронизации и другие особенности моделирования многопоточного объектно-ориентированного ПО.
Известны два подхода к преобразованию совокупности диаграммы классов, состояний для каждого класса и их взаимодействия в сеть Петри и её анализу. В первом подходе предлагается набор правил преобразования в высокоуровневую сеть Петри без учета событий, указания расширения сетей Петри и практических рекомендаций по преобразованию и анализу, что делает невозможным его применение в индустрии ПО. В цикле статей по второму подходу предлагается использовать раскрашенную иерархическую сеть Петри. Несмотря на подробное описание, в данном событийном подходе различных аспектов преобразования в сеть Петри диаграмм состояний любой сложности отсутствуют правила использования и преобразования в элементы сети Петри широко применяемых для синхронизации в многопоточном приложении реальных программных элементов, не учитываются параметры событий и другая специфика разработки многопоточного объектно-ориентированного ПО ЦДУК.
В указанных подходах можно выделить ряд недостатков, которые затрудняют применение этих подходов в инженерии ПО: 1) в них нет описания технологий применения профессиональных, свободно распространяемых пакетов моделирования раскрашенных иерархических сетей Петри; 2) нет рекомендаций по анализу функционирования ПО сетью Петри на основе его связи со свойствами и структурой сети; 3) нет предложений по автоматизации процесса моделирования и анализа; 4) нет практических рекомендаций для преодоления ограничений пакета моделирования на размер пространства состояний модели.
В результате обзора не обнаружено публикаций, предлагающих шаблоны моделей и кода для проектирования многопоточных системных служб управления и контроля. Отсутствуют предложения по спецификации требований к многопоточному ПО с помощью диаграммы процессов и диаграмм деятельности, детализирующих алгоритмы потоков, с учётом используемых при реализации кода элементов синхронизации, с аттестацией полученного набора диаграмм при помощи раскрашенных иерархических сетей Петри.
Второй раздел посвящен исследованию возможностей применения классических и раскрашенных сетей Петри в разработке многопоточного ПО.
В результате анализа определен набор свойств классических сетей Петри, обязательных для проверки ПО на соответствие требованиям и надежности. Очень важным свойством сети Петри является отсутствие тупиковых («мёртвых») маркировок. Для устранения этого свойства разработчик анализирует проблему возникновения «мертвой» маркировки и изменяет структуру сети Петри и соответствующий ей алгоритм работы моделируемой системы, представленный на UML-диаграммах. При моделировании многопоточного ПО с ограниченными ресурсами должны быть обязательно проверены границы мест, моделирующих семафоры, критические секции и стеки. Свойство живости характеризует достижимость и функциональность всех переходов в сети. Если моделирование выявит, что существуют «мертвые» переходы, то необходимо перестроение модели и исключение нефункционирующих переходов, так как их присутствие означает невыполнение какой-то части алгоритма.
В результате рассмотрения было выявлено стремительное увеличение сложности классической сети Петри при масштабировании и невозможность моделирования многих аспектов объектно-ориентированных моделей, служащих основой для реализации реальной системы. Для решения данных проблем предложено использовать раскрашенные иерархические сети Петри. Приведенные ниже утверждения об эквивалентности, а также описанные в работе Йенсена правила эквивалентности и преобразования позволяют взаимно переносить на раскрашенные иерархические сети Петри все свойства, основные концепции и методы анализа классических сетей Петри.
Утверждение 1: Пусть имеется неиерархическая раскрашенная сеть Петри . Определим эквивалентную простую сеть Петри
по следующим правилам: 1)
; 2)
; 3)
где
– множество неотрицательных целых чисел,
и
; 4)
. Здесь:
,
,
,
– конечные множества непустых типов (цветов), мест, переходов, дуг, а N, C, G, E, I – функции вершин, цвета, охраны переходов, выражения дуг и начальной разметки.