МЕТОДЫ СИНТЕЗА СТРУКТУР ПРОГРАММНЫХ СИСТЕМ

Болонкин А. В.,
аспирант,
МТУСИ (г. Москва),
ИПУ РАН (г. Москва)

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

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

1. Графический подход

К данному подходу относятся методы на основе DFD, IDEF-SADT, EPC, UML. Они используют диаграммы для представления модели программной системы. Большинство данных методов стандартизовано, имеет большую историю развития и применения [5].

DFD

В основе DFD (Data Flow Diagrams) лежат диаграммы потоков данных. Модель системы в контексте DFD представляется в виде информационной модели, компонентами которой являются потоки данных, переносящие информацию от одной подсистемы к другой. Каждая из подсистем выполняет определенные преобразования входного потока данных и передает результаты обработки информации в виде потоков данных для других подсистем. Основными компонентами диаграмм потоков данных являются внешние сущности, накопители данных, процессы, потоки данных и системы/подсистемы. Информационная модель системы строится как иерархическая схема в виде контекстной диаграммы, на которой исходная модель представляется в виде модели подсистем соответствующих процессов преобразования данных. В настоящее время диаграммы потоков данных используются в некоторых CASE-средствах для построения информационных моделей систем обработки данных.

Достоинства: акцент на использовании данных в системе, наглядность диаграмм.

Недостатки: отсутствие явных средств для объектно-ориентированного представления моделей сложных систем и представления сложных алгоритмов обработки данных.

IDEF-SADT

Начало разработки диаграмм функционального моделирования относится к середине 1960-х годов, когда Дуглас Т. Росс предложил специальную технику моделирования, получившую название SADT (Structured Analysis & Design Technique). Военно-воздушные силы США использовали методику SADT в качестве части своей программы интеграции компьютерных и промышленных технологий (Integrated Computer Aided Manufacturing, ICAM) и назвали ее IDEF0 (Icam DEFinition), которая впоследствии выросла в семейство стандартов IDEF, включающее в себя более десятка стандартов анализа и проектирования. В данном случае основной акцент делается на стандарт IDEF0 [2], поскольку именно он является основой IDEF, наиболее широко известен и имеет распространение.

Достоинства: использование функционального подхода, наглядность диаграмм, четкий синтаксис и семантика диаграмм, возможность декомпозиции диаграмм и моделирование иерархии процессов.

Недостатки: смешение связей по данным и управлению, слабо выраженная временная последовательность, отсутствие спецификаций процессов (в т. ч. ограничений на вход и выход).

EPC

Метод EPC (Event-driven Process Chain — Событийные цепочки процессов) был создан в рамках методологии ARIS (Architecture of Integrated Information Systems — Архитектура интегрируемых информационных систем), разработанной компанией IDS Scheer AG (Германия) для структурированного описания, анализа, последующего совершенствования бизнес-процессов предприятия и управления ими, а также подготовки к внедрению сложных информационных систем.

EPC основан на использовании направленных графов событий и функций, которые соединены связями, задающими условное и параллельное выполнение процессов. Кроме этого, EPC определяет использование логических операторов, таких как OR, AND и XOR. Основное преимущество EPC заключается в его простоте и наглядности, что позволяет широко использовать данный метод для описания бизнес-процессов. В то же время EPC и ARIS содержат в себе огромное количество различных элементов, которые затрудняют процесс моделирования, хотя и упрощают понимание моделей.

Достоинства: использование процессного подхода, наглядность диаграмм.

Недостатки: слабая формализация синтаксиса и семантики диаграмм, сложность процесса моделирования, направленность на описание бизнес-процессов.

UML

Унифицированный язык моделирования (UML) [3—5] является стандартным инструментом для визуализации, специфицирования, конструирования и документирования артефактов программных систем.

Первая версия стандарта UML вышла в 1997 г., а в 2004 г. был утвержден стандарт UML 2.0 [4]. В основе UML лежит объектно-ориентированный подход (ООП), целью применения которого является выделение объектов, задействованных в процессе, и распределение между ними ответственностей за выполняемые действия. Словарь языка UML включает три вида строительных блоков: сущности, отношения и диаграммы.

Достоинства: четкое выделение объектов, связей между ними и функций, разделение связей по управлению и данным, возможность специфицирования процессов.

Недостатки: слабая формализация синтаксиса и семантики диаграмм, некоторая сложность для понимания диаграмм пользователям, не знакомым с ООП.

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

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

Таким образом, можно подвести следующие итоги по графическому подходу. Достоинствами являются простота и наглядность моделей для пользователя, стандартизация методов, их связь с моделированием бизнес-процессов. Недостатками графического подхода можно назвать слабую формализацию методов (EPC, UML), смешение связей по данным и управлению (IDEF-SADT), слабо выраженную временную последовательность (DFD, IDEF-SADT).

2. Формальный подход

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

Теория множеств

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

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

Достоинства: простая для понимания и наглядная математическая абстракция, четкий синтаксис и семантика.

