Java: Multithreading — Part 2 — Race condition

~Demystifying multithreading~

8 min readMar 9, 2019

If you are new to multithreading or if you need a refresher, please read Part 1 of this series here — https://blog.usejournal.com/java-multithreading-part-1-ec0c42bbead6

Race Condition

“…We, even we here, hold the power and bear the responsibility...”
— Abraham Lincoln, 1862

Analogy

Analogy 1

When you want to give valuable advice to someone you really care about, the first step is to listen to them. When you both talk simultaneously, you will end up leaving the person in a bad state.

Analogy 2

When you want to advise your kid, it makes sense that either you or your spouse talk to the kid but not both simultaneously. If you both start advising the kid simultaneously, it will leave the kid in a bad state at the end of the conversion.

Same applies to multithreaded applications. When you want to change the state of an object [a subject in real life!], which is shared and mutable (changeable) and leave it in the desired state, you will have to do it sequentially.

Of course, you can pass the control to other threads, that are waiting to access the same object, once you are done. This way, you will be 100% sure and confident that your application will behave in a predictable manner in all environments and in all situations.

“With great power comes great responsibility” — Uncle Ben, Spider-Man

Let us walk through an example scenario that has the potential to leave the state of a shared mutable object in an undesirable state.

From my mobile bank app, I am in the process of withdrawing $100

Withdrawal involves the following non-atomic sequence of steps

1) Get the current available balance
2) Check if balance >= withdrawal amount
3) If yes, then subtract $100 from the balance
4) Update the balance (in heap for other threads to see)

Coincidentally, my friend is depositing $100 into my account at the same time as I was withdrawing.

Deposit involves the following non-atomic sequence of steps

5) Get the current available balance
6) Add $100 to the balance
7) Update the balance (in heap for other threads to see)

Withdrawal and Deposit happen in 2 different application threads and they both must share the same Account object. Since the withdrawal and deposit operations constitute more than one step and the end result of these operations is to change the state of the shared object, the following scenario may occur:

Balance should have been 100, but it is now 200 due to the withdrawal and deposit operations being done at the same time on the same account without accounting for non-atomic nature of the operations.

In other words, operations interleaved due to non-atomic nature of withdrawal and deposit and because of the concurrent access; leaving the account balance (shared mutable state) in a dangerously inconsistent state.

Effectively, two threads were racing each other towards the end goal of altering the shared mutable state leading to the Race condition.

[This is just one of the many scenarios and it is totally up to the thread scheduling algorithm. Meaning, threads getting their turn to execute the non-atomic operations involving shared mutable state]

Let’s get some definitions sorted before we proceed to see the above scenario in action

Shared Mutable State

An instance or a class variable that could be modified by more than one thread of execution concurrently — because they are at the instance or class level (heap) rather than at the method level (stack).

Atomicity (or Atomic operation)

Sequence of operations executed as a single unit in order to change the state of the system. Either all the steps in the operation are executed or in case of failure, none of them are executed leaving the state of the system in a consistent state.

Interference

Multiple threads trying to concurrently modify the shared mutable state by executing non-atomic set of instructions — interfering each other in the process.

All the above factors contribute to

Race condition

When the shared mutable state is modified by a sequence of non-atomic operation concurrently by multiple interfering threads of execution, race condition is bound to happen; leaving the object in an undesirable state.

Now, let’s get into the thick of things. We are now going to tap into our multitasking ‘power’ and see where it goes.

1. Withdrawal thread: Gets the balance (100)
2. Withdrawal thread: Checks if balance >= withdrawal amount (100) = TRUE
5. Deposit thread: Gets the balance (100)
*Interference* — we are now witnessing the race
3. Withdrawal thread: Subtracts 100 from 100
4. Withdrawal thread: Updates the balance as 0
Deposit thread doesn’t bother as it has already read the balance (100)
6. Deposit thread: Adds 100 to 100 that it remembers as balance from step 5., though the current balance is 0
7. Deposit thread: Stores the new balance 200
I have won a lottery of $100 this time.

Two threads - deposit and withdrawal threads, sharing the shared mutable **account** object

I ran the above implementation in an infinite loop. On average, the race condition occurred 1 in 500 times. That is, the desired end state of current balance = 100 is violated because of concurrent modification of the same account from multiple user session threads (thread1 and thread2 in this case).

With great power comes great responsibility. Indeed.

Ideal scenario

Initial Balance of 100
100 withdrawn
100 deposited
Desired end state: Current Balance of 100

Let us now wield our power responsibly by coordinating access to the shared mutable state such that the read/write by multiple threads happens only sequentially.

Java language platform has an in-built mechanism to achieve this coordination among competing threads called — Monitor or lock in general. Every object has an intrinsic lock called monitor. We can let threads make use of it for sequential access by marking the methods as ‘synchronized’.

Synchronized access using the monitor or intrinsic lock

Now that we know about the Java language provision — lock, we are in a better position than before in terms of wielding power responsibly. Above implementation, with synchronized methods, will make sure that at any point in time, only one thread can read/write from/to ‘currentBalance’.

We can now make guarantees about our application’s robustness and sleep without nightmares of unreproducible production issues.

In addition to the monitor lock, any object can themselves act as locks as shown below

Using a custom lock to guard the shared state against concurrent access

Please note that the state that we want to protect against concurrent read/write must be guarded (locked) by the same object.

‘curreBalanceLock’ in this case guards both read and write. Using method level synchronization would lock down the entire method and all other synchronized methods; which may not be desirable if those methods are operating on other unrelated states.

In such cases, using custom lock objects for each of the independent states make sense as it is always recommended that the scope of synchronization must be limited to a minimum possible extent so as to improve responsiveness and performance of the application.

Non-atomic state change operations take the following forms

Check-then-Act
Reade-Modify-Write

Let’s quickly see them in action before we wrap up

Check-then-Act

Thread1 checks and finds the instance as null
Thread2 checks and finds the instance as null
Thread1 initializes the instance variable
Thread1 gets the newly created instance
Thread2 initializes the instance variable again
Thread2 gets the newly created instance

Desired state:
Only one instance of the Singleton class must exist at any point in time.
Actual state:
More than one instance of Singleton is now created because of racing threads

Reade-Modify-Write

Thread1 reads the value of the counter as 0
Thread2 reads the value of the counter as 0
Thread1 increments the value of the counter to 1
Thread2 increments the value of the counter to 1
Thread1 writes the value of the counter (1)
Thread2 writes the value of the counter (1)

Desired state:
counter = 2
Actual state:
counter = 1

Summary

Concurrent modification of shared mutable state involving non-atomic operation will lead to a race condition; leaving the state in an undesirable state. In order to guard against this pitfall, multithreaded applications must synchronize access to the shared mutable state.

By synchronizing access to the shared mutable state, we achieve the following

Mutual exclusion locking — Avoids thread interference (interleaving) during concurrent state modification involving non-atomic operations by locking down the critical block so as to mutually exclude threads from concurrent access.
Memory consistency — Ensures visibility of the state modified by one application thread to threads that will subsequently be accessing the same state. (Will explain this in the next post)