マルチスレッドとミューテックスは初めてなので、初心者向けにウィキペディアを調べていました。私はこの部分に出くわしました：
CAS を使用すると、実行する必要のある操作を各ノードが表すリンク リストを作成することで、共有データ構造の待機なしの相互排除を実現できます。次に、CAS を使用して、新しいノードの挿入中にリンク リスト内のポインターを変更します。その CAS で成功できるプロセスは 1 つだけです。同時にノードを追加しようとする他のすべてのプロセスは、再試行する必要があります。その後、各プロセスはデータ構造のローカル コピーを保持し、リンクされたリストをトラバースすると、そのローカル コピーでリストから各操作を実行できます。
これで、基本的に値を所定の値と比較し、一致する場合はそれらを交換するアトミック操作を使用する CAS の基本概念を理解しました。しかし、ここで「目的の操作のリンクされたリスト」が何を意味するのかを理解できませんでしたか? また、すべてのプロセスが同じ操作のリンク リストに従うのはなぜでしょうか。
リンクされたリストは、共有データ構造に対する操作を保持します。
たとえば、スタックがある場合、プッシュとポップで操作されます。リンクされたリストは、疑似共有スタック上のプッシュとポップのセットになります。そのスタックを共有する各スレッドは、実際にはローカル コピーを持ち、現在の共有状態に到達するために、操作のリンク リストをたどり、スタックのローカル コピーに各操作を順番に適用します。リンクされたリストの最後に到達すると、そのローカル コピーは現在の状態を保持します (もちろん、いつでも古くなる可能性があります)。
従来のモデルでは、各プッシュとポップの周りにある種のロックがありました。各スレッドは、ロックを取得するのを待ってから、プッシュまたはポップを実行してから、ロックを解放します。
このモデルでは、各スレッドはスタックのローカル スナップショットを持ち、リンクされたリスト内の操作を適用することによって、他のスレッドのスタック ビューとの同期を維持します。スタックを操作したいときは、直接操作しようとはしません。代わりに、リンクされたリストにプッシュまたはポップ操作を追加するだけなので、他のすべてのスレッドがその操作を確認でき、同期を維持できます。次に、もちろん、リンクされたリストの操作を適用し、(たとえば) ポップが発生したときに、どのスレッドがポップを要求したかをチェックします。この特定のポップを要求したスレッドである場合にのみ、ポップされた項目を使用します。