9

複数のスレッドが読み取りまたは書き込みを行っているときに、ロックのないキューを持つことは可能ですか? 1 つの読み取りスレッドと 1 つの書き込みスレッドで機能するロックレス キューを使用した実装を見たことがありますが、いずれのスレッドも複数のスレッドで機能することはありませんでした。出来ますか？そうではないと思います。誰かがそれを証明できますか/証明したいですか?

4

6 に答える 6

14

利用可能なアルゴリズムは複数あります。最終的にはAn Optimistic Approach to Lock-Free FIFO Queues を実装しました。これは、ポインターのタグ付けを介して ABA 問題を回避し (上のCMPXCHG8B命令が必要x86です)、実稼働アプリ (Delphi で記述) で正常に動作します。 . ( Java コードを含む別のバージョン)

それにもかかわらず、本当に本当にロックレスであるためには、ロックフリー メモリ アロケータも必要です。スケーラブルなロックフリー動的メモリ割り当て(コンカレント ビルディング ブロックで実装) または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

.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 に答える
0

特にロックは必要ありませんが、キューからものを削除するアトミックな方法です。これは、ロックなしでアトミックテスト アンド セット命令を使用しても可能です。

于 2010-06-11T06:37:14.423 に答える
0

OmniThreadLibrary には、Primoz Gabrijelcic (Delphi Geek) による動的ロック解放キューがあります: http://www.thedelphigeek.com/2010/02/omnithreadlibrary-105.html

于 2010-06-11T14:41:20.250 に答える