<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);">
Hi Kim,</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 class="elementToProof" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
The recent updated to AQS reacquisition has to do with behavior if for some reason there's an exception thrown (think SOE or OOM, or something like that), so it isn't really applicable in this case.</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>
<ol start="1" data-listchain="__List_Chain_182" style="direction: ltr; text-align: left;">
<li style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(15, 92, 26); direction: ltr;">
The queue is full, and T2 is executing <code>put()</code> and is waiting in <code>
Condition.await()</code>.</li><li style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(15, 92, 26); direction: ltr;">
T1 calls <code>queue.take()</code>, removes an item from the queue, and is about to send a
<code>signal()</code><br>
</li><li style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(15, 92, 26); direction: ltr;">
T3 is about to call <code>put()</code> and is just before <code>lock.lockInterruptibly()</code>.</li><li style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(15, 92, 26); direction: ltr;">
T1 decreases the count and sends a <code>signal()</code>, indicating that space is available in the queue.<br>
</li><li style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(15, 92, 26); direction: ltr;">
T3 acquires the lock via <code>lock.lockInterruptibly()</code>, successfully enqueues an item because the count condition is satisfied, and releases the lock.<br>
</li><li style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(15, 92, 26); direction: ltr;">
T2 receives the signal and wakes up, but since T3 already enqueued an item, the count has increased, and T2 must wait again in
<code>await()</code>.</li></ol>
<div class="elementToProof" style="direction: ltr; font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div class="elementToProof" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
I've re-read ReentrantLock and AQS, and from my understanding on the logic the Condition's place in the wait queue should be maintained, which means that T3 shouldn't be able to "barge". (tryLock() is documented to allow barging)<br>
<br>
Let us know if you can come up with a reproducer which says otherwise. 👍</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" style="color: inherit;"></div>
<div style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<hr style="display: inline-block; width: 98%;">
<div id="divRplyFwdMsg" dir="ltr" style="color: inherit;"><span style="font-family: Calibri, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);"><b>From:</b> 김민주 <miiiinju00@gmail.com><br>
<b>Sent:</b> Friday, 6 September 2024 04:43<br>
<b>To:</b> Viktor Klang <viktor.klang@oracle.com><br>
<b>Cc:</b> Archie Cobbs <archie.cobbs@gmail.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</span>
<div> </div>
</div>
<p style="direction: ltr; margin-top: 0px; margin-bottom: 0px;"><b>Hi Archie,</b></p>
<p style="direction: ltr; margin-top: 0px; margin-bottom: 0px;">Thanks to your valuable suggestions, I was able to come up with a much more appropriate test, and I’ve learned a great deal in the process. I truly appreciate your insights! While this approach
is clearly a significant improvement over the previous one, I still feel there might be concerns about the atomicity between
<code>notFull.await()</code> and the signaling from outside, but I can’t deny that this new approach provides much better guarantees. Your feedback has been incredibly helpful, and I’m very grateful for your time and effort. Thank you again!</p>
<p style="direction: ltr; margin-top: 0px; margin-bottom: 0px;"><br>
</p>
<p style="direction: ltr; margin-top: 0px; margin-bottom: 0px;"><br>
</p>
<p style="direction: ltr; margin-top: 0px; margin-bottom: 0px;"><br>
</p>
<p style="direction: ltr; margin-top: 0px; margin-bottom: 0px;"><br>
</p>
<hr style="direction: ltr;">
<p style="direction: ltr; margin-top: 0px; margin-bottom: 0px;"><b>Hi Viktor,</b></p>
<p style="direction: ltr; margin-top: 0px; margin-bottom: 0px;">Thank you for sharing your thoughts, which have given me much to consider. I have a follow-up question regarding the improvements in AQS that you mentioned. Specifically, I’d like to clarify whether
these improvements ensure that, in the fair mode of <code>ReentrantLock</code>, threads waiting on a
<code>Condition</code> are placed back in the queue without acquiring the lock, or if the signaling thread can now immediately acquire the lock after being signaled.</p>
<p style="direction: ltr; margin-top: 0px; margin-bottom: 0px;">Initially, my concern was that a thread receiving a signal might still face starvation if another thread calls
<code>put()</code> and acquires the lock before the signaled thread can do so. Here's an example scenario:</p>
<ol start="1" data-listchain="__List_Chain_183" style="direction: ltr;">
<li style="direction: ltr;">The queue is full, and T2 is executing <code>put()</code> and is waiting in
<code>Condition.await()</code>.</li><li style="direction: ltr;">T1 calls <code>queue.take()</code>, removes an item from the queue, and is about to send a
<code>signal()</code><br>
</li><li style="direction: ltr;">T3 is about to call <code>put()</code> and is just before
<code>lock.lockInterruptibly()</code>.</li><li style="direction: ltr;">T1 decreases the count and sends a <code>signal()</code>, indicating that space is available in the queue.<br>
</li><li style="direction: ltr;">T3 acquires the lock via <code>lock.lockInterruptibly()</code>, successfully enqueues an item because the count condition is satisfied, and releases the lock.<br>
</li><li style="direction: ltr;">T2 receives the signal and wakes up, but since T3 already enqueued an item, the count has increased, and T2 must wait again in
<code>await()</code>.<br>
</li></ol>
<p style="direction: ltr; margin-top: 0px; margin-bottom: 0px;">It seems to me that this scenario could occur regardless of whether
<code>ReentrantLock</code> is in fair mode or not. Has the improvement in AQS addressed this type of contention scenario to prevent such starvation issues, or is this still a possible outcome?</p>
<hr style="direction: ltr;">
<p style="direction: ltr; margin-top: 0px; margin-bottom: 0px;">Your insights into "unbounded unfairness" have also provided me with a lot of food for thought, and I’m grateful for the opportunity to reflect on these issues. </p>
<p style="direction: ltr; margin-top: 0px; margin-bottom: 0px;">In your view, would the thread contention scenario I’ve described fall under the category of unbounded unfairness, or would it be considered an acceptable level of contention?</p>
<p style="direction: ltr; margin-top: 0px; margin-bottom: 0px;"><br>
</p>
<p style="direction: ltr; margin-top: 0px; margin-bottom: 0px;">Once again, thank you for all the knowledge and understanding I've gained through your feedback. I'm truly grateful for your time and expertise.</p>
<p style="direction: ltr; margin-top: 0px; margin-bottom: 0px;"><br>
</p>
<p style="direction: ltr; margin-top: 0px; margin-bottom: 0px;"><br>
</p>
<p style="direction: ltr; margin-top: 0px; margin-bottom: 0px;">Best regards,<br>
Kim Minju</p>
<p style="direction: ltr; margin-top: 0px; margin-bottom: 0px;"><br>
</p>
<div style="direction: ltr;"><br>
</div>
<div style="direction: ltr;">2024년 9월 6일 (금) 오전 4:52, Viktor Klang <<a href="mailto:viktor.klang@oracle.com" id="OWA27d1caf4-0620-a7f4-4464-dc8ab70119e8" class="OWAAutoLink">viktor.klang@oracle.com</a>>님이 작성:</div>
<blockquote style="margin: 0px 0px 0px 0.8ex; padding-left: 1ex; border-left: 1px solid rgb(204, 204, 204);">
<div style="direction: ltr; font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
Archie,<br>
<br>
I should've been more specific—Condition-as-implemented-by-ReentrantLock (in fair mode) provides stronger (for some definition of stronger) semantics that the Condition interface specifies.</div>
<div style="direction: ltr; font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div style="direction: ltr; font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
Since it's related, I've recently integrated a hardening of AQS and AQLS reacquisition logic in await().</div>
<div style="direction: ltr; font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div style="direction: ltr; font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
Given what you presented earlier about the detection of "producer parked" it's likely that the conclusion is that ABQ works as expected.</div>
<div style="direction: ltr; font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div id="x_m_-5543794601931186038Signature" 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="x_m_-5543794601931186038appendonsend" style="color: inherit;"></div>
<hr style="direction: ltr; display: inline-block; width: 98%;">
<div id="x_m_-5543794601931186038divRplyFwdMsg" dir="ltr" style="color: inherit;">
<span style="font-family: Calibri, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);"><b>From:</b> Archie Cobbs <<a href="mailto:archie.cobbs@gmail.com" id="OWA3fbfe2fe-65f1-e66c-e8aa-2429e9794703" class="OWAAutoLink">archie.cobbs@gmail.com</a>><br>
<b>Sent:</b> Thursday, 5 September 2024 21:23<br>
<b>To:</b> Viktor Klang <<a href="mailto:viktor.klang@oracle.com" id="OWAf3dcb66f-f138-7450-0aec-3e2741a3e857" class="OWAAutoLink">viktor.klang@oracle.com</a>><br>
<b>Cc:</b> 김민주 <<a href="mailto:miiiinju00@gmail.com" id="OWAbda2b37a-d87b-61d6-c5e9-d037ba0d6daf" class="OWAAutoLink">miiiinju00@gmail.com</a>>; Daniel FUCHS <<a href="mailto:daniel.fuchs@oracle.com" id="OWA40fe0607-bd41-715b-2c9b-5f92298d238a" class="OWAAutoLink">daniel.fuchs@oracle.com</a>>;
<a href="mailto:core-libs-dev@openjdk.org" id="OWA9a667119-549b-705e-1c0f-6ec584973ad6" class="OWAAutoLink">
core-libs-dev@openjdk.org</a> <<a href="mailto:core-libs-dev@openjdk.org" id="OWA3682009c-2d66-95c9-decd-69e834093fd2" class="OWAAutoLink">core-libs-dev@openjdk.org</a>><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</span>
<div> </div>
</div>
<div style="direction: ltr;">Apologies in advance if I'm misunderstanding anything...</div>
<div style="direction: ltr;"><br>
</div>
<div style="direction: ltr;">On Thu, Sep 5, 2024 at 2:05 PM Viktor Klang <<a href="mailto:viktor.klang@oracle.com" id="OWA03b3fe36-b05a-4e33-f3e7-051aa886745f" class="OWAAutoLink">viktor.klang@oracle.com</a>> wrote:</div>
<blockquote style="margin: 0px 0px 0px 0.8ex; padding-left: 1ex; border-left: 1px solid rgb(204, 204, 204);">
<div style="direction: ltr;"> Thread state polling aside, for as long as Condition::await() is allowed to spuriously wake, FIFO just cannot be "guaranteed".</div>
</blockquote>
<div style="direction: ltr;"> </div>
<div style="direction: ltr;">What about this statement in the Javadoc for ReentrantLock.newCondition():</div>
<div style="direction: ltr;"><br>
</div>
<blockquote style="margin: 0px 0px 0px 0.8ex; padding-left: 1ex; border-left: 1px solid rgb(204, 204, 204);">
<div style="direction: ltr;">The ordering of lock reacquisition for threads returning from waiting methods is the same as for threads initially acquiring the lock, which is in the default case not specified, but for
<i>fair</i> locks favors those threads that have been waiting the longest.</div>
</blockquote>
<div style="direction: ltr;"><br>
</div>
<div style="direction: ltr;">So what you're saying is that a spurious wakeup on a Condition is not the same thing as a spurious signal() on a Condition; if it were, then the above statement would apply and FIFO ordering would be preserved.</div>
<div style="direction: ltr;"><br>
</div>
<div style="direction: ltr;">Of course, a spurious wakeup would not find the condition being waited on satisfied unless there was a big coincidence. So an ordering violation that actually mattered should be exceedingly rare.</div>
<div style="direction: ltr;"><br>
</div>
<div style="direction: ltr;">Anyway, this does seem to be a glitch in how things are supposed to work. That is: there can be no guaranteed ordering for Condition waiters when there can be spurious wakeups.</div>
<div style="direction: ltr;"><br>
</div>
<div style="direction: ltr;">Maybe this corner case should be documented. Or better yet, fix the bug by requiring Condition to "filter out" spurious wakeups if preserving FIFO ordering (it should be possible).</div>
<div style="direction: ltr;"><br>
</div>
<div style="direction: ltr;">-Archie</div>
<div style="direction: ltr;"><br>
--</div>
<div style="direction: ltr;">Archie L. Cobbs</div>
</blockquote>
</body>
</html>