Недостатки: сложность представления взаимосвязей, необходимость использования теории множеств в совокупности с другими методами для моделирования структуры системы.

Теория графов

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

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

В теории графов разработаны методы анализа отдельных классов графов. Одним из методов, который может быть применен для построения структуры системы, является алгоритм решения задачи о кратчайшем пути, которая сводится к нахождению минимальных путей во взвешенном графе от одной вершины до всех остальных. Известны различные реализации алгоритма решения этой задачи: волновой алгоритм, алгоритм Дейкстры, алгоритм Беллмана-Форда, алгоритм Флойда и другие. Существуют работы по синтезу структур программных и аппаратных систем на основе алгоритма решения задачи о кратчайших путях [6]. С помощью этого алгоритма производится построение оптимальной структуры системы на основе данных о характеристиках ее составных частей.

Достоинства: наглядное представление элементов системы и связей между ними, четкий синтаксис и семантика.

Недостатки: отсутствие возможности отображения динамики системы, акцентирование внимания на понятии состояний.

Конечные автоматы

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

M = (K, S, p, s, F),

где K — конечное множество состояний автомата, s Î K — единственно допустимое начальное состояние автомата, F Ì K — множество конечных состояний, причём допустимо F = Æ, и F = K, Σ — допустимый входной алфавит, из которого формируются строки, считываемые автоматом, p: K ´ S ® K — функция переходов. Автомат начинает работу в состоянии s, считывая по одному символы входной строки. Считанный символ переводит автомат в новое состояние из K, в соответствии с функцией переходов. Процесс продолжается до тех пор, пока не будет достигнуто одно из состояний F.

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

Достоинства: наглядное представление элементов системы и связей между ними, четкий синтаксис и семантика.

Недостатки: ограниченные возможности отображения динамики системы, акцентирование внимания на понятии состояний.

Сети Петри

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

Сети Петри — это математическая дисциплина, основанная на классической теории графов и являющаяся расширением теории конечных автоматов. Она возникла в 60-х годах ХХ века и с тех пор постоянно развивается. В рамках этого подхода рассматривались различные версии и модификации сетей Петри (под разными названиями). Независимо предполагались также формализмы, которые оказывались эквивалентными по своим свойствам и возможностям сетям Петри. На основе одного из вариантов сетей Петри (High-level Petri Nets) в настоящее время создается международный стандарт ISO/IEC 15909 [8]. Сети Петри — сложная, хорошо развитая теория, в ней строго определены такие понятия, как состояния, условия, переходы и т. п. Она включает также графическую нотацию (систему графических обозначений, с помощью которых можно изображать соответствующие графы). Эта область хорошо исследована математиками: установлены многие свойства сетей Петри, доказаны важные теоремы.

Практическое использование теории сетей Петри в основном было связано с описанием поведения сложных систем, например элементов интегральных схем. Существует немало работ, которые используют сети Петри для описания и исследования алгоритмов работы программных систем (например, [9, 10]), и, на наш взгляд, данный подход предлагает удобную формализацию системы с целью ее последующего моделирования.

Достоинства: предоставляют возможность математически строгого описания системы с разделением состояний и процессов (переходов).

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

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

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

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

– модель системы должна обладать свойством иерархичности в целях удобства ее представления;

– разбивку системы на локальные алгоритмы следует производить в соответствии с используемыми данными;

– необходимо различать связи по данным и по управлению;

– расчет общих характеристик и свойств системы следует вести на основе характеристик локальных алгоритмов;

– модель системы должна отражать динамику системы и четкую временную последовательность процессов.

Разработку метода синтеза и его описание планируется изложить в будущих работах.

1. Болонкин А. В. Сравнительный анализ технологий системного проектирования. Сборник статей международной конференции «CAD/CAM/PDM-2005». — М.: ИПУ РАН, 2005

2. Integration Definition for Function Modeling (IDEF0). Draft Federal Information Processing Standards Publication. 1993. — 128 p.

3. Буч Г., Рамбо Дж., Якобсон А. Язык UML. Руководство пользователя. — М.: ДМК, 2001. — 432 с.

4. Unified Modeling Language: Infrastructure. Version 2.0. 2005

5. Леоненков А. В. Самоучитель по UML. — BHV–Санкт-Петербург, 2004. — 432 с.

6. Артамонов Е. И., Хачумов В. М. Синтез структур специализированных средств машинной графики. - М.: ИПУ РАН, 1991

7. Котов В. Е. Сети Петри. — М.: Наука. 1984. — 160 с.

8. High-level Petri Nets — Concepts, Definitions and Graphical Notation. Final Draft International Standard ISO/IEC 15909. 2000

9. Maciel P., Barros E., Rosenstiel W. A Petri Net Model for Hardware/Software Codesign // Design Automation for Embedded Systems. — 1999. #4. — P. 243–310

10. Shinkawa Y. A Formal Approach to Software Composition in Component Based Software Development. — The University of Tsukuba, 2000