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 использует двоичную кучу на основе массива.
Хотя внутри используется единый механизм блокировки, операция взятия может выполняться одновременно с операцией помещения . Использование простой спин-блокировки делает это возможным.
Типичным вариантом использования является использование задач с разными приоритетами. Мы не хотим, чтобы задача с низким приоритетом заменяла задачу с высоким приоритетом .
3.4. DelayQueue
Мы используем DelayQueue , когда потребитель может взять только просроченный товар . Интересно, что внутри используется PriorityQueue для упорядочения элементов по истечении срока их действия.
Поскольку это не очередь общего назначения, она не охватывает столько сценариев, сколько ArrayBlockingQueue или LinkedBlockingQueue . Например, мы можем использовать эту очередь для реализации простого цикла событий, аналогичного тому, что есть в NodeJS. Мы помещаем асинхронные задачи в очередь для последующей обработки по истечении срока их действия.
3.5. LinkedTransferQueue
LinkedTransferQueue представляет метод передачи . В то время как другие очереди обычно блокируются при производстве или потреблении элементов, LinkedTransferQueue позволяет производителю ожидать потребления элемента .
Мы используем LinkedTransferQueue , когда нам нужна гарантия того, что определенный элемент, который мы помещаем в очередь, был кем-то взят. Кроме того, мы можем реализовать простой алгоритм обратного давления, используя эту очередь. Действительно, блокируя производителей до момента потребления, потребители могут управлять потоком производимых сообщений .
3.6. Синхронная очередь
В то время как очереди обычно содержат много элементов, SynchronousQueue всегда будет иметь максимум один элемент. Другими словами, нам нужно рассматривать SynchronousQueue как простой способ обмена некоторыми данными между двумя потоками .
Когда у нас есть два потока, которым требуется доступ к общему состоянию, мы часто синхронизируем их с помощью CountDownLatch или других механизмов синхронизации. Используя SynchronousQueue , мы можем избежать ручной синхронизации потоков .
3.7. ConcurrentLinkedQueue
ConcurrentLinkedQueue — единственная неблокирующая очередь в этом руководстве. Следовательно, он предоставляет алгоритм «без ожидания», в котором операции добавления и опроса гарантированно являются потокобезопасными и возвращаются немедленно . Вместо блокировок эта очередь использует CAS (Compare-And-Swap) .
Внутри он основан на алгоритме из книги «Простые, быстрые и практичные неблокирующие и блокирующие алгоритмы параллельных очередей » Магеда М. Майкла и Майкла Л. Скотта.
Это идеальный кандидат для современных реактивных систем , где использование блокирующих структур данных часто запрещено.
С другой стороны, если наш потребитель в конечном итоге ожидает в цикле, нам, вероятно, следует выбрать блокирующую очередь в качестве лучшей альтернативы.
4. Вывод
В этом руководстве мы рассмотрели различные реализации параллельных очередей, обсудив их сильные и слабые стороны. Имея это в виду, мы лучше подготовлены для разработки эффективных, надежных и доступных систем.