УНИВЕРСИТЕТ ИТМО
Кафедра «Технологии программирования»

Алгоритмизация и программирование для систем логического управления и «реактивных» систем

5. Алгоритмизация и программирование "реактивных" систем

Технология, описанная в разд.2, предназначена для создания алгоритмического и программного обеспечения систем логического управления, в которых ввод входных переменных выполняется только путем опроса [155, 156] - используется "циклический исполнитель" [91]. Другая особенность этой технологии состоит в том, что при ее применении программы реализуются компилятивно: по графам переходов строятся конструкции switch или их аналоги, которые выполняются непосредственно и поэтому являются "активными".

А. А. Грабовский (АО "Каскод", Санкт-Петербург) применил автоматный подход, изложенный в [8], для программной реализации логической части систем управления, проектируемых на микроконтроллерах фирмы "Сименс", для которых характерен развитый механизм обработки прерываний. При этом по таблично заданным графам переходов автоматически строится массив (напоминающий конструкции switch), который является "пассивным" и обрабатывается интерпретатором, учитывающим возможность появления запросов на обработку во время, когда микроконтроллер реализует соответствующий переход в одном из графов.

Этот подход использовал также и С. Б. Терентьев (НПО "Аврора") при реализации протоколов в распределенных управляющих системах, построенных на основе указанных микроконтроллеров. При этом написание программ выполнялось формально и изоморфно непосредственно по построенным графам переходов.

Н. И. Туккель (НПО "Аврора") и автор применили SWITCH-технологию при разработке системы управления дизель-генератором, реализуемой на промышленном компьютере и операционной системе QNX, в которой управляющая программа выполняется как один процесс, а программа, моделирующая объект управления - как другой процесс. При этом был создан вариант SWITCH-технологии для "реактивных" систем [39, 186], ввиду того что управление на основе событий приводит к существенным отличиям при проектировании системы по сравнению со случаем применения в ней только "циклического исполнителя" [91]. Такие системы обычно реализуются на промышленных компьютерах, работающих под управлением операционных систем реального времени.

Этот вариант технологии характеризуется следующими особенностями:

