SoftCraft: Задача о стрелках

SoftCraft
разноликое программирование

Задача о стрелках

Программа, демонстрирующая решение описываемой задачи (21 кб)

Формулировка задачи

В [1] приведена следующая формулировка задачи о стрелках, предложенной Майхиллом. "Имеется цепь стрелков, каждый из которых может общаться только с двумя своими непосредственными соседями. Цепь состоит из конечного числа стрелков, два крайних стрелка имеют только по одному соседу. Один из крайних стрелков получает команду, после чего стрелки должны договориться и одновременно произвести выстрел. Существуют ли правила поведения стрелков, обеспечивающие решение этой задачи, если количество слов, которыми могут обмениваться стрелки и объем внутренней памяти каждого из них ограничены и не зависят от длины цепи?"

Уточнение постановки задачи

Выше приведена достаточно расплывчатая формулировка задачи. Чтобы успешно ее решить, необходимо уточнить некоторые моменты.

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

Следствием данных уточнений является то, что ни какой сигнал не может распространиться посредством объектом мгновенно: каждый объект, участвующий в процессе передачи сигнала, вносит в его распространение как минимум единичную задержку. Кроме того, объекты взаимодействия (в нашем случае - стрелки), реализуя подсчет интервалов времени, способны при необходимости осуществить и задержку распространения сигнала на необходимое число тактов абстрактного времени. Данные уточнения приводят к следующей формулировке задачи Майхилла (см. [2]).

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

В некоторый момент левофланговый (или правофланговый) получает пакет с приказом "пли!", который адресован всем стрелкам и должен быть выполнен ими одновременно.

Алгоритм решения задачи

В соответствии с уточнениями алгоритм решения задачи может сводиться к следующему алгоритму поведения каждого отдельного стрелка, который можно свести к выполнению следующих указаний (см. также [2, 3]).

"Указание 1. Если ты левофланговый и получил приказ "шеренга, пли", то запомни свой номер 1 и сообщи его правому соседу.

Указание 2. Если ты не правофланговый и левый сосед сообщил тебе номер V, запомни свой номер V+1 и в следующую секунду сообщи его правому соседу.

В соответствии с этой частью инструкций на n-й секунде все стрелки уже будут знать свои порядковые номера. Дальнейшие указания регулируют обратный поток информации от правофлангового к левофланговому.

Указание 3. Если ты правофланговый и левый сосед сообщил тебе номер n-1, то в следующую секунду отвечай ему "готов!" и приступай к обратному счету в уме: n, n-1, n-2, …, т.е. в каждую секунду считай по одному числу.

Указание 4. Если твой порядковый номер V и правый сосед доложил тебе "готов!", то со следующей секунды приступай к обратному счету V, V-1, …; при этом, если V>1, т.е. если ты не левофланговый, то в следующую секунду доложи левому соседу "готов!".

Указание 5. Досчитав до нуля, стреляй!

Аналогичные указания даются, когда приказ получен правофланговым".

В соответствии с данными указаниями стрелки выстрелят одновременно через 2n секунд (тактов абстрактного времени) после получения приказа. И можно видеть, что ни при каких обстоятельствах это время не может быть меньше n, т.к. это время соответствует минимальному времени распространении информации с одного фланга цепи на другой [2].

Структурная модель задачи

Структурная модель программы, моделирующей поведение цепи стрелков, представлена на рис.1 (см. Лист 1. проекта). Из нее видно, что в число структурных блоков задачи, кроме собственно объектов стрелков - R1, R2, … RN, введен объект, названный офицером - Officer. В нашем случае он не только будет принимать приказ от верховного командования, отдавая его цепи стрелков, но и будет выполнять некоторые сервисные функции: например, по состоянию ближайшего к нему стрелка определять момент совершения выстрела. Кроме офицера в структурную модель введен структурный блок, протоколирующий (записывающий в файл) текущие состояния объектов на каждом такте абстрактного времени. Это объект с именем WriteStates. Анализируя созданный им протокол, мы сможем иметь точное представление о состоянии (поведении) всех объектов на всем протяжении процесса моделирования решения поставленной задачи.

