В системах управления логика может быть реализована как программно, так и аппаратно. Вопросы аппаратной реализации конечных автоматов достаточно хорошо изучены, известен ряд эффективных методов решения этой задачи. Однако эти методы не относятся напрямую к предмету этой книги (задачи логического управления интересны нам не сами по себе, а как источник концепций, которые легли в основу парадигмы автоматного программирования). Поэтому в данном разделе обсуждается только программная реализация автоматов в задачах логического управления. На практике программная реализация применима в тех случаях, когда управление осуществляется программируемым вычислительным устройством (программируемым логическим контроллером, микроконтроллером, персональным компьютером и т. п.).В данном разделе предполагается, что объекты управления, их сигнализаторы и исполнительные механизмы реализованы аппаратно. Поэтому обсуждаться будет только технология программной реализация управляющей части системы: автомата или множества взаимодействующих автоматов. Для иллюстрации предлагаемой технологии выбран язык программирования C. С одной стороны, этот язык традиционно используется для реализации систем управления, а с другой — является относительно высокоуровневым и достаточно популярным. Отметим, что это всего лишь пример: обсуждаемая технология может быть использована совместно с большинством существующих императивных языков программирования.
Каковы критерии оптимальности технологии программной реализации автоматов в системах логического управления? Исходя из специфики данной области (сложное поведение, жесткие ограничения на время выполнения и объем занимаемой памяти), основными критериями можно считать следующие. Возможность формального преобразования графа переходов автомата в проyyграммный код. Проектирование логики — одна из главных и самых трудных задач при создании систем со сложным поведением. Графы переходов помогают справиться с этой задачей, делая логику наглядной. Было бы нецелесообразно, уже построив граф переходов, однозначно описывающий логику, предпринимать еще одно творческое усилие, чтобы преобразовать диаграмму в код. Это преобразование должно быть формальным и однозначным. В этом случае его можно поручить машине. Изоморфизм программного кода графу переходов автоматаyy. Если программный код предназначен для чтения и модификации человеком, то каждому структурному элементу графа переходов (состоянию, переходу) должна соответствовать отдельная конструкция языка программирования. Такое однозначное соответствие в работе [4] названо изоморфизмом. Эффективность по времени и по памяти.yy Большинство управляющих систем являются системами реального времени. В качестве вычислительных устройств, осуществляющих управление, чаще всего используются микроконтроллеры, в которых объем памяти, доступной пользователю, невелик. В связи с этим следует отдавать предпочтение менее гибким, но более простым и быстрым решениям. Пусть на стадии проектирования для управления системой был построен активный автомат Мура первого рода с s состояниями, n входными и m выходными переменными. Работу этого автомата можно описать с помощью блок-схемы (рис. 2.29).
Алгоритм начинается с блока инициализации, в котором внутренней переменной присваивается номер стартового состояния. Далее следует бесконечный цикл, в котором последовательно выполняются ввод входного воздействия, вызов функции, реализующей один такт работы автомата, и вывод выходного воздействия. Реализация блоков ввода и вывода зависит от конкретной системы и не относится напрямую к предмету этой книги. Поэтому далее в этом разделе обсуждается только реализация функции «Такт». В течение каждого такта работы автомату необходимо: в зависимости от текущего состояния установить некоторые выходные переyyменные в единицу, а остальные — в ноль; в зависимости от текущего состояния и значений входных переменных обновить yyсостояние.Эту последовательность действий можно описать с помощью блок-схемы так, как это показано на рис. 2.30 Вверху схемы расположен дешифратор состояний, в котором поток управления разветвляется в зависимости от значения текущего состояния. В каждой из ветвей находится блок формирования выходного воздействия и дешифратор входных воздействий (в нем поток управления разветвляется в зависимости от значения текущего входного воздействия). Для обозначения входных воздействий в схеме для удобства вместо битовых векторов используются эквивалентные им натуральные числа. В каждой из ветвей, исходящих из дешифраторов входных воздействий, выполняется обновление текущего состояния. В языке C существует два основных способа реализации такого алгоритма: с помощью таблиц и с помощью инструкции выбора.В первом случае функции выходов и переходов автомата представляются в виде таблиц (массивов) в памяти. Для того чтобы представить функцию выходов, требуется массив из s элементов, сопоставляющий вектор значений выходных переменных каждому состоянию. Для представления функции переходов требуется таблица из s строк и 2n столбцов, сопоставляющая каждому состоянию и вектору значений входных переменных новое состояние. Таблицы действий и переходов строятся динамически во время выполнения программы. Поэтому данный способ является более гибким по сравнению с использованием инструкции выбора: автомат можно изменять в ходе выполнения программы. Однако эта гибкость достигается ценой некоторой потери производительности. Кроме того, при описанном способе хранения размер таблицы переходов растет экспоненциально с увеличением числа входных переменных автомата. В большинстве случаев нет объективной необходимости хранить всю эту таблицу целиком: значение функции переходов в каждом состоянии зависит не от всех компонентов входного воздействия, а лишь от небольшого набора значимых входных переменных. Это наблюдение можно использовать для сокращения размера таблиц переходов и действий в том случае, если требуется компактное представление автоматов, которое можно легко создавать и модифицировать в процессе выполнения программы. Например, такое представление необходимо для оптимизации автоматов, которая обсуждается в параграфе 4.4. В контексте настоящего раздела динамическая модификация структуры автомата не требуется. Поэтому в целях повышения быстродействия предпочтение следует отдать второму из упомянутых выше способов реализации (с помощью инструкции выбора), так как он является статическим. Для обозначения инструкции выбора в C используется ключевое слово switch. В других императивных языках программирования высокого уровня имеются аналогичные инструкции. Инструкции выбора можно использовать для реализации дешифраторов состояний и входных воздействий (см. рис. 2.30). В результате шаблон реализации такта автомата Мура примет следующий вид (листинг 2.1).При таком подходе автомат описывается статически — его структура закодирована в тексте программы. Это свойство обеспечивает требуемое быстродействие. Однако остается другая проблема: экспоненциальный рост описания автомата с ростом числа входных переменных. Действительно, число меток case во вложенной инструкции выбора, а следовательно, и объем текста программы экспоненциально зависит от n (числа входных переменных).
Для решения этой проблемы вспомним наблюдение, сделанное в связи с таблицами: в большинстве случаев только небольшой набор входных переменных является значимым в каждом состоянии. Поэтому в указании значения функции переходов для всех возможных входных воздействий нет необходимости. Как правило, только некоторые сочетания значений нескольких входных переменных приводят к смене состояния. По-видимому, наиболее компактный способ записи функции переходов используется в нотации графов переходов: для каждого состояния задается множество исходящих переходов, помеченных условиями в виде булевых формул. Опыт показывает, что в реальных задачах размер этих формул практически не увеличивается с ростом числа входных переменных. Предложенный выше шаблон реализации легко модифицировать так, чтобы в нем использовалось компактное представление функции переходов. Для этого достаточно заменить внутреннюю инструкцию выбора несколькими инструкциями ветвления (по числу дуг, исходящих из данного состояния на графе переходов). Условиями ветвления будут метки исходящих дуг. Отметим, что петлям в автомате Мура сопоставлять инструкции ветвления нет необходимости. Модифицированный шаблон реализации представлен в листинге 2.2.Решение проблемы неоправданно большого объема представления автомата попутно привело к еще одному улучшению: формальное преобразование графа переходов в код стало проще. Однако действительно ли описание переходов из состояния в виде последовательности инструкций ветвления изоморфно описанию в виде множества исходящих дуг? Источником несоответствия может быть тот факт, что инструкции ветвления всегда выполняются в порядке, заданном текстом программы, а порядок проверки условий на дугах в графе не определен. Однако в корректном (непротиворечивом) графе переходов порядок проверки условий на дугах не имеет значения. Если же в графе переходов дугам назначены приоритеты, то и в тексте программы соответствующие инструкции ветвления должны располагаться в порядке, заданном приоритетами. В качестве примера использования рассмотренного шаблона приведем реализацию автомата системы управления клапаном, проектирование которого обсуждалось в разделе 2.1.1.Отметим, что ключевые слова else в данной реализации введены исключительно для повышения быстродействия программы. Поскольку условия переходов из каждого состояния в этом случае ортогональны, указанные ключевые слова можно не писать. Выше обсуждалась реализация систем со сложным поведением, управляемых одним автоматом. Перейдем к вопросам реализации систем, управляемых взаимодействующими автоматами. В этом случае такт работы каждого из автоматов удобно реализовать в виде отдельной функции. Если автоматы в системе взаимодействуют путем обмена номерами состояний, то в условиях ветвления, кроме входных переменных, будут участвовать внутренние переменные других автоматов. В блоках формирования выходных воздействий помимо инструкций присваивания значений выходным переменным появятся обращения к вложенным и вызываемым автоматам. Обращение к вложенному автомату выполняется путем вызова функции, реализующей такт его работы. Обращение к вызываемому автомату — более сложная операция. Один из способов ее реализации предполагает создание для каждого вызываемого автомата Ai (описанного с помощью функции void A<i>()) дополнительной функции, которая имеет следующую структуру: После этого в точке обращения к вызываемому автомату выполняется вызов функции Call_A<i>().Если при проектировании системы была произведена параллельная автоматная декомпозиция, то существует два основных варианта реализации. Вся система выполняется на одном процессоре. В этом случае необходимо 1. обеспечить псевдопараллельную работу автоматов. Здесь проявляется одно из достоинств автоматного программирования: даже в том случае, если среда выполнения не поддерживает многозадачность, псевдопараллельное выполнение автоматов легко обеспечить, поместив вызовы соответствующих им функций подряд в теле цикла главной программы (рис. 2.31).Каждый автомат выполняется на отдельном процессоре. В этом случае каждая 2. из функций, реализующих такты работы автоматов системы, помещается в свой собственный цикл внутри отдельной главной программы. Здесь на первый план выступают вопросы взаимодействия и синхронизации. В частности, необходимо обеспечить согласованность данных, которыми обмениваются автоматы в системе. Выбор того или иного решения этих проблем зависит от специфики конкретной системы. В качестве примера приведем реализацию системы управления двумя клапанами. Из нескольких вариантов архитектуры, предложенных в разделе 2.1.2, выберем тот, в котором осуществлялась параллельная автоматная декомпозиция. Предположим, что система должна выполняться на одном процессоре. Листинг 2.5 содержит реализации функций, отвечающих за такт работы каждого из двух автоматов, а также шаблон реализации главной программы.