Реализация множественной очереди блокировки производителя / потребителя в C \ C ++

Question

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

Первое - действительно ли эта реализация работает при использовании нескольких производителей / потребителей или есть что-то, чего мне не хватает в оригинальной реализации Майкла-Скотта, котораяработает с несколькими настройками производителя / потребителя.

Второй - в статье Оптимистический подход к свободным от блокировок очередям FIFO В разделе «Удаление» показано использование фиктивного значения.Как я могу определить, что является подходящим значением для использования?Если я использую целые числа, что убедит меня в том, что целое число, которое я выберу для фиктивного значения, не является фактическим значением, которое я решил поставить в очередь?

Любой совет или общее направление было бы замечательно.И если кто-то хочет знать, я создаю это в Visual Studio, чтобы лучше понять неблокирующие алгоритмы.Я хотел бы сделать это настолько универсальным, насколько это возможно, чтобы я мог ставить в очередь все что угодно (данные в очереди формируются на основе шаблонов, чтобы пользователь мог указать, что ставить в очередь).

Answer 1

Остерегайтесь зла: АБА проблема .

Вы можете начать читать это , это и это .

Answer 2

Нет явной поддержки инструкций атомарного процессора, необходимых для реализации неблокирующих очередей в C ++ (пока, это в более новых спецификациях).

Возможно получить доступ к инструкциям на вашем компьютере, но вы 'Вам придется либо встроить некоторую сборку, либо найти библиотеку (TBB или, может быть, boost), которая сделает это за вас.

Answer 3

Вы можете сделать дешевый тип обертки, чтобы отслеживать правильность элементов, и пользователь мог прозрачно передавать значения, не беспокоясь об этом.Это приводит к небольшим накладным расходам памяти, но на самом деле нет лучшего способа, если вы хотите разрешить постановку в очередь и удаление нулевых значений (вместо того, чтобы рассматривать их как «фиктивных» часовых).

Пример:

template<typename T>
class MyQueue
{
    /* . . . */
public:
    void Enqueue(T * value)
    {
        MyQueueItem item;
        item.value = value;
        item.isValid = true;

        /* enqueue it now
           . . . */
    }

    T * Dequeue()
    {
        MyQueueItem validItem;
        /* Get the first element where isValid == true
           . . . */
        return validItem.value;
    }

private:
    struct MyQueueItem
    {
        T * value;
        bool isValid;
    };
};