stack-elimination

Stack with Elimination

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

1. Напишите базовую реализацию на основе односвязного списка.
2. Добавьте массив фиксированного размера (найдите оптимальное значение для вашей машины и желаемого количества параллельных потоков экспериментальным способом) для elimination-а.
3. Операция push пытаться записать элемент в случайную ячейку этого массива (нужно делать несколько попыток в соседних ячейках при неудачной записи) и в цикле фиксированного размера ждет изменений на этой ячейки (spin wait). Если другой поток "забрал" значение, то операция завершается. Иначе, ячейка "сбрасывается" на начальное состояние, и операция выполняется в базовой версии стека.
4. Операция pop должна сначала пытаться найти себе пару в массиве для elimination-а (так же делая несколько попыток). В случае неудачи идёт в бозовую версию стека.

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

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

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

Ограничения

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