Санкт-Петербургский государственный университет информационных

технологий, механики и оптики

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

Шопырин Данил Геннадьевич

Методы объектно-ориентированного проектирования

и реализации программного обеспечения

реактивных систем

Специальность 05.13.13 – Телекоммуникационные системы и

компьютерные сети Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель – доктор технических наук, профессор Шалыто А.А.

Санкт-Петербург Оглавление ВВЕДЕНИЕ

ГЛАВА 1. ОБЗОР МЕТОДОВ ПРОЕКТИРОВАНИЯ И

РЕАЛИЗАЦИИ РЕАКТИВНЫХ СИСТЕМ НА ОСНОВЕ

КОНЕЧНЫХ АВТОМАТОВ

1.1. Язык описания и спецификации SDL

1.2. Графический язык Statecharts

1.3. Синхронное программирование

1.3.1. Язык Argos

1.3.2. Язык SyncCharts

1.4. SWITCH-технология

1.5. Реализация систем на основе SWITCH-технологии

1.6. Конечные автоматы в объектно-ориентированных системах 1.6.1. Паттерн проектирования State и его варианты

1.6.2. Реализация автоматных объектов на основе методов........ 1.6.3. Расширение поведения конечных автоматов с помощью наследования

Выводы

ГЛАВА 2. РЕАЛИЗАЦИЯ АВТОМАТНЫХ СИСТЕМ НА

ОСНОВЕ БИБЛИОТЕКИ STOOL

2.1. Термины и определения

2.2. Архитектура библиотеки STOOL

2.3. Обзор классов библиотеки STOOL

2.4. Основные возможности

2.4.1. Выделение состояния системы в целом

2.4.2. Действия и деятельности

2.4.3. Повторное использование автоматов

2.4.4. Автоматическое протоколирование

2.4.5. Механизм обработки ошибок

2.4.6. Параллельные вычисления

2.4.7. Реализация входных и выходных воздействий.................. 2.5. Пример использования библиотеки STOOL

2.5.1. Проектирование и реализация автоматов

2.5.2. Реализация окружения

2.5.3. Связывание системы автоматов

2.5.4. Протоколирование работы системы

2.5.5. Запуск системы автоматов

Выводы

ГЛАВА 3. ГРАФИЧЕСКАЯ НОТАЦИЯ ДЛЯ

ПРОЕКТИРОВАНИЯ АВТОМАТНЫХ ОБЪЕКТОВ

3.1. Термины и определения

3.2. Наследование автоматных объектов

3.3. Декомпозиция и структурирование логики автоматных объектов

3.4. Диаграммы поведения автоматных объектов

3.4.1. Графическое представление наследования автоматов...... 3.4.2. Графическое представление структурирования логики автоматных объектов

Выводы

ГЛАВА 4. РЕАЛИЗАЦИЯ АВТОМАТНЫХ ОБЪЕКТОВ НА

ОСНОВЕ ВИРТУАЛЬНЫХ МЕТОДОВ И ВИРТУАЛЬНЫХ

ВЛОЖЕННЫХ КЛАССОВ

4.1. Демонстрационный пример: доступ к файлу

4.2. Реализация автоматных объектов на основе виртуальных методов

4.2.1. Термины и определения

4.2.2. Метод реализации автоматных объектов на основе виртуальных методов

4.2.3. Отношения и взаимодействия

4.2.4. Реализация посредника

4.2.5. Реализация контекста и структурирование логики............ 4.2.6. Расширение логики с помощью наследования

4.2.7. Каркас VMBase

4.2.8. Недостатки VM-метода

4.3. Реализация автоматных объектов на основе виртуальных вложенных классов

4.3.1. Термины и определения

4.3.2. Метод реализации автоматных объектов на основе виртуальных вложенных классов

4.3.3. Отношения и взаимодействия

4.3.4. Реализация посредника

4.3.5. Реализация контекста и структурирование логики.......... 4.3.6. Расширение логики с помощью наследования................. 4.3.7. Реализация расширения поведения в группе состояний. 4.3.8. Каркас VICBase

Выводы

ГЛАВА 5. ВНЕДРЕНИЕ ПРЕДЛОЖЕННЫХ МЕТОДОВ

ПРОЕКТИРОВАНИЯ И РЕАЛИЗАЦИИ АВТОМАТНЫХ

ОБЪЕКТОВ В ПРАКТИКУ РАЗРАБОТКИ РЕАКТИВНЫХ

СИСТЕМ

5.1. Эмуляция систем связи Inmarsat-C и Inmarsat-D+

5.1.1. Область внедрения

