WWW.DISSERS.RU

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

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

Pages:     | 1 || 3 |

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

Предлагаемый подход выигрывает как у проверок на основе состояний протокола [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 fbegin while f1=2 do alt procif f3>1 then procreturn return else procprocreturn fi;

a return 2; b end c return procedure main;

begin if f2=1 then Рис. 1: Расширение графических диаprocfi;

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

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

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

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

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

На рис. 4 показано использование блоков при разборе оператора if общего вида. Множество кодов возврата “функции” (C0) на основе выражения разбивается на 2 подмножества (C0-then и C0-else). К соответствующим вершинам одного подмножества присоединяется блок ветви 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]. Это и попытка представить поведение системы в виде конечного автомата 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 Specifications from MSCs // Proc. of 9th SDL Forum — 1999. — P. 55-67.

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

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

Pages:     | 1 || 3 |






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