Фобер и др. Безлимитная очередь FIFO: несколько потребителей и производителей?

Question

Мне было интересно, была ли очередь fifo, представленная в статье Фобера и др. http://nedko.arnaudov.name/soft/L17_Fober.pdf, многократным потребителем и производила очередь fifo. Если нет, то какая лучше всего задокументирована очередь FIFO для нескольких потребителей и производителей?

Спасибо

Answer 1

Я не читал статью, но здесь я делаю большое предположение: в статье используется метод CAS (сравнение и своп) для достижения параллелизма.

Без блокировки не означает освобождение блока. Использование CAS остановит другие потоки, но по крайней мере один поток будет все время двигаться вперед.

Несколько производителей пишут в одну очередь - это не проблема. Хитрость заключается в нескольких потребителей. Если каждый потребитель должен получить доступ к данным, то я реализую его несколькими очередями, и данные будут обрабатываться в следующей очереди после обработки в одной. Если вы имеете в виду несколько потребителей через потоки, то это сработало бы по вышеуказанному методу

Answer 2

да. прочитайте раздел «3.1. Линейность» операция pop предполагает, что может произойти одновременное удаление очереди. Это означает, что несколько потоков смогут использовать очередь.

Answer 3

Я не знаю «очереди Фобера», но уже написал FIFO без блокировки в качестве кольцевых буферов. Относительно легко можно получить очередь «без блокировки», что означает, что считыватели не блокируют записывающие устройства, и наоборот, но множественные считыватели должны быть сериализованы, а множественные записывающие устройства тоже должны быть. Таким образом, он не является полностью свободным от блокировки, но между читателями и писателями все еще нет блокировки / блокировки.

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