Новые песни о главном - II

Продолжим начатое в предыдущей статье (см. "Мир ПК", #6/98, с. 114) совершенствование "скелета" программ, т. е. их алгоритмической модели. В тот раз мы говорили в основном о моделировании двумерных программ, сейчас речь пойдет о параллельном программировании в третьем и четвертом измерениях (подробнее о метафоре измерений см. "Мир ПК", #10/97, с. 116), o формальной конечно-автоматной (КА) модели для этих измерений и ее реализации.

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

Для программирования автоматов вместо гипотетического языка мы будем теперь пользоваться языком Си++ и библиотекой поддержки автоматных классов FSA (библиотеку FSA можно получить по адресу http://www.osp.ru/pcworld/1998/01/fsamdi.zip).

Подпрограммы и реентерабельность

С точки зрения теории функции и подпрограммы (далее будем говорить только о подпрограммах) не очень интересны, но на практике они активно эксплуатируются программистами. И если с обычными подпрограммами все понятно, то какими должны быть КА-подпрограммы?

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

Как процесс подпрограмма имеет обычно те же характеристики, что и процесс, который ее запустил. Возможности управления выполнением ограничиваются, пожалуй, только запуском. Подпрограмма должна обязательно завершиться, чтобы вернуть управление вызвавшему ее процессу или процессу, к которому она была подключена (подключение подпрограммы к "чужому" процессу вполне возможно). Таковы в общих чертах основные характеристики, существенные для нас при рассмотрении процессов и подпрограмм.

Для организации КА-подпрограмм необходимо ввести понятие вложенного автомата (подавтомата) и определить, когда становятся истинными значения, которые являются результатом работы такого автомата.

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

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

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

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

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

В статье "О бильярде с Visual C++" (см. "Мир ПК", #1/98, с. 202) создание КА-процессов (мячиков) выполняется с помощью оператора LoadFSA (в примере FLoad), которому в качестве параметров передаются указатель на среду исполнения и приоритет процесса. Если к объектам-мячикам из статьи применить метод базового автоматного класса FCall, создающий подавтоматы, то те же КА-объекты начнут функционировать как КА-подпрограммы. Но для этого потребуется автоматный процесс, который бы их вызывал, а также изменения в алгоритме работы объектов, назначение которых - гарантировать завершение работы подавтомата. Действительно, процессы-мячики функционируют "вечно", а подпрограмма должна завершаться, т. е. автомат, соответствующий объекту, должен в какой-то момент переходить в заключительное состояние (в библиотеке FSA это состояние с именем "00"), поэтому в программу потребуется добавить фрагмент, который бы это обеспечивал.

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

Повторно входимые, или реентерабельные (re-entrant) программы и подпрограммы имеют огромное значение и особенно важны для параллельного программирования. В частности, ядро КА-системы, на которое возложена интерпретация автоматов, просто обязано быть реентерабельным, так как одновременно используется многими автоматными процессами.

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

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

О работе над ошибками

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

Технология на базе автоматной модели способна предложить новый уровень контроля качества создаваемого программного продукта. Механизмов его обеспечения у КА гораздо больше, чем у БС. Рассмотрим только один из самых простых и эффективных механизмов - контроль текущего состояния КА-программы.

Известно, что протестировать в полном объеме даже небольшой программный продукт очень сложно. Но предусмотреть анализ ошибочных ситуаций в любом состоянии КА-программы вполне возможно. Автомат или совершает переход в следующее состояние, или (если переход не определен) "виснет" в текущем. Используя эту особенность функционирования автоматной модели, можно легко ввести средства диагностики текущего состояния КА, которые значительно облегчат поиск и локализацию ошибочных ситуаций.

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

Пока же создается впечатление, что попытки выиграть "битву за надежность" (или лучше сказать "с надежностью"?) программных продуктов перешли в основном на организационный уровень (см., например, репортаж Г. И. Рузайкина "За качественное ПО" - "Мир ПК", #2/98, с. 52). Но если БС действительно не могут предложить ничего кардинально нового для повышения качества разработки программ, то для КА такие решения существуют. Одно из них мы только что обсудили.

Сетевая автоматная модель и RS-триггер

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

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

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

В первой статье приведен граф автомата отдельного элемента И-НЕ, входящего в состав триггера. Но это подавтомат, который всегда переходит в заключительное состояние "00". Чтобы модель И-НЕ соответствовала процессу, таблицу переходов автоматов нужно немного "подправить", добавив переходы (дуги) из состояния "S0" в состояние "S1"

Как видим, в новом варианте модель элемента И-НЕ даже проще. Отпала нужда в переменных, соответствующих выходному состоянию модели, и действиях, которые ими оперируют. Информацию о состоянии выходов модели можно получить, анализируя ее текущее внутреннее состояние. Нет и перехода из состояния "St" в состояние "S0": он был нужен, чтобы установить начальное значение переменной, соответствующей выходу элемента, а теперь начальным является состояние "S1".

Число предикатов не изменилось, и имена их остались прежними, но на графе они для наглядности обозначены по-другому. Первому предикату (он обозначен буквой R или S в зависимости от имени входа) соответствует один из входов триггера, а второму - состояние соседнего элемента И-НЕ (обозначен стрелкой от состояния соседнего автомата к синхронизируемой дуге перехода). Конъюнкция множества предикатов изображается "планкой" в стиле сетей Петри - утолщенным отрезком линии.

Программа трехмерного RS-триггера

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

С помощью структуры CPrmRS организуется управление триггером. Ее конструктор по умолчанию устанавливает данные, соответствующие входам триггера, в единицу. При этом, если на выходе элементов будет единица (соответствующее условие - состояние "S1" моделей элементов), триггер должен сразу войти в режим генерации. Далее, используя клавиши мыши, его можно из этого состояния вывести, войти в режим генерации опять или установить одно из устойчивых состояний.

Класс CIne представляет элемент И-НЕ. Он порожден из класса LFsaAppl - базового класса, реализующего компонентную модель сетевой автоматной модели. В составе класса CIne имеется два указателя - bX и tskIne. Первый необходим для связи с переменной, соответствующей одному из входов триггера, второй - это указатель на указатель элемента И-НЕ, подключенного ко второму входу элемента И-НЕ. Текущее внутреннее состояние этого элемента будет определять состояние второго входа элемента И-НЕ.

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

Класс CFlipFlop представляет собственно триггер. Он создает модели элементов и запоминает их адреса в соответствующих элементах структуры CPrmRS.

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

Вот и вся, причем в полном объеме, программа трехмерного триггера. Код, объемлющий модель триггера, кроме строк, подключающих FSA-библиотеку, может быть и другим. В данном случае он достаточно прост. Более сложную реализацию объемлющих классов можно найти в файле проекта, прилагаемого к электронной версии этой статьи (http://www.osp.ru/pcworld/1998/07/trigger.zip).

Четвертое программное измерение

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

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

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

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

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

О "неспетом"

При обсуждении аппаратных проблем совместной работы множества процессоров часто говорится, что на нерегулярных задачах сложно заставить работать эффективно более двух-четырех процессоров: при увеличении числа процессоров растут и накладные расходы на обеспечение параллельной работы, и в какой-то момент они начинают превышать выигрыш в производительности. Все это верно для модели БС, но не для автоматов. Уже для отдельной (компонентной) модели КА "планка" четырех процессоров легко преодолима. Как показывает опыт работы с автоматами, число предикатов и действий, которые могут быть запущены параллельно для нерегулярных задач, в этом случае намного выше. А ведь есть еще объединение автоматов в сеть!

Для автоматов чем больше процессоров, тем лучше. Уже простейшая задача моделирования триггера распараллелена на уровне сети на три процесса: два элемента И-НЕ и один процесс, отображающий состояние триггера. Как минимум два процессора для своих предикатов может задействовать каждый отдельный элемент И-НЕ и т. д. и т. п. Прямо дух захватывает, когда представляешь, с какой скоростью можно заставить работать RS-триггер! И если о таких аппаратных перспективах пока можно только мечтать, то существующая виртуальная автоматная машина позволяет познакомиться с тем, как это может быть и, я надеюсь, когда-нибудь будет.

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

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

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