# Race Condition A race condition is a concurrency problem that may occur inside a critical section when multiple threads compete for the same resource. # Critical Section A critical section is a section of code that is executed by multiple threads and where the sequence of execution for the threads makes a difference in the result of the current execution of the critical section. # Two Types of Race Conditions Race conditions can occur when two or more threads read and write the same variable according to one of these two patterns * Read-modify-write * Check-then-act ## Read-modify-write The read-modify-write patterns means that two or more threads first read a given variable, then modify its value, and write it back to the variable. For this to cause a problem, the new value must depend one way or another on the previous value. ``` public class Counter { protected long count = 0; public void add(long value){ this.count = this.count + value; } } ``` The problem can occur if two threads tread read the value (into CPU registers) then modify the value (in the CPU registers) and then write the values back. Imagine two threads, A and B, executing the add method on the sam instance of the Counter class. There is no way to know when the operating system switches between the two threads. The code in the add() method is not executed as a single atomic instruction by the JVM. It is executed as a set of smaller instructions. 1. Read this.count from memory into register 2. Add value to register 3. Write register to memory Observe what happens with the following mixed execution of threads A and B ``` this.count = 0; A: Reads this.count into a register (0) B: Reads this.count into a register (0) B: Adds value 2 to register B: Writes register value (2) back to memory. this.count now equals 2 A: Adds value 3 to register A: Writes register value (3) back to memory. this.count now equals 3 ``` Thread A added value 3 and thread B added value 2. Therefore, the resulting value in memory should have been 5. However, since the execution of the two threads is interleaved, the result ends up being different. Instead of 5, the value left in this.count will be the value written by the last thread to write its value. In the above case it is thread A, but it could as well have been thread B. ## Check-then-act The check-then-act pattern means that two or more threads check for a given condition. For instance, if a Map contains a given value and then go on to act based on that information. The problem may occur if two threads check the Map for a given value at the same time - see that the value is present - and then both threads try to take (remove) that value. However, only one of the threads can actually take the value. The other thread will get a null value back. This could also happen when a Queue is used instead of a Map. ``` public class CheckThenActExample { public void checkThenAct(Map<String, String> sharedMap) { if(sharedMap.containsKey("key")){ String val = sharedMap.remove("key"); if(val == null) { System.out.println("Value for 'key' was null"); } } else { sharedMap.put("key", "value"); } } } ``` If two threads call the checkThenAct() method on the same object instance, then two or more threads may execute the if-statement at the same time, evaluate sharedMap.containsKey("key") to true, and thus move into the body code block of the if-statement. Inside the if statement, multiple threads may try to remove the key, value pair stored for they key "key", but only one of them will actually be able to do it. The rest will get a null value back, since another thread already removed the key, value par. # Preventing Race Conditions Race conditions can be prevented by executing the critical section as an atomic instruction. That means that once a single thread is executing it, no other threads can execute it until the thread inside it leaves the critical section. Race conditions are avoided by proper thread synchronization in critical sections. Thread synchronization can be achieved using a synchronized block of Java code. Thread synchronization can also be achieved using other synchronization constructs like locks or atomic variables like AtomicInteger. # Critical Section Throughput It makes sense for a small critical section to wrap it inside a single synchronized block. However, it may be beneficial to break a large critical section into smaller critical sections to allow multiple threads to execute each a smaller critical section. ``` public class TwoSums { private int sum1 = 0; private int sum2 = 0; public void add(int val1, int val2){ synchronized(this){ this.sum1 += val1; this.sum2 += val2; } } } ``` The summing of two different sum member variables is executed inside a Java synchronized block to prevent race conditions. However, since the two sum variables are independent of each other, you could split their summing up into two separate synchronized blocks. ``` public class TwoSums { private int sum1 = 0; private int sum2 = 0; private Integer sum1Lock = new Integer(1); private Integer sum2Lock = new Integer(2); public void add(int val1, int val2){ synchronized(this.sum1Lock){ this.sum1 += val1; } synchronized(this.sum2Lock){ this.sum2 += val2; } } } ``` Two different threads can execute the add() method at the same time. One inside the first synchronized block and the other inside the second synchronized block. The two synchronized blocks are synchronized on different objects, so two different threads can execute the two blocks independently. As a result, threads will have to wait less for each other to execute the add() method. The example above is very simple. In a real life shared resource, the breaking down of critical sections may be a whole lot more complicated and require more analysis of execution order possibilities.