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

[김민주]

*Hi Archie,*

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 notFull.await() 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!





------------------------------

*Hi Viktor,*

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 ReentrantLock, threads waiting on a
Condition are placed back in the queue without acquiring the lock, or if
the signaling thread can now immediately acquire the lock after being
signaled.

Initially, my concern was that a thread receiving a signal might still face
starvation if another thread calls put() and acquires the lock before the
signaled thread can do so. Here's an example scenario:

   1. The queue is full, and T2 is executing put() and is waiting in
   Condition.await().
   2. T1 calls queue.take(), removes an item from the queue, and is about
   to send a signal()
   3. T3 is about to call put() and is just before lock.lockInterruptibly().
   4. T1 decreases the count and sends a signal(), indicating that space is
   available in the queue.
   5. T3 acquires the lock via lock.lockInterruptibly(), successfully
   enqueues an item because the count condition is satisfied, and releases the
   lock.
   6. T2 receives the signal and wakes up, but since T3 already enqueued an
   item, the count has increased, and T2 must wait again in await().

It seems to me that this scenario could occur regardless of whether
ReentrantLock 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?
------------------------------

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.

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?


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.



Best regards,
Kim Minju



2024년 9월 6일 (금) 오전 4:52, Viktor Klang <viktor.klang at oracle.com>님이 작성:

> 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>
> 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/20240906/2575eea5/attachment-0001.htm>