[External] : Re: [POTENTIAL BUG] Potential FIFO violation in BlockingQueue under high contention and suggestion for fair mode in ArrayBlockingQueue and LinkedBlockingQueue

[Viktor Klang]

Archie,

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.

Since it's related, I've recently integrated a hardening of AQS and AQLS reacquisition logic in await().

Given what you presented earlier about the detection of "producer parked" it's likely that the conclusion is that ABQ works as expected.

Cheers,
√


Viktor Klang
Software Architect, Java Platform Group
Oracle
________________________________
From: Archie Cobbs <archie.cobbs at gmail.com>
Sent: Thursday, 5 September 2024 21:23
To: Viktor Klang <viktor.klang at oracle.com>
Cc: 김민주 <miiiinju00 at gmail.com>; Daniel FUCHS <daniel.fuchs at oracle.com>; core-libs-dev at openjdk.org <core-libs-dev at openjdk.org>
Subject: Re: [External] : Re: [POTENTIAL BUG] Potential FIFO violation in BlockingQueue under high contention and suggestion for fair mode in ArrayBlockingQueue and LinkedBlockingQueue

Apologies in advance if I'm misunderstanding anything...

On Thu, Sep 5, 2024 at 2:05 PM Viktor Klang <viktor.klang at oracle.com<mailto:viktor.klang at oracle.com>> wrote:
 Thread state polling aside, for as long as Condition::await() is allowed to spuriously wake, FIFO just cannot be "guaranteed".

What about this statement in the Javadoc for ReentrantLock.newCondition():

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 fair locks favors those threads that have been waiting the longest.

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.

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.

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.

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).

-Archie

--
Archie L. Cobbs
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.openjdk.org/pipermail/core-libs-dev/attachments/20240905/f49b70ad/attachment-0001.htm>