Вам в какую очередь?

В пакете java.util.concurrent доступно 7 очередей. Самые простые из них это

🔸 ArrayBlockingQueue
🔸 LinkedBlockingQueue
🔸 ConcurrentLinkedQueue

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

Часть 1: внутреннее устройство

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

Что это даёт? По сути - ничего.
Вспомним 2 списка с похожим строением - ArrayList и LinkedList. В первом легко искать элемент по индексу, во втором - вставлять и удалять элемент из середины списка.
Для очереди это не важно, потому что нас интересует только работа с началом и концом очереди.

Часть 2: механизм синхронизации

А здесь уже интереснее:
🔹 ArrayBQ использует один ReentrantLock
🔹 LinkedBQ - два ReentrantLock: один для начала очереди, другой - для конца
🔹 ConcurrentLQ использует CAS операции для обновления крайних элементов

Давайте попарно сравним их между собой

▪️ArrayBQ и LinkedBQ

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

Если размер колеблется около нуля, то поддерживать два лока слишком затратно, гораздо проще работать с одним локом на всю очередь. Это вариант ArrayBQ.

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

▪️LinkedBQ и ConcurrentLQ

Допустим, наша очередь никогда не пустует. Что лучше - два ReentrantLock или две CAS операции?

Здесь разница в методах, которые нам нужны.

CAS операции обновляют только сами элементы - начало и конец очереди.

ReentrantLock ограждает критическую секцию, внутри которой
▫️ Проверяется текущий размер и сама возможность добавить в очередь
▫️ Обновляется начало или конец очереди
▫️ Уведомляются потоки, которые, возможно ждут на другом конце очереди

Добавление и удаление в ConcurrentLQ происходит очень быстро. Если нужны дополнительные опции - фиксированный размер, блокирующие вызовы, то лучше подойдёт LinkedBQ.

Поэтому критерий выбора очереди №2: необходимые методы и ограничения на размер