<div dir="ltr"><p>Hello core-libs-dev team,</p><p>My name is Kim Minju, and I have investigated a potential issue with both <code>ArrayBlockingQueue</code> and <code>LinkedBlockingQueue</code> implementations when handling high contention scenarios. While I am not entirely certain whether this is a bug or expected behavior, </p><p>I would like to share my findings and seek your input. If this is indeed an issue, I would also like to propose a fix and work on implementing it, with the community's guidance and support.</p><h3>Problem Description:</h3><p>When the queue is full, and both <code>put()</code> operations and item consumption occur simultaneously, threads that have been waiting to insert elements using <code>notFull.await()</code> are expected to be unblocked in a strict FIFO order. However, in my tests, when space becomes available, both the unblocked threads and newly arriving <code>put()</code> requests compete for the lock, potentially leading to race conditions. This can result in newer threads acquiring the lock first and inserting items before previously blocked threads, which seems to violate FIFO order.</p><p>In <code>ArrayBlockingQueue</code>, while a fair mode is available, it does not seem to fully guarantee strict FIFO order under high contention. Additionally, <code>LinkedBlockingQueue</code> lacks any fair mode, which seems to exacerbate the issue, allowing newer threads to preempt waiting threads more easily.</p><p>I am unsure if this behavior is by design or if it can be improved. I would greatly appreciate any feedback from the community regarding whether this is an intended behavior or a potential issue.</p><h3>Steps to Reproduce:</h3><p>Here is a test case that demonstrates how FIFO order can be violated when threads blocked on <code>put()</code> calls are unblocked and compete with new <code>put()</code> requests for lock acquisition:</p><pre><code class="gmail-language-java">import static org.junit.jupiter.api.Assertions.fail;

import java.lang.Thread.State;
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;
import java.util.concurrent.atomic.AtomicInteger;
import org.junit.jupiter.api.Test;

class BlockingQueueFIFOTest {

    @Test
    void testFIFOOrder() throws InterruptedException {
        final int QUEUE_CAPACITY = 10;
        AtomicInteger sequenceGenerator = new AtomicInteger(0);

        // Create a blocking queue with a fixed capacity
        BlockingQueue<Integer> queue = new LinkedBlockingQueue<>(QUEUE_CAPACITY);
//        queue = new ArrayBlockingQueue<>(QUEUE_CAPACITY, true);

        // Prefill the queue to its capacity
        // This is crucial for the test as it ensures subsequent put operations will block
        // By filling the queue first, we guarantee that following put operations
        // will be queued in the exact order they are called (10, 11, 12, ...)
        // This setup creates a controlled environment for testing FIFO behavior
         for(int i = 0;i<QUEUE_CAPACITY;i++) {
            queue.put(sequenceGenerator.getAndIncrement());
        }

        final int PRODUCER_COUNT = 100;
        final int PRODUCER_COUNT_WHEN_CONSUMING = 1000;

        // Create multiple producer threads
        // Each thread attempts to put a single item into the already full queue
        // Since the queue is full, these put operations will block in the order they are called
        // This configuration ensures items enter the queue's waiting list in a predictable sequence (10, 11, 12, ...)
        // allowing us to verify if they are later consumed in the same order
        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 BLOCKED state
            // This ensures that the thread is waiting on the full queue
            while (thread.getState() == State.RUNNABLE || thread.getState() == State.NEW);
        }

        List<Integer> result = new ArrayList<>();

        // This simulates a real-world high-contention scenario on a full queue
        // When space becomes available, it's not just waiting threads that compete
        // New put requests arrive simultaneously, adding to the contention
        // This tests if FIFO order is maintained under intense pressure from both
        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
                while (thread.getState() == State.RUNNABLE || thread.getState() == State.NEW);
            }
        });
        producingWhenConsumingThread.start();

        for (int i = 0; i < PRODUCER_COUNT + QUEUE_CAPACITY + PRODUCER_COUNT_WHEN_CONSUMING ; i++) {
            Integer item = queue.take();
            result.add(item);
        }
        System.out.println("result = " + result);

        for (int i = 0; i < result.size() - 1; i++) {
            if (result.get(i) > result.get(i + 1)) {
                fail("FIFO order violated at index " + i + ": " + result.get(i) + " > " + result.get(i + 1));
            }
        }
    }
}

</code></pre><h3>Expected Behavior:</h3><p>When the queue is full and multiple threads are blocked on <code>put()</code> operations (using <code>notFull.await()</code>), these threads should be unblocked in the order they were blocked, with newly arriving <code>put()</code> requests waiting until the blocked threads have inserted their elements. The blocked threads should have priority over new threads, and lock acquisition should respect this order.</p><h3>Actual Behavior (Observed in Testing):</h3><p>Under high contention, both <code>ArrayBlockingQueue</code> and <code>LinkedBlockingQueue</code> seem to violate FIFO order due to lock contention between threads that were blocked on <code>notFull.await()</code> and new <code>put()</code> requests. Newly arriving threads can sometimes preempt previously blocked threads, resulting in newer items being inserted ahead of older ones.</p><p>Again, I am uncertain if this is an expected consequence of the current implementation or if there is room for improvement.</p><h3>Proposed Solution (If This is a Problem):</h3><p>If this behavior is not intended, I propose modifying both <code>ArrayBlockingQueue</code> and <code>LinkedBlockingQueue</code> so that if there are threads waiting on <code>notFull.await()</code>, newly arriving <code>put()</code> requests would be forced to wait behind the blocked threads. This could help ensure that previously blocked threads insert their items in FIFO order, minimizing FIFO violations due to lock contention.</p><p>Additionally, I suggest adding an option for <strong>fair mode</strong> in <code>LinkedBlockingQueue</code>, similar to what is available in <code>ArrayBlockingQueue</code>. This would further ensure that waiting threads are processed in a predictable and fair manner, preventing newer threads from preempting waiting threads and thus maintaining strict FIFO order.</p><h3>Performance Considerations:</h3><p>I understand that implementing stricter FIFO guarantees may impact overall throughput, especially in high-contention scenarios. To address this, I suggest making these changes configurable, allowing users to choose between strict FIFO ordering and potentially higher throughput, depending on their workload needs.</p><p>If the community deems this change valuable, I am willing to conduct thorough performance testing to quantify the impact on throughput and latency under various workloads, and I could create JMH benchmarks to measure the performance differences between the current and proposed implementations.</p><h3>Request for Sponsorship and Feedback:</h3><p>As I am not yet an Author in the OpenJDK project, I am seeking guidance and potential sponsorship to address this issue, should it be deemed necessary.</p><ul>
<li>I would appreciate the community's thoughts on whether this behavior is expected or a potential issue worth addressing.</li>
<li>If the community agrees that this is a significant issue, I welcome guidance on the best approach to tackle it within the current Java implementation.</li>
<li>I am looking for a sponsor who might be interested in supporting this effort. With sponsorship, I would be glad to:
<ul>
<li>Conduct a deeper analysis of the problem</li>
<li>Create a prototype implementation for review</li>
<li>Prepare and submit a formal patch</li>
<li>Participate in the review process and make necessary adjustments</li>
</ul>
</li>
</ul><p>Thank you for your time and consideration. I look forward to your feedback and the opportunity to contribute to the improvement of Java's concurrent collections.</p><p>Best regards,</p><p>Kim Minju</p><p>

























</p><p><a href="mailto:miiiinju00@gmail.com">miiiinju00@gmail.com</a></p></div>