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

[김민주]

Dear Daniel,

Thank you for your insightful feedback on my approach. After carefully considering your points, I realize that I made a significant mistake in my initial implementation. I sincerely appreciate you bringing this to my attention.

You were absolutely correct in pointing out the potential issues with ensuring the order of put calls and the need for external synchronization. Upon review, I noticed that my original code was erroneously checking for NEW or RUNNABLE states, which, as you rightly suggested, doesn't guarantee that the thread has entered a waiting state. This was a clear oversight on my part.

Moreover, I now understand that using a while loop to check the thread state was fundamentally flawed. The awaitmethod is internally encapsulated within the BlockingQueue implementation, meaning there's no way to guarantee from outside the class that await has actually been called.

To address this error, I've modified the code as follows:

for (int i = 0; i < PRODUCER_COUNT; i++) {
            Thread thread = new Thread(() -> {
                try {
                    queue.put(sequenceGenerator.getAndIncrement());
                } catch (InterruptedException e) {
                    // ignore
                }

            });
            thread.start();
            // Wait for the producer thread to enter WAITING state
            // This ensures that the thread is waiting on the full queue
            while (thread.getState() != State.WAITING);
        }

Thread producingWhenConsumingThread = new Thread(() -> {
            for (int i = 0; i < PRODUCER_COUNT_WHEN_CONSUMING; i++) {
                Thread thread = new Thread(() -> {
                    try {
                        queue.put(sequenceGenerator.getAndIncrement());
                    } catch (InterruptedException e) {
                        // ignore
                    }

                });
                thread.start();

                // Wait for the producer thread to enter BLOCKED state
                // This ensures that the thread is waiting on the full queue

                // Terminated: queue has enough space to put the item, then the thread can terminate immediately
                while (thread.getState() != State.WAITING && thread.getState() != State.TERMINATED);

            }
        });
(Terminated: queue has enough space to put the item, then the thread can terminate immediately)

While this change ensures we're verifying that each thread has either entered a waiting state or completed its operation, I acknowledge that it still doesn't provide a perfect solution due to the encapsulation of the await method. This approach should more accurately simulate the scenario of multiple threads competing to put items into a full queue, without requiring external synchronization, but it has its limitations.

I believe this modification addresses some of the concerns you raised while still attempting to maintain the original intent of the test.

Your expertise and the time you've taken to review my work are greatly appreciated. Your feedback has been invaluable in helping me correct this mistake, improve the accuracy of this test, and most importantly, understand the limitations of trying to observe internal queue behaviors from outside.

I'm very interested in your thoughts on this updated approach and any suggestions you might have for better testing strategies given the encapsulation challenge. If you see any further areas for improvement or have additional insights, I'd be very eager to hear them.

Thank you once again for your help and for fostering this productive discussion. Your input has been crucial in refining my understanding and implementation, and in highlighting important aspects of concurrent programming that I had overlooked.



P.S. After further reflection, I wanted to add a note about the challenge of external synchronization in this context. My primary goal was to implement external synchronization as much as possible. However, due to the nature of the `await` operation, which is atomic and encapsulated within the `BlockingQueue` implementation, I found myself limited in options to verify that a thread had actually executed the `put` operation and entered a waiting state.

The while loop checking for the WAITING state seemed to be the only viable approach I could think of to indirectly confirm that a thread had called `put` and was now waiting. I acknowledge this is still an imperfect solution, as it doesn't guarantee the exact moment the thread entered the waiting state, nor does it provide true external synchronization.

I'm particularly interested in your thoughts on how we might better approach this challenge. Are there alternative methods to verify the atomic execution of `put` and the subsequent waiting state, while still maintaining as much external control as possible? Your expertise in this area would be greatly appreciated.

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/20240904/4f1d75f1/attachment.htm>