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

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы исследований. Основная задача разработчика мно­гопоточного (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, M_o), где: (Р, Т, F) — конечная сеть; P — непустое множество элементов сети, называемых местами; T — непустое множество элементов сети, называемых переходами; — отношение инцидентности; — функция кратности дуг; — функция начальной разметки сети Петри.

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

Известны два подхода к преобразованию совокупности диаграммы клас­сов, состояний для каждого класса и их взаимодействия в сеть Петри и её ана­лизу. В первом подходе предлагается набор правил преобразования в высоко­уровневую сеть Петри без учета событий, указания расширения сетей Петри и практических рекомендаций по преобразованию и анализу, что делает невоз­можным его применение в индустрии ПО. В цикле статей по второму подходу предлагается использовать раскрашенную иерархическую сеть Петри. Несмотря на подробное описание, в данном событийном подходе различных ас­пектов преобразования в сеть Петри диаграмм состояний любой сложности отсутствуют правила использования и преобразования в элементы сети Петри широко применяемых для синхронизации в многопоточном приложении реаль­ных программных элементов, не учитываются параметры событий и другая специфика разработки многопоточного объектно-ориентированного ПО ЦДУК.

В указанных подходах можно выделить ряд недостатков, которые затруд­няют применение этих подходов в инженерии ПО: 1) в них нет описания технологий применения профессиональных, сво­бодно распространяемых пакетов моделирования раскрашенных иерархических сетей Петри; 2) нет рекомендаций по анализу функционирования ПО сетью Петри на основе его связи со свойствами и структурой сети; 3) нет предложений по автоматизации процесса моделирования и анализа; 4) нет практических рекомендаций для преодоления ограничений пакета моделирования на размер пространства состояний модели.

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

Второй раздел посвящен исследованию возможностей применения клас­сических и раскрашенных сетей Петри в разработке многопоточного ПО.

В результате анализа определен набор свойств классических сетей Петри, обязательных для проверки ПО на соответствие требованиям и надежности. Очень важным свойством сети Петри является отсутствие тупиковых («мёрт­вых») маркировок. Для устранения этого свойства разработчик анализирует проблему возникновения «мертвой» маркировки и изменяет структуру сети Петри и соответствующий ей алгоритм работы моделируемой системы, пред­ставленный на UML-диаграммах. При моделировании многопоточного ПО с ограниченными ресурсами должны быть обязательно проверены границы мест, моделирующих семафоры, критические секции и стеки. Свойство живости ха­рактеризует достижимость и функциональность всех переходов в сети. Если моделирование выявит, что существуют «мертвые» переходы, то необходимо перестроение модели и исключение нефункционирующих переходов, так как их присутствие означает невыполнение какой-то части алгоритма.

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

Утверждение 1: Пусть имеется неиерархическая раскрашенная сеть Петри . Определим эквивалентную простую сеть Петри по следующим правилам: 1); 2) ; 3) где – множество неотрицательных целых чисел, и ; 4) . Здесь: ,,, – конечные множества непустых типов (цве­тов), мест, переходов, дуг, а N, C, G, E, I – функции вершин, цвета, охраны пе­реходов, выражения дуг и начальной разметки.

Утверждение 2: Пусть имеется иерархическая раскрашенная сеть Петри . Определим эквивалентную неиерархиче­скую раскрашенную сеть Петри как набор , ко­торый удовлетворяет следующим условиям: 1) ; 2) ; 3) ; 4) ; 5) ; 6); 7) ; 8) ; 9) . Здесь S, SN – множества страниц и подстановочных вершин (состав­ных переходов); SA, PT, PA, FT функции связывания страниц, типов портов, связывания портов и типа слияния; PN – множество портов; FS – конечное множество множеств мест слияния; PP – мультимножество первичных страниц.

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

Анализ пространства состояний модели, отражающего все возможные маркировки, позволяет получить все указанные свойства сети Петри. Его построение и анализ для реальных систем выполняется с помощью компьютерного инструмента. Набор инструментов «CPN Tools» позволяет бы­стро и легко создавать и редактировать сети Петри, проводить их моделирование и анализ. В данном разделе работы приведен полный стандарт­ный отчёт для модели взаимодействия таксофона и ЦДУКТ и описаны его со­ставляющие. Фрагмент отчета с выводами о правильности модели и соответст­вии требованиям приведен в таблице 1. Отчет содержит разделы: статистика пространства состояний – число узлов, дуг и статус (полное); свойства обрати­мости – список возвратных маркировок (Home Markings) и «мертвых» маркиро­вок (Dead Markings); свойства ограниченности – верхние и нижние числовые границы (Integer Bounds) и мультимножеств (Multi-set Bounds); свойства живу­чести – список «живых» переходов (Live Transition Instances) и «мертвых» пере­ходов (Dead Transition Instances); свойства справедливости срабатывания пере­ходов – Just - обосновано, Fair - доказано, Impartial - объективно и No Fairness - не определено.

Таблица 1. Анализ отчета о пространстве состояний сети Петри

Результаты отчета