Стрелки! Нале-во! Из задач для 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). Здесь предпринята попытка обойти стандартную проблему конечности и результативности алгоритма. С одной стороны, под такое определение подходят и наши «бесконечные» алгоритмы, но, с другой, остается вопросом, что считать результатом алгоритма и как быть с ролью бесконечных циклов в последовательных алгоритмах?

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

Абстрактные типы алгоритмов

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

К.Хоар в статье «О структурной организации данных» (см. [4]), определяя понятие абстрактных типов данных (АТД), выделяет следующие этапы абстрагирования: 1) абстракция; 2) представление; 3) манипуляция; 4) аксиоматизация. Если рассуждать по аналогии об АТА, становится понятной роль рассмотренных выше «бесконечных» алгоритмов и правомерность использования такого понятия.

1. Бесконечный» алгоритм — абстракция реального и вполне ощущаемого программистами понятия зацикливания программ (вредного или полезного, сознательно создаваемого или возникающего в результате логических ошибок — это особый вопрос).
2. Автоматная модель, как и блок-схема, — одна из форм представления алгоритмов. Она является основой для определения одного из возможных видов АТА (другие виды — блок-схемы, сети Петри и т.д.).
3. Манипуляции с формальной моделью (операции композиции-декомпозиции автоматов и др.) доказывают необходимость, пользу и полное право на существование бесконечно зацикленных алгоритмов.
4. Наличие аксиом на множестве операций над автоматами, или аксиоматизация параллельной модели, является дополнительным средством наведения порядка в рамках общей теории параллельных систем на базе автоматов (и не только их!).

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

Заключение

Еще раз спасибо В.Н. Пинаеву за инициирование важного и серьезного разговора, который в итоге привел к рассмотрению некоторых «вечных» понятий программирования. Он, как мне кажется, завершился достаточно плодотворно: мы прояснили роль бесконечных циклов и определили, по аналогии с АТД, понятие абстрактных типов алгоритмов — АТА. Это еще один пример того, как обсуждение, казалось бы, элементарных задач и проблем приводит к результатам, затрагивающим даже фундаментальные основы. А их (основ) понимание и развитие есть не что иное, как наше движение вперед по пути совершенствования знаний об окружающем мире. Что может быть важнее и интереснее?!

Оглянитесь налево-направо и, возможно, вы, как и новобранцы, откроете для себя в этом мире много удивительных вещей, которым тоже попытаетесь дать свое толкование, объяснение и обоснование. Успехов!

Литература

1. Любченко В.С. Батарея, огонь!, или Задача Майхилла для Microsoft Visual C++ (О синхронизации процессов в среде Windows)//Мир ПК. 2000, № 2, с.148—155.
2. Заморин А.П., Марков А.С. Толковый словарь по вычислительной технике. М.: Русский язык, 1988. 221 с.
3. Мальцев А.И. Алгоритмы и рекурсивные функции. 2-е изд. М.: Наука, 1986. 386 с.
4. Дал У., Дейкстра Э., Хоар К. Структурное программирование. М.: Мир, 1975. 248 с.