c - リストに対するアトミック操作

Question

リストがあり、test_and_setそのパラメーターがポインター address の計算である操作を使用したいとしますl->a.next->next。test_and_setこれはアトミックではなく、役に立たないと思います。TAS がアトミックに動作するように、そのポインター値をアトミックに計算する方法はありますか?

Answer 1

あなたはおそらくCASを意味します（より便利です）。

一般的に：はい、トランザクションまたは待機のないデータ構造を実装するためによく使用されます。

まず最初に、アドレス計算をアドレスのアトミック操作から分離しましょう。最初に、何かをスワップする必要がある特定のアドレスを取得します。CAS は、そこに到達した方法を気にしません。

具体的には、最初に各スレッドが次のポインターを置き換えたい場所が見つかるまでリストをナビゲートする必要があります。その後、CAS を使用してこれを試行して繰り返すことができます。スレッドが再試行のためにリストを再ウォークする必要があるかどうかは、シナリオによって異なります。

トリッキーな部分は、実際にはコード内の別の場所にあります。つまり、リスト ノードを解放(または再利用) する場所です。一般に、これまでにリストから切断されたノードチェーンを再利用または解放できないと想定する必要があります。実際には、使用できるヒューリスティックがありますが、これはユースケースによって異なります。