авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

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

Совместное использование msc и sdl моделей при разработке событийно-ориентированных систем

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

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

Соколов Владимир Владимирович СОВМЕСТНОЕ ИСПОЛЬЗОВАНИЕ MSC И SDL МОДЕЛЕЙ ПРИ РАЗРАБОТКЕ СОБЫТИЙНО-ОРИЕНТИРОВАННЫХ СИСТЕМ 05.13.11 — Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Санкт-Петербург 2007

Работа выполнена на кафедре системного программирования математико механического факультета Санкт-Петербургского государственного уни верситета.

Научный консультант: доктор физико-математических наук, профессор Терехов Андрей Николаевич

Официальные оппоненты: доктор технических наук, профессор Гольдштейн Борис Соломонович кандидат физико-математических наук, доцент Костин Владимир Андреевич

Ведущая организация: Институт системного программирования РАН

Защита диссертации состоится “26” апреля 2007 года в 1630 часов на заседании диссертационного совета Д212.232.51 по защите диссертаций на соискание ученой степени доктора наук при Санкт-Петербургском государ ственном университете по адресу: 198504, Санкт-Петербург, Старый Пе тергоф, Университетский пр., д. 28, математико-механический факультет Санкт-Петербургского государственного университета.

С диссертацией можно ознакомиться в Научной библиотеке Санкт Петербургского государственного университета по адресу: 199034, Санкт Петербург, Университетская наб., д. 7/9.

Автореферат разослан “21” марта 2007 года.

Ученый секретарь диссертационного совета доктор физико-математических наук, профессор Б.К.Мартыненко

Общая характеристика работы

Актуальность темы В последнее десятилетие в развитии программного обеспечения произошел качественный скачок. Электронный мир теперь распределен, параллелен и взаимосвязан. Банки, авиалинии, телефонные компании не могут рабо тать без интенсивного обмена информацией между всеми действующими объектами. С возрастанием сложности протоколов взаимодействия потре бовались специальные средства, нацеленные на их описание, разработку и отладку.

Системы, в которых использовались сложные протоколы взаимодействия, существовали достаточно давно. Это телекоммуникационные системы. Со ответствующие проблемы там были успешно разрешены, в результате чего были созданы стандарты SDL (Specification and Description Language) [15] и MSC (Message Sequence Chart) [14, 16]. Данные стандарты были раз работаны Международным Консультационным Комитетом по Телеграфии и Телефонии, ныне ITU-T. MSC и SDL являются стандартом де-факто в международной телефонии. Организация ITU-T использует их для специ фикации других стандартов (протоколов) — UMTS, GSM, E-DSS-1, V5.2, SS7 и других. MSC и SDL широко используются в известных фирмах – раз работчиках телекоммуникационного оборудования.

MSC и SDL применяются для описания динамического поведения систе мы. В современных системах разработки телекоммуникационного ПО ис пользуются оба стандарта, поскольку они дают различную информацию и дополняют друг друга. MSC больше относится к этапу проектирования, а SDL — к этапу программирования. Возникает необходимость обеспечения их согласованности, поскольку они по-разному описывают одни и те же алгоритмы поведения. Параллельное использование моделей без их согла сования приводит в тому, что одна модель дает корректное описание, а дру гая содержит устаревшую информацию. Для того, чтобы переиспользовать данные с MSC модели существует синтез SDL диаграмм по MSC [6, 20, 21].

Для проверки их согласованности существует ряд алгоритмов верифика ции [11, 12, 13].

Выбранные алгоритмы совместного использования моделей вносят ряд ограничений на всю технологию. Например, алгоритмы генерации могут как урезать MSC модель [19], так и запрещать модифицировать SDL мо дель [20], а так же влияют на согласование данных, описывающих струк туру системы [20, 21] (то есть, на то, что непосредственно не относится к событийному описанию системы). Алгоритмы верификации тоже име ют свои границы применимости. Поэтому возникает проблема интеграции различных подходов в рамках разрабатываемой технологии так, чтобы они обеспечивали как описательную, так и алгоритмическую мощь.

