Bug ID: JDK-8300663 java/util/concurrent/SynchronousQueue/Fairness.java failed with "Error: fair=true i=0 j=1"

JDK 21	JDK 22
21.0.2Fixed	22 b08Fixed

I'm still thinking as I did in sister issue https://bugs.openjdk.org/browse/JDK-8314515?focusedCommentId=14605989&page=com.atlassian.jira.plugin.system.issuetabpanels%3Acomment-tabpanel#comment-14605989 SynchronousQueue does maintain a total order of its waiting threads - it's just a linked list! This order matters to users (even if not directly observable), and is in the spec. In the spirit of "design for testability", SynchronousQueue should make its wait queue observable by adding a method to do so. You could make it module-private if reluctant to make it public. (But that's a lot of work and I'm not (yet) volunteering to do it myself)
16-09-2023
A pull request was submitted for review. URL: https://git.openjdk.org/jdk21u/pull/168 Date: 2023-09-15 18:39:02 +0000
15-09-2023
[~martin] Having thought about this for a while, and after deliberations with Doug. I strongly suspect that any test trying to assert for fairness in this case will have to establish a total order, and as such total order is not likely to exist in any real-world use-case my bet is that fairness in this case (synchronous queue) is not observable. I'm very much open to be convinced otherwise, so if you have any suggestion as to how to proceed it's more than welcome.
13-09-2023
... or slightly better: If the only remaining problem is misfiring because of blockages during classloading, it would suffice to run twice, ignoring the first run. A version that adds this to Martin's s pasted below Viktor: do you know how to run tier2 tests across platforms to check this before PR? Also, I'm not sure why we even have this test if the only property it detects cannot be observed by users? import java.util.ArrayList; import java.util.List; import java.util.concurrent.BlockingQueue; import java.util.concurrent.CountDownLatch; import java.util.concurrent.SynchronousQueue; import java.util.concurrent.ThreadLocalRandom; import java.util.concurrent.atomic.AtomicReference; public class Fairness { public class Fairness { private static void testFairness(boolean fair, boolean warm, SynchronousQueue<Integer> q) throws Throwable { int threadCount = ThreadLocalRandom.current().nextInt(2, 8); AtomicReference<Throwable> badness = new AtomicReference<>(); List<Thread> ts = new ArrayList<>(); for (int i = 0; i < threadCount; i++) { final Integer I = i; CountDownLatch ready = new CountDownLatch(1); Runnable put = () -> { try { ready.countDown(); q.put(I); } catch (Throwable fail) { badness.set(fail); } }; Thread t = new Thread(put); t.start(); ts.add(t); ready.await(); // Wait for each call to q.put to block before starting the next while (t.getState() == Thread.State.RUNNABLE) Thread.yield(); } for (int i = 0; i < threadCount; i++) { int j = q.take(); // Fair queues are specified to be FIFO. // Non-fair queues are LIFO in our implementation. if (fair ? j != i : j != threadCount - 1 - i) { // ignore on warmup to avoid false-alarms on class-loading String msg = String.format("fair=%b i=%d/%d j=%d%n", fair, i, threadCount, j); if (warm) throw new Error(msg); } for (Thread t : ts) t.join(); if (badness.get() != null) throw new Error(badness.get()); } public static void main(String[] args) throws Throwable { testFairness(false, false, new SynchronousQueue<Integer>()); testFairness(false, false, new SynchronousQueue<Integer>(false)); testFairness(true, false, new SynchronousQueue<Integer>(true)); testFairness(false, true, new SynchronousQueue<Integer>()); testFairness(false, true, new SynchronousQueue<Integer>(false)); testFairness(true, true, new SynchronousQueue<Integer>(true)); } }
08-08-2023
Not yet PRed. I'm wondering if while we are at it, we should include the stack-probe-on-yield that was done for forkjoin/AsyccShutDownNow. This would help guard against misfires on blockages during class-loading but also make it more white-box-y and so fragile wrt future updates.
07-08-2023
[~dl] [~martin] Was the test update PR:ed, or primarily for consideration?
07-08-2023
I was feeling some guilt about this test, so ... Here's a proposed improvement: import java.util.ArrayList; import java.util.List; import java.util.concurrent.BlockingQueue; import java.util.concurrent.CountDownLatch; import java.util.concurrent.SynchronousQueue; import java.util.concurrent.ThreadLocalRandom; import java.util.concurrent.atomic.AtomicReference; public class Fairness { private static void testFairness(boolean fair, SynchronousQueue<Integer> q) throws Throwable { int threadCount = ThreadLocalRandom.current().nextInt(2, 8); AtomicReference<Throwable> badness = new AtomicReference<>(); List<Thread> ts = new ArrayList<>(); for (int i = 0; i < threadCount; i++) { final Integer I = i; CountDownLatch ready = new CountDownLatch(1); Runnable put = () -> { try { ready.countDown(); q.put(I); } catch (Throwable fail) { badness.set(fail); } }; Thread t = new Thread(put); t.start(); ts.add(t); ready.await(); // Wait for each call to q.put to block before starting the next while (t.getState() == Thread.State.RUNNABLE) Thread.yield(); } for (int i = 0; i < threadCount; i++) { int j = q.take(); // Fair queues are specified to be FIFO. // Non-fair queues are LIFO in our implementation. if (fair ? j != i : j != threadCount - 1 - i) throw new Error(String.format("fair=%b i=%d/%d j=%d%n", fair, i, threadCount, j)); } for (Thread t : ts) t.join(); if (badness.get() != null) throw new Error(badness.get()); } public static void main(String[] args) throws Throwable { testFairness(false, new SynchronousQueue<Integer>()); testFairness(false, new SynchronousQueue<Integer>(false)); testFairness(true, new SynchronousQueue<Integer>(true)); } }
28-07-2023
I just noticed that this test doesn't strictly guarantee ordering of producers in the case of spurious wakeups. Which would account for rare failures. I'll find a better way to do this.
27-07-2023
Changeset: 8d1ab570 Author: Doug Lea <dl@openjdk.org> Date: 2023-07-22 10:41:42 +0000 URL: https://git.openjdk.org/jdk/commit/8d1ab57065c7ebcc650b5fb4ae098f8b0a35f112
22-07-2023
A pull request was submitted for review. URL: https://git.openjdk.org/jdk/pull/14317 Date: 2023-06-05 18:52:00 +0000
20-07-2023
Re-assigning to you, Doug :)
03-07-2023
Here's a log file snippet from the jdk-22+2-30-tier8 sighting: java/util/concurrent/SynchronousQueue/Fairness.java #section:main ----------messages:(7/219)---------- command: main Fairness reason: Assumed action based on file name: run main Fairness started: Mon Jun 12 12:00:59 GMT 2023 Mode: agentvm Agent id: 28 finished: Mon Jun 12 12:02:00 GMT 2023 elapsed time (seconds): 61.47 ----------configuration:(12/1534)---------- <snip> ----------System.err:(12/532)---------- java.lang.Error: fair=true i=0 j=3 at Fairness.testFairness(Fairness.java:64) at Fairness.main(Fairness.java:73) at java.base/jdk.internal.reflect.DirectMethodHandleAccessor.invoke(DirectMethodHandleAccessor.java:103) at java.base/java.lang.reflect.Method.invoke(Method.java:580) at com.sun.javatest.regtest.agent.MainActionHelper$AgentVMRunnable.run(MainActionHelper.java:333) at java.base/java.lang.Thread.run(Thread.java:1583) JavaTest Message: Test threw exception: java.lang.Error JavaTest Message: shutting down test result: Failed. Execution failed: `main' threw exception: java.lang.Error: fair=true i=0 j=3
12-06-2023
[~vklang] For many years, until 2021-02 (when I left Google) I did almost all integrations from jsr166 CVS into openjdk, including stress testing and release engineering. So you can't generally tell "real" authorship from git blame (fine grained detail is only available via CVS!). SynchronousQueue is one of the classes that only dl understands deeply.
23-02-2023
Yes, this did arise in the initially-loom-only update to avoid spins for virtual threads but with yet being able to check for them and deal with them specially. This might be hard to address until loom is out of preview status.
06-02-2023
[~martin] Could this perhaps be related to https://github.com/openjdk/jdk/commit/63e3bd7613918c6838ee89151d62a8695e27dcba where there's a (small) window of opportunity where SynchronousQueue is not fair?
26-01-2023
[~dcubed] I'm not able to reproduce this problem. Could be a spurious issue related to thread scheduling of the test?
25-01-2023