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

Question

Из JavaDocs:

• A ConcurrentLinkedQueue является подходящим выбором, когда многие потоки будут совместно использовать доступ к общей коллекции. Эта очередь не разрешает нулевые элементы.
• ArrayBlockingQueue - это классический «ограниченный буфер», в котором массив фиксированного размера содержит элементы, вставленные производителями и извлеченные потребителями. Этот класс поддерживает необязательную политику справедливости для упорядочивания ожидающих потоков производителей и потребителей
• LinkedBlockingQueue обычно имеет более высокую пропускную способность, чем очереди на основе массива, но менее предсказуемую производительность в большинстве одновременных приложений.

У меня есть 2 сценария, один требует очереди для поддержки многих производителей (потоков, использующих ее) с одним потребителем, а другой - наоборот.

Я не понимаю, какую реализацию использовать. Может кто-нибудь объяснить, в чем различия?

Кроме того, что такое «необязательная политика справедливости» в ArrayBlockingQueue?

Answer 1

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

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

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

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

Answer 2

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

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

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

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

Answer 3

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

BlockingQueue с ArrayBlockingQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, PriorityBlockingQueue и SynchronousQueue.

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

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

Answer 4

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

Answer 5

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();
}

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

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

Answer 6

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