Применение сетей петри в разработке многопоточного программного обеспечения с ограниченными разделяемыми ресурсами на примере центров дистанционного управления

На правах рукописи

Коротиков Сергей Викторович

ПРИМЕНЕНИЕ СЕТЕЙ ПЕТРИ В РАЗРАБОТКЕ МНОГОПОТОЧНОГО ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ С ОГРАНИЧЕННЫМИ РАЗДЕЛЯЕМЫМИ РЕСУРСАМИ НА ПРИМЕРЕ ЦЕНТРОВ ДИСТАНЦИОННОГО УПРАВЛЕНИЯ И КОНТРОЛЯ

Специальность 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 – функции вершин, цвета, охраны пе­реходов, выражения дуг и начальной разметки.