distributed-mutex

Distributed Mutex

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

Задача

В файле src/Process.kt находится описание интерфейса, который вам предстоит реализовать. Свой код вы должны писать на языке Kotlin в файле src/ProcessImpl.kt. Не забудьте указать свое имя и фамилию в файле с вашим решением.

Допустима также реализация на Java. Для этого удалите ProcessImpl.kt и вместо него напишите файл ProcessImpl.java с классом mutex.ProcessImpl, который реализует интерфейс mutex.Process и имеет публичный конструктор, принимающий ссылку на объект реализующий интерфейс mutex.Environment. Шаблон для такого класса дан в файле src/ProcessJavaImpl.java.

Проект

Для работы над проектом рекомендуется импортировать Gradle проект build.gradle.kts в IntelliJ IDEA, но это не обязательно. Работу и тестирование проекта можно также производить из командной строки.

Окружение процесса

Тестовая система будет запускать ваш код в нескольких процессах, каждому из которых выдан уникальный идентификатор начинающийся с единицы. Через ссылку на объект Environment ваш процесс может узнать конфигурацию системы и общаться с другими процессами:

• env.processId — возвращается идентификатор вашего процесса (нумерация с единицы).
• env.nProcesses — возвращает общее число процессов.
• env.send(destId, message) — посылает сообщение процессу с номером destId (нумерация с единицы).
• env.locked() — должен быть вызвать вашим процессом при входе в критическую секцию только если был запрос (смотри ниже).
• env.unlocked() — должен быть вызван вашим процессом при выходе из критической секции только если был запрос (смотри ниже).

Методы вашего класса ProcessImpl.kt будут вызываться из главного потока процесса в следующих случаях:

• onMessage(srcId, message) — вызывается при получении сообщения от другого процесса с номерм srcId (нумерация с единицы), которое было послано другим процессом через env.send(...). Между каждой парой процессов гарантируется FIFO порядок передачи сообщений (передача происходит через протокол TCP/IP).
• onLockRequest() — вызывается в случае запроса на вход в критическую секцию. Процесс должен инициировать алгоритм входа в критическую секцию и, после входа в неё, вызвать env.locked. Этот метод не будет повторно вызыватьcя до выхода из критической секции.
• onUnlockRequest() — вызывается в случае запроса на выход из критической секции. Процесс должен вызвать env.unlocked и инициировать алгоритм выхода из критической секции. Этот метод будет вызываться только если ранее был осуществлен вход в критическую секцию (был вызван env.locked).

Работа с сообщениями

Сообщения формируются путем создания объекта класса Message. Каждое сообщение состоит из последовательности полей одного из трех типов: числового, строкового, перечислимого. Запись полей в сообщение осуществляется с помощью вызовов сооствествующих методов writeXxx, а чтение — с помощью соответсвтующей последовательности вызовов readXxx. Например, чтобы создать сообщение состоящие из из числового поля time и перечисления типа:

enum class Type { REQ, OK }

Надо написать такой код:

val message = Message {
    writeInt(time)
    writeEnum(Type.REQ)
}

А для того, чтобы такое сообщение прочитать:

message.parse {
    val time = readInt()
    val type = readEnum<Type>()
    // ... use type & time here
}

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

Для удобства можно объединить создание сообщения и его посылку в один вызов:

evn.send(destId) {
    writeInt(time)
    writeEnum(Type.REQ)
}

Примеры алгоритмов

К заданию прилагается ряд уже реализованных алгоритмов взаимного исключения. Они не подходят в качестве ответа на данное здание, но помогут вам разобраться с окружением и способами реализации различных распределенных алгоритмов, а также прояснить требования предъявляемые к алгоритмам взаимного исключения в данном задании.

