C++ Academy · Урок

Реализация очереди без блокировок

Пошагово разберите проектирование очереди без блокировок для одного производителя и одного потребителя.

«Реализация очереди без блокировок» — бесплатный урок C++ Academy на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения C++ Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс C++ Academy содержит 4 уроков всего.

Зачем нужны очереди без блокировок

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

SPSC и MPMC

Два варианта:

SPSC — один производитель, один потребитель (самый простой и быстрый вариант)
MPMC — несколько производителей, несколько потребителей (наиболее универсальный вариант)

SPSC — естественный выбор, когда Вы контролируете оба конца.

Эскиз кольцевого буфера SPSC

Кольцевой буфер с двумя индексами: началом (потребителем) и концом (производителем). Каждая сторона обновляет свой индекс.

template <typename T, size_t N>
class SpscQueue {
    T buffer_[N];
    std::atomic<size_t> head_{0};
    std::atomic<size_t> tail_{0};
public:
    bool push(const T& v);
    bool pop(T& v);
};

Добавление в SPSC

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

bool push(const T& v) {
    const size_t t = tail_.load(std::memory_order_relaxed);
    const size_t next = (t + 1) % N;
    if (next == head_.load(std::memory_order_acquire))
        return false;     // full
    buffer_[t] = v;
    tail_.store(next, std::memory_order_release);
    return true;
}

Извлечение из SPSC

Потребитель проверяет наличие данных, считывает их, а затем публикует результат, обновляя индекс начала.

bool pop(T& v) {
    const size_t h = head_.load(std::memory_order_relaxed);
    if (h == tail_.load(std::memory_order_acquire))
        return false;     // empty
    v = buffer_[h];
    head_.store((h + 1) % N, std::memory_order_release);
    return true;
}

Согласование порядков памяти

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

Заполнение строк кэша

Чтобы избежать ложного совместного использования, разместите head_ и tail_ в разных строках кэша, обычно на расстоянии 64 байт друг от друга. Используйте alignas.

alignas(64) std::atomic<size_t> head_{0};
alignas(64) std::atomic<size_t> tail_{0};

MPMC: гораздо сложнее

Несколько производителей или потребителей требуют дополнительной координации — обычно с циклами CAS для общих индексов. Существует множество вариантов реализации: очередь Вьюкова, очередь MS и очередь на основе указателей опасности.

Boost.Lockfree

Безблокировочные очереди промышленного качества сложно реализовать. Используйте Boost.Lockfree или очередь ProducerConsumerQueue из Folly вместо собственной реализации.

Компромиссы

Безблокировочные очереди:

Обеспечивают более высокую пропускную способность при конкуренции
Обеспечивают ограниченную задержку, поскольку не нужно ждать освобождения блокировки
Гораздо сложнее в написании и отладке
Ошибки в порядке операций с памятью незаметны и трудноуловимы

Тестирование безблокировочного кода

Используйте ThreadSanitizer (-fsanitize=thread), чтобы обнаруживать гонки данных. Используйте стресс-тесты со случайными вставками задержек, чтобы выявить ошибки в порядке операций.

Когда достаточно мьютекса

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

Быстрая проверка

Что такое ложное совместное использование и зачем дополнять head_ и tail_?

Итоги

Безблокировочная очередь SPSC использует кольцевой буфер с индексом конца, которым владеет производитель, и индексом начала, которым владеет потребитель. Используйте порядок операций с семантикой захвата и освобождения и размещайте индексы в разных строках кэша. Для MPMC предпочтительнее использовать протестированную библиотеку.

Часто задаваемые вопросы

Урок «Реализация очереди без блокировок» бесплатный?

Да — полный текст урока «Реализация очереди без блокировок» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс C++ Academy, подпишись на CoddyKit PRO. Курс C++ Academy содержит 4 уроков всего.

Чему я научусь в уроке «Реализация очереди без блокировок»?

Пошагово разберите проектирование очереди без блокировок для одного производителя и одного потребителя. Ты практикуешь C++ Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать C++ Academy?

Предыдущий опыт не требуется. C++ Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.

Сколько времени занимает урок «Реализация очереди без блокировок»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке C++ Academy?

Да. Каждый урок C++ Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

← Назад к C++ Academy