88

私は、C++ のロックフリー キューについてかなりグーグルで調べてきました。いくつかのコードといくつかの試行を見つけましたが、コンパイルできたものは何もありませんでした。ロックフリーのハッシュも大歓迎です。

要約：これまでのところ、肯定的な答えはありません。「本番対応」のライブラリはなく、驚くべきことに、既存のライブラリのどれも STL コンテナーの API に準拠していません。

4

15 に答える 15

41

1.53 の時点で、boost は、キュー、スタック、シングル プロデューサー/シングル コンシューマー キュー (つまりリング バッファー) を含む一連のロック フリー データ構造を提供します。

于 2013-02-18T12:53:06.720 に答える
25

出発点は、単一のプロデューサーとコンシューマー、または複数のいずれかの Herb Sutter の DDJ 記事のいずれかです。彼が提供するコード (各記事の 2 ページ目からインラインで開始) では、C++0x スタイルの atom<T> テンプレート型を使用しています。Boostインタープロセスライブラリを使用して模倣できます。

ブースト コードはプロセス間ライブラリの深部に埋もれていますが、適切なヘッダー ファイル (atomic.hpp) を読み込んで、システム上で必要な比較と交換操作の実装を読んだところ、見慣れたものに見えました。

于 2009-07-22T09:14:38.097 に答える
17

Facebook のFollyは、C++11 に基づいたロックフリーのデータ構造を持っているようです<atomic>:

これらは現在本番環境で使用されているとあえて言えば、他のプロジェクトでも安全に使用できると思います。

乾杯！

于 2013-04-15T15:51:24.303 に答える
11

そのようなライブラリがありますが、それはCにあります。

C++へのラッピングは簡単なはずです。

liblfds

于 2009-10-17T10:18:24.150 に答える
10

boost.lockfree は、lockfree スタックおよび fifo クラスの C++ 実装を作成する試みです。

公開 git リポジトリ

于 2009-08-28T10:21:57.697 に答える
9

与えられた答えのほとんどをチェックした後、私は次のようにしか述べることができません。

答えはNOです。

箱から出してすぐに使用できるようなものはありません。

于 2009-08-27T19:51:30.503 に答える
6

私が知っている最も近いものは、Windows Interlocked Singly Linked Listsです。もちろんWindowsのみです。

于 2009-10-09T16:06:18.293 に答える
5

複数のプロデューサー/単一のコンシューマーのキュー/FIFO がある場合は、SLIST または単純な Lock Free LIFO スタックを使用して 1 つの LockFree を簡単に作成できます。あなたがすることは、コンシューマー用に 2 番目の「プライベート」スタックを用意することです (これは、単純にするために SLIST として、または選択した他のスタック モデルとしても実行できます)。コンシューマはプライベート スタックから項目をポップします。プライベート LIFO が使い果たされるたびに、共有された同時実行 SLIST をポップオフする (SLIST チェーン全体を取得する) のではなく、フラッシュを実行してから、フラッシュされたリストを順番にウォークし、項目をプライベート スタックにプッシュします。

これは、単一プロデューサー/単一消費者および複数プロデューサー/単一消費者で機能します。

ただし、複数のコンシューマーの場合 (シングル プロデューサーまたはマルチ プロデューサーのいずれか) では機能しません。

また、ハッシュ テーブルに関する限り、ハッシュをキャッシュのセグメントごとにロックを持つセグメントに分割するだけの「ストライピング」の理想的な候補です。これは、Java 並行ライブラリが行う方法です (32 ストライプを使用)。軽量のリーダー/ライター ロックを使用している場合、同時読み取りのためにハッシュ テーブルに同時にアクセスでき、競合するストライプで書き込みが発生している場合にのみ停止します (ハッシュ テーブルの拡張を許可する場合)。

自分でロールする場合は、すべてのロックを隣り合わせの配列に配置するのではなく、ロックをハッシュ エントリでインターリーブして、誤った共有が発生する可能性が低くなるようにしてください。

