WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 || 3 | 4 |

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

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

В указанных подходах можно выделить ряд недостатков, которые затруд­няют применение этих подходов в инженерии ПО: 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. Анализ отчета о пространстве состояний сети Петри

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

Выводы

State Space (Статистика) Status: Full Nodes: 33093 Arcs: 149580

Пространство состояний модели вычислено полностью и содержит 33093 узла и 149580 дуг.

Свойства обратимости

Home Markings All

Dead Markings None

Все маркировки являются «домашними» - мо­дель обратима. «Мертвые» маркировки отсут­ствуют – в модели нет тупиков.

Свойства живучести

Dead Transition Instances None

Live Transition Instances All

«Мертвых» переходов нет.

Все переходы «живые». Во время сеанса связи возникают все события.

Свойства ограниченности – верхние и нижние границы: числовые и мультимножеств

Best Integer Bounds (Upper,Lower), Best (Upper,Lower) Multiset Bounds

IDackRec 1 0

End 3 0

Ringing 2 0

…………………………

IDackRec 1`(1,(1,1))++1`(2,(1,1))

LineBusy 1`1++1`2

…………………………

Сеть ограниченная, с границами равными 3 для места End, 2 для места Ringing, 1 для места IDackRec и т.д., что соответствует исход­ным данным. На основании данных верхних границ мультимножеств мест делаем вывод о наличии в местах меток в соответствии с пра­вилами функционирования модели.

Fairness Properties (справедливость срабатывания переходов)

Busy Just

DialN Impartial

MeetMeTone Fair

End No Fairness

Справедливость срабатываемости перехода Busy обоснована, перехода Impartial объек­тивна, MeetMeTone доказана, а перехода End и остальных переходов не доказана.

Несмотря на широкие возможности пакета «CPN Tools», ввод исходных данных и вывод результатов значительно замедляет процесс. Кроме того, пакет имеет ограничение на размер пространства состояний. Для преодоления этого ограничения, повышения эффективности моделирования и, как следствие, ана­лиза, предлагается набор программных решений. Он позволяет легко манипу­лировать исходными данными для создания их различных комбинаций при по­мощи таблицы Microsoft Excel и получать автоматически набор текстовых файлов, которые загружаются в модель при помощи кодовых сегментов (рис.1). Помимо автоматизации это позволяет решить проблему «взрыва» пространства состояний, легко управляя его сложностью при масштабировании модели.

Рис.1. Компоненты технологии инициализации модели

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

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

Шаг 1. На диаграмме вариантов использования отразить функциональ­ное назначение системы (в процессе сбора требований).

Шаг 2. На диаграммах последовательности детализировать критичные ва­рианты использования.

Шаг 3. На диаграмме процессов отразить процесс и все необходимые по­токи для проектируемого многопоточного программного модуля.

Шаг 4. На диаграммах деятельности отразить последовательность выпол­нения действий процессом и потоками, а также их взаимодействие при использовании критических ресурсов с учетом элементов синхронизации.

Шаг 5. Диаграммы деятельности преобразовать в раскрашенную иерархи­ческую сеть Петри с помощью определенного набора правил.

Шаг 6. Исследовать правильность функционирования модели путём выпол­нения прогона (simulation) с использованием различных комбинаций исходных данных по различным последовательностям выполнения. При обнаружении ошибки выполнить переход на шаг 4,3,2,1 в зависимости от типа ошибки.

Шаг 7. Анализ корректности набора отчетов о полном пространстве со­стояний с различными комбинациями исходных данных. При обнаружении ошибки выполнить переход на шаг 4,3,2,1 в зависимости от типа ошибки.

Шаг 8. Выполнить этап проектирования с помощью полученного набора UML-диаграмм.

Шаги 1 и 2 широко используются в разработке ПО, и их применение в ра­боте не рассматривается. На третьем шаге методики предлагается шаблон диа­граммы процессов (рис. 2). Как и все последующие диаграммы, она ориентиро­вана на ЦДУК. Количество потоков ожидания зависит от количества каналов (устройств) связи. Количество потоков опроса зависит от количества управляе­мых устройств, но при большом интервале между сеансами связи (опросами), достаточном для опроса всех устройств, может использоваться один поток.

Рис.2. Шаблон диаграммы процессов службы управления и контроля

Рис.3. Детализация деятельности потока слежения и передачи команд

На четвертом шаге методики на диаграммах деятельности детализиру­ются особенности алгоритмической реализации каждого потока. Предлагается использовать траекторию объектов для отображения критических секций, фла­гов, семафоров и других элементов синхронизации работы параллельных пото­ков с указанием места взятия и отдачи ресурса для ка­нала передачи, соединения с БД и флага работы службы (рис. 3). Ресурс с множеством экземпляров помечается как Multiple instances для отличия объектов с единич­ными и множественными экземплярами, учета этой особенности при преобра­зовании в сеть Петри и выборе элемента синхронизации доступа к ресурсу.

Предложенные шаблоны UML-диаграмм для ЦДУК и правила их по­строения являются новым результатом, готовым к практическому применению.

На пятом шаге диаграммы деятельности преобразуются в раскрашенную иерархическую сеть Петри, реализуемую в пакете CPN Tools. Элементы диа­грамм деятельности преобразуются в соответствующие эквиваленты сети Петри. Известные правила преобразования диаграмм деятельности в ординар­ную сеть Петри были систематизированы, и на их основе предложены четыре правила преобразования основных элементов диаграммы деятельности и соз­даны ещё три правила для преобразования элементов синхронизации многопо­точного приложения и выделения процессов и потоков в страницы сети Петри.

Рис.4. Страница службы управления и контроля

Пример применения предложенных правил проиллюстрирован на рис.4 для главной страницы модели службы контроля и управления. Флаг работы службы bWorking реализован как место слияния, так как он используется для синхронизации потоков. Такое решение предлагается применять для всех эле­ментов синхронизации и ссылок на общие данные объекта класса «родителя» и классов «потомков». Работа потоков, инициализации и останова отражена в виде составных переходов с соответствующими подстраницами.

Pages:     | 1 || 3 | 4 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»