Лист 1 (начало)

Структурная модель

Рис.1. Структурная модель задачи о стрелках

Краткое описание

1. Назначение
На рис.1. представлена структурная модель задачи имитационного моделирования поведения стрелков в задаче Майхилла. Дополнительно к стрелкам в задачу введены блок, моделирующий поведение офицера (он отдает команду стрелкам) и блок, выполняющий протоколирование внутренних состояний объектов, составляющих модель цепи стрелков.

2. Перечень блоков
Officer - модель офицера;
Rifleman 1, 2, … N - модели стрелков;
WriteStates - блок протокола;
Примечание. Блоки Officer и WriteStates не обязательные. Первый введен для удобства управления цепью стрелков, второй - для визуализации решения.

3. Функционирование модели
Объекты модели функционируют параллельно. Время для всех объектов едино и моделируется абстрактным дискретным временем. Офицер, получив команду, передает ее ближайшему стрелку, тот следующему и т.д. Чтобы выполнить команду, стрелки обмениваются между собой информацией. По истечении некоторого периода времени они должны одновременно выполнить команду выстрел. В модели - перейти в одинаковое для всех объектов состояние. При этом все промежуточные состояния объектов на каждом такте протоколируются созданным для этого объектом, который функционирует параллельно остальным объектам, составляющим задачу.

Лист 1 (окончание)

Модель взаимодействия структурных блоков

Модель взаимодействия объектов задачи, созданная в соответствии со структурной моделью задачи и, исходя их алгоритма действия структурных объектов, представлена на рис.1 листа 2. проекта. В соответствии с ней, объекты обмениваются сигналами, которые соответствуют их текущим внутренним состояниям. Так, передача состояния (сигнала) "огонь" соответствует распространению команды, поступившей к офицеру, по цепи. При этом возврат соседу своего состояния "готов", говорит о переходе объекта к выполнению команды "пли!" - выполнению инструкции 3. В последующем переход в состояние "выстрел" будет соответствовать моменту выполнения команды стрелком.

Лист 2 (начало)

Модель взаимодействия объектов

Рис. 1. Модель взаимодействия объектов задачи о стрелках

Краткое описание

1. Назначение
Определяет перечень связей и сигналов, определяющих протокол взаимодействия объектов в задаче о стрелках.

2. Перечень связей блоков
Блок Officer (офицер):
   - состояние "огонь" блока поступает на вход блока Rifleman 1 (крайний в цепи стрелок, стоящий рядом с офицером);
   - текущее состояние блока поступает в блок WriteStates.
Блок Rifleman 1 (ближайший к офицеру или крайний слева стрелок):
   - состояние "огонь" поступает к стрелку справа,
   - состояние "сон" поступает к офицеру.
Блок Rifleman 2… (стрелок внутри цепи):
   - состояние "огонь" поступает к стрелку справа,
   - состояние "готов" поступает к стрелку слева,
Блок Rifleman N (крайний справа стрелок):
   - состояние "готов" поступает к стрелку слева.
Примечание 1. Определение связи включает имя/номер выходного канала блока и имени блока, с которым существует связь.
Примечание 2. Все стрелки составляют массив стрелков. Блок WriteStates имеет доступ к состояниям стрелков, анализируя текущие состояния объектов, составляющих данный массив.

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

Лист 2 (окончание)

Модель офицера

Модель структурного блока Officer в форме автоматной модели представляет лист 3 проекта. На нем рис. 1а представляет структурную модель управляющего блока (УБ) автоматной модели. На этом уровне офицер - блок, имеющий два входных и один выходной канал, где по каналу с номером 1 поступает информация о необходимости отдать команду стрелкам, а по 2-му каналу - информация о внутреннем состоянии соседа-стрелка. Выходной сигнал y1 формирует задержку на некоторое число тактов, за которые соседний стрелок покинет свое начальное состояние (как буден видно далее - состояние "сон").

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

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