5.1.2. Использование глобальных систем спутниковой связи.. 5.1.3. Тестирование взаимодействия с системами глобальной спутниковой связи

5.1.4. Постановка задачи

5.1.5. Применимость автоматного программирования.............. 5.1.6. Проектирование поведения терминала системы Inmarsat 5.1.7. Реализация терминала системы Inmarsat

5.2. Каркас для построения графических редакторов Iris............. 5.2.1. Обзор каркаса Unidraw

5.2.2. Механизмы редактирования в каркасе Unidraw............... 5.2.3. Архитектура каркаса Iris

5.2.4. Механизмы в каркасе Iris

5.2.5. Реализация манипуляторов в каркасе Iris

5.3. Сравнение методов реализации автоматных объектов.......... Выводы

ЗАКЛЮЧЕНИЕ

ЛИТЕРАТУРА

Введение Актуальность проблемы. При разработке объектно-ориентированного программного обеспечения телекоммуникационных систем актуальна задача проектирования, описания и реализации их поведения. Программные системы можно разделить на следующие классы [1]:

• преобразующие системы – это системы, завершающие свое выполнение после преобразования входных данных (например, архиватор, компилятор). В таких системах обычно входные данные известны и доступны на момент запуска системы, а выходные данные доступны после ее завершения;

• интерактивные системы – это системы, взаимодействующие с окружающей средой в режиме диалога (например, текстовый редактор). Характерной особенностью таких систем является то, что они могут контролировать скорость взаимодействия с окружающей средой – заставлять окружающую среду «ждать»;

• реактивные системы – это системы, взаимодействующие с окружающей средой посредством обмена сообщениями в темпе, задаваемом средой.

Многие телекоммуникационные системы являются представителями класса реактивных систем. Реактивные системы имеют следующие особенности [1]:

• время отклика реактивной системы задается ее окружением;

• поведение реактивных систем детерминировано;

• для реактивных систем характерен параллелизм;

• сбои в работе реактивных систем крайне нежелательны.

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

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

