Распределённое взаимное исключение

В этом задании вы реализуете несколько алгоритмов для взаимного исключения в распределенной системе.

Задача

В файле MutexProcess.java находится описание интерфейса, который вам предстоит реализовать. Свой код вы должны писать на языке Java или Kotlin.

Реализацию на Java пишите в файлах:

• ProcessCentralized.java — реализация централизованного алгоритма.
• ProcessLamport.java — реализация алгоритма Лампорта.
• ProcessRickartAgrawala.java — реализация алгоритма Рикарта и Агравала.
• ProcessToken.java — реализация алгоритма на основе токена.
• ProcessPhilosophers.java — реализация алгоритма обедающих философов.

Для решения на Kotlin откройте Java файл из списка выше и нажмите Ctrl+Alt+Shift+K (Cmd+Alt+Shift+K на MacOS) в IntelliJ IDEA для конвертации соответствующего фала из XXX.java в XXX.kt. На вопрос "Some code in the rest of your project may require corrections after performing this conversion. Do you want to find such code and correct it too?" отвечайте "No". Пишите код в соответствующем kt файле, который получится после конвертации.

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

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

• env.getProcessId() — возвращается идентификатор процесса (нумерация с единицы).
• env.getNumberOfProcesses() — возвращает общее число процессов.
• env.send(destinationPid, message) — посылает сообщение message процессу с номером destinationPid (нумерация с единицы).
• env.lock() — должен быть вызван процессом при входе в критическую секцию.
• env.unlock() — должен быть вызван процессом при выходе из критической секции.

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

Интерфейс процесса

Методы вашего класса будут вызываться в следующих случаях:

• onMessage(sourcePid, message) — вызывается при получении сообщения от другого процесса с номером sourcePid (нумерация с единицы), которое было отправлено этим процессом через env.send(...).

• onLockRequest() — вызывается в случае запроса на вход в критическую секцию. Процесс должен инициировать алгоритм входа в критическую секцию и, после входа в неё, вызвать метод env.lock().

  Вызов env.lock() необязательно должен быть сделан в теле метода onLockRequest(): можно вызвать env.lock() в ходе обработки очередного сообщения, но только после того как процессу был сделан запрос на вход в критическую секцию с помощью метода onLockRequest().

  Метод onLockRequest() не будет повторно вызываться до выхода этого процесса из критической секции.

• onUnlockRequest() — вызывается в случае запроса на выход из критической секции. Процесс должен немедленно вызвать метод env.unlock() и инициировать алгоритм выхода из критической секции. Этот метод будет вызываться только если ранее был осуществлен вход в критическую секцию (был вызван env.lock()).

Замечания

• В алгоритме на основе токена гарантируется, что число процессов в системе составляет не менее двух;
• В алгоритме Лампорта гарантируется, что сообщения между каждой парой процессов доставляются в порядке FIFO;
• В централизованном алгоритме предполагается, что процесс с идентификатором 1 является координатором;
• В алгоритме на основе токена предполагается, что изначально токеном владеет процесс с идентификатором 1.

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

Каждое отправленное сообщение должно быть сериализуемо. Описание класса сообщений может выглядеть, например, так на Java:

record MyMessage(int key, String value) implements java.io.Serializable {}

или на Kotlin:

data class MyMessage(val key: Int, val value: String) : java.io.Serializable

Размер каждого отправленного сообщения не должен превышать ста байт.

Заметьте, что метод onMessage(int senderPid, Object message)в качестве аргумента принимает не описанный вами тип сообщения, а java.lang.Object. На Java используйте приведения типов вида:

MyMessage typedMessage = (MyMessage) message;

и, если нужно, оператор instanceof

if (message instanceof MyMessage) {
    // ...
}

для приведения сообщения к нужному вам типу.

На Kotlin:

val typedMessage = message as MyMessage
// or 
if (message is MyMessage) { 
    // ...
}

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

Тестирования реализации происходит путем запуска тестов:

• ProcessCentralizedTest.java
• ProcessLamportTest.java
• ProcessRickartAgrawalaTest.java
• ProcessTokenTest.java
• ProcessPhilosophersTest.java

Из командной строки: ./gradlew test

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