А.А. Шалыто – Программная реализация управляющих автоматов.

А.А. Шалыто.

Источник: http://is.ifmo.ru/works/switch_prr/

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

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

Технология предполагает пять стадий разработки автоматных программ, каждая из которых состоит из ряда этапов: системное проектирование (1-7); проектирование формальной спецификации автомата или системы взаимосвязанных автоматов (8-13); логическое проектирование автоматов (14-20); программирование (21,22); проверка правильности программ (23-27), применимая для задач небольшой размерности. Перечислим этапы разработки.

    I. Системное проектирование.

  1. Описание объекта управления с выделением источников и приемников информации и указанием его свойств.
  2. Описание «алгоритма» управления, заданного заказчиком.
  3. Дополнение «алгоритма», учитывающее опыт разработки.
  4. Выбор органов управления и средств представления информации.
  5. Построение схемы связей «органы управления — управляющий автомат — органы управления — средства представления информации».
  6. Представление в случае необходимости управляющего автомата в виде взаимосвязанной системы управляющих автоматов.
  7. Декомпозиция каждого управляющего автомата на автомат и функциональные элементы задержки.

    II. Проектирование формальной спецификации автомата или композиции автоматов.

  8. Выбор языка спецификаций, позволяющего в доступной форме согласовать с заказчиком поведение автомата и легко перейти к программе. Выполнено сравнение функциональных схем, схем алгоритмов и графов переходов и обоснован выбор последних в качестве языка спецификации.
  9. Построение исходного графа переходов для каждого автомата с учетом взаимодействия автоматов.
  10. Обеспечение полноты и непротиворечивости графа переходов для каждого автомата.
  11. Согласование системы взаимосвязанных автоматов (формальной спецификации) с заказчиком.
  12. Построение формальной спецификации для функциональных элементов задержки.
  13. Построение формальной спецификации для модели объектов управления.

    III. Логическое проектирование автоматов.

  14. Выбор структурной модели каждого автомата (автомат без выходного преобразователя, автомат Мура и т.д.) и разновидности, зависящей от расположения технологических элементов задержки в модели.
  15. Выбор вида кодирования состояний каждого автомата (принудительное, логарифмическое, многозначное и т.д.). Обоснован выбор многозначного кодирования.
  16. Выбор алгоритмической модели программной реализации каждого автомата (система булевых формул, таблица переходов, схема алгоритма, конструкция switch). Обоснован выбор конструкция switch.
  17. Построение алгоритмической модели каждого автомата.
  18. Оптимизация булевых формул, помечающих дуги графов переходов (раздельная или совместная).
  19. Выбор и построение алгоритмической модели функциональных элементов задержки.
  20. Выбор и построение алгоритмической модели объектов управления.

    IV. Программирование

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

    V. Проверка правильности программ, применимая для задач небольшой размерности.

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

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

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

Изоморфизм графа переходов и конструкции switch обеспечивает управляемость (изменяемость) программной реализации.

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

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