Java for Beginner

ConcurrentLinkedQueue, внутреннее устройство, особенности и преимущества

ConcurrentLinkedQueue — это неконкурирующая неблокирующая очередь на основе связанного списка, предоставляемая в пакете java.util.concurrent. Она поддерживает высокую степень конкурентности благодаря использованию алгоритмов без блокировок (lock-free algorithms).

Особенности и преимущества

Неконкурирующая: Методы ConcurrentLinkedQueue реализованы таким образом, что могут использоваться несколькими потоками одновременно без необходимости явной синхронизации.
Неблокирующая: Основана на алгоритмах без блокировок, что позволяет избежать блокировок и взаимных блокировок, повышая производительность в условиях высокой конкурентности.
Поддержка FIFO (First-In-First-Out): Гарантирует, что элементы будут обрабатываться в порядке их добавления.

Внутреннее устройство

ConcurrentLinkedQueue использует алгоритм Майкла-скотта (Michael-Scott) для реализации неблокирующей очереди на основе связанного списка. Основные компоненты включают узлы (nodes) и ссылки на голову (head) и хвост (tail) очереди.

Внутренний класс Node:

Узел содержит элемент данных и ссылку на следующий узел.

private static class Node<E> {
    volatile E item;
    volatile Node<E> next;

    Node(E item) {
        this.item = item;
    }
}

Голова и хвост очереди:

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

private transient volatile Node<E> head;
private transient volatile Node<E> tail;

Алгоритм Майкла-скотта:

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

public boolean offer(E e) {
    final Node<E> newNode = new Node<>(e);
    for (Node<E> t = tail, p = t; ; ) {
        Node<E> q = p.next;
        if (q == null) {
            if (p.next = q) {
                tail = newNode;
                return true;
            }
        } else {
            p = (t != tail) ? tail : q;
        }
    }
}

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

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

import java.util.concurrent.ConcurrentLinkedQueue;

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

        // Вставка элементов
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);

        // Извлечение элементов
        System.out.println(queue.poll()); // 1
        System.out.println(queue.poll()); // 2
        System.out.println(queue.poll()); // 3
    }
}

Ссылки на полезные статьи (спасибо авторам за проделанную работу) :
https://www.baeldung.com/java-queue-linkedblocking-concurrentlinked
https://www.geeksforgeeks.org/concurrentlinkedqueue-in-java-with-examples/

#Java #Training #Medium #ConcurrentLinkedQueue

Baeldung

LinkedBlockingQueue vs ConcurrentLinkedQueue | Baeldung

Learn the difference between LinkedBlockingQueue and ConcurrentLinkedQueue in Java

488 viewsДен, 05:16

Java for Beginner

Основные методы ConcurrentLinkedQueue и примеры использования

offer(E e):

Вставляет элемент в конец очереди. Возвращает true после успешного добавления.

ConcurrentLinkedQueue<Integer> queue = new ConcurrentLinkedQueue<>();
queue.offer(1);
queue.offer(2);

poll():

Извлекает и удаляет элемент из головы очереди. Возвращает null, если очередь пуста.

Integer item = queue.poll();
System.out.println(item); // 1

peek():

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

Integer item = queue.peek();
System.out.println(item); // 2

isEmpty():

Проверяет, пуста ли очередь.

boolean isEmpty = queue.isEmpty();
System.out.println(isEmpty); // false

size():

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

int size = queue.size();
System.out.println(size); // 1

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

Производитель-потребитель:

import java.util.concurrent.ConcurrentLinkedQueue;

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

        // Производитель
        new Thread(() -> {
            for (int i = 0; i < 10; i++) {
                queue.offer(i);
                System.out.println("Produced: " + i);
            }
        }).start();

        // Потребитель
        new Thread(() -> {
            for (int i = 0; i < 10; i++) {
                Integer item;
                while ((item = queue.poll()) == null) {
                    // Ожидание элемента
                }
                System.out.println("Consumed: " + item);
            }
        }).start();
    }
}

Очередь задач:

import java.util.concurrent.ConcurrentLinkedQueue;

public class TaskQueueExample {
    public static void main(String[] args) {
        ConcurrentLinkedQueue<Runnable> taskQueue = new ConcurrentLinkedQueue<>();

        // Запуск потока исполнителя задач
        new Thread(() -> {
            while (true) {
                Runnable task = taskQueue.poll();
                if (task != null) {
                    task.run();
                }
            }
        }).start();

        // Добавление задач в очередь
        taskQueue.offer(() -> System.out.println("Task 1 executed"));
        taskQueue.offer(() -> System.out.println("Task 2 executed"));
    }
}

#Java #Training #Medium #ConcurrentLinkedQueue

413 viewsДен, 13:59

About

Blog

Apps

Platform