9

このロックフリーキューの擬似コードをどのように実装できますCか？

ENQUEUE(x)
    q ← new record
    q^.value ← x
    q^.next ← NULL
    repeat
        p ← tail
        succ ← COMPARE&SWAP(p^.next, NULL, q)
        if succ ≠ TRUE
            COMPARE&SWAP(tail, p, p^.next)
    until succ = TRUE
    COMPARE&SWAP(tail,p,q)
end

DEQUEUE()
    repeat
        p ← head
        if p^.next = NULL
            error queue empty
    until COMPARE&SWAP(head, p, p^.next)
    return p^.next^.value
end

アトミックメモリアクセスに組み込み関数をどのように使用しますか 

__sync_bool_compare_and_swap (type *ptr, type oldval type newval, ...)

私は現在持っています

typedef struct queueelem {
    queuedata_t data;
    struct queueelem *next;
} queueelem_t;

typedef struct queue {
    int capacity;
    int size;
    queueelem_t *head;
    queueelem_t *tail;
} queue_t;

queue_t *
queue_init(int capacity)
{
    queue_t *q = (queue_t *) malloc(sizeof(queue_t));
    q->head = q->tail = NULL;
    q->size = 0;
    q->capacity = capacity;
    return q;
}
4

5 に答える 5

15

https://www.liblfds.org/

パブリックドメイン、ライセンスなし、Cでのロックフリーアルゴリズムのポータブル実装。

WindowsおよびLinux用の箱から出して構築します。

LinuxでGCCを使用するため、組み込み関数を使用します（128ビットCASを除いて、組み込み関数はありません。そのためにインラインアセンブリを使用します）。

M＆Sキューが含まれています。ソースコードを見て、それがどのように行われるかを確認してください。

于 2011-05-26T15:01:29.897 に答える
5

目標が本番コードである場合は、それを行わないでください。ロックを使用します。

前の質問では、その理由を説明する十分な情報があります。ガベージコレクターがない場合のキューやスタックなどの単純なデータ構造の正しいロックフリー実装は、（悪名高い）ABA問題のためにトリッキーで洗練されています。残念ながら、いくつかの研究論文は、何らかの理由でABAを考慮していません。あなたの擬似コードはそのような論文の1つから取られているようです。これをCに変換し、ノードにヒープに割り当てられたメモリを使用する場合、実際のコードで使用すると、不確定なバグが発生します。

あなたが経験を積むためにこのようなことをしているのなら、SOフェローがあなたのためにそれを解決することを期待しないでください。引用されたすべての資料などを読み、ABAなどのロックフリーアルゴリズムのすべてのニュアンスを本当に理解していることを確認し、問題に対処するためのさまざまな手法を研究し、既存のロックフリー実装を研究する必要があります。

最後に、与えられた擬似コードをCに変換するためのガイダンスはほとんどありません。

q^.value ← xq_elem->data = x;
repeat ... until COMPARE&SWAP(head, p, p^.next)と同等の 意味do {...} while (!__sync_bool_compare_and_swap(q_obj->head, q_elem, q_elem->next);

ここq_objで、はタイプのインスタンスqueue_t（つまりキュー）でありq_elem、はタイプのインスタンスqueueelem_t（つまりキューノード）です。

于 2011-05-23T06:39:39.160 に答える
0

正確にはCではありませんが、提案されているBoost.Lockfreeライブラリを確認してください。内部は非常に簡単に作成でき、Cに移植できます。または、逆に、Boost.LockfreeをCAPIでラップして使用することもできます。

同様に、Boostcon 2010には、ロックフリープログラミングとSTMについて多くの議論がありました。このテーマに興味がある場合は、一見の価値があります。ビデオへのリンクは見つかりませんが、Intel、IBM、AMDの講演はCPUレベルでSTMを扱っているため、一見の価値があります。

于 2011-05-23T05:03:28.863 に答える
0

あなたが望むものはMCSキューロックと呼ばれているように聞こえます（一見名前が付けられていますが、それは本当にロックフリーであり、待機フリーではありません）、そしてここで利用可能ないくつかの良い擬似コードがあります：http：//www.cs.rochester .edu / research / Synchronization / pseudocode / ss.html＃mcs

于 2011-05-23T05:30:36.260 に答える
-2

私はCを使用して、最小化されたロックフリーキューの実装を記述します。

lfq。

それは多くの生産者、多くの消費者をサポートします。

于 2017-02-22T01:17:06.487 に答える