Цепи стрелков ( Firing Squad Problem )

Эта классическая проблема синхронизации коллектива взаимодействующих объектов была поставлена Дж. Майхиллом в 1957 г. и опубликована в [ЕМ62]. Данной проблеме посвящено большое количество литературы. На русском языке обсуждение проблемы было опубликовано в книге [ММ71].

Постановка проблемы

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

стрелков, которые все одинаковы. Этот алгоритм функционирования стрел­ков и нужно построить.

Идея решения

Основная идея решения заключается в посылке по цепи стрелков сигналов, распространяющихся с разной скоростью. Очевидно, что самая большая скорость распространения сигнала по цепи — один стрелок в единицу вре­мени. Если один сигнал распространяется втрое медленнее другого, то два этих сигнала могут встретиться на середине цепочки после, того, как более медленный сигнал отразится от края цепи. Сигнал в нашем случае — это изменение состояния элемента цепи — стрелка. Пример распространения сигналов представлен на рис. 20.1. Каждая строка отражает состояния стрелков цепочки на очередном шаге по времени. В каждой строке прямо­угольники представляют стрелков, цвет прямоугольников показывает состояние стрелка. Крайний левый прямоугольник — Генерал, крайний правый прямоугольник — Сержант. В приведенном здесь решении модели­руется работа алгоритма из 13 состояний, число шагов которого о(п), и все­гда меньше Зп, где п — число стрелков.

Описание модели

Модель Firing Squad Problem находится в папке Model Examples\Part V. Она содержит три активных объекта, которые моделируют поведение Гене­рала, Сержанта и стрелка. Модель собирается в корневом объекте Root, ко­торый включает одного Генерала, массив стрелков и одного Сержанта.

Модель Генерала

Модель Генерала (General) содержит внутреннюю переменную mystate типа char и две интерфейсные переменные того же типа, exposeMystate и right. Кроме того, объект содержит стейтчарт и два статических таймера (рис. 20.2).

Переменная mystate принимает значение текущего состояния этого актив­ного объекта. Состояния объектов в модели обозначаются символами. Вы­ходная интерфейсная переменная называется exposeMystate, она передает состояние данного активного объекта тем переменным, которые будут с нею связаны. Входная интерфейсная переменная right будет показывать состоя­ние соседа справа. Начальные значения этих переменных неважны.

Стейтчарт с именем main содержит три состояния, начальное с именем а, состояние готов с именем r, и состояние стреляй с именем S. В нашей мо­дели активные объекты переходят из состояния в состояние синхронно, ка­ждую единицу модельного времени, но только в том случае, если выполне­ны условия перехода — в частности, соседи находятся во вполне определенных состояниях. Самое простое решение смоделировать такие пе­реходы — это выполнять их по сигналу с учетом защиты (Guard). Сигналом, по которому разрешен переход, является получение любого объекта типа

object, этот сигнал периодически будет посылаться стейтчарту таймером synchro. Переход из состояния а в состояние r осуществляется, как только такое событие произойдет, потому что Генерал делает первый шаг, выдавая команду приготовиться независимо от каких-либо условий с самого начала функционирования системы. Переход Генерала из состояния r в заключи­тельное состояние s требует, чтобы состояние его правого соседа было тоже готов, т. е. имело имя r.

При входе в каждое состояние переменной myState присваивается значение, соответствующее этому состоянию, например, при входе в состояние с име­нем r выполняется оператор mystate= 'R'.

"Жизнь" этому объекту придает таймер synchro, который периодически каждую единицу модельного времени генерирует событие, направленное непосредственно стейтчарту с именем main. Это описывается вызовом функ­ции fireEvent с передачей произвольного, объекта базового типа object у стейтчарта:

main.fireEvent(new Object ());

Аргументом у функции fireEvent () может быть, в частности, объект любо­го типа, а переход стейтчарта может быть определен, если объект именно этого класса получен. Поскольку здесь важен лишь факт получения собы­тия, использована передача объекта класса object, и в защите соответст­вующего перехода получение объекта именно этого класса проверяется. Второй таймер с именем timer — тоже периодический. Он разрешает пере­дачу значения текущего состояния в интерфейсную переменную exposeMystate. Такая передача не может быть осуществлена в тот же самый момент, в который состояние объекта изменилось, потому что принятие решения о переходах всех активных объектов производится на основании состояний соседей на предыдущем такте. Поэтому измененное состояние объекта передается в интерфейсную переменную тоже периодически, но с небольшим сдвигом по времени. Такой сдвиг позволяет передачу состояния соседям осуществить только после того, как все объекты установят свое но­вое состояние в соответствии с предыдущим состоянием соседей.

Модель Сержанта

Модель Сержанта (sergeant) строится полностью аналогично модели Гене­рала. Исключение составляет только то, что начальное состояние Сержанта помечено меткой M и переход из этого состояния в состояние r (состояние Готов) осуществляется, только если выполняется некоторое условие, отра­жающее состояние его левого соседа.

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

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

Корневой объект

Корневой объект с именем Root включает один объект типа Генерал, один объект типа Сержант и массив стрелков. Массив стрелков задается тем, что в поле Количество объектов для введенного в окно Root объекта soldier устанавливается параметр N. Этот параметр задается как параметр объекта

Root.

Объекты, введенные в поле редактора объекта Root, имеют интерфейсные переменные, и их нужно соединить подходящим образом. Такое соединение двух объектов может быть выполнено графически в поле графического ре­дактора проведением соединительной линии (коннектора), однако в данной модели мы должны соединить переменное число объектов (в массиве стрел­ков их количество задается параметром). Альтернативная возможность со­единения — использовать библиотечную функцию соединения, которая, собственно, и порождается для каждого коннектора при трансляции графи­ческого изображения структуры активного объекта в соответствующий код на языке Java.

Соединение нужно выполнить до начала работы модели, поэтому соответст­вующий код записывается в поле Код инициализации окна Код объекта Root. Сначала двумя операторами связывается выходная переменная exposeMystate Генерала с входной переменной left самого левого стрелка, а также вход­ная переменная right этого стрелка с входной переменной exposeMystate Генерала:

general._ref_exposeMyState.connect(soldier.item(0)._ref_left); general._ref_right.connect(soldier.item(0)._ref_exposeMyState);

Далее в цикле связываются между собой стрелки, а последней парой опера­торов крайний правый стрелок связывается с Сержантом.

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

модельного времени относительно целых его значений. Здесь это сделано со сдвигом на 0.5. В поле Действие при срабатывании этого таймера выполня­ются операторы, выполняющие визуализацию.