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

[김민주]

Hi Daniel

I hope you're doing well. I wanted to follow up on a previous message I sent. Since this is my first time contributing to OpenJDK, I realized I might not have communicated the issue clearly, and I wanted to provide more context about the situation I encountered.

In the put() method of LinkedBlockingQueue, when the queue reaches its capacity, threads block on notFull.await(). For example, if threads T1, T2, T3, and T4 call put() in sequence when the queue is full, they all wait in the notFull.await() state in sequence as expected.

Normally, when space becomes available in the queue, I would expect the thread that called put() first (T1) to be signaled, allowing it to proceed in FIFO order. However, the issue arises when a new thread, T5, tries to put() at the same time T1 is signaled to proceed.

In this scenario, both T1 (which was waiting) and T5 (which just arrived) compete for the ReentrantLock. This competition can lead to T5 acquiring the lock first, allowing it to perform the put() operation before T1, despite T1 having waited the longest. As a result, T1 experiences "starvation," and the order becomes T2, T3, T4, and finally T1, which breaks the expected FIFO order.

In the test code I provided, if you remove the capacity limit of the queue, the mentioned issue does not occur, and the test passes successfully. You can confirm this by using the new LinkedBlockingQueue<>() constructor without any capacity-related options.

In a previous discussion, there was a suggestion to synchronize the sequenceNumber and queue.put() using an external lock. However, my intention was to simulate a scenario where T1, T2, T3, and T4 all block in the await() state after sequentially attempting put(). I wanted to observe how they behave when a new thread (T5) arrives and competes for the lock.

If I use an external lock, T1 will block in the await() state, but T2, T3, and T4 will be waiting for the external lock rather than entering the await() state in put(). This would prevent me from simulating the specific behavior I’m trying to test.

I’d appreciate your thoughts on whether this behavior (where a newly arriving thread can overtake a waiting thread) is expected or if it’s worth further investigation. As this is my first attempt to contribute to OpenJDK, I’m eager to learn from the process and would love to help resolve the issue if necessary.

Also, since English is not my first language, I hope my previous emails didn’t come across as rude or unclear. If they did, I sincerely apologize, as it was never my intention to be disrespectful. I’m still learning how to communicate effectively in this space, and I appreciate your understanding and patience.

Thank you for your time and guidance.

Best regards,

Kim Minju


> 2024. 9. 4. 오후 9:35, Daniel Fuchs <daniel.fuchs at oracle.com> 작성:
> 
> Hi Kim,
> 
> On 04/09/2024 12:50, 김민주 wrote:
>> In the original approach, I intended for each thread to call |put|, confirm that it has entered the waiting state, and then allow the next thread to put the next sequence value and also enter the waiting state. This approach was designed to simulate a situation where the queue is already full and each thread has to wait in line for space to become available.
> 
> The problem with that is that you would still need to ensure that each
> thread calls `put` in order, and for that, you would still need
> external synchronization.
> 
> I am not an expert in java.util.concurrent, but it feels like the
> fix you had in mind would not buy you much.
> 
> best regards,
> 
> -- daniel
> 

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