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

[Archie Cobbs]

Hi Kim,

On Sat, Sep 7, 2024 at 10:36 AM 김민주 <miiiinju00 at gmail.com> wrote:

> Here's a clearer outline of the scenario:
>
>    - Threads T1 to T10 are waiting on Condition::await() because the
>    queue is full.
>    - T11 calls take() and holds the lock via lock.lockInterruptibly().
>    - T12 calls queue.put() and enters the wait queue for
>    lock.lockInterruptibly(). (As I understand, the wait queue for
>    ReentrantLock and Condition are separate.)
>    - T11 reduces the count and sends a signal, then releases the lock.
>    - T1 receives the signal and moves to the lock queue. Since the
>    ReentrantLock is in fair mode, T12 (which was already waiting) gets
>    priority, and T1 will acquire the lock later.
>    - T12 acquires the lock and successfully enqueues.
>
> From one reading of the Javadoc, your step #5 ("T12 gets priority") is not
supposed to happen that way. Instead, one of T1 through T10 should be
guaranteed to acquire the lock.

Here it is again (from 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.


But part of the problem here is that this documentation is ambiguous.

The ambiguity is: are ALL threads trying to acquire the lock, whether on an
initial attempt or after a condition wakeup, ordered for fairness together
in one big pool? → In this case step #5 can't happen. Call this
Interpretation A.

Or is this merely saying that threads waiting on a condition reacquire the
lock based on when they started waiting on the condition, but there are no
ordering guarantees between those threads and any other unrelated threads
trying to acquire the lock? → In this case step #5 can happen. Call this
Interpretation B.

So I think we first need to clarify which interpretation is correct here, A
or B.

On that point, Victor said this:

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


So it sounds like Victor is confirming interpretation A. Victor do you
agree?

If so, then it seems like we need to do two things:

1. File a Jira ticket to clarify the Javadoc, e.g. to say something like
this:

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. *In the latter case, the
> ordering consideration includes all threads attempting to acquire the lock,
> regardless of whether or not they were previously blocked on the condition.*
>

2. Understand why Kim's updated test case is still failing (it must be
either a bug in the test or a bug in ArrayBlockingQueue).

-Archie

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