• в качестве базового используется понятие "автомат", а не "класс", "объект", "алгоритм" или "агент", как это имеет место при других подходах. При этом соответствующая область программирования может быть названа "автоматно-ориентированное программирование";
• в общем случае автоматы рассматриваются не изолированно, а как составные части взаимосвязанной системы - системы взаимосвязанных автоматов, поведение которой формализуется с помощью системы взаимосвязанных графов переходов;
• в качестве основной применяется модель смешанного автомата, для описания поведения которого используется соответствующий граф переходов только с "простыми" состояниями (гиперсостояния не используются);
• расширена (по сравнению с [8]) нотация, применяемая при построении графов переходов (например, в части перечисления вложенных автоматов);
• на этапе изучения предметной области на основе технического задания, которое при автоматизации технологических процессов обычно выдается Заказчиком в словесной форме в виде совокупности сценариев и случаев использования [91], строится структурная схема системы, позволяющая получить общее представление об организации управления, применяемой аппаратуре и интерфейсе объекта управления;
• на этапе анализа на основе технического задания выделяются сущности, каждая из которых называется автоматом (например, автомат управления насосом или автомат контроля температуры);
• состояния каждого автомата первоначально определяются по выделенным состояниям объекта управления или его части, а при большом их количестве - по алгоритму управления, построенному в другой нотации (например, в виде схемы алгоритма [51]);
• в автоматы также могут быть введены и другие состояния, связанные, например, с неправильными действиями Оператора;
• каждый автомат при необходимости может быть декомпозирован;
• итеративный процесс анализа может выполняться многократно и завершается созданием перечня автоматов и перечня состояний для каждого из них;
• на этапе проектирования в отличие от традиционного программирования вводится подэтап - кодирование состояний автомата. При этом в каждом автомате для различия состояний применяется многозначный код, в качестве комбинаций которого вводятся десятичные номера состояний;
• автоматы взаимодействуют за счет обмена номерами состояний, вложенности и вызываемости. Они также могут быть одновременно вложенными и вызываемыми;
• строится схема взаимодействия автоматов, отражающая указанные типы взаимодействий. Она формализует систему взаимодействующих автоматов. Эта схема заменяет в предлагаемой технологии диаграмму объектов и частично диаграмму взаимодействий (диаграмму кооперации), которые применяются в объектном моделировании [91];
• входные воздействия разделяются на события, действующие кратковременно, и входные переменные, вводимые путем опроса;
• входные воздействия целесообразно реализовывать в виде входных переменных, а применять события - для сокращения времени реакции системы. При этом одно и то же входное воздействие может быть одновременно представлено и событием и входной переменной;
• прерывания обрабатываются операционной системой и передаются программе в виде сообщений, а после этого обрабатываются как события с помощью соответствующих обработчиков;
• некоторые входные переменные могут формироваться в результате сравнения входных аналоговых сигналов с уставками;
• номера состояний других автоматов, с которыми автомат взаимодействует за счет обмена номерами состояний, также рассматриваются в качестве его входных воздействий;
• все выходные воздействия являются действиями, а не деятельностями;
• группы входных и выходных воздействий связываются с состояниями, выделенными для каждого автомата;
• связи каждого автомата с его "окружением" формализуются схемой связей автомата, предназначенной для полного описания интерфейса автомата. В этой схеме приводятся источники и приемники информации, полные названия всех воздействий и их обозначения, а также информация о том, в какой автомат он вложен и какие автоматы вложены в него;
• имя автомата начинается с символа 'A', имя события - с символа 'e' (от английского слова event - событие), имя входной переменной - с символа 'x', имя переменной состояния автомата - с символа 'y', а имя выходного воздействия - с символа 'z'. После каждого из указанных символов следует номер соответствующего автомата или воздействия;
• система взаимосвязанных автоматов образует системонезависимую (например, от операционной системы) часть программы, которая реализует алгоритм функционирования системы управления;
• реализация входных переменных, обработчиков событий, выходных воздействий, вспомогательных модулей и пользовательских интерфейсов образует системозависимую часть программы;
• обработчики событий содержат вызовы функций графов переходов (автоматов) с передачей им соответствующих событий. Функции входных и выходных воздействий вызываются из функций, реализующих автоматы. Функции, образующие вспомогательные модули, вызываются из функций входных и выходных воздействий. Таким образом, автоматы находятся в "центре" структуры программы, создаваемой на основе предлагаемого подхода;
• если составляющая системозависимой части программы спроектирована как автомат (например, автомат разбора файла рекомендаций Оператору), то он также может быть введен в схему взаимодействия автоматов;
• если платформа не изменяется, то вспомогательные модули могут быть использованы повторно, как образцы [91];
• запуск автоматов может производиться как из системозависимой части программы (например, из обработчиков событий), так и из системонезависимой части;
• вложенные автоматы последовательно запускаются с передачей "текущего" события в соответствии с путем в схеме взаимодействия автоматов, определяемым их состояниями в момент запуска головного автомата. При этом последовательность запуска и завершения работы автоматов напоминает алгоритм поиска в глубину [157];
• вызываемые автоматы запускаются из выходных воздействий с передачей соответствующих "внутренних" событий;
• автоматы могут запускаться однократно с передачей какого-либо события или многократно (в цикле) с передачей одного и того же события;
• при реализации системы учтено, что функции, реализующие автоматы, не реентерабельны (не допускают повторного запуска до их завершения);
• каждый автомат при запуске выполняет не более одного перехода;
• после обработки очередного события автомат сохраняет свое состояние и "засыпает" до появления следующего события;
• дуги и петли графов переходов помечаются произвольными логическими формулами, которые могут содержать входные переменные и предикаты, проверяющие номера состояний других автоматов и номера событий;
• дуги и петли кроме условий переходов могут содержать список последовательно выполняемых выходных воздействий;
• вершины в графах переходов практически всегда являются устойчивыми и содержат петли. Если на петле не выполняются выходные воздействия, то она умалчивается. В противном случае, в явном виде изображаются одна или несколько петель, каждая из которых помечена по крайней мере выходными воздействиями;
• вершина графа переходов может содержать список последовательно запускаемых вложенных автоматов и список последовательно выполняемых выходных воздействий;
• для обобщения "одинаковых" исходящих дуг в каждом графе переходов допускается объединение вершин в группы. Также допускается слияние входящих в вершину дуг в одну линию;
• каждый граф переходов проверяется на достижимость, непротиворечивость, полноту и отсутствие генерирующих контуров;
• этап завершается построением графа переходов для каждого автомата, совокупность которых образует систему взаимосвязанных автоматов;
• на этапе реализации строится программа, в которой графы переходов, входные переменные, обработчики событий и выходные воздействия выполняются в виде функций. Кроме того, программа содержит вспомогательные модули, состоящие из наборов соответствующих функций (например, модуль управления таймерами);
• выделение функций декомпозирует задачу, а выделение состояний - ее последовательностную логику;
• для хранения номера состояния автомата (различения состояний) используется одна внутренняя переменная. Для различения изменения состояния применяется вторая переменная, носящая вспомогательный характер;
• разработан универсальный алгоритм программной реализации иерархии графов переходов с произвольным их количеством и произвольным уровнем вложенности;
• каждый граф переходов формально и изоморфно реализуется отдельной функцией (подпрограммой), создаваемой по шаблону, содержащему две конструкции switch и оператор if. Первая конструкция switch вызывает вложенные автоматы и реализует переходы и действия на дугах и петлях. Оператор if проверяет изменилось ли состояние, и если оно изменилось, вторая конструкция switch активирует вложенные автоматы и реализует действия в новой вершине;
• после реализации графа переходов текст подпрограммы должен корректироваться для обеспечения бесповторности опроса входных переменных, помечающих дуги, исходящие из одного состояния. Таким образом, решается проблема "риска" [8];
• каждая входная переменная и каждое выходное воздействие также реализуется функцией, что и позволяет применять SWITCH-технологию не только для решения задач логического управления;
• имена функций и переменных, используемых при реализации автоматов, совпадают с обозначениями, применяемыми в схемах связей автоматов и графах переходов. Например, переменная, в которой хранится номер произошедшего события, имеет имя 'e';
• все функции, реализующие входные переменные, записываются в порядке возрастания их номеров в один файл, а реализующие выходные воздействия - в другой;
• функции, реализующие автоматы, входные переменные и выходные воздействия, содержат вызовы функций для обеспечения протоколирования;
• этап завершается построением структурной схемы разработанного программного обеспечения, отражающей взаимодействие его частей. Эта схема может включать схему взаимодействия автоматов, которая при этом отдельно не выпускается;
• на этапе отладки обеспечена возможность одновременной индикации значений переменных состояний всех автоматов на одном экране;
• на этапе сертификации за счет введения в функции автоматов, входных и выходных воздействий вызовов функций протоколирования обеспечено автоматическое ведение протокола. В нем указываются события, запуск автоматов, их состояния в момент запуска, переходы в новые состояния, завершение работы автоматов, значения входных переменных, выходные воздействия и время начала выполнения каждого из них. Кроме "полного" протокола также автоматически строится "короткий" протокол, в котором фиксируются только события и инициируемые ими выходные воздействия, интересующие Заказчика;
• сообщения в "полном" протоколе о запуске и завершении реализации каждого автомата играют роль скобок, логически выделяющих разные уровни вложенности автоматов;
• на этапе документирования для точного оформления результатов проектирования и разработки программы создается и сдается в архив документация (по крайней мере в электронном виде), имеющая как минимум следующую комплектность: структурная схема системы; схема разработанного программного обеспечения; распечатки экранов пользовательских интерфейсов; перечни событий, входных переменных и выходных воздействий; диаграмма взаимодействия автоматов; описание нотации, используемой в графах переходов; шаблон для реализации графов переходов смешанных автоматов произвольного уровня вложенности; для каждого автомата: словесное описание (фрагмент технического задания), рассматриваемое в качестве комментария, схема связей автомата, граф переходов и исходный текст функции, реализующей автомат; алгоритмы, например в виде графов переходов, и исходные тексты вспомогательных модулей и функций, реализующих входные переменные, обработчики событий и выходные воздействия; протоколы для сертификации программы, выполняющие роль контрольных примеров [158]; руководство программиста; руководство пользователя;
• изложенный вариант технологии может использоваться и при построении модели объекта управления, для которой должен создаваться аналогичный комплект документации;
• после этого, при появлении любых изменений, возникающих в ходе дальнейших этапов жизненного цикла программы, весь комплект документации (по завершении каждого этапа) должен корректироваться [159]. Для этого составляется перечень исполняемых модулей программы, в котором для каждого из них указывается значение циклической контрольной суммы, отражающей любое изменение в модуле. При этом Контролер по документации должен знать значение этой суммы для исходного файла, и после завершения каждого этапа при любом изменении указанного значения требовать представления извещения на выполненную модификацию, по которому документация должна быть комплектно откорректирована и сдана в архив.