В общем виде задача сравнения MSC и SDL алгоритмически неразрешима, поэтому необходима разработка алгоритма, который бы абстрагировался от части информации и давал адекватные результаты. Существующие под ходы плохо работают при рассогласованиях моделей, допустимых с точки зрения человеческой логики, таких как добавление и удаление сообщений, цикличности частей моделей;

неполнота MSC модели и т.д.

Существенным минусом известных алгоритмов генерации является то, что в них нет возможности влиять на генерируемый SDL код. Для разработ ки это неудобно, поэтому автор ставит задачу о настройке SDL кода. То есть, среди ряда SDL моделей, соответствующих данному MSC, выбрать наиболее удобную для технолога1.

Как верификация, так и генерация базируются на том, что существует MSC модель, практически полностью аналогичная SDL модели. На самом деле, существующий стандарт (H)MSC [14, 16] хорошо приспособлен лишь для описания прямых веток. То есть, хорошо приспособлен лишь для де тализации сценариев поведения. Описание ошибочных ситуаций ведет к большому количеству перерисовок сценариев вместо соответствующего их дополнения. Данный момент очень неудобен для технолога. Причиной это го является то, что существующая детализация является аналогом про цедуры в АЯВУ, однако логика описания ошибочных ситуаций ближе к функциям. Необходимо разработать соответствующую MSC–подобную мо дель.



Цели работы Целью работы является разработка подхода по совместному использова нию MSC и SDL моделей и реализация его в технологическом средстве.

Разработка подхода была разделена на решение следующих основных за дач:

– выработать структуру средства, предоставляющего набор возможно стей совместного использования MSC и SDL с отслеживанием кор ректности разработки;

– разработать верификацию SDL диаграмм по MSC диаграммам при априорном знании о наличии расхождений;

– разработать алгоритм генерации SDL диаграмм по MSC диаграммам, позволяющий строить SDL код, отвечающий требованиям технолога;

Так мы называем разработчика, создающего продукт с помощью технологии – расширить MSC модель для возможности создавать максимально полные MSC описания.

Общая методика MSC и SDL модели рассматриваются как структуры, задающие языки, со стоящие из сообщений. Каждый такой язык задается с помощью конечного автомата. Разработаны алгоритмы перехода от предметной области MSC и SDL в конечный автомат и обратно. Для разбора языков использовались контекстно-свободные (LALR(1)) грамматики. Разработаны алгоритмы об работки конечного автомата на базе конечно-автоматных алгоритмов и гра фов, специфичные для предметной области и выбранной задачи. Оценка применимости полученных алгоритмов осуществлялась экспериментально.

Основные результаты Предложена методология совместного использования MSC и SDL диа грамм.

Разработана математическая модель верификации SDL по MSC, позволя ющая осуществлять проверки моделей в при наличии ряда отличий, появ ляющихся в течение жизненного цикла.

Создан алгоритм автоматизированной генерации SDL кода по конечному автомату, позволяющий получать SDL код, удобный для технолога.

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

Научная новизна Представлен оригинальный взгляд на совместное использование MSC и SDL моделей, использующий разработанные алгоритмы верификации, ге нерации, расширения MSC и сочетания статических данных MSC и SDL.

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

Впервые поставлена задача настройки генерируемого SDL кода под требо вания технолога.

Разработан оригинальный алгоритм генерации SDL по MSC, реализующий данную настройку.





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

Практическая и теоретическая ценность Разработан технологический подход по совместному использованию MSC и SDL моделей, позволяющий ускорить процесс разработки и отладки ПО, существенной частью которого являются протоколы взаимодействия.

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

Разработанные подходы могут быть применены для ряда других си стем, сводящихся к конечно-автоматным. Например, в подходах на базе UML [23].

Алгоритмы генерации SDL могут быть так же применены для систем, в которых SDL является промежуточной моделью [10], а так же для опти мизации существующего SDL кода.

На практике предложенные методы были использованы при разработке объектов и исследованиях кода реальных промышленных систем.

Апробация работы Результаты работы докладывались на семинаре Института системного про граммирования РАН (2006 год, г. Москва).

Предложенная технология была реализована в виде набора технологиче ских средств, дополняющих средство REAL [2, 4].