Лист 3 (начало)

Объект Officer ("офицер")

Рис. 1. Модель блока Officer

Краткое описание

1. Назначение
Моделирует поведение офицера: отдает команду крайнему в цепи стрелку, определяет момент выполнения команды цепью всех стрелков.

2. Базовые классы

LFsaAppl

3. Связи

Имеет связь с ближним крайним в цепи стрелком (анализирует его состояние "сон").

4. Функционирование
4.1. Роли состояний:
   "сон" - офицер ждет поступления команды от внешней среды.
   "огонь" - отражает факт поступления команды.
   "ждать" - ждет состояния "сон" стрелка.
   "все" - стрелки выполнили команду "пли!" офицера.

4.2. Алгоритм работы:
Находясь в состоянии "сон", офицер ждет поступления приказа на выдачу команды стрелкам (вызов внешней средой его метода SetCommand). Получив команду (x1 принимает значение true), офицер переходит в состояние "огонь", отдавая тем самым приказ крайнему в цепи стрелку. После этого сразу осуществляет переход в состояние "ждать", выполнив на переходе действие y1. Данное действие создает вложенный автомат, который реализует задержку перехода в данное состояние (сначала осуществляются переходы в состояния вложенного автомата - в протоколе им соответствуют состояния "D"). Перейдя в состояние "ждать" и дождавшись в нем состояния "сон" стрелка, офицер выполняет переход в состояние "все", фиксируя момент завершения выполнения приказа. После этого автомат завершает работу, переходя в заключительное состояние.

Лист 3 (окончание)

Модель стрелка

Модель стрелка - структурного блока Rifleman - представлена на рис.1 листа 4 проекта. На рис. 1а представлен структурная модель УБ автоматной модели. Она имеет четыре входных и столько же выходных каналов.

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

Примечание. Использование стандартного вложенного автомата-задержки из автоматной библиотеки - пример упрощения модели. В этом случае не нужно в рамках модели верхнего уровня - модели стрелка организовывать цикл задержки перехода из состояния "готов" в состояние "выстрел" (см. модель стрелка в [3]). Ее реализует вложенный автомат, создаваемый в действии y2 модели стрелка.

Лист 4 (начало)

Объект Rifleman ("стрелок")

Рис. 1. Модель блока Rifleman

Краткое описание

1. Назначение
Моделирует поведение стрелка в цепи.

2. Базовые классы

LFsaAppl

3. Связи

Имеет связи со своими ближайшими соседями (стрелки слева и справа).

4. Функционирование
4.1. Роли состояний:
   "сон" - стрелок ждет команду "огонь" от соседа слева;
   "огонь" - отражает факт поступления команды, ожидает состояния "готов" от соседа справа;
   "готов" - отражает состояние готовности выполнить выстрел, выполняет обратный отсчет;
   "выстрел" - стрелок выполняет команду "пли!" офицера.

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

Лист 4 (окончание)

Модель блока протоколирования текущих состояний объектов

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

Объект в начальном своем состоянии анализирует указатель на модель задачи. Если он установлен, выполняется открытие файла. Далее в состоянии "w0" в цикле в действии y1 выполняется формирование текстовой строки, содержащей текущие состояния объектов, которая записывается в файл протокола. Выход из цикла формирования протокола состояний произойдет, когда модель офицера перейдет в свое заключительное состояние - "00".

Примечание 1. Любому активному объекту в параллельной автоматной среде назначается уровень приоритета. В нашем случае объекту, формирующему протокол, нужно его установить большим, чем у остальных объектов модели. В задаче объекты, составляющие модель задачи, имеют по умолчанию приоритет равный 1. Присвоение более низкого приоритета гарантирует определенную последовательность действий. В данном случае нам необходимо, чтобы на текущем такте автоматного времени действие y1 выполнилось после всех действий остальных объектов модели (нас интересует изменение ими своих текущих внутренних состояний).

