3

ここに画像の説明を入力 ここに画像の説明を入力

また、私はc実装を行っており、現在キューの構造を持っています:

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

int CompareAndExchange (void **a, void *comparand,void *new) {
    int success = 0;
    pthread_mutex_lock(&CE_MUTEX);
    if ((*a) != comparand) {
       (*a) = new;
       //return     TRUE
       success = 1;
    }
    pthread_mutex_unlock(&CE_MUTEX);     
   //return     FALSE
    return success;
 }

しかし、キューとデキュー機能を使用して続行する方法がわかりません...

  • コードはどのようになりますか？
4

5 に答える 5

2

また、このテーマに関する最近のブーストコントーク: https://github.com/boostcon/2011_presentations/raw/master/wed/lockfree_2011_slides.pdf

于 2011-05-22T18:46:21.287 に答える
2

少し前に、この問題に対する素晴らしい解決策を見つけました。これまでに発見された中で最も小さいと思います。

リポジトリには、それを使用して N スレッド (リーダーとライター) を作成し、単一のシートを共有する方法の例があります。

テスト例でいくつかのベンチマークを作成し、次の結果を得ました (100 万操作/秒):

バッファサイズ別

スループット

スレッド数別

ここに画像の説明を入力

スレッド数によってスループットが変化しないことに注目してください。

これがこの問題の究極の解決策だと思います。それは機能し、信じられないほど高速でシンプルです。何百ものスレッドと単一の位置のキューがあっても。スレッド間のパイプラインとして使用して、キュー内にスペースを割り当てることができます。

リポジトリには、C# と Pascal で記述された初期バージョンがいくつかあります。その本当の力を示すために、より完全に洗練されたものを作ることに取り組んでいます。

作業を検証したり、いくつかのアイデアを手伝ってくれる人がいることを願っています. または、少なくとも、それを破ることができますか?

于 2020-01-06T19:33:49.113 に答える
2

あなたの疑似コードはABA 問題に悩まされる可能性があります (そしてほとんどの場合そうなります)。ポインターのみがチェックされ、付随する一意のスタンプはチェックされないため、この文書はその点で使用され、ロックの一般的なガイドとして見つかります。落とし穴のあるフリーキューの実装。

ロックフリープログラミングを扱うときは、Herb Sutter の作品を読むのも良い考えです。Herb Sutter は何が必要なのか、なぜそれが必要なのか、そして潜在的な弱点について洞察に満ちた良い説明を与えてくれます (ただし、彼の古い出版物/記事のいくつかはいくつかの隠れた/予期しない問題が含まれていることが判明した場合)。

于 2011-05-22T16:05:00.240 に答える
0

（これは今のところここに残しておきますが、編集を参照してください。）

Cでのロックフリーキューの実装を知っていますか？

最近、ロックレスキューを作成しました（http://www.ideone.com/l2QRp）。実際に正しく動作することを保証することはできませんが、バグを見つけることができず、問題なくいくつかのシングルスレッドプログラムで使用したので、それほど明らかな問題はありません。

簡単な使用例：

queue_t queue;
int val = 42;
queue_init(&queue,sizeof val);
queue_put(&queue,&val);
val = 0; 
queue_pop(&queue,&val);
printf("%i\n",val); // 42
queue_destroy(&queue);

編集：

@Alexey Kukanovが指摘したように、tmpがポップされ、解放され、再度割り当てられ、nullのチェックとスワッピングの間に再び置かれると、queue_popは失敗する可能性があります。

    if(!tmp->next) return errno = ENODATA;
    /* can fail here */
    } while(!sync_swap(q->head,tmp,tmp->next));

これを修正する方法はまだわかりませんが、理解できたら（願わくば）更新します。今のところ、これは無視してください。

于 2011-05-22T18:08:32.613 に答える