stm-bank

STM Bank

Задание включает в себя следующие исходные файлы:

• src/Bank.kt содержит интерфейс для гипотетического банка.
• src/BankImpl.kt содержит простую реализации операций банка используюя STM.
• src/STM.kt содержит незаконченную реализацю obstruction-free STM.

Задание

Необходимо закончить реализацию STM, написав реализацию метода TxVar.openIn вместо написанного там кода-заглушки, который должен открывать пременную в указанной транзакции и применять к ней функцию update. Алгоритм такого STM без блокировок описан в учебнике "The Art of Multiprocessor Programming" by Maurice Herlihy and Nir Shavit и был рассказан на лекции.

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

Весь код должен содержаться в файле STM.kt.

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

Для проверки вашего решения запустите из корня репозитория:

• ./gradlew build на Linux или MacOS
• gradlew build на Windows

При этом автоматически будут запущены следующие тесты:

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

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

Сделайте наблюдения

При запуске MTStressTest присходит замер пропускной способности реализации банка и выдается среднее количество операций в секунду, которе выполняет реализация банка при этом профиле нагрузки.

• Сравните пропускную способность реализации BankImpl в этом задании "STM Bank" и в предыдущем задании "Lock-Free Bank". Какая реализация работает быстрей и почему?
• Что можно сказать о простоте реализации (количестве кода) в реализации BankImpl в этих двух заданиях?

Сделанные наблюдения понадобятся вам во время контрольной работы.

Формат сдачи

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