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

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

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

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

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

Ответ 1

Остерегайтесь зла: Проблема ABA.

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

Ответ 2

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

Пример:

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;
    };
};

Ответ 3

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

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