Разработанные подходы использовались при разработке телефонной стан ции “Юнивер–А” — многоканального радиоудлинителя телефонных линий.

Публикации Основные результаты диссертации изложены в 3-х работах, перечисленных в конце автореферата.

Структура и объем диссертации Диссертация состоит из введения, 4-х глав, заключения, списка литературы и 3-х приложений. Текст диссертации изложен на 146-ти страницах. Список литературы содержит 74-ре наименования.

Содержание работы Во введении показывается актуальность выбранной темы исследований, излагаются научный и исторический контексты диссертационной работы.

Кратко перечислены основные результаты диссертации.

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

Дается обзор существующих подходов по совместному использованию MSC и SDL моделей с указанием их сильных и слабых сторон:

1. MSC и SDL независимы, что плохо из-за их несогласованности и двой ного проектирования системы — сначала на MSC, потом на SDL.

2. Попытки создавать системы на основе MSC диаграмм с последующим синтезом SDL.

(a) Только на MSC модели с использованием SDL только как проме жуточной модели без возможности ее редактирования [20]. Дан ный подход имеет ряд недостатков, связанных с недостаточными возможностями MSC модели и с утратой выразительности SDL.

(b) “Односторонний синтез” [6, 21], неудобный с точки зрения под держки всего цикла разработки.

(c) “Инкрементальные алгоритмы” [17, 19], которые требуют такого количества ограничений, что применимы лишь в очень малом классе случаев.

3. Алгоритмы сравнения используемых MSC и SDL диаграмм для про верки соответствия.

(a) Генерация трасс2 с MSC диаграмм с “наложением” 3 их на SDL диаграммы [11, 12].

(b) Алгоритмы параллельного исполнения моделей c анализом внут ренних состояний протокола [13].

Формулируются условия построения CASE системы: возможность незави симого использования MSC и SDL моделей;

генерация SDL по MSC;

вери фикация SDL по MSC с учетом изменений, появляющихся в течение жиз ненного цикла системы. Описание статической части системы4 выделяется в отдельную модель, которой пользуются и MSC, и SDL. Данная модель заменяет соответствующие возможности описания системы в каждом из стандартов. Указываются проблемные места, которые присутствуют в су ществующих подходах совместного использования MSC и SDL.

Трассой называем цепочку сообщений Мы говорим, что трасса “наложилась”, если мы представили такой вариант выполнения SDL, что при этом была порождена цепочка входящих и выходящих сообщений, специфицированная трассой Имеющиеся классы системы, сообщения, параметры сообщений, интерфейсы, порты и т.д. [15, 16] В первой главе описывается математический аппарат, используемый во всей работе. Формулируются необходимые определения и теоремы, даются комментарии к ним.

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

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

Дается формальное определение алгоритма верификации и его обоснова ние в терминах предметной области MSC и SDL диаграмм. Сутью алго ритма являются:

1. для обрабатываемого объекта выбираются его SDL диаграммы и мно жество MSC диаграмм, являющееся подмножеством диаграмм, в ко торых он присутствует;

2. переход от MSC и SDL диаграмм к конечным автоматам, порождаю щих для данного объекта такой же язык из сообщений, который бы порождала соответствующая модель;

3. замена в конечных автоматах части переходов, маркированных сооб щениями, на -переходы. То есть, устранение соответствующих пере ходов из рассмотрения. При автоматической работе алгоритма оста ются только сообщения, присутствующие на обоих автоматах;

4. поиск такого состояния на модифицированном SDL-автомате, что на чиная с него можно “наложить” все возможные трассы, задаваемые модифицированным MSC-автоматом. Количество данных трасс мо жет быть бесконечным;

5. интерпретация результата в рамках предметной области.

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

Предлагаемый подход выигрывает как у проверок на основе состояний протокола [13], так и у конечно-автоматных моделей без словарей сооб щений [18] за счет интеграции нескольких идей:

– переход от SDL и MSC к конечно-автоматным моделям с учетом спе цифики SDL и MSC (конструкции параллельного исполнения MSC, уничтожение и сохранение сообщений, не обрабатываемых в текущем SDL-состоянии и т.д.);

