ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы исследований. Основная задача разработчика многопоточного (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 – функции вершин, цвета, охраны переходов, выражения дуг и начальной разметки.
Утверждение 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. Анализ отчета о пространстве состояний сети Петри