Задача Майхилла для Microsoft Visual C++

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

Алгоритм поведения и автоматная модель стрелка

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

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

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

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

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

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

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

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

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

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

// Предикаты

x1 Состояние соседа слева "Огонь!"?

// Команда "Огонь";

x2 Состояние соседа справа "Готов!"?

x3 Свой номер не равен нулю?

// Действия

y1 Установить свой номер: взять номер

соседа слева

и увеличить на 1

y2 Уменьшить свой номер на 1

y3 Произвести выстрел

Кстати, эти строки в дальнейшем можно превратить в комментарии к операторам "автоматной программы".