10

スレッド間で同期する必要がある非常に単純なデータのコンテナーを作成しました。最高のパフォーマンスが欲しい。ロックは使いたくない。

「リラックスした」アトミックを使いたい。部分的には、その少し余分な活力のためであり、部分的にはそれらを本当に理解するためです.

私はこれに多くの作業をしてきましたが、このコードが私が投げたすべてのテストに合格するところまで来ました。しかし、それは完全な「証拠」ではないので、私が見逃しているものがあるかどうか、またはこれをテストできる他の方法があるかどうか疑問に思っていますか?

ここに私の前提があります：

  • ノードが適切にプッシュおよびポップされ、スタックが決して無効にされないことだけが重要です。
  • メモリ内の操作の順序は、1 つの場所でのみ重要であると私は信じています。
    • compare_exchange 操作自体の間。これは、アトミックが緩和されていても保証されます。
  • 「ABA」問題は、ポインタに識別番号を追加することで解決されます。32 ビット システムでは、これにはダブルワードの compare_exchange が必要であり、64 ビット システムでは、ポインタの未使用の 16 ビットが ID 番号で埋められます。
  • したがって、スタックは常に有効な状態になります。 （右？）

これが私が考えていることです。「通常」、私たちが読んでいるコードについて推論する方法は、それが書かれた順序を見ることです。メモリは「順不同」に読み書きできますが、プログラムの正確性を無効にする方法ではありません。

マルチスレッド環境ではそれが変わります。それがメモリフェンスの目的です - コードを見て、それがどのように機能するかを推測できるようにするためです。

ここですべてが順不同になる可能性がある場合、リラックスしたアトミックで何をしているのでしょうか? ちょっと遠すぎませんか？

私はそうは思いませんが、それが私がここで助けを求めている理由です.

compare_exchange 操作自体は、相互に順次の一貫性を保証します。

アトミックへの読み取りまたは書き込みが行われる他の唯一の時間は、compare_exchange の前にヘッドの初期値を取得することです。変数の初期化の一部として設定されます。私が知る限り、この操作が「適切な」値を返すかどうかは関係ありません。

現在のコード:

struct node
{
    node *n_;
#if PROCESSOR_BITS == 64
    inline constexpr node() : n_{ nullptr }                 { }
    inline constexpr node(node* n) : n_{ n }                { }
    inline void tag(const stack_tag_t t)                    { reinterpret_cast<stack_tag_t*>(this)[3] = t; }
    inline stack_tag_t read_tag()                           { return reinterpret_cast<stack_tag_t*>(this)[3]; }
    inline void clear_pointer()                             { tag(0); }
#elif PROCESSOR_BITS == 32
    stack_tag_t t_;
    inline constexpr node() : n_{ nullptr }, t_{ 0 }        { }
    inline constexpr node(node* n) : n_{ n }, t_{ 0 }       { }
    inline void tag(const stack_tag_t t)                    { t_ = t; }
    inline stack_tag_t read_tag()                           { return t_; }
    inline void clear_pointer()                             { }
#endif
    inline void set(node* n, const stack_tag_t t)           { n_ = n; tag(t); }
};

using std::memory_order_relaxed;
class stack
{
public:
    constexpr stack() : head_{}{}
    void push(node* n)
    {
        node next{n}, head{head_.load(memory_order_relaxed)};
        do
        {
            n->n_ = head.n_;
            next.tag(head.read_tag() + 1);
        } while (!head_.compare_exchange_weak(head, next, memory_order_relaxed, memory_order_relaxed));
    }

    bool pop(node*& n)
    {
        node clean, next, head{head_.load(memory_order_relaxed)};
        do
        {
            clean.set(head.n_, 0);

            if (!clean.n_)
                return false;

            next.set(clean.n_->n_, head.read_tag() + 1);
        } while (!head_.compare_exchange_weak(head, next, memory_order_relaxed, memory_order_relaxed));

        n = clean.n_;
        return true;
    }
protected:
    std::atomic<node> head_;
};

他の質問と比べて、この質問の何が違うのですか? リラックスしたアトミック。彼らは質問に大きな違いをもたらします。

それで、あなたはどう思いますか？足りないものはありますか？

4

3 に答える 3

2

ポップ操作の難しさはさておき、物足りないと思いますmemory_order_relaxed。ノードをプッシュする前に、いくつかの値がノードに書き込まれ、ノードがポップされたときに読み取られると想定します。値が読み取られる前に実際に書き込まれたことを確認するには、何らかの同期メカニズムが必要です。 memory_order_relaxedその同期を提供していません... memory_order_acquire/memory_order_releaseでしょう。

于 2014-07-20T13:53:43.867 に答える
2

このコードは完全に壊れています。

これが機能しているように見える唯一の理由は、現在のコンパイラがアトミック操作全体での並べ替えに対してあまり積極的ではなく、x86 プロセッサがかなり強力な保証を持っていることです。

最初の問題は、同期がないと、このデータ構造のクライアントが、初期化されるノード オブジェクトのフィールドを見ることさえ保証されないことです。次の問題は、同期がないと、プッシュ操作でヘッドのタグの任意の古い値を読み取れる可能性があることです。

メモリ モデルで可能なほとんどの動作をシミュレートする CDSChecker ツールを開発しました。オープンソースで無料です。データ構造で実行して、興味深い実行を確認してください。

緩和されたアトミックを利用するコードについて何かを証明することは、現時点では大きな課題です。ほとんどの証明方法は、本質的に帰納的であり、帰納する順序がないため、機能しません。だから、あなたは薄い空気の読み取りの問題から抜け出します...

于 2015-01-29T09:59:36.960 に答える