Примечание 2. В рамках действия y1 выполняется запрос реального внутреннего состояния объектов, т.е. с учетом состояний вложенных автоматов. В нашем случае это относится к состояниям автомата FDelayCLK, реализующего "вложенные задержки". Уровень опроса состояний автоматной модели реализуется в методе FGetState. По умолчанию возвращается "реальное состояние". Если выполнить метод с параметром равным нулю, то будут возвращаться состояния автоматов только верхнего уровня иерархии. Этот режим иногда необходим, если нужно скрыть состояния вложенных автоматов. Но при этом необходимо учесть, что искажается реальное состояние автоматной модели. Оно при активном вложенном автомате, соответствует этому автомату, а не автомату, который выше в иерархии вложенной автоматной модели.

Лист 5 (начало)

Объект WriteStates ("протокол")

Рис 1. Модель объекта WriteStates

Краткое описание

1. Назначение
Запомнить в файле текущие состояния объектов.

2. Базовые классы

LFsaAppl

3. Связи

Существует связь в целом с моделью задачи и с одним из ее объектов - "офицером".

4. Функционирование
Переход из начального состояния "ws"произойдет лишь при наличии указателя на объект, содержащий объекты цепи стрелков. При соблюдении этого условия, перейдя в состояние "w0", объект в цикле на каждом такте автоматного, выполняет действие y1. В теле данного действия выполняется опрос текущих состояний всех объектов, составляющих модель, которые затем запоминаются в файле. Условием выхода из цикла является переход модели офицера в заключительное состояние - "00". При этом завершается и формирование протокола.

Лист 5 (окончание)

Модель задачи (объект CChainShot)

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

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

Лист 6 (начало)

Объект CChainShot (модель задачи)

Рис 1. Головной объект - CNetFsaChainShot

Краткое описание

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

2. Базовые классы

Нет.

3. Управление, связи

Создание нужного количества объектов, управление процессом моделирования и запуск цикла моделирования осуществляются через соответствующие методы объекта (подробнее см. п.4 - функционирование).

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

создать объект, передав ему указатель на автоматную среду, в которую будут загружены активные объекты;
определить число стрелков в цепи, задав значение свойству nNumberOfRiflemans;
вызвать метод CreateObjects, который создаст объекты задачи;
отдать команду стрелкам, вызвав метод VolleyFire.

Пример выполнения выше описанных шагов представлен в листинге 1 (части кода реализации класса CNetFsaChainShot).

CNetFsaChainShot::CNetFsaChainShot()
        :CArrayNetFsa()
{
        …
        pCChainShot = new CChainShot(pNetFsa);  //      создать цепь стрелков
        …
        //      запуск процесса моделирования
        pNetFsa->go_task();
}
…

void CNetFsaChainShot::Create(int n)
{
        pCChainShot->nNumberOfRiflemans = n;
        pCChainShot->CreateObjects();
}

Листинг 1. Создание объекта модели задачи о стрелках

В данном случае в конструкторе класса CNetFsaChainShot создается объект класса CChainShot, а свойства модели и создание объектов, входящих в нее, выполняются в рамках вызова метода Create класса CNetFsaChainShot.

Примечание. Метод VolleyFire вызывается в методе Fire класса CNetFsaChainShot.

Лист 6 (окончание)

Модель приложения (объект CNetFsaChainShot)

Лист 7 проекта представляет объект, который представляет в целом приложение, которое включает в себя на объектном уровне не только модель задачи, но и другие объекты (в нашем случае - еще и объект, выполняющий протоколирование состояний объектов модели задачи). Он порожден от класса CArrayNetFsa, который формирует создает автоматную параллельную среду для активных объектов приложения. А потому именно указатель на данный объект передается при создании объекта модели задачи (см. выше описание объекта CChainShot). Данный объект в процессе своего создания создает и объект класса CWriteStates, который формирует протокол. В рамках его метода OnIdle выполняется управление функционированием среды - реализация цикла моделирования решения задачи и выход из этого цикла по завершении процесса получения решения. Моделирование завершается, когда модель офицера переходит в свое заключительное состояние и как процесс перестает быть активной.

