|
Страница 1 из 6
О синхронизации процессов в среде 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 Произвести выстрел Кстати, эти строки в дальнейшем можно превратить в комментарии к операторам "автоматной программы". |