Реализации Java Queue, какой?

От Javadoc:

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

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

Я не понимаю, следует ли использовать ConcurrentLikedQueue или другие (реализация array или linkedList). Wherent 'все эти реализации должны быть параллельными? Я имею в виду, может кто-нибудь объяснить мне, в чем разница между ConcurrentLikedQueue и LinkedBlockingQueue?

Кроме того, что такое факультативная политика конфиденциальности в ArrayBlockingQueue, пожалуйста?

Ответ 1

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

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

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

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

Ответ 2

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

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

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

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

Ответ 3

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

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

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

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

Ответ 4

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

Ответ 5

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

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

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 и другие связанныеList.

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

Ответ 6

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