まず、トピックにあまり詳しくない人のために、ブロックレスアルゴリズムとは何か、なぜ必要なのかを簡単に説明したいと思います。 多くの場合、マルチスレッドアプリケーションでは、処理キューを作成できる例として、複数のスレッドから同じデータへのアクセスが使用されます。 このデータの整合性（統合）を維持するためには、同時の調整されていない変更からデータを保護する方法が必要です。 通常、このようなメソッドはあらゆる種類のロック（スピンロック、ミューテックス）であり、データへの同時アクセスを完全に防ぎ、読み取りまたは書き込みのためにデータにアクセスする前に閉じ、必要な操作が完了した後に開きます。
スピンロックとミューテックスの違いを説明することなく、使用するロックに関係なく、この原則は変わらないことを言いたいと思います。
ロックフリーアルゴリズムは、CAS（比較およびスワップ）などのアトミック操作を使用して、同時アクセスを調整し、データが損なわれないようにします。 その結果、ロックフリーアルゴリズムのパフォーマンスは通常大幅に向上します。 実装の高度な複雑さがなければ、すべてがうまくいきます。ABAの問題から始まり、全員がエッジに追いつき、リモートメモリセグメントへのアクセスの危険で終わり、プログラムがクラッシュしたためです。 そして、まさにその複雑さゆえに、ロックフリーアルゴリズムはまだほとんど使用されていません。
しかし、これがすべての歌詞です。そして、ここで要点を説明しましょう。 私はスタックの多くの非ブロック実装に出会いました：いくつかは間違いなく動作しません、いくつかは「ナイーブ」です、すなわち ABA、多くの労働者の問題を考慮に入れないでください。 たとえば、私がここで見つけたロックフリースタックを実装するときに発生する可能性のある問題の非常に良い説明を持つそのようなスタックの1つ： blog.memsql.com/common-pitfalls-in-writing-lock-free-algorithms 。
これを理解したい人にとっては、ロックフリーアルゴリズムの問題とそれらを解決する方法を示す非常に良い記事です。
ロックフリースタックの問題の1つは動的メモリ管理です。スタックノードを割り当て、（メモリリークが必要ない場合は）削除する必要があります。 この場合、問題は削除によって正確に発生します。 スタックの「単純な」実装を使用します。
void push(void *data) { struct stack_node_s *node = malloc(sizeof(struct stack_node_s)); node->data = data; do { node->next = head; } while(!compare_and_swap(&head, node->next, node); } void *pop() { struct stack_node_s *node; void *result = NULL; do { node = head; } while(node && !compare_and_swap(&head, node, node->next); if(node) { result = node->data; free(node); } return result; }
この実装は、「ナイーブ」と呼ばれます。これは、CASが成功した場合、念頭に置いていたデータを正確に把握できたと考えているためです。 実際、頭が反復の開始時と同じであることが判明する多くのシナリオがありますが、それは完全に異なることを意味します。
たとえば、読み取りスレッドの1つがノードにヘッドを保存し、node-> nextを取得したが、compare_and_swapがまだ呼び出されていない状況を想定します。 その後、スレッドは中断され、他のスレッドに制御を与えます。そのスレッドの1つはヘッドの削除と削除を管理し、もう1つはヘッドの削除と削除を管理し、3番目のスタックをスタックに配置します。この要素のメモリは、それが置かれたアドレスから割り当てられました古い頭。 その後、制御は最初のスレッドに戻ります。
この場合、nodeはheadと一致しますが、node-> nextが取ることができたのは無関係であるだけでなく、リモートのメモリを指します。
この問題は、多くのソースでABAの「問題、またはABA」問題と呼ばれています。 彼女は、ロックフリーアルゴリズムに関わる初心者マニアの真の惨劇です。 最もよく解決されるのは、スタックに配置されるたびに変わるカウンタータグのポインターに加えて、ポインターの値が同じであっても、タグとポインターのペアが異なることです。
この実装で発生する2番目の問題は、メモリの解放です。 この問題を実証するために、読み取りスレッドの1つがヘッドをノードに保存し、他のスレッドに制御を移した状況を想定しましょう。 別の読み取りストリームは、スタックから抽出してメモリを削除する手順全体を実行することができました。 制御が最初のスレッドに戻ると、node-> nextを取得しようとすると、メモリの解放された部分が参照されます。これは、もちろんあまり良くなく、プログラムのクラッシュにつながることさえあります。 この問題はさまざまな方法で解決されます。 私が言及した記事では、いわゆるハザードポインター、つまり削除できないポインターのリストを使用しています。 メモリの一部を削除する前に、スレッドはこのリストをチェックします。 他の方法があります。たとえば、一時的にスタックヘッドを、別のスレッドで削除されないようにする条件値に置き換えます。 私が提供したい実装は、1つの単純な事実に基づいています：スタックへのアクセスは、単一の要素を介して行われます：リストの先頭です。したがって、同時に変更することはまだ不可能です。テールでは、ロックフリーアプローチからのゲインは非常に低いです。
したがって、スタックへの複合アプローチを提供したいと思います。 このアルゴリズムでは、記録はロックフリーモードで実行されます。 CASに加えてCASは、複数のスレッドでの同時読み取りを回避するためにスピンロックも使用します。 読み取りは1つのスレッドでのみ実行されるため、解放されたメモリへのアクセスの問題はすぐになくなります。 また、 読み取り操作中に、削除してから貼り付けるオプションは使用できず（挿入のみ可能）、ABAの問題は自動的に消えます。 言い換えると、最大の問題を引き起こす可能性がある部品の1つだけでロックを使用するアルゴリズムを提案します。
私の場合、実装は次のようになります。
void thread_buffer_push(struct thread_buffer_s *head, void *data) { struct thread_buffer_s *tb, *oldhead; tb = malloc(sizeof(struct thread_buffer_s)); tb->data = data; oldhead = head->next; tb->next = oldhead; while(!__sync_bool_compare_and_swap(&head->next, oldhead, tb)) { usleep(1); oldhead = head->next; tb->next = oldhead; } } void* thread_buffer_pop(struct thread_buffer_s *head) { struct thread_buffer_s *current; void *result = NULL; // Spinlock acquire while(!__sync_bool_compare_and_swap(&head->list_mutex, 0, 1)) { usleep(1); } current = head->next; // NOONE can pop and delete the same element, since it's read-locked // But it can change since the stack can be pushed without locking while(current && !__sync_bool_compare_and_swap(&head->next, current, current->next)) { usleep(1); current = head->next; } if(current) { result = current->data; free(current); } // Spinlock release while(!__sync_bool_compare_and_swap(&head->list_mutex, 1, 0)) { usleep(1); } return result; }
この実装は、上記のエラーを考慮したロックフリーアルゴリズム、およびスピンロックとミューテックス（pthread_mutex）を使用したアルゴリズムとともに、パフォーマンスがテストされました。 Usleep（1）は、私が提供したリンクの記事に記載されている推奨事項に従って、実験後に追加されました。
これらの各アルゴリズムの推定実行時間は次のとおりです（すべてのテスト中にわずかに変更されました）。
ミューテックス：
実際の0m1.336s
ユーザー0m1.173s
sys 0m3.628s
ロックフリー：
実際の0m0.533s
ユーザー0m0.792s
sys 0m0.046s
スピンロック：
実際の0m0.520s
ユーザー0m0.630s
sys 0m0.018s
セミロック：
実際の0m0.353s
ユーザー0m0.360s
sys 0m0.075s
ロックフリーアルゴリズムとスピンロックアルゴリズムのわずかな違いは、上で書いたように、スタックには共通のアクセスポイント（ヘッド）が1つしかないという事実によって説明されています。 これらの違いがロックフリーアルゴリズムを支持しないという事実は、リモートポインターへのアクセスに対する保護を追加する副作用です。
私がしたい結論は次のとおりです。ロックフリーアルゴリズムを実装する前に、使用されるデータ構造の分析は、複数のストリームの同時アクセスの可能性のために必要です。 ロックフリーのアプローチでは、パフォーマンスを大幅に向上させることなくhemo核のみを追加する可能性があります（たとえば、スタックの場合）。 この記事では、並列アルゴリズムの実装へのアプローチの組み合わせの可能性も示しています。