Стрелки! Нале-во! Из задач для Microsoft Visual C++...

В меню программы добавим пункты для выбора вида поворота (налево/направо) и для выполнения одного дискретного шага автоматного времени модели.

В. С. Любченко

Меню примера

В меню программы добавим пункты для выбора вида поворота (налево/направо) и для выполнения одного дискретного шага автоматного времени модели. По умолчанию новобранцы по команде Fire (ее название осталось прежним, хотя содержание изменилось) поворачиваются налево, а программа работает в пошаговом режиме: после подачи команды и отображения начального положения новобранцев каждая следующая конфигурация цепи выводится, когда пользователь выбирает в меню пункт Step.

Чтобы отменить пошаговый режим, нужно в классе CBullet убрать из кода предиката x4 анализ переменной bStep, заменив его на «жесткий» возврат значения true. Тогда вся последовательность поворотов новобранцев будет отображаться сразу после команды Fire в соответствии с предварительно установленным типом поворота.

Счетчик поворотов

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

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

Лучше всего поместить счетчик в класс CChainShot, создающий цепь новобранцев, и ввести указатель на него в класс новобранца. Увеличивать значение счетчика, очевидно, должен класс CHead. Можно было бы делать это в действиях y6 и y7, соответствующих повороту направо и налево, но поскольку они выполняются и при инициализации объекта (в действии y5 на переходе из состояния «st» в «b1»), то имеет смысл ввести специальное действие y8, вставив его на переходы между состояниями «Л» и «П».

Контролер

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

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

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

Код класса «контролерского лица» представлен в листинге 5, а конструктор класса CChainShot, подключающий «второе лицо» к последнему в строю новобранцу, — в листинге 6.

Особенности параллельной реализации

Параллельное программирование столь же существенно отличается от обычного, как, например, объектное от структурного. Сейчас ООП, несмотря на сложности его освоения, приобрело статус стандарта де-факто. Думаю, что в недалеком будущем это произойдет — просто обязано произойти! — и с параллельным программированием. Но точно так же, как существуют нюансы в применении объектной парадигмы, так не обходится без них и параллельное программирование.

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

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

Другое дело контролер. Он должен вывести значение счетчика только после того, как его изменят все, кто хотел. Но как определить нужный момент, особенно при непредсказуемом числе потребителей ресурса? Проблема решается с помощью механизма приоритетов (вот для чего мы вводили их в классе TBounce!). Как уже упоминалось, приоритет задается при загрузке автоматного процесса с помощью метода FLoad класса LFsaAppl. У этого метода два параметра: адрес объекта, реализующего автоматную среду, в которую «грузится» компонентный автомат сети, и значение приоритета для данного автомата.

Библиотека FSA допускает три значения приоритета — 0, 1 и 2, причем чем больше значение, тем позже исполняется процесс. Ранее, в задаче Майхилла, всем автоматным объектам (стрелкам, пулям и офицеру) по умолчанию присваивался один и тот же приоритет, равный 1. Оставим его неизменным, а процессу-контролеру, который должен выполняться после всех поворотов, установим более низкий приоритет 2 (см. листинг 5).

Бесконечное программирование

Чистая математика делает то, что можно, и так, как нужно. Прикладная математика делает то, что нужно, и так, как можно.

Профессиональный фольклор

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

Сколько можно организовать бесконечных циклов в последовательном программировании? Один и только один, а лучше, скажут, — ни одного! Безусловно, вы сможете написать программу и с несколькими бесконечными циклами (рискуя при этом получить соответствующее предупреждение от «умного» компилятора), но при исполнении программа зациклится на первом из них, а до остальных очередь просто не дойдет.

Без преувеличений можно сказать, что вся история последовательного программирования представляет собой борьбу со случайным или «преднамеренным» проникновением бесконечных циклов в программы. Фактически она еще продолжается: скажем, проблема зацикливания обработчиков сообщений в Windows актуальна и сейчас, несмотря на выход все более совершенных версий ОС.

Иное дело — параллельное программирование. Это мир «бесконечных» алгоритмов. То, чего избегают, что отвергают в последовательном программировании и что для него смертельно, оказывается удобным, эффективным и полезным для программирования параллельного, так что можно предложить заменить заезженное выражение «параллельное программирование» термином «бесконечное программирование».

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

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

Так, согласно большинству неформальных определений алгоритм — это результативная, конечная во времени последовательность определенных шагов [2]. И лишь очень редко определение алгоритма дополняется пунктами типа: «если способ получения последующей величины из какой-нибудь заданной величины не дает результата, то должно быть указано, что надо считать результатом алгоритма (направленность алгоритма)» ([3], с. 10). Здесь предпринята попытка обойти стандартную проблему конечности и результативности алгоритма. С одной стороны, под такое определение подходят и наши «бесконечные» алгоритмы, но, с другой, остается вопросом, что считать результатом алгоритма и как быть с ролью бесконечных циклов в последовательных алгоритмах?

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

22.10.2001г