– операции фильтрации, разделяющие общее множество сообщений на “используемые” и “неиспользуемые”;

– проверки на включение языков, реализуемой с помощью математики конечных автоматов.

Это дает возможность проверять соответствие MSC и SDL диаграмм на соответствие в ряде случаев, когда другие алгоритмы не применимы.

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

Проводится обзор существующих алгоритмов по генерации SDL из MSC.

Фактически существует две группы — серия московских работ [3, 20] и се рия канадских [6, 17, 21]. Во всех данных методах сначала осуществляется переход от MSC к конечному автомату. Наиболее существенное отличие между ними в том, что в канадских работах генерация начинается сразу, а в московских к конечному автомату перед этим применяются алгорит мы детерминизации и минимизации. Канадские алгоритмы выдают код, в котором лучше угадывается изначальный MSC, более точно рассчитывают правила для конструкции Save, но из-за отсутствия алгоритма детерми низации применимы не всегда, а из-за отсутствия минимизации могут вы давать менее оптимальный код. Московский вариант может осуществить синтез всегда, но при этом он может как улучшать компактность SDL, так и ухудшать ее, а так же понижать степень узнаваемости MSC в SDL.

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

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

Для этого вводится промежуточная модель между MSC и SDL диаграм мами для настройки процедуры синтеза. Это конечный автомат. Он более компактен, чем MSC и SDL модели, и удобен для редактирования перед последующей генерацией SDL. На результат генерации можно повлиять ис пользуя данные из модели MSC, модели SDL и на уровне конечных автома тов. Например, два параллельно выполняющихся MSC сценария, при вы полнении ряда ограничений, удобно реализовывать тремя участками SDL кода, которые выполняют каждый из сценариев и процедуру, которая со здает и завершает исполнение данных “сценариев”, а так же передает сооб щения на них. SDL модель мы используем когда работаем с уже готовым SDL кодом — например, используем описатели “*” для состояний и сообще ний, а так же описатель “–” для состояний при выделении общих участков кода. Иногда это может существенно уменьшить его объем.

Наиболее существенной, с точки зрения влияния на получаемый SDL, яв ляется область работы с конечными автоматами. При этом конечный авто мат представляется в виде графа, с которым удобно работать визуально.

На данном графе изображены состояния конечного автомата и переходы между ними. Переходы несут информацию о имени сообщения и его типе — посылаемое или принимаемое. С конечным автоматом можно работать ли бо и до, и после связки процедур детерминизация–минимизация для защи ты от изменений, либо после выполнения данных алгоритмов. Работа “и до, и после” путем замены части сообщений на отсутствующие в списке, а потом замена обратно решает проблему детерминизации во выходящим сообщениям, иногда негативно влияющую на SDL код. Работа “и до, и по сле” путем замены целой области и замены обратно позволяет защитить ее от изменений, вносимых данными алгоритмами. Работа “после” позволяет “переразложить” код нужным образом, а так же интерактивно выделять процедуры путем обнаружения гамаков [1].

При построении SDL диаграмм по MSC диаграммам для выбранного объ екта проходим по следующей цепочке:

1. проверка корректности MSC описания [6, 8];

2. переход от MSC диаграмм данного объекта к недетерминированному конечному автомату, порождающему все трассы данного объекта [3];

3. опциональная защита частей автомата от процедур преобразования;

4. детерминизация автомата;

5. минимизация автомата;

6. “восстановление” автомата, если применялись алгоритмы пункта 3;

7. опциональное “переразложение” автомата и выделение процедур;

8. построение схемы SDL кода.

Данный алгоритм позволяет настраивать генерируемый SDL код под требо вания технолога, чего нет ни в одном из алгоритмов генерации. Поскольку при генерации SDL диаграмм по MSC диаграммам используется переход MSCFSMSDL, то вместо MSC диаграмм может быть задана любая модель, которая сводится к конечным автоматам. Это открывает возмож ность переноса информации из других технологий в SDL. Особо следует отметить, что исходной моделью может также служить и SDL модель. Та ким образом можем проводить оптимизацию уже написанного SDL кода.

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