Излагаемый вариант технологии обладает следующими достоинствами:

• в отличие от объектного моделирования [91, 113], во-первых, построение всех основных моделей основано на применении только автоматной терминологии, а во-вторых, используется динамическая модель только одного типа - система взаимосвязанных графов переходов;
• применение такой динамической модели позволяет эффективно описывать и реализовывать задачи рассматриваемого класса даже при большой их размерности. Применение графов переходов в качестве языка спецификаций алгоритмов делает обозримым даже весьма сложное поведение программы и позволяет легко вносить изменения как в спецификацию, так и в ее реализацию;
• совместное рассмотрение схемы связей автомата и его графа переходов позволяет понимать этот граф, а совместное рассмотрение этого графа и изоморфной ему подпрограммы позволяет понимать эту подпрограмму;
• подробное документирование проекта создания программного обеспечения позволяет при необходимости вносить изменения в него через длительный срок после его выпуска и даже другими Специалистами;
• без использования объектно-ориентированного подхода программа четко разделяется на две части - системонезависимую и системозависимую;
• при проектировании системонезависимой части программы детали реализации входных и выходных воздействий скрыты. Они раскрываются только при реализации системозависимой части программы;
• этапы проектирования и реализации системонезависимой части программы полностью разделены;
• реализация входных переменных и выходных воздействий в виде функций обеспечивает: их протоколирование, простоту перехода от одних типов источников и приемников информации к другим, наличие действующего макета программы [158] в любой момент времени после начала реализации системозависимой части;
• упорядоченное хранение функций, реализующих входные переменные и выходные воздействия, упрощает внесение изменений;
• для кодирования любого числа состояний автомата используется только одна внутренняя переменная, что обеспечивает наблюдаемость поведения автомата за счет "слежения" за изменениями значений только этой переменной. Для системы из N автоматов "слежение" выполняется по N многозначным переменным, значения каждой из которых выводятся на "отладочный" экран, представленный в форме, определяемой схемой взаимодействия автоматов;
• каждый граф переходов формально и изоморфно реализуется по шаблону, что при необходимости позволяет решить обратную задачу - однозначно восстановить граф переходов по этой подпрограмме;
• системонезависимая часть программы имеет регулярную структуру и, следовательно, легко читается и корректируется;
• системонезависимая часть программы зависит только от наличия компилятора или интерпретатора выбранного языка программирования на используемой платформе. При смене аппаратуры или переносе программы под другую операционную систему необходимо изменить только системозависимую часть;
• автоматическое ведение протокола в терминах спецификации обеспечивает возможность сертификации программы. При этом демонстрируется соответствие функционирования программы "поведению" системы взаимосвязанных графов переходов для рассматриваемых событий при выбранных значениях входных переменных. Это достигается за счет сопоставления "полного" протокола со спецификацией. Совокупность "полных" протоколов обеспечивает возможность сертификации программы в целом. Для сертификации в терминах, понятных Заказчику, могут применяться "короткие" протоколы, которые можно использовать также и в качестве фрагментов методики проверки функционирования системы. При этом отметим, что из двух групп понятий "объект-алгоритм" и "алгоритм-программа" сертификация обычно связывается только со второй группой понятий;
• "короткий" протокол позволяет определить наличие ошибки в выдаче выходных воздействий, а "полный" - определить автомат, который при этом необходимо откорректировать. Поэтому "короткие" протоколы могут быть названы "проверяющими", а "полные" - "диагностирующими";
• возможность автоматического получения "полных" протоколов в терминах автоматов показывает, что система взаимосвязанных графов переходов, используемая для спецификации алгоритмов, является не "картинкой", а математической моделью;
• несмотря на достаточно высокую трудоемкость проведения "подробной" сертификации при применении предлагаемых протоколов, этот способ существенно более практичен, чем другие подходы к построению качественных программ, которые изложены, например, в [160, 161];
• порождаемый некоторыми событиями протокол или его часть является соответствующим сценарием. Таким образом, сценарий [64] строится автоматически при анализе программы, а не вручную при ее синтезе, как это предлагается делать при других подходах [91, 113]. Ручное построение всей совокупности сценариев и формальный синтез системонезависимой части программы по ним для задач со сложной логикой практически не осуществимы;
• излагаемый подход не исключает интерактивной отладки и сертификации;
• поведение системы взаимосвязанных автоматов является разновидностью коллективного поведения автоматов [162] и может использоваться при построении "многоагентных систем, состоящих из реактивных агентов" [163].

Разработка системы управления дизель-генератором, выполненная с помощью предлагаемого варианта технологии [186], подтвердила мнение Ф.Брукса [158] о том, что время, затрачиваемое на проектирование алгоритма, при котором строятся не картинки, а математические модели, значительно превышает время, затрачиваемое на написание системонезависимой части программы, изоморфной спроектированному алгоритму, а также мнение Д.Воаса [164] о CASE-средствах, которые сами по себе мало что убыстряют, а "практика их применения показала только то, что из некорректных картинок можно получить некорректный код".

Текст подпрограммы, построенной с помощью предложенного варианта технологии, и "полный" протокол ее работы, проверяющий все переходы автомата, реализующего алгоритм управления объектом "тулбар", приведен в п.3.2 Приложения к работе [54].