«1. Обзор

В этом руководстве мы рассмотрим некоторые основные реализации параллельных очередей в Java. Общие сведения об очередях см. в нашей статье «Руководство по интерфейсу очередей Java».

2. Очереди

В многопоточных приложениях очереди должны обрабатывать несколько параллельных сценариев производителей-потребителей. Правильный выбор параллельной очереди может иметь решающее значение для достижения хорошей производительности наших алгоритмов.

Во-первых, мы увидим некоторые важные различия между блокирующей и неблокирующей очередью. Затем мы рассмотрим некоторые реализации и лучшие практики.

2. Блокирующая и неблокирующая очередь

BlockingQueue предлагает простой потокобезопасный механизм. В этой очереди потоки должны ожидать доступности очереди. Производители будут ждать доступной мощности, прежде чем добавлять элементы, а потребители будут ждать, пока очередь не опустеет. В этих случаях неблокирующая очередь либо выдаст исключение, либо вернет специальное значение, например null или false.

Для реализации этого механизма блокировки интерфейс BlockingQueue предоставляет две функции поверх обычных функций Queue: put и take. Эти функции эквивалентны добавлению и удалению в стандартной очереди.

3. Реализации параллельных очередей

3.1. ArrayBlockingQueue

Как следует из названия, эта очередь внутренне использует массив. Как следствие, это ограниченная очередь, то есть она имеет фиксированный размер.

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

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

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

3.2. LinkedBlockingQueue

LinkedBlockingQueue использует вариант LinkedList, где каждый элемент очереди является новым узлом. Хотя это делает очередь в принципе неограниченной, она по-прежнему имеет жесткое ограничение Integer.MAX_VALUE.

С другой стороны, мы можем установить размер очереди с помощью конструктора LinkedBlockingQueue(int capacity).

Эта очередь использует разные блокировки для операций ввода и вывода. Как следствие, обе операции могут выполняться параллельно и повышать пропускную способность.

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

Говорят, что производительность LinkedBlockingQueue непредсказуема. Другими словами, нам всегда нужно профилировать наши сценарии, чтобы убедиться, что мы используем правильную структуру данных.

3.3. PriorityBlockingQueue

PriorityBlockingQueue — это наше решение, когда нам нужно потреблять элементы в определенном порядке. Для этого PriorityBlockingQueue использует двоичную кучу на основе массива.

Хотя внутри он использует один механизм блокировки, операция взятия может выполняться одновременно с операцией помещения. Использование простой спин-блокировки делает это возможным.

Типичный вариант использования — выполнение задач с разными приоритетами. Мы не хотим, чтобы задача с низким приоритетом заменяла задачу с высоким приоритетом.

3.4. DelayQueue

Мы используем DelayQueue, когда потребитель может взять только просроченный товар. Интересно, что внутри используется PriorityQueue для упорядочения элементов по истечении срока их действия.

«Поскольку это не очередь общего назначения, она не охватывает столько сценариев, сколько ArrayBlockingQueue или LinkedBlockingQueue. Например, мы можем использовать эту очередь для реализации простого цикла событий, аналогичного тому, что есть в NodeJS. Мы помещаем асинхронные задачи в очередь для последующей обработки по истечении срока их действия.

3.5. LinkedTransferQueue

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

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

3.6. SynchronousQueue

Хотя очереди обычно содержат много элементов, SynchronousQueue всегда будет иметь максимум один элемент. Другими словами, нам нужно рассматривать SynchronousQueue как простой способ обмена некоторыми данными между двумя потоками.

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

3.7. ConcurrentLinkedQueue

ConcurrentLinkedQueue — единственная неблокирующая очередь в этом руководстве. Следовательно, он предоставляет алгоритм «без ожидания», в котором операции добавления и опроса гарантированно являются потокобезопасными и возвращаются немедленно. Вместо блокировок эта очередь использует CAS (Compare-And-Swap).

Внутри он основан на алгоритме из книги «Простые, быстрые и практичные неблокирующие и блокирующие алгоритмы параллельных очередей» Магеда М. Майкла и Майкла Л. Скотта.

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

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

4. Заключение

В этом руководстве мы рассмотрели различные реализации параллельных очередей, обсудив их сильные и слабые стороны. Имея это в виду, мы лучше подготовлены для разработки эффективных, надежных и доступных систем.