Лист 7 (начало)

Объект CNetFsaChainShot (головной объект-приложение)

Рис 1. Головной объект - CNetFsaChainShot

Краткое описание

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

2. Базовые классы

CArrayNetFsa - класс параллельной автоматной среды.

3. Связи

4. Функционирование
Для решения задачи необходимо выполнить следующую последовательность вызова методов.

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

Пример последовательности выполнения данных шагов показан в листинге 1.

int main(int argc, char* argv[])
{
        if (argc != 2) return 0;
        int nR = atoi(argv[1]);

        CNetFsaChainShot CNFChainShot;          // объект-приложение
        CNFChainShot.Create(nR);                // создать заданное число стрелков
        CNFChainShot.Fire();                    // подать команду - огонь!                      
        CNFChainShot.OnIdle();                  // запуск автоматных процессов
        return 0;
}

Листинг 1. Головной модуль программы

Лист 7 (окончание)

О результатах экспериментов

Результат решения задачи представлены на листе 8. В нем отражены состояния офицера и стрелков. Легко можно видеть, что есть момент, когда все стрелки одновременно переходят в состояние "выстрел". А это говорит о том, что найдет правильный алгоритм поведения отдельного стрелка.

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

Эксперименты с моделью показывают, что необходимо выполнять определенные требования к передаче сигналов между объектами. Так введение задержки на передачу сигнала "огонь" не сказывается на результатах решения: стрелки стреляют одновременно. Но, с другой стороны, задержка в распространении сигнала "готов" недопустима: стрелки сбиваются со счета и начинают стрелять вразнобой. Для проверки задержку сигнала "огонь" можно ввести в действие y1 (см. его код), а чтобы задержать передачу сигнала "готов", нужно ввести задержку на переходе из состояния "огонь" в состояние "готов", введя, например, действие подобное действию y5.

Лист 8 (начало)

ПРОТОКОЛЫ

Количество стрелков в цепи:5
   1:D,огонь,сон,сон,сон,сон,
   2:ждать,огонь,огонь,сон,сон,сон,
   3:ждать,огонь,огонь,огонь,сон,сон,
   4:ждать,огонь,огонь,огонь,огонь,сон,
   5:ждать,огонь,огонь,огонь,огонь,огонь,
   6:ждать,огонь,огонь,огонь,огонь,готов,
   7:ждать,огонь,огонь,огонь,готов,D,
   8:ждать,огонь,огонь,готов,D,D,
   9:ждать,огонь,готов,D,D,D,
  10:ждать,готов,D,D,D,D,
  11:ждать,выстрел,выстрел,выстрел,выстрел,выстрел,
  12:ждать,D,D,D,D,D,
  13:ждать,D,D,D,D,D,
  14:ждать,выстрел,выстрел,выстрел,выстрел,выстрел,
  15:ждать,D,D,D,D,D,
  16:ждать,D,D,D,D,D,
  17:ждать,выстрел,выстрел,выстрел,выстрел,выстрел,
  18:ждать,сон,сон,сон,сон,сон,
  19:все,сон,сон,сон,сон,сон,

Протокол 1. Решение задачи о стрелках


Количество стрелков в цепи:5
   1:D,огонь,сон,сон,сон,сон,
   2:ждать,огонь,огонь,сон,сон,сон,
   3:ждать,огонь,огонь,D,сон,сон,
   4:ждать,огонь,огонь,D,сон,сон,
   5:ждать,огонь,огонь,огонь,сон,сон,
   6:ждать,огонь,огонь,огонь,огонь,сон,
   7:ждать,огонь,огонь,огонь,огонь,огонь,
   8:ждать,огонь,огонь,огонь,огонь,готов,
   9:ждать,огонь,огонь,огонь,готов,D,
  10:ждать,огонь,огонь,готов,D,D,
  11:ждать,огонь,готов,D,D,D,
  12:ждать,готов,D,D,D,D,
  13:ждать,выстрел,выстрел,выстрел,выстрел,выстрел,
  14:ждать,D,D,D,D,D,
  15:ждать,D,D,D,D,D,
  16:ждать,выстрел,выстрел,выстрел,выстрел,выстрел,
  17:ждать,D,D,D,D,D,
  18:ждать,D,D,D,D,D,
  19:ждать,выстрел,выстрел,выстрел,выстрел,выстрел,
  20:ждать,сон,сон,сон,сон,сон,
  21:все,сон,сон,сон,сон,сон,