于 2009-10-09T16:00:12.877 に答える
3

そして、Intel ThreadingBuildingBlocksが登場しました。そしてしばらくの間、それは良かった。

PS：あなたはconcurrent_queueとconcurrent_hash_mapを探しています

于 2009-07-22T12:18:12.123 に答える
1

私の知る限りでは、そのようなものはまだ公開されていません。実装者が解決しなければならない問題の 1 つは、ロックフリーのメモリ アロケータが必要なことです。これは存在しますが、今のところリンクが見つからないようです。

于 2009-07-22T12:14:56.270 に答える
1

以下は、Concurrent lock free Queue http://www.drdobbs.com/parallel/writing-a-generalized-concurrent-queue/211601363?pgno=1に関する Herb Sutter の記事からのものです。コンパイラの並べ替えなど、いくつかの変更を加えました。このコードをコンパイルするには、GCC v4.4+ が必要です。

#include <atomic>
#include <iostream>
using namespace std;

//compile with g++ setting -std=c++0x

#define CACHE_LINE_SIZE 64

template <typename T>
struct LowLockQueue {
private:
    struct Node {
    Node( T* val ) : value(val), next(nullptr) { }
    T* value;
    atomic<Node*> next;
    char pad[CACHE_LINE_SIZE - sizeof(T*)- sizeof(atomic<Node*>)];
    };
    char pad0[CACHE_LINE_SIZE];

// for one consumer at a time
    Node* first;

    char pad1[CACHE_LINE_SIZE
          - sizeof(Node*)];

// shared among consumers
    atomic<bool> consumerLock;

    char pad2[CACHE_LINE_SIZE
          - sizeof(atomic<bool>)];

// for one producer at a time
    Node* last;

    char pad3[CACHE_LINE_SIZE
          - sizeof(Node*)];

// shared among producers
    atomic<bool> producerLock;

    char pad4[CACHE_LINE_SIZE
          - sizeof(atomic<bool>)];

public:
    LowLockQueue() {
    first = last = new Node( nullptr );
    producerLock = consumerLock = false;
    }
    ~LowLockQueue() {
    while( first != nullptr ) {      // release the list
        Node* tmp = first;
        first = tmp->next;
        delete tmp->value;       // no-op if null
        delete tmp;
    }
    }

    void Produce( const T& t ) {
    Node* tmp = new Node( new T(t) );
    asm volatile("" ::: "memory");                            // prevent compiler reordering
    while( producerLock.exchange(true) )
        { }   // acquire exclusivity
    last->next = tmp;         // publish to consumers
    last = tmp;             // swing last forward
    producerLock = false;       // release exclusivity
    }

    bool Consume( T& result ) {
    while( consumerLock.exchange(true) )
        { }    // acquire exclusivity
    Node* theFirst = first;
    Node* theNext = first-> next;
    if( theNext != nullptr ) {   // if queue is nonempty
        T* val = theNext->value;    // take it out
        asm volatile("" ::: "memory");                            // prevent compiler reordering
        theNext->value = nullptr;  // of the Node
        first = theNext;          // swing first forward
        consumerLock = false;             // release exclusivity
        result = *val;    // now copy it back
        delete val;       // clean up the value
        delete theFirst;      // and the old dummy
        return true;      // and report success
    }
    consumerLock = false;   // release exclusivity
    return false;                  // report queue was empty
    }
};

int main(int argc, char* argv[])
{
    //Instead of this Mambo Jambo one can use pthreads in Linux to test comprehensively
LowLockQueue<int> Q;
Q.Produce(2);
Q.Produce(6);

int a;
Q.Consume(a);
cout<< a << endl;
Q.Consume(a);
cout<< a << endl;

return 0;
}
于 2012-09-14T13:25:34.850 に答える
0

cで書かれた別の解決策を見つけました：

http://www.ddj.com/hpc-high-performance-computing/219500200

于 2009-10-21T09:13:10.443 に答える