Перейти к основному содержимому

LinkedBlockingQueue против ConcurrentLinkedQueue

· 5 мин. чтения

Задача: Наибольшая подстрока палиндром

Для заданной строки s, верните наибольшую подстроку палиндром входящую в s. Подстрока — это непрерывная непустая последовательность символов внутри строки. Стока является палиндромом, если она читается одинаково в обоих направлениях...

ANDROMEDA 42

1. Введение

LinkedBlockingQueue и ConcurrentLinkedQueue — две наиболее часто используемые параллельные очереди в Java . Хотя обе очереди часто используются в качестве параллельной структуры данных, между ними существуют тонкие характеристики и различия в поведении.

В этом кратком руководстве мы обсудим обе эти очереди и объясним их сходства и различия.

2. Связанная очередь блокировки

LinkedBlockingQueue — это необязательно ограниченная реализация очереди блокировки, что означает, что при необходимости можно указать размер очереди. ``

Давайте создадим LinkedBlockingQueue , которая может содержать до 100 элементов:

BlockingQueue<Integer> boundedQueue = new LinkedBlockingQueue<>(100);

Мы также можем создать неограниченную LinkedBlockingQueue , просто не указывая размер:

BlockingQueue<Integer> unboundedQueue = new LinkedBlockingQueue<>();

Неограниченная очередь подразумевает, что размер очереди не указывается при создании. Поэтому очередь может динамически расти по мере добавления в нее элементов. Однако, если памяти не осталось, очередь выдает ошибку java.lang.OutOfMemoryError.

Мы также можем создать LinkedBlockingQueue из существующей коллекции:

Collection<Integer> listOfNumbers = Arrays.asList(1,2,3,4,5);
BlockingQueue<Integer> queue = new LinkedBlockingQueue<>(listOfNumbers);

Класс LinkedBlockingQueue реализует интерфейс BlockingQueue , который обеспечивает ему характер блокировки .

Блокирующая очередь указывает, что очередь блокирует доступ к потоку, если она заполнена (когда очередь ограничена) или становится пустой. Если очередь заполнена, то добавление нового элемента заблокирует поток доступа, если для нового элемента не будет свободного места. Точно так же, если очередь пуста, доступ к элементу блокирует вызывающий поток:

ExecutorService executorService = Executors.newFixedThreadPool(1);
LinkedBlockingQueue<Integer> queue = new LinkedBlockingQueue<>();
executorService.submit(() -> {
try {
queue.take();
}
catch (InterruptedException e) {
// exception handling
}
});

В приведенном выше фрагменте кода мы обращаемся к пустой очереди. Поэтому метод take блокирует вызывающий поток.

Функция блокировки LinkedBlockingQueue связана с некоторыми затратами. Эта стоимость связана с тем, что каждая операция размещения или взятия блокируется между потоками-производителями или потоками-потребителями. Таким образом, в сценариях со многими производителями и потребителями действия « установить и принять» могут выполняться медленнее.

3. Параллельная связанная очередь

ConcurrentLinkedQueueэто неограниченная, потокобезопасная и неблокирующая очередь.

Давайте создадим пустую ConcurrentLinkedQueue :

ConcurrentLinkedQueue queue = new ConcurrentLinkedQueue();

Мы также можем создать ConcurrentLinkedQueue из существующей коллекции:

Collection<Integer> listOfNumbers = Arrays.asList(1,2,3,4,5);
ConcurrentLinkedQueue<Integer> queue = new ConcurrentLinkedQueue<>(listOfNumbers);

В отличие от LinkedBlockingQueue, ConcurrentLinkedQueue является неблокирующей очередью . Таким образом, он не блокирует поток, когда очередь пуста. Вместо этого он возвращает null . Поскольку он неограничен, он выдаст java.lang.OutOfMemoryError , если нет дополнительной памяти для добавления новых элементов.

Помимо того, что ConcurrentLinkedQueue не блокирует, у него есть дополнительные функции.

В любом сценарии производитель-потребитель потребители не будут конкурировать с производителями; однако несколько производителей будут конкурировать друг с другом:

int element = 1;
ExecutorService executorService = Executors.newFixedThreadPool(2);
ConcurrentLinkedQueue<Integer> queue = new ConcurrentLinkedQueue<>();

Runnable offerTask = () -> queue.offer(element);

Callable<Integer> pollTask = () -> {
while (queue.peek() != null) {
return queue.poll().intValue();
}
return null;
};

executorService.submit(offerTask);
Future<Integer> returnedElement = executorService.submit(pollTask);
assertThat(returnedElement.get().intValue(), is(equalTo(element)));

Первая задача, offerTask , добавляет элемент в очередь, а вторая задача, pollTask, извлекает элемент из очереди. Задача опроса дополнительно сначала проверяет очередь на наличие элемента, поскольку ConcurrentLinkedQueue не блокирует и может возвращать нулевое значение .

4. Сходства

И LinkedBlockingQueue, и ConcurrentLinkedQueue являются реализациями очередей и имеют некоторые общие характеристики. Давайте обсудим сходство этих двух очередей:

  1. Оба реализуют интерфейс очереди
  2. Оба они используют связанные узлы для хранения своих элементов .
  3. Оба подходят для параллельного доступа

5. Отличия

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

   | Особенность    | LinkedBlockingQueue    | ConcurrentLinkedQueue   | 
| **Блокирующая природа** | Это блокирующая очередь, реализующая интерфейс `BlockingQueue .` | Это неблокирующая очередь и не реализует интерфейс `BlockingQueue .` |
| **Размер очереди** | Это опционально ограниченная очередь, что означает возможность определения размера очереди во время создания. | Это неограниченная очередь, и нет возможности указать размер очереди во время создания. |
| **Блокировка природы** | Это ** очередь на основе блокировки** | Это **безблокировочная очередь** |
| **Алгоритм** | Он реализует **свою блокировку на основе алгоритма `очереди с двумя блокировками .` ** | Он основан на **алгоритме Майкла и Скотта для неблокирующих очередей без блокировок.** |
| **Реализация** | В механизме алгоритма `очереди с двумя блокировками` `LinkedBlockingQueue` использует две разные блокировки — `putLock` и `takeLock` . Операции `put/take` используют первый тип блокировки, а операции `take/poll` используют другой тип блокировки. `` `` `` `` `` | **Он использует CAS (Compare-And-Swap** ) для своих операций . |
| **Блокирующее поведение** | Это блокирующая очередь. Таким образом, он блокирует доступ к потокам, когда очередь пуста. | Он не блокирует доступ к потоку, когда очередь пуста, и возвращает `null` |

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

В этой статье мы узнали о LinkedBlockingQueue и ConcurrentLinkedQueue.

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

Как всегда, исходный код примеров доступен на GitHub .