Протокол 2. Моделирование задержки сигнала "огонь" (3-й стрелок - 2 такта)


Количество стрелков в цепи:5
   1:D,огонь,сон,сон,сон,сон,
   2:ждать,огонь,огонь,сон,сон,сон,
   3:ждать,огонь,огонь,D,сон,сон,
   4:ждать,огонь,огонь,D,сон,сон,
   5:ждать,огонь,огонь,огонь,сон,сон,
   6:ждать,огонь,огонь,огонь,огонь,сон,
   7:ждать,огонь,огонь,огонь,огонь,огонь,
   8:ждать,огонь,огонь,огонь,огонь,готов,
   9:ждать,огонь,огонь,огонь,D,D,
  10:ждать,огонь,огонь,огонь,D,D,
  11:ждать,огонь,огонь,огонь,D,D,
  12:ждать,огонь,огонь,огонь,готов,D,
  13:ждать,огонь,огонь,готов,D,выстрел,
  14:ждать,огонь,готов,D,D,D,
  15:ждать,готов,D,D,D,D,
  16:ждать,выстрел,выстрел,выстрел,выстрел,выстрел,
  17:ждать,D,D,D,D,D,
  18:ждать,D,D,D,D,D,
  19:ждать,выстрел,выстрел,выстрел,выстрел,выстрел,
  20:ждать,D,D,D,D,сон,
  21:ждать,D,D,D,D,сон,
  22:ждать,выстрел,выстрел,выстрел,выстрел,сон,
  23:ждать,сон,сон,сон,сон,сон,
  24:все,сон,сон,сон,сон,сон,

Протокол 3. Моделирование задержки сигнала "готов" (4-й стрелок - 3 такта)

Лист 8 (окончание)

Выводы

На примере решения задачи о стрелках демонстрирует решение следующих проблем:

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

По отношению используемой автоматной модели вообще к библиотеке FSA в рамках представленного решения детально демонстрируются следующие приемы программирования:

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

На отображении результатов решения необходимо остановиться подробнее. В данном случае ни что не мешает вместо формирования текстового файла или в дополнение к нему организовать вывод, например, в графической форме, строить диаграммы сигналов/состояний и т.д. и т.п. Параллельные технологии, как это видно, позволяют осуществить такой параллельный же контроль над приложением, ни сколько не вмешиваясь при этом в его работу. "Непараллельные" технологии таких качеств не имеют. Один из примеров того, как часто выполняют отладку, протоколирование и т.п. - получение протоколов работы объектов приложения в проектах, созданных в рамках SWITCH-технологии (см. [4]).

Литература

Варшавский В.И., Поспелов Д.А. Оркестр играет без дирижера: размышления об эволюции некоторых технических систем и управления ими. - М.: Наука. Главная редакция физико-математической литературы, 1984, - 208с.
Трахтенброт Б.А. Алгоритмы и вычислительные автоматы. М.: Советское радио, 1974, - 200с.
Любченко В.С. Батарея огонь! или Задача Майхилла для Microsoft Visual C++ (О синхронизации процессов в среде Windows). "Мир ПК", № 2/00. http://www.osp.ru/pcworld/2000/02/148.htm
Раздел Проекты сайта СПбГИТМО (ТУ) http://is.ifmo.ru/?i0=projects.

¹ См. выше понятие единичного такта абстрактного времени.