Race Conditions

General Problem

• Scheduler is allowed to switch context between every operation. So even read and write access to longs and doubles are not guaranteed to be atomic.
• Number of all possible interleavings depending on the number of threads $n$ and the number of atomic instructions $m$ : $$ \text{#interleavings} = \frac{(n * m)!}{(m!)^n}$$ so, for example with 2 threads and 3 atomic instructions we get $$ \text{#interleavings} = \frac{(2 * 3)!}{(3!)^2} = \bold{20}$$ for 4 threads and 3 atomic instructions we already get 369'600 different possibilities!
• Definition of a Race Condition: Two or more threads are accessing some shared data and at least one is modifying. The final result depends on the timing of how the threads are scheduled.
• Problem: Thread scheduling on the JVM is nondeterministic
• Solution: Use proper synchro. This means managing access to shared, mutable state
• Invariants: Properties about an objects state that always hold. Preserving invariants is harder in a concurrent setting.

Java language features to solve it

• We use locking. Its a mechanism to enforce mutual exclusion.
• The synchronized keyword is the built in locking mechanism for enforcing atomicity. It consists of two parts:
  • reference to an object that will server as lock.
  • a block of code to be guarded by that lock.
• Data Protection: synchronized flag does not protect data, it can still be manipulated by direct access or unsynchronized threads.
  • For each mutable state variable that may be accessed by more than one thread, all access to that variable must be performed with the same lock held. In this case, we say that the variable is guarded by that lock.
  • For every invariant that involves more than one variable, all the variables involved in that invariant must be guarded by the same lock.