Race Condition vs. Data Race in Java

Race Condition vs. Data Race in Java

Race conditions and data races may seem similar, but they are very different. Check out this post for more on the differences between race conditions and data races in Java.

Valentin Kovalenko

Aug. 07, 18 · Java Zone ·

Free Resource

It may seem that the terms race condition and data race have the same meaning, while — in fact — they are different. In the book,  Java Concurrency in Practice , it says: "Not all race conditions are data races, and not all data races are race conditions, but they both can cause concurrent programs to fail in unpredictable ways." In order to further explain this, I am going to demonstrate a situation where there is a race condition, but there is no data race. I also do this by showing a situation where there are a data race and no race condition.

Introduction

A race condition is a property of an algorithm (or a program,  system, etc.) that is manifested in displaying anomalous outcomes or behavior because of the unfortunate ordering (or relative timing) of events.

A data race is the property of an  execution of a program. According to the  Java Memory Model (JMM) , an execution is said to contain a data race if it contains at least two conflicting accesses (reads of or writes to the same variable) that are not ordered by a  happens-before (HB) relationship (two accesses to the same variable are said to be conflicting if at least one of the accesses is a write).

This definition can probably be generalized by saying that an execution contains a data race if it contains at least two conflicting accesses that are not properly coordinated (a.k.a synchronized), but I am going to talk about data races as they are defined by the JMM. And, unfortunately, the above definition has a significant flaw. While it has been pointed out many times by different people, the problem has never been fixed:

• " The way 'data race' and 'correctly-synchronized' programs are defined in JMM continue bothering me. It makes completely legit programs producing consistent results with all shared variables declared volatile ... to be 'incorrectly synchronized,' because the data race definition is equally applicable to plain and volatile accesses. So, my question is: shouldn't data race be specified in JMM for non-volatile conflicting accesses only? " (I asked this question in the  concurrency-interest discussion list  2017. I recommend it for those who are interested in a formal explanation of the problem).
• " Is volatile read happens-before volatile write? " stackoverflow.com , 2013.
• " Volatile happens before the question " [ Concurrency-interest discussion list ,  the answer , 2012]
• " JLS3 contains glitch concerning volatiles? " Java Memory Model discussions list  and  the answer , 2005.

Despite the incorrect definition stated by JMM that remains unchanged, I am going to use a fixed version. An execution is said to contain a data race if it contains at least two conflicting non-volatile accesses to a shared variable that are not ordered by a happens-before relation.

While the data race is a property of an execution and not a program, you may often see people saying that a program has a data race. And, we do not have to look far to find such situations, because even JMM does so in some places. The phrase "program has a data race" means that there are executions of the program, which are allowed by JMM and contain the data race (hereafter, in this post, I will refer to an execution allowed by JMM as just an execution).

Examples

Race Condition Example

While I could have described an algorithm with a race condition in plain English, I will show you a source code of a program in Java that has this condition to emphasize that data race and race condition do not necessarily imply one another — even in Java programs.

class RaceConditionExample {
  static volatile boolean flag = false;

  static void raiseFlag() {
    flag = true;
  }

  public static void main(String... args) {
    ForkJoinPool.commonPool().execute(RaceConditionExample::raiseFlag);
    System.out.print(flag);
  }
}

The only shared variable in the program (1) is a flag, and it is marked as volatile. Hence, by definition, there are no data races in any execution of this program. And, yet, it is obvious that the program may print not only true (let's say the desired outcome) but also false, because we do not impose any order between the action-reading flag for printing and the action-writing true to flag (see method  raiseFlag ). More specifically, these two actions are  synchronization actions . Thus, they are  totally ordered with synchronization order (SO) . However, both orders are allowed and lead to different program outputs (false and true respectively):

• SO: read for printing; write true

• SO: write true; read for printing

This program can exit correctly without ever executing the method raiseFlag . So, the program clearly has a race condition, despite having no data races.

We can get rid of a race condition in our program by changing the program as follows (the approach is only being used for demonstration purposes, so please don't copy it blindly to a real code, because there are similar ways to accomplish the same goal):

class NoRaceConditionExample {
  static volatile boolean flag = false;//w0

  static void raiseFlag() {
    flag = true;//w1
  }

  public static void main(String... args) {
    ForkJoinPool.commonPool().execute(RaceConditionExample::raiseFlag);
    while (!flag);//r_i, where i ∈ [1, k], k is finite
    System.out.print(flag);//r
  }
}

For this program, JMM allows executions with the following synchronization orders (there can't be any other synchronization orders) (2)

• SO1: w0, w1, r_1, r

This gives synchronized-with (w1, r), because w1 and r are both the same volatile variable flag, and hence, HB(w1, r) makes r == true.

• SO2: w0, r_1, ..., w1, ... r_k, r

This gives r == true (similar to the above).

Hereby, all executions of this modified program produce the same result — they print true. Therefore, this program does not have a race condition.

I would like to add that, while race condition is not directly mentioned in JMM, there is a phrase " freedom from data races still allows errors arising from groups of operations that need to be perceived atomically and are not. " This successfully describes a particular case of a race condition.

Data Race Example

Let us change the example by getting rid of the volatile modifier.

class DataRaceExample {
  static boolean flag = false;//w0

  static void raiseFlag() {
    flag = true;//w1
  }

  public static void main(String... args) {
    ForkJoinPool.commonPool().execute(DataRaceExample::raiseFlag);
    while (!flag);//r_i, where i ∈ [1, k), k may be infinite
    System.out.print(flag);//r
  }
}

Now, all executions have data races, because the flag   is not volatile, and there are no sources for HB relations between w and any r_i or between w and r. By definition, we have executions of this program containing data races. In this situation, JMM allows either true or false to be read by any of the reads r_i, r. The program may not only print true or false, but it may also hang executing  while (!flag)   infinitely and never actually perform the action r.

Now, we have a program that produces anomalous outcomes, and they are not caused by any unfortunate ordering or timings but, rather, by data races in the executions of the program.

For the sake of completeness, I need to say that data races do not always lead to unexpected outcomes (while race conditions — by definition — do), and, sometimes, they are used to allow the program to perform faster. These are so-called benign data races. Examples of such benign cases can be found in the code from the Java Development Kit (JDK):

/* java.lang.String from OpenJDK 10
 * see http://hg.openjdk.java.net/jdk10/master/file/be620a591379/src/java.base/share/classes/java/lang/String.java#l1513
 */
private int hash; // Default to 0

public int hashCode() {//read/write actions from/to hash field are not ordered with HB
    int h = hash;
    if (h == 0 && value.length > 0) {
        hash = h = isLatin1() ? StringLatin1.hashCode(value)
                              : StringUTF16.hashCode(value);
    }
    return h;
}

/* java.util.concurrent.ConcurrentHashMap from OpenJDK 6
 * see http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b27/java/util/concurrent/ConcurrentHashMap.java#362
 * unfortunately, this implementation was changed even in OpenJDK 6, so grepcode.com is the only public source known to me
 */
V get(Object key, int hash) {
  if (count != 0) {//volatile read
    HashEntry<K,V> e = getFirst(hash);
    while (e != null) {
      if (e.hash == hash && key.equals(e.key)) {
        V v = e.value;//read of a plain value field without synchronization does not impose HB
        if (v != null)
          return v;
        return readValueUnderLock(e);//read again with synchronization, impose HB
      }
      e = e.next;
    }
  }
  return null;
}

Footnotes

(1) Here we are ignoring any shared variables used inside  ForkJoinPool.commonPool().execute(DataRaceExample::raiseFlag) without the loss of generality.

(2) This explanation assumes that a reader is familiar with formal JMM rules.