<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<style type="text/css" style="display:none;"> P {margin-top:0;margin-bottom:0;} </style>
</head>
<body dir="ltr">
<div class="elementToProof" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
Good point, Archie—I completely forgot to mention the fact that polling thread state doesn't necessarily ensure that the thread has been enqueued once the thread state is moved to blocking/waiting.<br>
<br>
Thread state polling aside, for as long as Condition::await() is allowed to spuriously wake, FIFO just cannot be "guaranteed".</div>
<div class="elementToProof" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div id="Signature" style="color: inherit;">
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
Cheers,<br>
√</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<b><br>
</b></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<b>Viktor Klang</b></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
Software Architect, Java Platform Group<br>
Oracle</div>
</div>
<div id="appendonsend"></div>
<hr style="display:inline-block;width:98%" tabindex="-1">
<div id="divRplyFwdMsg" dir="ltr"><font face="Calibri, sans-serif" style="font-size:11pt" color="#000000"><b>From:</b> Archie Cobbs <archie.cobbs@gmail.com><br>
<b>Sent:</b> Thursday, 5 September 2024 18:44<br>
<b>To:</b> 김민주 <miiiinju00@gmail.com><br>
<b>Cc:</b> Viktor Klang <viktor.klang@oracle.com>; Daniel FUCHS <daniel.fuchs@oracle.com>; core-libs-dev@openjdk.org <core-libs-dev@openjdk.org><br>
<b>Subject:</b> Re: [External] : Re: [POTENTIAL BUG] Potential FIFO violation in BlockingQueue under high contention and suggestion for fair mode in ArrayBlockingQueue and LinkedBlockingQueue</font>
<div> </div>
</div>
<div>
<div dir="ltr">
<div dir="ltr">
<div>Hi Kim,</div>
<div><br>
</div>
<div>I think there may be an issue with your test. Specifically, this code is suspect:</div>
<div>
<pre> // Wait for the producer thread to enter BLOCKED state
// This ensures that the thread is waiting on the full queue
while (thread.getState() == State.RUNNABLE || thread.getState() == State.NEW);</pre>
</div>
<div>I don't think that actually guarantees that the thread is blocked in <span style="font-family:monospace">
put()</span>.<br>
</div>
<div><br>
</div>
<div>I was able to reproduce the bug using <span style="font-family:monospace">ArrayBlockingQueue()</span>, but could no longer reproduce it after I changed the above code to this:</div>
<div><br>
</div>
<div><span style="font-family:monospace"> // Wait for the producer thread to block in queue.put()<br>
// This ensures that the thread is waiting on the full queue<br>
while (!queue.isPutting(thread));</span><br>
</div>
<div><br>
</div>
<div>after also making this change to <span style="font-family:monospace">ArrayBlockingQueue.java</span>:</div>
<div><br>
</div>
<div style="margin-left:40px"><span style="font-family:monospace">--- a/src/java.base/share/classes/java/util/concurrent/ArrayBlockingQueue.java<br>
+++ b/src/java.base/share/classes/java/util/concurrent/ArrayBlockingQueue.java<br>
@@ -365,10 +365,31 @@ public void put(E e) throws InterruptedException {<br>
Objects.requireNonNull(e);<br>
final ReentrantLock lock = this.lock;<br>
lock.lockInterruptibly();<br>
+ final boolean added = puttingThreads.add(Thread.currentThread());<br>
try {<br>
while (count == items.length)<br>
notFull.await();<br>
enqueue(e);<br>
+ } finally {<br>
+ if (added)<br>
+ puttingThreads.remove(Thread.currentThread());<br>
+ lock.unlock();<br>
+ }<br>
+ }<br>
+<br>
+ private final java.util.HashSet<Thread> puttingThreads = new java.util.HashSet<>();<br>
+<br>
+ /**<br>
+ * Test for putting thread.<br>
+ *<br>
+ * @param thread thread to test<br>
+ * @return true if thread is a putting thread<br>
+ */<br>
+ public boolean isPutting(Thread thread) {<br>
+ final ReentrantLock lock = this.lock;<br>
+ lock.lock();<br>
+ try {<br>
+ return puttingThreads.contains(thread);<br>
} finally {<br>
lock.unlock();<br>
}</span></div>
<div><br>
</div>
<div>So the original test may not be correct due to Java memory model subtleties, etc.<br>
</div>
<div><br>
</div>
<div>-Archie<br>
</div>
<br>
</div>
<span class="x_gmail_signature_prefix">-- </span><br>
<div dir="ltr" class="x_gmail_signature">Archie L. Cobbs<br>
</div>
</div>
</div>
</body>
</html>