Автор оригинала: Mathieu Fortin.
1. Обзор
В этом уроке мы рассмотрим некоторые из основных реализаций параллельных очередей в Java. Общее введение в очереди см. в нашем руководстве по интерфейсу очереди Java.
2. Очереди
В многопоточных приложениях очереди должны обрабатывать несколько одновременных сценариев “производители-потребители”. Правильный выбор параллельной очереди может иметь решающее значение для достижения хорошей производительности в наших алгоритмах.
Во-первых, мы увидим некоторые важные различия между блокирующей очередью и неблокирующей. Затем мы рассмотрим некоторые реализации и лучшие практики.
2. Блокирующая и Неблокирующая очереди
BlockingQueue предлагает простой потокобезопасный механизм . В этой очереди потокам необходимо дождаться доступности очереди. Производители будут ждать наличия свободных мощностей, прежде чем добавлять элементы, в то время как потребители будут ждать, пока очередь не опустеет. В этих случаях неблокирующая очередь либо выдаст исключение, либо вернет специальное значение, например null или false .
Для достижения этого механизма блокировки интерфейс BlockingQueue предоставляет две функции поверх обычных функций Queue : put и take . Эти функции эквивалентны add и remove в стандартной очереди .
3. Параллельные Реализации Очередей
3.1. ArrayBlockingQueue
Как следует из названия, эта очередь использует массив внутри. Как следствие, это ограниченная очередь, то есть она имеет фиксированный размер .
Примером использования является простая рабочая очередь. Этот сценарий часто представляет собой низкое соотношение производителей и потребителей, когда мы разделяем трудоемкие задачи между несколькими работниками. Поскольку эта очередь не может расти бесконечно, ограничение размера действует как порог безопасности, если возникает проблема с памятью .
Говоря о памяти, важно отметить, что очередь предварительно выделяет массив. Хотя это может повысить пропускную способность, он также может потреблять больше памяти, чем необходимо . Например, очередь большой емкости может оставаться пустой в течение длительного периода времени.
Кроме того, ArrayBlockingQueue использует одну блокировку для операций put и take . Это гарантирует отсутствие перезаписи записей за счет снижения производительности.
3.2. LinkedBlockingQueue
В LinkedBlockingQueue используется вариант LinkedList , где каждый элемент очереди является новым узлом. Хотя это в принципе делает очередь неограниченной, у нее все еще есть жесткий предел Integer.MAX_VALUE .
С другой стороны, мы можем установить размер очереди с помощью конструктора LinkedBlockingQueue(int capacity) .
Эта очередь использует различные блокировки для операций put и take . Как следствие, обе операции могут выполняться параллельно и повышать пропускную способность.
Поскольку LinkedBlockingQueue может быть как ограниченным, так и неограниченным, зачем нам использовать ArrayBlockingQueue поверх этого? LinkedBlockingQueue необходимо выделять и освобождать узлы каждый раз, когда элемент добавляется или удаляется из очереди . По этой причине ArrayBlockingQueue может быть лучшей альтернативой, если очередь быстро растет и быстро сжимается.
Производительность LinkedBlockingQueue , как говорят, непредсказуема. Другими словами, нам всегда нужно профилировать наши сценарии, чтобы убедиться, что мы используем правильную структуру данных.
3.3. Приоритетная блокировка очереди
PriorityBlockingQueue -это наше решение , когда нам нужно потреблять элементы в определенном порядке . Для достижения этой цели PriorityBlockingQueue использует двоичную кучу на основе массива.
Хотя внутри он использует один механизм блокировки, операция take может выполняться одновременно с операцией put . Использование простого спин-замка делает это возможным.
Типичным вариантом использования является использование задач с разными приоритетами. Мы не хотим, чтобы задача с низким приоритетом заняла место задачи с высоким приоритетом .
3.4. Очередь задержки
Мы используем Очередь задержки , когда потребитель может взять только просроченный товар . Интересно, что он использует Приоритетную очередь внутри, чтобы упорядочить элементы по истечении срока их действия.
Поскольку это не очередь общего назначения, она не охватывает столько сценариев, сколько ArrayBlockingQueue или LinkedBlockingQueue . Например, мы можем использовать эту очередь для реализации простого цикла событий, аналогичного тому, что находится в NodeJS. Мы помещаем асинхронные задачи в очередь для последующей обработки по истечении срока их действия.
3.5. LinkedTransferQueue
В LinkedTransferQueue вводится метод transfer . В то время как другие очереди обычно блокируются при производстве или потреблении элементов, LinkedTransferQueue позволяет производителю ждать потребления элемента .
Мы используем LinkedTransferQueue , когда нам нужна гарантия того, что конкретный элемент, который мы поместили в очередь, был кем-то взят. Кроме того, мы можем реализовать простой алгоритм противодавления, используя эту очередь. Действительно, блокируя производителей до потребления, потребители могут управлять потоком производимых сообщений .
3.6. Синхронная очередь
В то время как очереди обычно содержат много элементов, SynchronousQueue всегда будет иметь, самое большее, один элемент. Другими словами, нам нужно видеть SynchronousQueue как простой способ обмена некоторыми данными между двумя потоками .
Когда у нас есть два потока, которым нужен доступ к общему состоянию, мы часто синхронизируем их с CountDownLatch или другими механизмами синхронизации. Используя SynchronousQueue , мы можем избежать этой ручной синхронизации потоков .
3.7. Concurrentlink Queue
Concurrentlink Queue является единственной неблокирующей очередью в этом руководстве. Следовательно, он обеспечивает алгоритм “без ожидания”, в котором add и poll гарантированно будут потокобезопасными и немедленно вернутся . Вместо блокировок эта очередь использует CAS (Compare-And-Swap) .
Внутренне он основан на алгоритме из Простых, быстрых и практичных Алгоритмов Неблокирующих и блокирующих параллельных очередей Магеда М. Майкла и Майкла Л. Скотта.
Это идеальный кандидат для современных реактивных систем , где использование блокирующих структур данных часто запрещено.
С другой стороны, если ваш потребитель в конечном итоге ждет в цикле, мы, вероятно, должны выбрать blockingqueue в качестве лучшей альтернативы.
4. Заключение
В этом руководстве мы рассмотрели различные реализации параллельных очередей, обсудив их сильные и слабые стороны. Имея это в виду, мы лучше подготовлены для разработки эффективных, долговечных и доступных систем.