ConcurrentLinkedQueue

ConcurrentLinkedQueue — это неблокирующая потокобезопасная очередь с неограниченной ёмкостью, реализованная в Java на основе связного списка и алгоритма Майкла — Скотта (Michael-Scott). Она входит в состав пакета java.util.concurrent и предназначена для эффективного обмена данными между несколькими потоками без использования блокировок.

История

ConcurrentLinkedQueue была представлена в Java 5 (2004 год) в рамках пакета java.util.concurrent, разработанного Дугом Ли (Doug Lea) и его коллегами. Реализация основана на алгоритме неблокирующей очереди Майкла — Скотта, опубликованном в 1996 году. В Java 8 (2014 год) в реализацию были внесены оптимизации, связанные с использованием VarHandle для атомарных операций вместо AtomicReferenceFieldUpdater, что повысило производительность на современных процессорах.

Принцип работы

ConcurrentLinkedQueue использует неблокирующий алгоритм (lock-free), основанный на атомарных операциях сравнения с обменом (CAS — Compare-And-Swap). Это позволяет нескольким потокам одновременно добавлять и извлекать элементы без взаимных блокировок, что обеспечивает высокую пропускную способность в многопоточных сценариях.

Структура данных

Очередь построена на односвязном списке, где каждый узел (Node) содержит:

• Ссылку на хранимый элемент (item).
• Ссылку на следующий узел (next).

Головной узел (head) и хвостовой узел (tail) являются «ленивыми» — они не всегда указывают на фактические первый и последний элементы, а обновляются с задержкой для снижения накладных расходов на CAS-операции.

Алгоритм Майкла — Скотта

Алгоритм обеспечивает:

• Добавление (offer): создаётся новый узел, затем с помощью CAS хвостовой указатель переводится на него. Если CAS не удаётся (из-за конкуренции), поток повторяет попытку.
• Извлечение (poll): с помощью CAS головной указатель переводится на следующий узел. Если очередь пуста, возвращается null.

Характеристики

Основные свойства

• Потокобезопасность: гарантируется корректная работа при одновременном доступе нескольких потоков.
• Неограниченная ёмкость: очередь может расти динамически, ограничена только доступной памятью.
• FIFO-порядок: элементы обрабатываются в порядке добавления (первым вошёл — первым вышел).
• Слабая согласованность (weakly consistent): итераторы не гарантируют отображение всех элементов, добавленных после создания итератора, и могут пропускать элементы, удалённые в процессе итерации.

Производительность

• Операции добавления/извлечения: O(1) в среднем, но при высокой конкуренции возможны повторные попытки CAS.
• Отсутствие блокировок: потоки не приостанавливаются, что исключает проблемы взаимоблокировок (deadlock) и инверсии приоритетов.
• Память: каждый элемент хранится в отдельном узле, что создаёт дополнительные накладные расходы по сравнению с массивами.

Сравнение с блокирующими очередями

Применение

ConcurrentLinkedQueue используется в сценариях, где требуется высокая пропускная способность при обмене данными между потоками, а блокирующие операции не нужны. Типичные примеры:

• Пул потоков: в ThreadPoolExecutor используется для хранения задач, ожидающих выполнения.
• Обработка событий: в GUI-фреймворках (например, JavaFX) для передачи событий между потоками.
• Логирование: асинхронная запись логов в отдельный поток.
• Сбор данных: в системах реального времени для передачи данных от датчиков к обработчикам.

Ограничения

• Не поддерживает блокирующие операции (например, take() из BlockingQueue).
• Не гарантирует строгой согласованности при итерации.
• Не подходит для сценариев с одним производителем и одним потребителем (лучше использовать ArrayBlockingQueue или SynchronousQueue).

Пример использования

```java import java.util.concurrent.ConcurrentLinkedQueue;

public class Example { public static void main(String[] args) { ConcurrentLinkedQueue<String> queue = new ConcurrentLinkedQueue<>();

// Добавление элементов queue.offer("A"); queue.offer("B"); queue.offer("C");

// Извлечение элементов String element = queue.poll(); // "A" String peek = queue.peek(); // "B" (без удаления)

// Итерация for (String s : queue) { System.out.println(s); } } } ```

Интересные факты

• В Java 8 в ConcurrentLinkedQueue были внедрены VarHandle для атомарных операций, что заменило использование AtomicReferenceFieldUpdater и улучшило производительность на 10–20% в некоторых тестах.
• Алгоритм Майкла — Скотта, лежащий в основе очереди, считается одним из фундаментальных в области неблокирующих структур данных.
• ConcurrentLinkedQueue не поддерживает null-элементы — попытка добавить null вызовет NullPointerException.

Критика

• Отсутствие блокирующих операций может быть недостатком в сценариях, где требуется ожидание появления элемента (например, в модели потребитель-производитель с ограниченным буфером).
• Слабая согласованность итераторов может приводить к неожиданным результатам при параллельных модификациях.
• При очень высокой конкуренции (сотни потоков) CAS-операции могут вызывать значительные накладные расходы из-за повторных попыток.

Источники

• Doug Lea. «Concurrent Programming in Java: Design Principles and Patterns» (1999).
• Maged M. Michael, Michael L. Scott. «Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms» (1996).
• Java Documentation: java.util.concurrent.ConcurrentLinkedQueue (Java 8+).
• Brian Goetz et al. «Java Concurrency in Practice» (2006).