Java CLI to demonstrate different strategies for concurrency
TODO Rerun all experiments on 8-processor machine for better effect.
Before you start, make sure you have java and maven installed
-
Build executable jar
mvn clean package assembly:single -
Run jar
java -jar stm-demo.jar -
Play with options
-strategy=BASELINE-threads=2-accounts=100-nPerThread=100000
The problem solved in this demo is transfer funds between accounts.
We consider just two metrics:
- Delta between whole balance before and after
- Elapsed time
General approach is based on following interfaces.
AccountStrategy factory creates Account and Bank
public interface AccountStrategy {
Account createAccount(long initialBalance);
Bank createBank(Account[] accounts);
}Account could increment its balance by value and get a current anount.
public interface Account {
void incBalance(long amount);
long balance();
}Bank is shared object and has access to all accounts and implements a transfer logic between accounts
public interface Bank {
void transfer(Account a1, Account a2, long amount);
Account[] accounts();
}TransactionThread just wraps bank logic in a thread and runs it multiple times.
The simplest one. No synchronization involved.
Running it with 1 thread gives us great baseline time for a process
Options: -strategy=baseline -threads=1 -accounts=1000 -nPerThread=10000000
[INFO] Strategy: BASELINE
[INFO] Evaluation started...
[INFO] Sum before: 10000000
[INFO] Sum after: 10000000
[INFO] Delta: 0
[INFO] Finished. Time elapsed: 1674 ms
But if we add one more thread to simulation, balance consistency is broken
Options: -strategy=baseline -threads=2 -accounts=1000 -nPerThread=10000000
[INFO] Strategy: BASELINE
[INFO] Evaluation started...
[INFO] Sum before: 10000000
[INFO] Sum after: 10084680
[INFO] Delta: 84680
[INFO] Finished. Time elapsed: 2592 ms
Adding synchronized keyword on account level solves the problem.
Options: -strategy=sync_account -threads=2 -accounts=1000 -nPerThread=10000000
[INFO] Strategy: SYNC_ACCOUNT
[INFO] Evaluation started...
[INFO] Sum before: 10000000
[INFO] Sum after: 10000000
[INFO] Delta: 0
[INFO] Finished. Time elapsed: 4482 ms
Sure it takes more time as overhead for synchronization, but consistency is saved. Let's reduce number of accounts to two.
Options: -strategy=sync_account -threads=4 -accounts=2 -nPerThread=10000000
[INFO] Strategy: SYNC_ACCOUNT
[INFO] Evaluation started...
[INFO] Sum before: 20000
[INFO] Sum after: 17687
[INFO] Delta: 2313
[INFO] Finished. Time elapsed: 300020 ms
What happened?
We encountered a deadlock and simulation never ends (it ends, actually, because of service.awaitTermination(5, TimeUnit.MINUTES))
For better deadlock reproducability we added a Thread.yield() to incBalance method.
To avoid deadlocks situation we could add synchronized on transfer method.
But our program becomes single-threaded. You won't get speed if you have a lot of processors.
Options: -strategy=sync_bank -threads=10 -accounts=1000 -nPerThread=10000000
[INFO] Strategy: SYNC_BANK
[INFO] Evaluation started...
[INFO] Sum before: 10000000
[INFO] Sum after: 10000000
[INFO] Delta: 0
[INFO] Finished. Time elapsed: 21799 ms
Test it on 100 threads.
Options: -strategy=sync_bank -threads=100 -accounts=1000 -nPerThread=10000000
[INFO] Strategy: SYNC_BANK
[INFO] Evaluation started...
[INFO] Sum before: 10000000
[INFO] Sum after: 10000000
[INFO] Delta: 0
[INFO] Finished. Time elapsed: 218227 ms
STM (Software Transactional Memory) by multiverse implementation
Just wrap your critical sections to StmUtils.atomic()
10 threads
Options: -strategy=stm -threads=10 -accounts=1000 -nPerThread=10000000
[INFO] Strategy: STM
[INFO] Evaluation started...
[INFO] Sum before: 10000000
[INFO] Sum after: 10000000
[INFO] Delta: 0
[INFO] Finished. Time elapsed: 14066 ms
100 threads
Options: -strategy=stm -threads=100 -accounts=1000 -nPerThread=10000000
[INFO] Strategy: STM
[INFO] Evaluation started...
[INFO] Sum before: 10000000
[INFO] Sum after: 10000000
[INFO] Delta: 0
[INFO] Finished. Time elapsed: 26586 ms
It just works
