2

次のような構造を想像してください。

struct my_struct {
    uint32_t refs
    ...
}

ルックアップ テーブルを介してポインタを取得する場合:

struct my_struct** table;

my_struct* my_struct_lookup(const char* name)
{
    my_struct* s = table[hash(name)];

    /* EDIT: Race condition here. */

    atomic_inc(&s->refs);

    return s;
}

マルチスレッド モデルでは、逆参照とアトミック インクリメントの間に競合が存在します。これは非常にパフォーマンスが重要なコードであることを考えると、逆参照とアトミック インクリメントの間のこの競合は通常どのように解決または回避されるのでしょうか?

編集: ルックアップ テーブルを介して構造体へのポインターを取得する場合my_struct、参照カウントをインクリメントするために、最初に構造体を逆参照する必要があります。これにより、他のスレッドが参照カウントを変更し、別のスレッドが存在しないメモリへのポインターを逆参照している間にオブジェクト自体の割り当てを解除する可能性がある場合、マルチスレッド コードで問題が発生します。プリエンプションといくつかの不運が組み合わさると、これは災害のレシピになる可能性があります.

4

3 に答える 3

1

誰かが上で言ったように、あなたは後で解放するためにメモリのリンクリストを作ることができるので、あなたのポインタは決して無効ではありません。これは、場合によっては便利な方法です。

または....32ビットポインタを使用して64ビット構造体を作成し、参照カウントやその他のフラグ用に32ビットを使用できます。構造体をユニオンでラップすると、構造体で64ビットのアトミック演算を使用できます。

union my_struct_ref {
    struct { 
      unsigned int       cUse     : 16,
                         fDeleted : 1;    // etc 
      struct my_struct  *s;
    } Data;
    unsigned long n64;
}

構造体のデータ部分を人間が読みやすく操作でき、n64ビット部分でCASを使用できます。

my_struct* my_struct_lookup(const char* name)
{
    struct my_struct_ref Old, New;
    int iHash = hash(name);

    // concurrency loop
    while (1) {
      Old.n64 = table[iHash].n64;
      if (Old.Data.fDeleted)
        return NULL;
      New.n64 = Old.n64;
      New.Data.cRef++;
      if (CAS(&table[iHash].n64, Old.n64, New.n64)) // CAS = atomic compare and swap
        return New.Data.s; // success
      // we get here if some other thread changed the count or deleted our pointer
      // in between when we got a copy of it int old.  Just loop to try again.
    } 
}

64ビットポインタを使用している場合は、128ビットCASを実行する必要があります。

于 2012-05-07T17:45:36.067 に答える
1

解決策の 1 つは、malloc() や free() ではなく、フリーリストを使用することです。これには明らかな欠点があります。

もう 1 つは、ロックのないガベージ コレクション (セーフ メモリの再利用とも呼ばれます) を実装することです。

この分野には多くの特許がありますが、エポックベースの LFGC は問題ないようです。

このメソッドを使用することの結果は、要素を指しているスレッドがない場合にのみ要素の割り当てが解除されることです。

前者のソリューションは、実装が非常に簡単です。もちろん、ロックフリーのフリーリストが必要です。そうしないと、システム全体がロックフリーではなくなります。

後者は実際には複雑ではありませんが、問題のアルゴリズムを学習する必要があり、時間と調査が必要です。

于 2012-04-26T22:51:42.400 に答える
0

特定した人種に加えて、メモリの一貫性に関する一般的な問題があります。

ロックフリーの方法でテーブルの変更をアトミックにすることができたとしてmy_struct*も、最後に変更したスレッドとは異なるスレッドから見た場合、メモリ ポイントのブロックは「古い」ままになる可能性があります。これはmy_struct.refs(常にアトミックを使用してアクセスする場合) には適用されませんが、他のすべてのフィールドには適用されます。これは、各 CPU コアに「プライベート」な書き込みバッファーとキャッシュの結果です。

正しいメモリ コンテンツが表示されることを保証する唯一の方法は、メモリ バリアを使用することです。それでも、典型的なロックはメモリバリアでもあるので、そもそもロックを使用しないのはなぜでしょうか?

ロックフリー プログラミングは、最初に思われるよりもはるかに複雑です。特に競合がまれな場合、OTOH ロックは非常に高速です。実際にロックベースの実装をベンチマークし、ロックが実際にボトルネックであることを確認しましたか?

于 2012-04-26T23:08:28.830 に答える