Какую реализацию параллельной очереди мне следует использовать в Java?

В основном разница между ними заключается в характеристиках производительности и поведении блокировки.

Если взять самое простое, ArrayBlockingQueue - это очередь фиксированного размера. Поэтому, если вы установите размер 10 и попытаетесь вставить 11-й элемент, оператор вставки будет заблокирован до тех пор, пока другой поток не удалит элемент. Проблема справедливости заключается в том, что происходит, если несколько потоков пытаются одновременно вставлять и удалять (другими словами, в период, когда Очередь была заблокирована). Алгоритм равноправия гарантирует, что первый поток, который запрашивает, будет первым потоком, который получит. В противном случае данный поток может ждать дольше, чем другие потоки, вызывая непредсказуемое поведение (иногда одному потоку требуется всего несколько секунд, потому что другие потоки, которые были запущены позже, обрабатывались первыми). Компромисс заключается в том, что для управления справедливостью требуются накладные расходы, что снижает пропускную способность.

Наиболее важное различие между LinkedBlockingQueue и ConcurrentLinkedQueue заключается в том, что если вы запрашиваете элемент из LinkedBlockingQueue, а очередь пуста, ваш поток будет ждать, пока там что-то не будет. ConcurrentLinkedQueue сразу же вернется с поведением пустой очереди.

Какой из них зависит от того, нужна ли вам блокировка. Когда у вас много производителей и один потребитель, это звучит так. С другой стороны, если у вас много потребителей и только один производитель, вам может не понадобиться блокирующее поведение, и вы можете просто попросить потребителей проверить, пуста ли очередь, и продолжить, если это так.

ConcurrentLinkedQueue означает, что блокировки не выполняются ( т.е. нет синхронизированного (этого) или Lock.lock звонков). Во время модификаций он будет использовать операцию CAS - Сравнить и поменять местами, чтобы увидеть, Узел / tail остается таким же, как и при запуске. Если это так, операция завершается успешно. Если узел голова / хвост отличается, он будет вращаться и повторить попытку.

LinkedBlockingQueue будет заблокирован до того, как любой модификация. Таким образом, ваши звонки с предложениями будут блокироваться, пока они не получат блокировку. Вы можете использовать перегрузку предложения, которая требует TimeUnit, чтобы сказать, что вы готовы подождать только X количество времени, прежде чем отказаться от добавления (обычно хорошо для очередей типов сообщений, где сообщение устарело после X количества миллисекунд).

Справедливость означает, что реализация Lock будет поддерживать порядок потоков. Это означает, что если поток A входит, а затем входит поток B, поток A первым получит блокировку. Без всякой справедливости, на самом деле не определено, что происходит. Скорее всего, это будет следующий запланированный поток.

Что касается того, какой из них использовать, это зависит от обстоятельств. Я обычно использую ConcurrentLinkedQueue, потому что Время, необходимое моим продюсерам, чтобы поставить работу в очередь, разнообразно. У меня не так много продюсеров, которые работают одновременно. Но со стороны потребителя сложнее, потому что опрос не переходит в хорошее состояние сна. Вы должны сами справиться с этим.

В заголовке вашего вопроса упоминаются очереди с блокировкой. Однако ConcurrentLinkedQueue не очередь блокировки.

BlockingQueue - это ArrayBlockingQueue, DelayQueue , LinkedBlockingDeque, LinkedBlockingQueue, PriorityBlockingQueue и SynchronousQueue.

Некоторые из них явно не подходят для ваших целей (DelayQueue, PriorityBlockingQueue и SynchronousQueue). LinkedBlockingQueue и LinkedBlockingDeque идентичны, за исключением того, что последняя представляет собой двустороннюю очередь (она реализует интерфейс Deque).

Поскольку ArrayBlockingQueue полезен только в том случае, если вы хотите ограничить количество элементов, я бы придерживался LinkedBlockingQueue.

ArrayBlockingQueue имеет меньший объем памяти, он может повторно использовать узел элемента, в отличие от LinkedBlockingQueue, который должен создавать объект LinkedBlockingQueue $ Node для каждой новой вставки.

1. SynchronousQueue (Взято из другого вопроса)

SynchronousQueue - это скорее передача обслуживания, тогда как LinkedBlockingQueue разрешает только один элемент. Разница в том, что вызов put() к SynchronousQueue не вернется, пока не будет соответствующий вызов take(), но с LinkedBlockingQueue размером 1 вызов put() (в пустую очередь) вернется немедленно. По сути, это реализация BlockingQueue для случаев, когда вам действительно не нужна очередь (вы не хотите поддерживать какие-либо ожидающие данные).

2. LinkedBlockingQueue (LinkedList Реализация, но не совсем JDK Реализация LinkedList Он использует статический внутренний класс Node для поддержания связей между элементами)

Конструктор для LinkedBlockingQueue

public LinkedBlockingQueue(int capacity) 
{
        if (capacity < = 0) throw new IllegalArgumentException();
        this.capacity = capacity;
        last = head = new Node< E >(null);   // Maintains a underlying linkedlist. ( Use when size is not known )
}

Класс узла, используемый для поддержки ссылок

static class Node<E> {
    E item;
    Node<E> next;
    Node(E x) { item = x; }
}

3. ArrayBlockingQueue (реализация массива)

Конструктор для ArrayBlockingQueue

public ArrayBlockingQueue(int capacity, boolean fair) 
{
            if (capacity < = 0)
                throw new IllegalArgumentException();
            this.items = new Object[capacity]; // Maintains a underlying array
            lock = new ReentrantLock(fair);
            notEmpty = lock.newCondition();
            notFull =  lock.newCondition();
}

IMHO Самая большая разница между ArrayBlockingQueue и LinkedBlockingQueue очевидна из конструктора, у которого есть базовая структура данных Array и другой связанный список.

ArrayBlockingQueue использует алгоритм двойных условий с одной блокировкой и LinkedBlockingQueue - вариант алгоритма "очереди с двумя блокировками" и имеет 2 блокировки 2 условия (takeLock, putLock)

ConcurrentLinkedQueue не блокируется, а LinkedBlockingQueue - нет. Каждый раз, когда вы вызываете LinkedBlockingQueue.put () или LinkedBlockingQueue.take (), вам нужно сначала получить блокировку. Другими словами, у LinkedBlockingQueue плохой параллелизм. Если вам важна производительность, попробуйте ConcurrentLinkedQueue + LockSupport.