Для результативной работы алгоритмов генерации и верификации необхо димо, чтобы существовало MSC описание системы, которое было бы как можно более полным. Существующий стандарт MSC имеет серьезный недо статок, не позволяющий описывать в нем обратные ветви (то есть, ветви, обрабатывающие ошибочные ситуации). Он хорошо работает для описания прямых ветвей (случаев, когда все происходит без ошибок) путем посте пенной декомпозиции сценариев. Когда на набор сценариев, описывающих прямые ветви, начинают добавлять проработку ошибочных ситуаций, то оказывается, что изменение детализирующего сценария влияет на детали зируемый. Зачастую данное изменение на этом не заканчивается, а продви гается “выше” по иерархии сценариев. В реальной работе это приводит к достаточно большому количеству “перерисовок” сценариев, на что тратится время.

Причина данной проблемы достаточно очевидна — из сценария невозможно вернуть результат его выполнения с последующим анализом в детализиру емом сценарии. При этом важным граничным условием является то, что решение данной проблемы не должно быть сложнее конечно-автоматной модели для последующего использования в генерации и верификации. Со ответствующая модель была разработана;

идеологически она является сме сью графического MSC и текстовых описаний;

при необходимости графи ческие и текстовые описания могут возвращать результат выполнения;

дан ный результат выполнения может быть проанализирован в текстовом опи сании с выполнением последующих действий примерно так же, как это делается на языке Pascal;

полное описание на данной модели конверти руется в конечный автомат для каждого из объектов для последующего использования.

function f2;

msc f begin while f1=2 do alt proc if f31 then proc return 1 return else proc proc4 return fi;

a return 2;

b end c return procedure main;

begin if f2=1 then Рис. 1: Расширение графических диа proc грамм для добавления возможности fi;

end возвращать результат Слева от рис. 1 приведен образец текстового описания предлагаемого рас ширения MSC. На самом рисунке изображено необязательное расширение графических сценариев возможностью возвращения результата его выпол нения. Как графические, так и текстовые описания делятся на “процедуры” и “функции”. “Процедуры” не возвращают результат. “Функции” результат возвращают. На примере продемонстрировано совместное использование текстовых и графических описаний, и организация “функций” на базе “про цедур” и обратно. По “процедуре” для любого объекта может быть построен конечный автомат, описывающий его язык, состоящий из входящих и вы ходящих сообщений.

Если проводить аналогии с обычными сценариями, то “процедура” явля ется сценарием, а “функция” является набором нумерованных сценариев.

Можно считать, что сценарии в “функции” являются вариантами выпол нения аналогично конструкции alt, и номер присвоен концу сценария. При использовании “функций” в текстовом описании данный набор можно раз делить необходимым образом согласно их нумерации и соединить с нуж ными последующими действиями. Для текстовых описаний реализованы конструкции: if;

case;

for;

while;

opt;

alt с Pascal’e-подобным синтаксисом.

При разборе “программы” на предложенном расширении MSC для фик сированного объекта используются структуры, изображенные на рис. 2. В графическом изображении данной структуры вершина S обозначает нача ло блока (аналогия начального состояния конечного автомата). Вершина K обозначает конец блока, при последовательном соединении блоков K со S S = S S используемая функция C Z K F C0 K C0-then C0-else Рис. 2: Структура, S1 S if ялд еинежарыв используемая при разборе расширения MSC (блок) часть then часть else C = C1 U C C1 C S Z = Z1 U Z Z1 Z K1 K a K=q q F = F0 U F1 U F F1 F2 F K Рис. 3: Блок, соответству- Рис. 4: Использование блоков при ющий посылке одного разборе оператора if общего вида сообщения единяется с S;

на рис. 3 приведен блок для одного сообщения. Множество вершин F обозначает завершение исполнения (аналогия множества завер шающих состояний конечного автомата). Z — множество вершин выхода из “процедуры” (return без кода возврата). C — множество вершин выхода из “функции”, маркированных кодом возврата (например, return 7 ).

Внутри блока находятся конечно-автоматные структуры, описывающие прием и посылку сообщений. В процессе разбора грамматики текстового расширения MSC происходят операции с данными блоками. На них же определены проверки корректности “программы”. Графические представ ления так же отображаются в подобные блоки. Блок, получающийся в кон це разбора, является “процедурой” и отображается в конечный автомат.

