Существует ли такая вещь, как очередь без блокировки для нескольких потоков чтения или записи?

Question

Я думал, возможно ли иметь очередь без блокировки , когда более одного потока читает или пишет?Я видел реализацию с безблокировочной очередью, которая работала с одним потоком чтения и одним потоком записи, но никогда не более чем для одного.Является ли это возможным?Я не думаю, что это так.Может / кто-нибудь хочет доказать это?

Answer 1

Доступно несколько алгоритмов, в итоге я реализовал Оптимистический подход к очередям FIFO без блокировок , который позволяет избежать проблемы ABA с помощью тегов-указателей (требуется инструкция CMPXCHG8B на x86), и он отлично работает в производственном приложении (написано на Delphi).( Другая версия, с Java-кодом )

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

Вы можететакже хотите посмотреть ответы для оптимистических очередей FIFO без блокировок impl?

Answer 2

Реализация Java без блокировки очереди позволяет как чтение, так и запись. Эта работа выполняется с помощью операции сравнения и установки (которая является одной инструкцией ЦП).

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

Answer 3

В .NET 4.0 существует класс ConcurrentQueue (T) .
Согласно C # 4.0, это реализация без блокировки. Смотрите также эту запись в блоге .

Answer 4

В .NET 4.0 существует Класс ConcurrentQueue .

Образец

https://dotnetfiddle.net/ehLZCm

public static void Main()
{
    PopulateQueueParallel(new ConcurrentQueue<string>(), 500);
}

static void PopulateQueueParallel(ConcurrentQueue<string> queue, int queueSize)
{
    Parallel.For(0, queueSize, (i) => queue.Enqueue(string.Format("my message {0}", i)));
    Parallel.For(0, queueSize,
        (i) =>
        {
            string message;
            bool success = queue.TryDequeue(out message);
            if (!success)
                throw new Exception("Error!");

            Console.WriteLine(message);
        });
}

Answer 5

В библиотеке OmniThread есть очередь с динамической блокировкой от Примоза Габриелчича (Делийский Компьютерщик): http://www.thedelphigeek.com/2010/02/omnithreadlibrary-105.html

Answer 6

Вам специально не нужна блокировка, но атомарный способ удаления вещей из очереди. Это также возможно без блокировки и с помощью атомарной инструкции test-and-set .