Distributed FIFO

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

Задача

Вам даны четыре алгоритма взаимного исключения:

• ProcessLamportMutex — алгоритм взаимного исключения Лампорта.
• ProcessRickartAgrawalaMutex — алгоритм взаимного исключения Рикарта и Агравалы.
• ProcessSyncCoordinatedMutex — централизованный алгоритм взаимного исключения (процесс 1 является координатором).
• ProcessTokenMutex — алгоритм взаимного исключения на основе токена.

В файле src/Visualise.kt находится интерактивная программа визуализации алгоритмов. Её можно запустить из IDEA используя функцию main либо из командной строки:

gradlew run

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

Три из 4-х предложенных алгоритмов корректно работают в любой сети передачи данных, но один из них работает корректно только при условии соблюдения FIFO порядка передачи сообщений.

Работа с визуализатором

В первой строке окна "Visualisation" находятся следующие элементы управления:

• "Name" — здесь нужно указать свое имя и фамилию.
• "Impl" — здесь нужно выбрать алгоритм.
• "Restart" — используйте для запуска алгоритма с начала.
• "Save" — нажмите для сохранения решения.

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

• Горизонтальная черточка — процесс запрашивает вход в критическую секцию.
• Черная окружность — процесс хочет послать сообщение. При нажатии мышкой на неё происходит доставка сообщения и внутри окружности появляется черный круг меньшего размера.
• Черный круг — процесс принял и обработал сообщение.
• Красный прямоугольник — вход и выход из критической секции.

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

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

После того как вам удастся получить исполнение, в котором оба процесса одновременно находятся в критической секции, нажмите кнопку "Save". Не забудьте перед этим указать свое имя и фамилию в поле "Name".

Решение будет записано в файл solution.txt, который вам надо добавить в репозиторий и закоммитить:

git add solution.txt
git commit -m "Solution"
git push origin master

Тестирование

Тестирование решения происходит путем запуска теста SolutionTest. Из командной строки: gradlew test.

Тест читает файл "solution.txt", проверяет его корректность и выполнение задания.

Формат сдачи

Выполняйте задание в этом репозитории. Решение должно быть в файле solution.txt.

Дополнительные возможности

Вы можете использовать этот визуализатор для работы над другими алгоритмами, например для отладки вашего решения к заданию "Distributed Mutex". Для этого положите файл с вашим решением в каталог src, проверьте что в его начале указан package mutex и добавите имя класса решения в список IMPLS, который находится в начале файла Visualise.kt, сразу после функции main.