msqueue

Michael-Scott Lock-Free Queue

Необходимо доработать реализую MSQueue так, чтобы она стала безопасной для использования из множества потоков одновременно. Используйте алгоритм очереди, предложенный M. Michael и L. Scott.

Ссылка на статью: http://www.cs.rochester.edu/~scott/papers/1996_PODC_queues.pdf

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

Сборка и тестирование

Для тестирования используйте команду mvn test, следующие тесты будут запущены:

• FunctionalTest.java проверяет базовую корректность множества.
• LinearizabilityTest.java проверяет реализацию множества на корректность в многопоточной среде.

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

Ограничения

• Все атомарные операции должны выполняться при помощи примитивов из библиотеки kotlinx.atomicfu.
• Использования любых примитивов из пакета java.util.concurrent.*, synchronized методов и блоков запрещены.
• Разрешается редактирование только файла StackImpl.java.