На рис. 4 показано использование блоков при разборе оператора if обще го вида. Множество кодов возврата “функции” (C0 ) на основе выражения разбивается на 2 подмножества (C0then и C0else ). К соответствующим вершинам одного подмножества присоединяется блок ветви then, а к дру гому — else через начальные вершины данных блоков. Концы блоков ветвей (K1 и K2 ) соединяются с дополнительной вершиной q. В результате из трех блоков (“функция”, блок ветви then и блок ветви else) получаем один блок, соответствующий оператору if. В качестве S для него будет выступать S0, в качестве C объединение C1 и C2, в качестве Z — Z1 и Z2, в качестве K — q, в качестве F — объединение F0, F1 и F2.

Рассмотрим место предложенного решения среди диаграмм, которые поз воляют описать алгоритмы взаимодействия нескольких объектов, и могут давать все поведение группы объектов или системы, а не разрозненных информационных срезов. Достаточно большое количество моделей, анало гично MSC, рассчитаны лишь на постепенную детализацию без проработки обратных ветвей, и имеют похожие проблемы. Это и MSC-подобная груп па — HMSC [14];

UML Sequence [23] и UML Collaboration [23] диаграммы;

Som’s Scenarios [24]. Это и попытка представить поведение системы в ви e де конечного автомата Chisel Diagrams [7]. Это и потоки данных — UML Activity диаграммы [23] и Use Case Maps (UCMs) [5]. Предлагаемое реше ние превосходит их по гибкости, поскольку логика стыковки различных вариантов поведения лучше описывается текстом. Так же следует упомя нуть текстовые языки, нацеленные на описание взаимодействия различных объектов (Pascal–FC, Occam, Ada, Java, Lotos и т.д.), но они предназначе ны для описания поведения одного объекта, и лежат вне рассматриваемой области.

Задача по расширению MSC для описания обратных веток уже ставилась — это LSCs (Life Sequence Charts) [9]. Предлагаемое решение перекрывает LSCs за счет возможности иметь произвольное множество кодов возврата, а не двух вариантов — нормального и ошибочного. Так же предлагаемое решение в рамках всего подхода сводимо к широко используемому SDL, а не требует отдельной модели для исполнения, как LSCs.

Существует модель CTP [22], являющаяся комбинацией MSC и сетей Пет ри. Разработанное решение лучше за счет комбинирования АЯВУ и MSC.

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

В заключении приведена краткая характеристика технологического под хода, разработке которого было посвящено данное исследование, и сфор мулированы основные полученные результаты.

В Приложении А. приведены используемые элементы MSC и SDL диа грамм. В Приложении B. дается грамматика предложенного расширения MSC. Приложение С. содержит список иллюстраций.

Список литературы [1] Касьянов В.Н. Оптимизирующие преобразования программ. — М.:Наука, 1988. — 336 с.

[2] Кознов Д.В. Визуальное моделирование компонентного программного обеспечения: Дис... канд. физ.-мат. наук — СПбГУ, 2000. — 82 с.

[3] Мансуров Н. Синтез исполняемых SDL спецификаций по сценарным моделям // Тр. ин-та Системного Программирования — 1999.

[4] Терехов А.Н. и др. REAL: методология и CASE средство разработки информационных систем и ПО систем реального времени // Програм мирование. — 1999. — № 5. — с. 45-51.

[5] Use Case Maps (UCMs) нотация. Определения, публикации, средства.

http://www.useCaseMaps.org/index.shtml [6] Abdalla M., Khendek F., Butler G. New Results on Deriving SDL Spec ications from MSCs // Proc. of 9th SDL Forum — 1999. — P. 55-67.

[7] Aho A., Gallagher S., Grieth N., Scheel C., Swayne D. Sculptor with Chisel: Requirements Engineering for Communications Services // Proc.

in 5th International Workshop on Feature Interactions in Telecommuni cations and Software Systems (FIW’98) — Lund, Sweden: IOS Press, 1998. — P. 45-63.

