авторефераты диссертаций БЕСПЛАТНАЯ РОССИЙСКАЯ БИБЛИОТЕКА - WWW.DISLIB.RU

АВТОРЕФЕРАТЫ, ДИССЕРТАЦИИ, МОНОГРАФИИ, НАУЧНЫЕ СТАТЬИ, КНИГИ

 
<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

Pages:   || 2 | 3 |

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

-- [ Страница 1 ] --

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

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

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

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



Pages:   || 2 | 3 |
 

Похожие работы:







 
© 2013 www.dislib.ru - «Авторефераты диссертаций - бесплатно»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.