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

Question

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

Answer 1

Есть несколько алгоритмов доступны, я в конечном итоге реализации An Optimistic Approach to Lock-Free FIFO Queues, что позволяет избежать проблем ABA через указатель пометки (нуждается в CMPXCHG8B инструкции по x86), и он прекрасно работает в приложении производства (написанном в Delphi). (Another version, with Java code)

Тем не менее, чтобы быть на самом деле, действительно беззамочные, вы также должны стопорное свободного распределения памяти - см Scalable Lock-Free Dynamic Memory Allocation (реализованный в Concurrent Building Block) или NBMalloc (но до сих пор я не получил использовать один из эти).

Вы также можете посмотреть ответы на optimistic lock-free FIFO queues impl?

Answer 2

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

Answer 3

С .NET 4.0 существует ConcurrentQueue(T) Class.
В соответствии с C# 4.0 в двух словах, это реализация без блокировки. См. Также blog entry.

Answer 4

Существует динамическая блокировка свободная очередь в OmniThreadLibrary по Примозу Gabrijelcic (делфийская Geek): http://www.thedelphigeek.com/2010/02/omnithreadlibrary-105.html

Answer 5

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

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

Answer 6

С .NET 4.0 существует ConcurrentQueue Class.

Образец

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