Race Condition vs. Data Race in Java

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⁽¹⁾ 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 that is reading flag for printing and the action that is 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

And moreover, this program can exit without even ever executing 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 better 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)⁽²⁾

• SO1: w0, w1, r_1, r

This gives synchronized-with (w1, r), because w1 and r both affect the same volatile variable flag, and hence, HB(w1, r), which gives 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 phrase 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

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

⁽²⁾ This explanation assumes that a reader is familiar with formal JMM rules.