9

我在想，当多个线程正在读取或写入时，是否可以有一个无锁队列？我见过一个带有无锁队列的实现，它与一个读取和一个写入线程一起工作，但任何一个线程都不会超过一个。是否可以？我不认为它是。可以/有人想证明吗？

4

6 回答 6

14

有多种算法可用，我最终实现了An Optimistic Approach to Lock-Free FIFO Queues，它通过指针标记避免了 ABA 问题（需要CMPXCHG8Bon 指令x86），并且它在生产应用程序中运行良好（用 Delphi 编写） . （另一个版本，带有 Java 代码）

尽管如此，要真正实现无锁，您还需要一个无锁内存分配器 - 请参阅Scalable Lock-Free Dynamic Memory Allocation (implemented in Concurrent Building Block ) 或NBMalloc (但到目前为止，我还没有使用过一个这些）。

您可能还想查看乐观无锁 FIFO 队列 impl 的答案？

于 2010-06-11T11:40:04.887 回答
3

Java 的无锁队列实现允许读取和写入。这项工作是通过比较和设置操作（这是一条 CPU 指令）完成的。

使用ConcurrentLinkedQueue一种方法，其中线程互相帮助从队列中读取（或轮询）对象。由于它是链接的，因此队列的头部可以接受写入，而队列的尾部可以接受读取（假设有足够的空间）。所有这些都可以并行完成，并且是完全线程安全的。

于 2010-06-11T16:59:32.353 回答
1

在 .NET 4.0 中，有ConcurrentQueue(T) Class。
简而言之，根据 C# 4.0，这是一个无锁实现。另请参阅此博客条目。

于 2010-06-11T06:47:55.650 回答
0

您并不特别需要锁，而是一种从队列中删除事物的原子方式。这在没有锁和原子测试和设置指令的情况下也是可能的。

于 2010-06-11T06:37:14.423 回答
0

Primoz Gabrijelcic（Delphi Geek）在 OmniThreadLibrary 中有一个动态无锁队列：http ://www.thedelphigeek.com/2010/02/omnithreadlibrary-105.html

于 2010-06-11T14:41:20.250 回答
0

在 .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);
        });
}
于 2016-08-26T23:00:16.190 回答