• язык описания и спецификации SDL (Specification and Description • унифицированный язык моделирования UML (Unified Modeling • язык синхронного программирования SyncCharts [4, 5].

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

• отсутствие удобных и непротиворечивых способов перехода от Для устранения этих недостатков с 1991 года в России разрабатывается SWITCH-технология [6], также известная как «автоматное программирование», которая предназначена для спецификации и реализации систем со сложным поведением, в том числе и телекоммуникационных. Графы переходов, используемые в автоматном программировании, весьма компактны, так как применяются совместно со схемами связей автоматов, подробно описывающими их интерфейс. Однако в автоматном программировании остаются недостаточно проработанными следующие вопросы:

• совместное использование объектно-ориентированного и автоматного программирования;

• объектно-ориентированное проектирование программного обеспечения реактивных систем;

• объектно-ориентированная реализация программного обеспечения реактивных систем.

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

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

Основные задачи

исследования состоят в следующем:

• совершенствование методов реализации автоматных систем на основе SWITCH-технологии;

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

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

Методы исследования. В работе использованы методы теории автоматов, объектно-ориентированного проектирования и программирования.

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

1. Предложен метод реализации автоматных систем на основе библиотеки STOOL (SWITCH-Technology Object Oriented Library), устраняющий ряд недостатков SWITCH-технологии.

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

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

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

Результаты диссертации были получены в ходе выполнения научноисследовательских работ «Разработка технологии программного обеспечения систем управления на основе автоматного подхода», выполненной по заказу Министерства образования РФ в 2001 – 2005 гг., и «Разработка технологии автоматного программирования», выполненной по гранту Российского фонда фундаментальных исследований № 02-07-90114 в 2002 – 2003 гг.

(http://is.ifmo.ru, раздел «Наука»).

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

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

Внедрение результатов работы. Результаты, полученные в диссертации, используются на практике:

• в компании Транзас (Санкт-Петербург) при разработке системы мониторинга мобильных объектов Navi-Manager, и в частности, ее коммуникационного сервера;

• в компании Транзас (Санкт-Петербург) при разработке каркаса для построения редакторов пространственных данных Iris;

• в учебном процессе на кафедре «Компьютерные технологии»

СПбГУ ИТМО при чтении лекций по курсу «Теория автоматов в Апробация диссертации. Основные положения диссертационной работы докладывались на научно-методических конференциях «ТелематикаТелематика-2004», «Телематика-2005» (Санкт-Петербург) и XXXIII конференции профессорско-преподавательского состава СПбГУ ИТМО (Санкт-Петербург, 2004).

Публикации. По теме диссертации опубликовано 7 печатных работ, в том числе в журналах «Информационно-управляющие системы» и «Информационные технологии моделирования и управления».

Структура диссертации. Диссертация изложена на 174 страницах и состоит из введения, пяти глав и заключения. Список литературы содержит 78 наименований.

Работа иллюстрирована 53 рисунками и содержит три таблицы.

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

Глава 1. Обзор методов проектирования и реализации реактивных систем на основе конечных автоматов 1.1. Язык описания и спецификации SDL Язык SDL (Specification and Description Language) является языком проектирования и реализации, предназначенным для разработки сложных, распределенных приложений [7]. Язык SDL используется для описания структуры, поведения и потоков данных системы. Типичной областью применения языка SDL является отрасль телекоммуникаций.

Разработка языка SDL началась в 1972 году в CCITT (Comit Consultatif International de Tlgraphique et Tlphonique). Первая версия языка SDL была выпущена в 1976 году. Последующие версии языка выпускались каждые четыре года. На сегодняшний день SDL является во всех смыслах полным и зрелым языком.

Отличительные черты современных версий языка SDL:

• язык SDL стандартизован международным стандартом ITU-T (International Telecommunications Union Technical standards group) • язык SDL является формальным языком, гарантирующим точность, целостность и четкость дизайна;

• язык SDL имеет изоморфные друг другу графическое и текстовое • язык SDL является самодокументирующимся языком проектирования и реализации;

• язык SDL является объектно-ориентированным языком, поддерживающим инкапсуляцию, полиморфизм и динамическое связывание;

• язык SDL имеет высокий уровень тестируемости, являющийся следствием высокой формальности языка;

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

Система на языке SDL состоит из следующих компонентов:

• структура – иерархия систем, блоков, процессов и процедур;

• коммуникации – система каналов и передаваемых по ним сигналов;

• поведение – процессы системы;

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

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

Рис. 1. Основные обозначения, используемые в SDL-диаграммах На рис. 2 в качестве примера приведена SDL-диаграмма процесса, управляющего доступом к некоторому ресурсу [9].

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

1.2. Графический язык Statecharts Графический язык проектирования программных систем Statecharts был предложен в работе [10]. Большинство известных подходов к проектированию систем с использованием конечных автоматов основаны, в той или иной степени, на языке Statecharts. Язык Statecharts является, в своем роде, родоначальником целого семейства языков и технологий, использующих конечные автоматы.

Язык Statecharts является расширением традиционной модели конечных автоматов [11], облегчающим разработку и спецификацию сложных реактивных систем. В традиционную модель добавляются элементы, позволяющие описывать такие понятия, как иерархия и параллелизм [12, 13].

Иерархия вводится путем вложенных состояний. Вложение состояний семантически соответствует операции XOR (исключительное ИЛИ). Если состояния A и B вложены в состояние C, как показано на рис. 3, то система может находиться только в одном из них, но не в обоих одновременно. Состояние C является абстракцией состояний A и B.

Например, микроволновая печь может находиться в состояниях ON и OFF (рис. 4,a). Причем, в состояние ON вложены состояния WAVE и GRILL.

Достоинством вложения состояний является то, что на некотором уровне детализации, пользователь может абстрагироваться от наличия состояний WAVE и GRILL (рис. 4,b), что чрезвычайно важно при проектировании сложных многомодульных систем.

Рис. 4. Пример абстрагирования посредством вложения состояний Параллелизм вводится путем ортогональных состояний. Ортогонализация состояний семантически соответствует операции AND (логическое И).

Если состояния A и B ортогональны друг другу и вложены в состояние C, как показано на рис. 5, то система обязана находиться в обоих этих состояниях одновременно (ортогональные состояния в языке Statecharts разделяются пунктирной линией). Таким образом, состояния A и B параллельны друг другу, а состояние C является их ортогональным произведением.

Пусть, например, самолет состоит из двух независимых подсистем – NAVIGATION и RADAR. Подсистема NAVIGATION содержит состояния ON_GROUD, CLIMB и CRUISE, а подсистема RADAR содержит состояния OFF и ON. Благодаря ортогонализации, эта система в целом может быть изображена так, как показано на рис. 6.

Соответствующий граф переходов традиционного конечного автомата (рис. 7) является произведением [14] конечных автоматов рассмотренных подсистем и содержит шесть состояний (3 x 2). Если бы каждая из подсистем содержала тысячу состояний, то результирующий граф переходов содержал бы миллион состояний. Данный эффект называется комбинаторным взрывом и является основным недостатком традиционных конечных автоматов. Отметим, что язык Statecharts успешно преодолевает эту проблему благодаря механизму ортогональных состояний.

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

Например, подсистемы самолета NAVIGATION и RADAR могут содержать состояния MALFUNCTION, в которое они переходят по событию FAIL (рис. 8).

Допустим, что подсистема NAVIGATION находится в состоянии CRUISE, а подсистема RADAR – в состоянии ON. В случае если окружением системы будет сгенерированно событие FAIL, обе подсистемы перейдут в свои состояния MALFUNCTION одновременно.

Рис. 8. Пример использования широковещательных событий ориентированным вариантом языка Statecharts [3, 15]. Автоматы в языке UML используются для задания поведения отдельных объектов. Конечные автоматы являются удобным способом описания поведения объектов или порядка вызова их операций.

Согласно спецификации [15], язык UML State Machines отличается от классического языка Statecharts следующим образом:

• события могут содержать параметры, в то время как в языке Statecharts они являются примитивными сигналами;

• не поддерживаются предопределенные действия языка Statecharts, такие как entered(s), exited(s) и т.д.

• не поддерживаются широковещательные события (broadcast), однако поддерживаются события предписанные множеству объектов;

• поддерживается понятие синхронного взаимодействия между автоматами;

• действия на переходе выполняются в порядке перечисления;

• поддерживаются точки динамического выбора (dynamic choice • модель выполнения опирается на потоки (threads), в отличие от языка Statecharts, опирающегося на «синхронное выполнение».

1.3. Синхронное программирование С начала 90-х годов в Западной Европе развиваются технологии программирования реактивных систем под общим названием «синхронное программирование» [4, 16].

Объясним основную идею синхронного программирования. Известно, что схемы делятся на синхронные, асинхронные и апериодические (с самосинхронизацией) [17]. При построении вычислительных машин в основном используются синхронные схемы, важнейшей составляющей которых являются синхронные автоматы с памятью. Каждый из таких автоматов содержит две составляющие (рис. 9):

• автомат без памяти, осуществляющий функциональное преобразование;

• тактируемые элементы памяти, хранящие состояние автомата.

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

В синхронном программировании вводится термин реакция. Реакция – это неделимый такт работы системы, в процессе которого все ее компоненты синхронно обрабатывают входные сигналы, изменяют свое состояние и формируют выходные сигналы. Считается, что длительность любой реакции равна нулю. В результате, интервалы реакции превращаются в моменты реакции. Следовательно, реакции не перекрываются друг с другом. Таким образом, система «работает» только в моменты реакций. Между моментами реакций система «бездействует». Это предположение называется синхронной гипотезой или гипотезой атомарных реакций [18].

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

Существуют две основные модели реактивных систем:

• системы, управляемые событиями (рис. 10,а);

• системы, управляемые таймером (рис. 10,б).

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

• вектором входных переменных ~i ;

• вектором выходных воздействий ~i.

Тогда реакция системы в целом есть комбинация реакций всех компонентов системы. При этом для каждого компонента справедлива система соотношений:

Комбинация реакций отдельных компонентов обеспечивается тем, что входные или выходные значения i-го компонента могут являться также входными значениями для j-го компонента:

где xin (k ) означает k-ю координату вектора ~in.

Отметим, что система, заданная таким образом не всегда имеет однозначное детерминированное поведение. Дело в том, что в ней могут возникнуть мгновенные обратные связи. Эта ситуация проиллюстрирована в терминах синхронных конечных автоматов на рис. 11 (мгновенная обратная связь выделена пунктиром).

Рис. 11. Мгновенная обратная связь при соединении двух автоматов Эта проблема может быть решена как минимум четырьмя разными способами [4]:

• каждая реакция системы разбивается на последовательность элементарных микрошагов (что приводит к многочисленным противоречивым интерпретациям [12]). Данный подход используется в Very High Speed Integrated Circuit Hardware Description Language (VHDL) [19], языке Statecharts [10] и других системах.

• вводится требование, что система не может содержать мгновенных обратных связей. Данный подход используется в языке программирования Lustre [20].

• вводится требование, что каждой реакции системы соответствует ровно один вариант перехода в следующее состояние. Данный подход используется в языке Esterel [21].

• вводится требование, что каждой реакции может соответствовать ни одного (программа заблокирована), один или более вариантов перехода в следующее состояние. В последнем случае имеет место недетерминированное поведение. Данный подход используется в языке Signal [22].

Язык Argos – это графический язык программирования, оперирующий конечными автоматами [23]. Синтаксис языка Argos похож на синтаксис языка Statecharts. Основным отличием является тот факт, что язык Argos опирается на синхронную гипотезу.

Также как и Statecharts, язык Argos оперирует конечными автоматами, расширяя синтаксис последних введением вложенных и ортогональных состояний.

В качестве примера на рис. 12 приведена программа, которая по каждому четвертому событию e1 генерирует событие e2.

Множество состояний на графе переходов обозначается множеством прямоугольников. Граф переходов имеет одно начальное состояние, помеченное дугой без начальной вершины. Множество переходов между состояниями представлено множеством помеченных дуг. Метки переходов состоят из входного и выходного воздействий, записанных в формате I[/O], где I — входное воздействие, а O – необязательное выходное воздействие.

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

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

1.3.2. Язык SyncCharts Язык SyncCharts – это графический язык программирования [5, 24], семантика которого полностью соответствует семантике языка Esterel [21].

Многие возможности унаследованы [25] из языков Statecharts и Argos.

Язык SyncCharts предоставляет мощный и гибкий синтаксис. Особенностью данного языка являются вытесняющие инструкции. Вытеснение (preemption) – это отказ некоторому процессу в праве выполняться навсегда (сильная форма) или временно (слабая форма) [26].

Простой пример программы на языке SyncCharts, взятый из работы [24], показан на рис. 13. Данная программа подсчитывает количество сигналов T и в момент, когда счетчик достигает значения пять, генерирует сигнал тревоги Alarm. Счетчик запускается посредством сигнала set и может быть прерван в любой момент сигналом reset.

Рис. 13. Watchdog – пример использования языка SyncCharts Конечное состояние обозначается двойной окружностью. Начальное состояние помечается дугой перехода, не имеющей начала. Нормальное завершение обозначается стрелкой с треугольником. Строгое вытеснение обозначается стрелкой с окружностью.

Примером строгого вытеснения может служить обработка сигнала reset. В момент возникновения этого сигнала все процессы, вложенные в состояние isON, немедленно прерываются и система покидает это состояние.

1.4. SWITCH-технология С 1991 года для программирования реактивных систем развивается SWITCH-технология [6, 27–36], также известная как «автоматное программирование» или «программирование с явным выделением состояний», которая в качестве языка спецификации использует графы переходов.

Семантика используемых в SWITCH-технологии графов переходов близка к семантике языка Statecharts, но не эквивалентна ей. В SWITCHтехнологии вводятся понятия автомат и вложение автоматов, и отсутствуют понятия вложенных и ортогональных состояний. Вложение и ортогонализация состояний в SWITCH-технологии реализуется посредством вложения автоматов и введения понятия «система автоматов».

Рассмотрим реализацию примеров, приведенных в разд. 1.2 с использованием SWITCH-технологии (используя синтаксис предлагаемый в работе [27]). На рис. 14 представлен аналог системы, изображенной на рис. 4.

Рис. 14. Пример абстрагирования посредством вложения автоматов Недостатком реализации на основе SWITCH-технологии, по сравнению с языком Statecharts, является наличие дублирующего состояния OFF в автомате A1.

Достоинство SWITCH-технологии состоит в лучшей инкапсуляции, так как:

• факт наличия разных режимов работы неизвестен на уровне автомата A0;

• отсутствуют переходы между разными уровнями детализации как, например, это имеет место при переходе из состояния OFF в На рис. 15 представлен аналог системы, изображенной на рис. 6.

Рис. 15. Пример ортогонализации посредством вложения автоматов К достоинствам, по сравнению со Statecharts-версией, можно отнести тот факт, что при использовании вложения автоматов не возникает проблемы с нотацией, как это имеет место при использовании вложенных ортогональных состояний [10]. Так, например, в языке Statecharts возникают трудности с расположением названия макросостояния, содержащего вложенные ортогональные состояния. Поэтому на рис. 6 название макросостояния AIRCRAFT изображено вовне прямоугольника этого состояния.

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

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

1.5. Реализация систем на основе SWITCH-технологии Согласно работе [29], автоматное программирование не противопоставляется процедурному или объектно-ориентированному программированию, и может быть использовано совместно с ними. Однако до сих пор остаются нерешенными некоторые проблемы, связанные с совместным использованием автоматного и объектно-ориентированного программирований.

В работе [29] предлагается хранить текущее состояние автомата в виде одной многозначной переменной интегрального типа (в частности, перечислимого типа). В этом случае поведение автомата реализуется с помощью оператора switch по этой переменной с вложенными условными операторами if по входным событиям.

Основными недостатками данного подхода являются:

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

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

• отсутствие механизмов автоматического протоколирования.

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

Указанные недостатки являются источником ошибок и затрудняют поддержку и сопровождение программных систем.

Использование двух последовательно выполняющихся операторов switch и «ручной» учет предыдущего состояния автомата связаны с необходимостью различения действий и деятельностей в состояниях [37].

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

1.6. Конечные автоматы в объектно-ориентированных системах Конечные автоматы широко используются при проектировании реактивных систем. Однако после перехода на объектно-ориентированную методологию, использование конечных автоматов сократилось по причине отсутствия полностью объектно-ориентированных методов их реализации. Многие номинально объектно-ориентированные методы реализации конечных автоматов, на самом деле, больше относятся к структурному программированию [38]. Наличие же больших блоков структурного кода в объектноориентированной программе ведет к потере однородности и, вследствие чего, усложнению системы.

Наиболее распространенные не объектно-ориентированные методы реализации конечных автоматов основаны на:

• вложенных условных операторах if [39];

• вложенных операторах switch [40];

• операторах goto [41];

• таблицах переходов [42, 43].

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

Применение четвертого метода снижает читабельность исходного кода.

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

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

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

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

Обзоры существующих объектно-ориентированных методов реализации автоматных объектов приведены в работах [38, 44–46]. В настоящей работе предлагаются два новых метода реализации автоматных объектов:

• метод реализации автоматных объектов на основе виртуальных • метод реализации автоматных объектов на основе виртуальных вложенных классов (разд. 4.3).

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

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

К сожалению, в современной иностранной и отечественной литературе сложилась путаница в отношении термина состояние (state). Основными альтернативными вариантами являются:

• macrostate (макросостояние) – используется достаточно редко (упоминается в [47]), конфликтует с термином «макросостояние»

• управляющее или автоматное состояние – используется в отечественных работах по SWITCH-технологии [48].

• mode (режим работы) – новый, еще не устоявшийся, термин В результате этой несогласованности иногда возникают весьма курьезные ситуации. Например, работа [47] называется «Methods for states», но в ней используется термин mode. В настоящей работе в качестве основного термина используется управляющее состояние, или просто состояние. Однако в первой главе, при обзоре существующих подходов к реализации автоматных объектов, используется оригинальная терминология.

1.6.1. Паттерн проектирования State и его варианты Наиболее известным методом реализации автоматных объектов является паттерн проектирования State, описанный в работе [49]. Многие современные методы реализации автоматных объектов, в том числе и предложенный в данной работе метод на основе виртуальных вложенных классов, являются усовершенствованными вариантами паттерна State.

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

Структура паттерна State приведена на рис. 16. Использование этого паттерна позволяет варьировать поведение объекта в зависимости от его внутреннего состояния таким образом, что извне создается впечатление изменения класса объекта.

Кроме управляющего состояния, или просто состояния, кардинальным образом влияющего на поведение объекта, объект может также иметь вычислительное состояние. Под вычислительным состоянием понимается совокупность всех атрибутов объекта, не управляющая его поведением непосредственно. Например, объект, управляющий поведением микроволновой печи, может находиться в управляющих состояниях OFF, WAVE и GRILL. Кроме того, этот объект должен хранить температуру в печи, время приготовления и другие параметры. Множество подобных атрибутов автоматного объекта является его вычислительным состоянием.

В паттерне State участвуют следующие объекты:

• контекст – определяет интерфейс автоматного объекта, хранит экземпляр текущего конкретного состояния и переадресует ему • состояние – определяет интерфейс для инкапсуляции поведения в • конкретное состояние – реализует поведение автоматного объекта в одном из его состояний.

Предлагается несколько вариантов отношений между объектами:

• контекст может передавать указатель на самого себя конкретным состояниям. В этом случае экземпляры состояний могут совместно пользоваться методами и полями контекста. Однако в результате этого увеличивается связность между контекстом и конкретными состояниями;

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

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

• переход в следующее состояние может осуществляться либо контекстом, либо объектом состояния. Первый вариант приводит к централизации логики автоматного объекта [50]. Второй — способствует увеличению гибкости системы [51], и, в частности, делает возможным расширение логики автоматного объекта с помощью наследования;

Достоинства паттерна проектирования State:

• не зависящее от управляющего состояния поведение автоматного объекта локализуется в классах управляющих состояний;

• переходы между состояниями выполняются явно.

Недостатки паттерна проектирования State:

• данный паттерн неудобен в случае большого числа состояний, так как приводит к написанию большого числа конкретных состояний;

• контекст отвечает за корректную диспетчеризацию всех внешних вызовов, что повышает связность системы.

На данный момент известно множество альтернативных вариантов паттерна State, некоторые из которых описаны ниже.

1.6.2. Реализация автоматных объектов на основе методов Рассмотрим альтернативный подход к реализации автоматных объектов, предложенный в работе [47]. Метод, поведение которого зависит от текущего состояния объекта, реализуется совокупностью методов, имеющих одинаковую сигнатуру и описывающих какой-то один вариант поведения объекта. В этом случае, состояние автоматного объекта хранится в виде набора указателей на методы, реализующие поведение объекта в данном состоянии. Таким образом, состояние автоматного объекта хранится не в виде скалярной переменной, а в виде вектора указателей на методы. Переключение состояний автоматного объекта осуществляется путем изменения одного или нескольких таких указателей.

Достоинствами этого метода являются:

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

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

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

1.6.3. Расширение поведения конечных автоматов с помощью наследования Проектирование и реализация сложных автоматных объектов на основе простых имеет большую практическую ценность, так как способствует:

• повторному использованию исходного кода;

• структурированию и декомпозиции исходного кода;

• сокращению дублирования исходного кода.

Вышеперечисленное приводит к сокращению затрат на поддержку и сопровождение программных систем.

Вопрос построения сложных объектов на основе более простых достаточно хорошо разработан в объектно-ориентированном программировании.

Основными применяемыми методами являются:

• наследование с использованием механизма виртуальных функций;

• мета-программирование на основе шаблонов.

В работе [51] описан ряд методов, позволяющих расширять логику конечных автоматов. При порождении производных автоматных объектов используются такие методы объектно-ориентированного программирования, как:

Наиболее интересным для настоящего исследования является расширение поведения автоматных объектов с помощью наследования. В предлагаемом в работе [51] методе реализации автоматных объектов контекст хранит указатель на текущие состояние и переадресует ему все вызовы интерфейса автоматного объекта. Все методы классов состояний возвращают экземпляр следующего состояния. Экземпляры состояний создаются в качестве глобальных переменных или статических переменных класса.

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

Возможность реализации перегрузки перехода достигается благодаря использованию так называемых «таблиц состояний» (StateMap). Таблицы StateMap аналогичны механизму таблиц виртуальных функций vtbl языка программирования C++ [52]. Каждое состояние автоматного объекта получает собственную таблицу состояний как параметр конструктора. Переход в следующее состояние осуществляется косвенно, через таблицу состояний StateMap.

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

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

Выводы Из изложенного выше следует:

• существующие методы реализации программных систем на основе SWITCH-технологии обладают рядом недостатков (использование двух операторов switch, отсутствие автоматического контроля изменения состояний автоматов, отсутствие средств автоматического протоколирования и т.д.);

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

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

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

Глава 2. Реализация автоматных систем на основе библиотеки STOOL В работах [27–29, 53] предлагается метод построения объектноориентированных программ с явным выделением состояний. В указанных работах подробно рассмотрены вопросы проектирования программ этого класса. Однако методы программной реализации, предлагаемые в них, обладают следующими недостатками:

• не выделено состояние системы;

• в функции, реализующей автомат, применяются два оператора switch, так как нет механизма различения действий и деятельностей в состояниях. Этот подход снижает удобочитаемость кода и увеличивает вероятность ошибки;

• нет механизма обеспечения повторного использования реализованных автоматов;

• функции протоколирования вручную вводятся в текст программы программистом, что нельзя назвать «автоматическим» построением протокола;

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

В настоящей работе предлагается способ реализации программных систем рассматриваемого класса, устраняющий перечисленные недостатки. В качестве базы для разработки программ с выделением состояний предлагается библиотека STOOL - SWITCH-Technology Object Oriented Library [37, 54]. В настоящее время эта библиотека реализована на языке C++. Ниже будет описана библиотека STOOL и рассмотрены вопросы разработки программных систем с ее использованием.

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

Автомат – конкретный экземпляр класса автоматов.

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

Выходное воздействие – некоторая операция, изменяющая внешнюю среду.

Система автоматов – совокупность автоматов.

Состояние системы – совокупность состояний всех автоматов системы.

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

Исключительная ситуация – возникает в случае невозможности опроса входного воздействия или выполнения выходного воздействия.

Этап автомата – набор последовательных запусков, в течение которых автомат сохраняет свое состояние.

Шаг этапа – каждый запуск автомата в течение этапа.

Действие в состоянии – вызов некоторого выходного воздействия, происходящий во время первого шага этапа автомата.

Деятельность в состоянии – вызов некоторого выходного воздействия, происходящий на каждом шаге этапа.

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

2.2. Архитектура библиотеки STOOL Предлагаемая архитектура программных систем отличается от архитектуры, предлагаемой в работах [27–29, 53]. Эти отличия состоят в следующем:

• автоматы, входные и выходные воздействия являются объектами;

• явно вводятся понятия класс автоматов и экземпляр класса автоматов;

• каждый автомат не располагает никакой информацией о других автоматах системы. При этом, во-первых, автомат не знает о существовании других автоматов, во-вторых, он не может непосредственно проверять их состояния, как это было предложено, например, в работе [6], а в-третьих – не может непосредственно запускать другие автоматы. Единственная связь автомата с «внешним миром» – это входные и выходные воздействия;

• автоматные объекты содержат только свое управляющее состояние. Вычислительное состояние вынесено за пределы автоматов и хранится в специальном объекте – окружении. Автоматы получают доступ к вычислительному состоянию исключительно через входные и выходные воздействия.

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

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

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

Поясним теперь, почему в рамках предлагаемого подхода понятие «событие» не применяется. Это связано с переносимостью библиотеки STOOL, на базе которой предлагается реализовывать системы. В разных системах существуют различные модели возникновения и обработки событий, которые весьма трудно обобщить в понятной и краткой форме. Введение в библиотеку какой-нибудь одной модели обработки событий сузило бы область применения библиотеки, а введение нескольких моделей усложнило бы дизайн библиотеки и простоту ее использования. Поэтому в рамках предлагаемой архитектуры реализация механизмов обработки событий возлагается на пользователя. Так, в случае использования операционной системы Windows, пользователь должен самостоятельно создавать и регистрировать обработчики событий этой системы, логика которых, однако, вынесена в автоматы.

Пусть, например, для левой кнопки мыши введено входное воздействие x0, возвращающее значение true, если кнопка нажата. При получении уведомления от пользовательского интерфейса о том, что кнопка нажата (например, событие WM_LBUTTONDOWN в ОС Windows), пользователь устанавливает соответствующий флаг и запускает автоматы, обрабатывающие это событие.

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

2.3. Обзор классов библиотеки STOOL Библиотека STOOL предоставляет абстрактные базовые классы для реализации автоматов, входных и выходных воздействий, а также «инфраструктуру» для организации системы в целом (рис. 17).

Рис. 17. Диаграмма основных классов библиотеки STOOL Для реализации автоматов, входных и выходных воздействий необходимы следующие классы библиотеки STOOL:

• Auto – базовый класс для разработки классов автоматов. Для определения класса автоматов программист должен переопределить метод execution(), реализующий граф переходов автомата;

• State – класс, который хранит состояние автомата. Каждый экземпляр класса Auto содержит экземпляр класса State. Класс State обеспечивает также протоколирование любого (даже ошибочного) изменения состояния автомата. Изменять экземпляр класса State программист может только внутри метода execution(), реализующего граф переходов;

• Input – базовый класс для реализации входных воздействий;

• Output – базовый класс для реализации выходных воздействий;

• Impact – класс, описывающий процесс выполнения выходного воздействия. Он предоставляет следующие методы: «Выполнить», «Откатить» и «Подтвердить». При каждом выполнении выходного воздействия создается соответствующий ему экземпляр класса Impact, который и осуществляет это воздействие.

Ниже приведено описание классов, необходимых для создания «инфраструктуры» системы:

• System – класс, управляющий системой автоматов. Содержит экземпляр класса ChangeServer, описанного ниже. Он также хранит список всех автоматов системы. Предполагается, что пользователь может создавать потомков класса System;

• Change – класс, управляющий системным переходом. При возникновении исключительной ситуации во время выполнения системного перехода этот класс отвечает за разворачивание (unwind) стека выполненных выходных воздействий. Класс Change является абстрактным. Библиотека STOOL предоставляет два потомка этого класса – SingleTaskChange и MultiTaskChange (для однопоточной и многопоточной работы). Эти классы могут быть расширены пользователем;

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

Дальнейшее описание библиотеки приводится в последующих разделах работы. Так, например, описываются методы Output::action(), Output::activity() и Output::jumpAction(), реализующие различные типы выходных воздействий.

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

Информацию обо всех автоматах системы можно получить с помощью метода System::enumerate(), а обо всех выполняющихся переходах – с помощью экземпляра класса возвращаемого методом System::getChangeServer().

Приведем пример кода, распечатывающий список автоматов системы, в котором используется метод System::enumerate():

/*...*/ 002 struct AutoReceiver 003 : public ItemsReceiver 004 { 005 virtual bool receiveCount( int _count ) {