Неблокирующая поточно-безопасная очередь в С++?

Ответ 1

Предполагая, что ваш процессор имеет двухуровневую схему сравнения и замены (compxchg8b на 486 или выше, compxchg16b на большинстве машин amd64 [не присутствует на некоторых ранних моделях Intel])... Существует алгоритм здесь.

Обновление. Не сложно перевести это на С++, если вы не боитесь сделать немного работы.: P

Этот алгоритм предполагает структуру "указатель с тегом", которая выглядит так:

// Be aware that copying this structure has to be done atomically...

template <class T>
struct pointer
{
   T *ptr;
   uintptr_t tag;
};

Затем вы хотите обернуть инструкции lock cmpxchg{8|16}b с помощью встроенного asm...

Может быть, тогда вы можете написать очередь node следующим образом:

template <class T>
struct queue_node
{
    T value;
    pointer<queue_node<T> > next;
};

Остальное - это более или менее транскрипция алгоритма, связанного с...

Ответ 2

Так как текущий стандарт С++ даже не признает существование потоков, в STL и в любой другой части стандартной библиотеки, безусловно, нет нити-безопасности.

Ответ 3

Это, кажется, популярный сюжет доктора Добба в прошлом году:

• Неблокированные очереди
• Написание кода Free-Free: исправленная очередь

Ответ 4

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

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

Ответ 5

Контейнеры STL не являются потокобезопасными, вы должны реализовать свою обработку для одновременного доступа.
Этот проект (С++) предназначен для одновременного доступа: CPH STL
и бумага.

Ответ 6

Короткий ответ - нет. STL не относится к concurrency (по крайней мере, на уровне спецификации). Текущий стандарт С++ ничего не говорит о потоках. Вы можете легко создать такую ​​очередь поверх STL и Boost - просто оберните std::queue и boost::mutex в свой собственный класс.

Ответ 7

Может быть, уже слишком поздно. Для справок в будущем эта версия является хорошей реализацией незакрепленных очередей (встроенная в безопасность потоков с некоторыми оговорками).

Multi производитель - многопользовательский

http://moodycamel.com/blog/2014/a-fast-general-purpose-lock-free-queue-for-c++

https://github.com/cameron314/concurrentqueue

Единый производитель - один потребитель

http://moodycamel.com/blog/2013/a-fast-lock-free-queue-for-c++

https://github.com/cameron314/readerwriterqueue

Ответ 8

В настоящее время неофициальный Boost.Lockfree - это то, что нужно учитывать. Я использую как FIFO, так и атомные типы.