[8] Ben-Abdallah H., Leue S. Syntactic detection of process divergence and nonlocal choice in message sequence charts // Proc. of the Tools and Algorithms for the Construction and Analysis of Systems, Third International Workshop (TACAS’97) — № 1217 in Lecture Notes in Computer Science — Enschede, The Netherlands: Springer, 1997. — P. 259-274.

[9] Damm W., Harel D. LSCs: Breathing Life into Message Sequence Charts // Proc. in 3rd IFIP International Conference on Formal Methods for Open Object-based Distributed Systems (FMOODS’99) — Kluwer Aca demic Publishers, 1999. — P. 293-312.

[10] Daveau J.-M., Marchioro G., Valderrama C., Jerraya A. VHDL genera tion from SDL specications // Proc. of the XIII IFIP Conf. on Com puter Hardware Description Languages (CHDL’97) — Toledo, Spain — 1997.

[11] EG 201 015 Ver. 1.2.1, Methods for Testing and Specication (MTS);

Specication of protocols and services;

Validation methodology for stan dards using Specication and Description Language (SDL);

Handbook — 1999. — 28 p.

[12] ETR 184 : Methods for Testing and Specication (MTS);

Overview of validation techniques for European Telecommunication Standards (ETSs) containing SDL — 1995. — 27 p.

[13] Holzmann G. Design and Validation of Computer Protocols // Prentice Hall, 1991 — ISBN 0-13-539834-7. — 512 p.

[14] ITU-T MSC2000R3 Draft Z.120: Message Sequence Charts ITU-T Rec ommendation Z.120. — 1999.

[15] ITU-T Recommendation Z.100: Specication and description language (SDL). — 1999. — 244 p.

[16] ITU-T Recommendation Z.120: Message Sequence Chart (MSC). — 1999. — 136 p.

[17] Khendek F., Vincent D. Enriching SDL Specications with MSCs // Proc. of 2nd Workshop of the SDL Forum Society on SDL and MSC (SAM2000) — 2000. — P. 305-319.

[18] Kurshan R. Computer-Aided Verication of Coordinating Processes // Princeton Series in Computer Science, 1994. — ISBN 0691034362. — 270 p.

[19] Li J., Horgan J. Applying formal description techniques to software architectural design // Computer Communications — Vol. 23 — № 12.

— 2000. — P. 1169-1178.

[20] Mansurov N., Zhukov D. Automatic synthesis of SDL models in Use Case Methodology // Proc. of 9th SDL Forum — 1999. — P. 225-240.

[21] Robert G., Khendek F., Grogono P. Deriving an SDL specication with a given architecture from a set of MSCs // Proc. of 8th SDL Forum — 1997. — P. 197-212.

[22] Roychoudhury A., Thiagarajan P.S. Communicating Transaction Pro cesses // Proc. in IEEE International Conference on Application of Concurrency in System Design (ACSD’2003) — 2003. — P. 157-166.

[23] Rumbaugh J., Jacobson I., Booch G. The Unied Modeling Language Reference Manual — Addison-Wesley, 1999. — 576 p.

[24] Som S., Dssouli R., Vaucher J. Toward an Automation of Requirements e Engineering using Scenarios //Journal of Computing and Information 2(1) — 1996. — P. 1110-1132.

Работы автора по теме диссертации 1. Соколов В.В. Проверка SDL диаграмм по MSC диаграммам на ос нове частичной информации // Системное программирование. — СПб.: 2004. — с. 366-390.

2. Терехов А.Н., Соколов В.В. Новые возможности технологии REAL // Вестн. С.-Петербург. ун-та. — Сер. 10., 2005. — Вып. 1-2. — с. 64-77.

3. Терехов А.Н., Соколов В.В. Реализация стыка между MSC– и SDL– диаграммами в технологии REAL // Программирование. — 2007. — № 1. — с. 35-50.

Terekhov A., Sokolov V. Implementation of the Conformation of MSC and SDL Diagrams in the REAL Technology // Programming and Computer Software (Engl., Transl.) — 2007. — № 1. — P. 24-33. — DOI: 10.1134/S0361768807010045.



 

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





 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

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