• ProcessLamportMutex — алгоритм взамного исключения Лампорта, посылает 3*(N - 1) сообщений на каждую критическую секцию.
• ProcessRickartAgrawalaMutex — алгоритм взамного исключения Рикарта и Агравалы, посылает 2*(N - 1) соообщений на каждую критическую секцию.
• ProcessSyncCoordinatedMutex — централизованный алгоритм взамного исключения (процесс 1 является координатором), посылает 2 сообщения на каждую критическую секцию, а координатор входит в критеческую секцию не посылая сообщений.
• ProcessTokenMutex — алгоритм взаимного исключения на основе токена. Он постоянно передает сообщение по кругу, даже если нет запросов на критическую секцию. В данной реализации, для удобства отладки, в передоваем сообщении содержится постоянно увеличивающийся идентификатор, который не нужен для работы самого алгоритма.

Отладка кода

Для запуска и отладки кода предлагается ряд готовых инструментов.

Конфигурация системы

Конфигурация запускаемой распределенной системы находится в файле system.properties и состоит из перечисления процессов (узлов) системы и их адресов. По умолчанию система сконфигурирована для работы с 5-ю процессами, запускаемыми на одной машине. Для отладки своего кода эта конфигурация может быть изменена.

Запуск одного процесса

Запусть процесс можно одим из двух способов:

• Запустив main функцию в файле src/system/Node.kt, передав ей в качестве аргумента номер процесса.
• Из командной строки gradlew node -PprocessId=<id>.

На экране будет виден подробный журнал работы просесса. Все посылаемые и принимаемые сообщения и всё взаимодействие с окружением всегда выводятся системой в журнал работы (для этого к коде процесса не надо писать никакого специального отладочного кода). В консоли можно вводить следующие команды:

• exit — останавливает работу.
• ping — проверяет жив ли процесс (отвечает на консоли сообщением PONG).
• lock — запрос на критическую секцию.
• unlock — запрос на выход из критической секции.

Запуск всех процессов одновременно

Запусть все процессы одновременно можно одим из двух способов:

• Запустив main функцию в файле src/system/System.kt.
• Из командной строки gradlew system.

На экране будет виден подробный журнал работы всех процессов. В консоли можно вводить следующие команды:

• exit — останавливает работу все процессов.
• ping — проверяет живы ли процессы (посылает ping всем процессам).
• lock — запрос на критическую секцию всем процессам (посылает lock всем процессам). В правильно работающем алгоритме только один процесс войдет в критическую секцию (в журнале появится запись <id> LOCKED) и будет дожидаться запроса на выход из критической секции.
• <id> lock — запрос на критическую секцию к процессу с номером <id>.
• <id> unlock — запрос на выход из критической секции к процессу с номером <id>.

Указание альтернативной реализации

По умолчанию, происходит запус процесcа реализованного в классе ProcessImpl. Не копируя исходный код, можно сразу запустить одну из готовых реализаций, перечисленных в секции Примеры алгоритмов, передав имя класса в качестве дополнительного аргурмента при запуске соответствующей main функции, например:

SystemKt ProcessLamportMutex

При запуске из командной строки надо указывать свойство проекта implName, например:

gradlew system -PimplName=ProcessLamportMutex

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

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

Тест проверяет корретность алгоритма (гарантию взаминого исключения), его прогресса (отсутствие взаимных блокировок), и замеряет эффективность алгоритма, считая количество передаваемых сообщений. Из-за проверки на эффективность, прилагаемые к заданию примеры алгоритмов не проходят тест.

Можно запускать тест в режиме, когда проверяется только взаимное исключение, но не эффективность алгоритма, передавая свойство проекта skipCountCheck=true. При такой проверке прилагаемые Примеры алгоритмов проходят тест, например:

gradlew test -PimplName=ProcessRickartAgrawalaMutex -PskipCountCheck=true

Для прохождения полноценного теста и сдачи задания необходимо реализовать алгоритм Обедающих Философов.

Формат сдачи

Выполняйте задание в этом репозитории. Ваш код должен быть реализован в одном файле src/ProcessImpl.kt или src/ProcessImpl.java.

Инструкции по сдаче заданий находятся в этом документе.