Необходимо доработать реализацию StackImpl
таким образом, чтобы она стала безопасной и эффективной при использовании из нескольких потоков одновременно.
В качестве базовой реализации используйте рассказанный на лекции алгоритм на основе односвязного списка.
Чтобы сделать алгоритм масштабируемым, необходимо использовать технику elimination.
Вы можете проверить эффективность вашего решения с помощью бенчмарка StackBenchmark
.
- Напишите базовую реализацию на основе односвязного списка.
- Добавьте массив фиксированного размера (найдите оптимальное значение для вашей машины и желаемого количества параллельных потоков экспериментальным способом) для elimination-а.
- Операция
push
пытаться записать элемент в случайную ячейку этого массива (нужно делать несколько попыток в соседних ячейках при неудачной записи) и в цикле фиксированного размера ждет изменений на этой ячейки (spin wait). Если другой поток "забрал" значение, то операция завершается. Иначе, ячейка "сбрасывается" на начальное состояние, и операция выполняется в базовой версии стека. - Операция
pop
должна сначала пытаться найти себе пару в массиве для elimination-а (так же делая несколько попыток). В случае неудачи идёт в бозовую версию стека.
Для тестирования используйте команду mvn test
. При этом автоматически будут запущены следующие тесты:
FunctionalTest.java
проверяет базовую корректность стека.LinearizabilityTest.java
проверяет реализацию стека на корректность в многопоточной среде.
- Все атомарные операции должны выполняться при помощи примитивов из библиотеки
kotlinx.atomicfu
. - Использования любых примитивов из пакета
java.util.concurrent.*
,synchronized
методов и блоков запрещены. - Разрешается редактирование только файла
StackImpl.java
.