Hi Kim,
Thanks for the details.
So to summarize:
- Kim is saying that "Interpretation B" is how it actually works.
- Viktor is saying that "Interpretation A" is how it actually works.
Do I have that right?
-Archie
P.S. Viktor: my apologies for misspelling your name before
On Sat, Sep 7, 2024 at 8:04 PM 김민주 <miiiinj...@gmail.com> wrote:
> Hi Arhice,
>
>
> First of all, I want to apologize if I may not have explained things
> clearly since English is not my first language. I’m really sorry about that.
>
>
> Even so, I deeply appreciate your response and taking the time to reply.
>
>
> First, I would like to confirm whether my understanding is correct.
>
> From what I know, ReentrantLock is based on AQS, and internally, threads
> are queued by being linked as Node.
>
> When ReentrantLock.newCondition is called, a ConditionObject is created.
> When Condition::await is called, the thread waits based on a ConditionNode,
> and the AQS head is replaced with AQS::signalNext, allowing the lock to
> be released. At this point, I understand that the node disappears from the
> AQS queue and starts waiting within the ConditionNode of the
> ConditionObject.
>
> As a result, I understand that the waiting places for ReentrantLock and
> Condition are different.
>
> To summarize, when Condition::await() is called, the node that was
> previously waiting in AQS receives the lock, disappears from the AQS queue,
> and starts waiting within the ConditionNode of the ConditionObject.
>
> Additionally, from what I understand, in Condition::doSignal, the first
> ConditionNode is removed, and then AQS::enqueue adds it to the tail of AQS
> .
>
> public class ConditionObject implements Condition, java.io.Serializable {
>
> private void doSignal(ConditionNode first, boolean all) {
> while (first != null) {
> ConditionNode next = first.nextWaiter;
> if ((firstWaiter = next) == null)
> lastWaiter = null;
> if ((first.getAndUnsetStatus(COND) & COND) != 0) {
> enqueue(first);
> if (!all)
> break;
> }
> first = next;
> }
> }
>
>
> When enqueue is called:
>
> public abstract class AbstractQueuedSynchronizer
> extends AbstractOwnableSynchronizer
>
> /*
> * Tail of the wait queue. After initialization, modified only via
> casTail.
> */
> private transient volatile Node tail;
>
> final void enqueue(Node node) {
> if (node != null) {
> for (;;) {
> Node t = tail;
> node.setPrevRelaxed(t); // avoid unnecessary fence
> if (t == null) // initialize
> tryInitializeHead();
> else if (casTail(t, node)) {
> t.next = node;
> if (t.status < 0) // wake up to clean link
> LockSupport.unpark(node.waiter);
> break;
> }
> }
> }
> }
>
>
> From my understanding, this attaches the node to the tail of AQS.
>
> To elaborate further on the situation:
>
> 1.
>
> Threads T1 to T10 are waiting on Condition::await() because the queue
> is full.
>
> (At this point, T1 to T10 are linked through ConditionNode.) [The AQS queue
> is empty, while ConditionNode holds T1 to T10.]
> 2.
>
> T11 calls take() and holds the lock via lock.lockInterruptibly().
>
> (Since no threads are waiting in the AQS queue, T11 will acquire the
> lock immediately.)
>
> [Now, AQS holds T11 at its head, and ConditionNode holds T1 to T10.]
> 3.
>
> T12 calls queue.put() and enters the wait queue for
> lock.lockInterruptibly(). (Since T11 is holding the lock with take(),
> T12 will be queued behind it in AQS.)
>
> [Now, AQS holds T11 and T12, while ConditionNode holds T1 to T10.]
> 4.
>
> T11 reduces the count and sends a signal, then releases the lock.
> 5.
>
> T1 receives the signal and moves to the lock queue. Since ReentrantLock is
> in fair mode,
>
> (When T11 sends the signal, T1, the first thread linked in
> ConditionNode, will be enqueued via AQS::enqueue. Now, AQS holds T11,
> T12, and T1, while ConditionNode holds T2 to T10.)
> 6.
>
> T11 releases the lock and wakes up T12.
>
> [Now, AQS holds T12 and T1, while ConditionNode holds T2 to T10.]
> 7.
>
> T12 acquires the lock and proceeds to enqueue in ArrayBlockingQueue without
> being blocked by while(count==length).
> 8.
>
> T12 releases the lock, and the next node in AQS is unparked.
>
> [Now, AQS holds T1, while ConditionNode holds T2 to T10.]
> 9.
>
> T1, having reacquired the lock after Condition::await(), fails to exit
> the while loop and waits again.
>
> [Now, ConditionNode holds T1 and T2 to T10.]
>
>
> This is how I currently understand the situation.
>
> If there are any mistakes in my understanding, I would greatly appreciate
> your clarification.
>
> Best Regards,
>
> Kim Minju
>
> 2024. 9. 8. 오전 3:34, Archie Cobbs <archie.co...@gmail.com> 작성:
>
> Hi Kim,
>
> On Sat, Sep 7, 2024 at 10:36 AM 김민주 <miiiinj...@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
>
>
>
--
Archie L. Cobbs
