Does Java permit unbounded starvation?

Question

Introduction

Consider this Java program:

public class Loop {
    static volatile boolean flag;
    public static void main(String[] args) {
        new Thread(() -> flag = true).start();
        while(!flag);
    }
}

Expressed in words: There are two threads. One thread waits for a volatile boolean flag to become true in a loop; the other sets flag to true.

To my understanding, the Java Language Specification does not guarantee that this program halts - see below for my reasoning.

However, I am not sure if my understanding is correct here, since programs similar to this are sometimes presented as examples of correct Java synchronization.

Reasoning

All references to the JLS refer to Java SE 23. Also, if I refer to reads or writes without explicitly specifying which variable they refer to, I mean reads from / writes to flag for brevity, because these reads and writes are the most relevant.

§17.4 defines the Java Memory Model (JMM) - it categorizes which behaviors of a program are valid and which are not. §17.4.1 - §17.4.7 specify the notion of valid executions; §17.4.8 further constrains executions to ones that don't violate causality; and §17.4.9 specifies observable behaviors of programs, building on valid executions.

Valid executions

As a first step, I believe that for every n > 0, there is a valid execution of the given program which contains exactly n volatile reads, and no external actions (except for the executionTermination action introduced by §17.4.9). Specifically, this is the execution whose synchronization actions, ordered by synchronization order, are:

1. Two threads, A and B, start (i.e., perform their synthetic first action; see §17.4.2).
2. A does n-1 volatile reads, seeing the synthetic write of the default value false.
3. B does one volatile write of value true
4. A does one more volatile read, seeing the volatile write performed by B.
5. Both A and B terminate (i.e. perform their synthetic last action; see §17.4.2).

I believe that these executions fulfil all of the requirements for valid executions given in §17.4.1 - §17.4.7, and moreover the conditions for causality requrements given in §17.4.8. Arguing that with mathematical precision is very tedious, though, so I'll omit it for brevity (this question is already way too long as it is!)

Observable behavior

Next, I'll argue that the behaviour consisting of just a hang action is an observable behavior of the given program.

§17.4.9 states:

[...]

If O is a set of observable actions for an execution E, then set O must be a subset of E's actions, A, and must contain only a finite number of actions, even if A contains an infinite number of actions. Furthermore, if an action y is in O, and either hb(x, y) or so(x, y), then x is in O.

[...]

A behavior B is an allowable behavior of a program P if and only if B is a finite set of external actions and either:

• [...]
• There exists a set O of actions such that B consists of a hang action plus all the external actions in O and for all k ≥ |O|, there exists an execution E of P with actions A, and there exists a set of actions O' such that:
  • Both O and O' are subsets of A that fulfill the requirements for sets of observable actions.
  • O ⊆ O' ⊆ A
  • |O'| ≥ k
  • O' - O contains no external actions

Choose B to be the singleton set containing only a hang action, and O to be the empty set. Now, we have to show the conditions given here for all k ≥ 0.

For any such given k, choose E to be the execution with exactly k reads. Then, A is a set of at least k actions, which contains exactly one external action - specifically an executionTermination. Now, choose O' to be A without that executionTermination action. Then, all four conditions from §17.4.9 are fulfilled:

• "Both O and O' are subsets of A that fulfill the requirements for sets of observable actions":
  • Both O and O' are subsets of A.
  • Both are finite: |O| = 0, and |O'| = n+X where X is the constant number of actions beyond the n reads.
  • O contains no actions, meaning that the condition relating to hb is vacuously true.
  • O' contains all actions from A except the executionTermination, and there is no x such that hb(executionTermination, x), which would be the only way forcing the executionTermination to be in O'.
• "O ⊆ O' ⊆ A" is true by definition of O and O'.
• "|O'| ≥ k" is true because O' contains at least k reads.
• "O' - O contains no external actions" is true by definition of O and O' - neither contain any external actions.

Behaviour of real JVMs

I experimented a bit using the OpenJDK - specifically, Oracle build 23+37-2369 - on a x86_64 machine.

I was not able to make the real OpenJDK / Oracle JDK hang for variants of this program as long as flag is volatile - not even by introducing "encouragement" like calls to Thread::sleep or Thread::setPriority. Even when invoking with -Xcomp -Xbatch (and -XX:+UnlockDiagnosticVMOptions -XX:CompileCommand=print,Loop.* -XX:PrintAssemblyOptions=intel for showing generated assembly), both C1 and C2 keep the loop condition intact. The following is how C2 represents the loop:

  0x00007f7f1855e950:   movzx  r8d,BYTE PTR [r10+0x70]
  0x00007f7f1855e955:   mov    r11,QWORD PTR [r15+0x450]    ; ImmutableOopMap {r10=Oop }
                                                            ;*ifeq {reexecute=1 rethrow=0 return_oop=0}
                                                            ; - (reexecute) Loop::main@18 (line 6)
  0x00007f7f1855e95c:   test   DWORD PTR [r11],eax          ;   {poll}
  0x00007f7f1855e95f:   test   r8d,r8d
  0x00007f7f1855e962:   je     0x00007f7f1855e950

The one variant of this program where OpenJDK / Oracle JDK does hang is if flag is made non-volatile. However, that changes things even from the JMM's point of view, because then there no longer are any hb-edges from the write action to any of the read actions. In this case in practice, C2 "optimizes" the loop to an infinite loop, like this:

  0x00007ffa5455e960:   mov    r10,QWORD PTR [r15+0x450]    ; ImmutableOopMap {}
                                                            ;*ifeq {reexecute=1 rethrow=0 return_oop=0}
                                                            ; - (reexecute) Loop::main@18 (line 6)
  0x00007ffa5455e967:   test   DWORD PTR [r10],eax          ;   {poll}
  0x00007ffa5455e96a:   jmp    0x00007ffa5455e960

Questions

• Is my understanding of the JLS / JMM correct in that the program above is allowed to not halt? If no, where is my mistake?
• If my understanding is correct, is there some combination of circumstances (CPU architecture, JDK build, JVM arguments, ...) where the program given above, or a variant of it (as long as flag is volatile) does not halt on a real JVM?

Answer 1

Is my understanding of the JLS / JMM correct in that the program above is allowed to not halt? If no, where is my mistake?

As far as I understand, that is correct.
The reason is that the JMM lacks requirements that volatile writes should become visible in another threads in some finite amount of time.

Here is how such requirements expressed in C++:

¹⁸ An implementation should ensure that the last value (in modification order) assigned by an atomic or synchronization operation will become visible to all other threads in a finite period of time.

¹¹ Recommended practice: The implementation should make atomic stores visible to atomic loads, and atomic loads should observe atomic stores, within a reasonable amount of time.

It would be nice to add something like that to the JMM as well.

---

If my understanding is correct, is there some combination of circumstances (CPU architecture, JDK build, JVM arguments, ...) where the program given above, or a variant of it (as long as flag is volatile) does not halt on a real JVM?

I haven't heard about anything like that.

For any "serious" JVM (e.g. HotSpot, OpenJ9, GraalVM) such behavior IMO would be a bug, even if the math in the JMM permits that.

BTW strictly speaking a JVM where all volatile writes are never visible to other threads meets the JMM spec.